Java有M个人挑选N人出来出席会议(无先后顺序)请计算出所有可能

版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明

约瑟夫环描述:约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编號1,23…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数数到的那个人出列;他的下一个人又从1开始报数,数到的那个人又出列;依此规律重复下去直到圆桌周围的人全部出列。

约瑟夫环问题输入人数n,第个人出列最后一个人的编号是多少?

1.先把这n个人按順序加进LinkedList选择链表是因为链表在进行大量数据插入删除的时候会比顺序表ArrayList的效率要高,而ArrayList在查找的时候效率会相对高

2.从索引0开始报数,到索引-1的时候也就是第个人出列。

3.排在这个人后面的人都向前移了一位也就是如4的索引原来是3的,在3出列之后队伍里还有[1,2,4,5]四个人,这时候4的索引变成了3-1=25的索引变成了4-1=3。所以新的索引就要从出列的人重新开始数再次数到-1。再次执行上面的删除操作

4.我们还会发现┅个问题,就是index一直加的话岂不是会数组越界了?这时候该怎么办呢怎么样才能让一个链表排出一个圈的效果呢?
我们可以用 索引 % 链表长度 进行取余操作

5.最后我们总结一下。需要初始化的索引与循环体内的代码如下:


本程序的思路是开一个数组其丅标表示1到个数,数组元素的值为1表示其下标代表的数被选中为0则没选中。
首先初始化将数组前n个元素置1,表示第一个组合为前n个数
然后从左到右扫描数组元素值的“10”组合,找到第一个“10”组合后将其变为“01”组合
同时将其左边的所有“1”全部移动到数组的最左端。
当第一个“1”移动到数组的-n的位置即n个“1”全部移动到最右端时,就得到了最后一个组合
例如求5中选3的组合:
版权声明:本文为博主原创文章遵循 版权协议,转载请附上原文出处链接和本声明

解法1:我们可以把棋盘的左下角看做二维坐标的原点(0,0),把棋盘的右上角看做二维坐標(,N)(坐标系的单位长度为小方格的变长)   

于是状态f(i,j)的状态转移方程为:

解法2:这个题目其实是一个组合问题对方向编号,向上是0向右是1,那么从左下角走到右上角一定要经过 个1和N个0这个题目可以转化为从+N个盒子中挑出个盒子有多少种方法。


发布了6 篇原创文章 · 获赞 4 · 访问量 2万+

我要回帖

更多关于 N/M 的文章

 

随机推荐