当前位置:主页   - 电脑 - 程序设计 - C#
N位数排序问题的通用解决方法
来源:网络   作者:   更新时间:2012-08-21
收藏此页】    【字号    】    【打印】    【关闭

  前两天看到了这篇帖子:看到的两道面试题,里面的第二道题非常有代表性,所以就用心做了一下。

  算法题: 一个任意的三位数(个十百位均不相同),求将个十百重新按不同的顺序组合共有多少个不同的三位数?分别是什么?(C#) 示例: 123: 123,132,213,231,312,321。

  一开始的想法就是写3个循环就能把答案凑出来,不过要是N位数怎么办要写N个循环吗?所以马上想到了使用递归来解决问题。每次取一个数字然后再从剩下的数字中拿第一个,然后依次类推直到拿到最后一个数字结束。不过这有个小问题就是对于1来说有两个结果123、132,这需要用List来保存结果不过这样实在不够优雅所以我选择了钟爱的yield return来简化代码。

  对于递归程序来说最关键的就是找到终结点,一开始我试了几个终结条件都不成功,最后冷静下来琢磨了一下一次排序的过程就是把N个数都枚举了一遍所以终结条件就是数字的位数。就省最后一个问题了排列中不能有重复的,这个只要模拟一下排序的过程就明白了:

  开始:      选出最左边的数字1,其字符串下标为0,当前枚举了1个数

  递归第一次:从头开始遍历,因为上一轮下标为0的数字已经被取了,所以使用下标为1的数字,判断该下标1是否已经被使用,因为没被使用,那么继续递归,当前枚举了2个数

  递归第二次:因为当前枚举的是第3个数所以到达终结点,返回3

  在这一次排序过程中我们需要记录每次被选中的数字的下标,再下次枚举时要进行判断是否已经存在了,所以我使用了一个和数字位数相同大小的数组来记录每次排序过程中选中的数字的下标。

  好了,上面都没看懂也没关系直接上代码,代码是最好的文档,不过在贴具体代码之前我要下介绍下我的两个辅助函数:

分享到:

其它资源

来源声明

  • 版权与免责声明
    1、本站所发布的文章仅供技术交流参考,本站不主张将其做为决策的依据,浏览者可自愿选择采信与否,本站不对因采信这些信息所产生的任何问题负责。
    2、本站部分文章来源于网络,其版权为原权利人所有。由于来源之故,有的文章未能获得作者姓名,署“未知”或“佚名”。对于这些文章,有知悉作者姓名的请告知本站,以便及时署名。如果作者要求删除,我们将予以删除。除此之外本站不再承担其它责任。
    3、本站部分文章来源于本站原创,本站拥有所有权利。
    4、如对本站发布的信息有异议,请联系我们,经本站确认后,将在三个工作日内做出修改或删除处理。
    请参阅权责声明

进入 esk365.com 首页