问题一:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。
我们要确定每次删除的数字在所有数字(TOTAL)的Index,那么每次删除一个数字后再下一个需要删除的数字在当前数字总数(TOTAL-1)中的相对Index。
解题思路:
回溯法: int arr[n] = {0,1,2,3,4,5,6,7,8,…,n-1};
假设要找n个数字中的第m个,即删除a[m-1]这个元素,然后从a[m]这个数字为起始删除第m个。
0 1 ... m-2 m-1 m ... n-1
0 1 ... m-2 m m+1 ... n -1
以第m个元素为起始,重新排列,并从0开始计数
m m+1 ... n -1 0 1 ... m-2 数组一 (编号m到n-1中有n-1-m+1=n-m个数)
0 1 .... n-m-1 n-m n-m+1 ... n-2 数组二 n-2=m-2+n-m
如果这时候数组二和数组一是一一对应的,例如数组二的第n-m+1元素就是数组一的 1元素所以如果数组二的元素位置记为x,在数组一的元素位置记为x',
则有 数组二-----> 数组一 x' = (x+m)%n 表示删除一个元素后,在当前总数中的相对Index对应在前一次总数中的相对index位置
那同理,数组三 ---->数组二 x' = (x+m)%(n-1)
显然,当知道最后一个数组(只有一个元素,index为0),可以推得其在前一次总数中(即有两个元素时)的Index位置。然后再回溯,以此类推可以知道其在原始总数的Index
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
int YSF(int i, int m) { if (i == 1) return 0; return (YSF(i - 1, m) + m) % i; } void Solution(int *arr, int length, int m) { int last = YSF(length, m); cout << arr[last] << endl; } int _tmain(int argc, _TCHAR* argv[]) { int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int m = 5; Solution(arr, 10, m); //从编号0开始删除第m个数 //Solution(arr+2, 10, m);//从编号2开始删除第m个数 system("pause"); return 0; } |
1 2 3 4 5 6 7 8 9 10 |
YSF(1,5)=0 YSF(2,5)=( YSF(1,5)+5)%2=1; YSF(3,5)=( YSF(2,5)+5)%3=0; YSF(4,5)=( YSF(3,5)+5)%4=1; YSF(5,5)=( YSF(4,5)+5)%5=1; YSF(6,5)=( YSF(5,5)+5)%6=0; YSF(7,5)=( YSF(6,5)+5)%7=5; YSF(8,5)=( YSF(7,5)+5)%8=2; YSF(9,5)=( YSF(8,5)+5)%9=7; YSF(10,5)=( YSF(9,5)+5)%10=2 |
也就说最后被删除的数字在最初的数列中的编号是2。
问题二:让n个人围成一圈,并将他们从1到n编号,从编号为1的那个开始残酷的计数,每次消去第二个人直到只留下一个幸存者。
如果n是6,那么2,4,6在通过圆圈的第一轮就将被消去;而初始位置为1和3的那些人将在第二轮被消去,留下一个初始位置为5的幸存者。J(6)=5。如果n为7,那么2,4,6,1位置上的人在通过圆圈的第一轮就将被消去;而初始位置为5和3的那些人将在第二轮被消去。J(7)=7。
解题思路:考虑奇数n和偶数n的情况。
当n为偶数(n=2k),那么对圆圈处理第一遍后,规模减半,一个初始位置为3的人在第二轮会处在2号位置上。也就是说J(2k)=2J(k)-1。
当n为奇数(n=2k+1),第一轮消去所有偶数位置上的人,把紧接着消去的位置1上的人也加进来,留下一个规模为k的实例。J(2k+1)=2J(k)+1。
一种做法是将n的二进制表示向左循环移动一位来得到J(n)。。
对于所有为2的乘方的n来说,它的约瑟夫斯问题的解是1。
问题3:参考自http://blog.csdn.net/csf111/article/details/6846095
http://blog.csdn.net/xiaowei_cqu/article/details/8585888
1) 问题描述
约瑟夫斯(Josephus)问题的一种描述是:编号为1,2,…,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止。试设计一个程序,按出列顺序印出各人编号。
2)基本要求
利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。
3)测试数据
n=7,7个人的密码依次为:3,1,7,2,4,8,4。m初值为6(正确的出列顺序应为6,1,4,7,2,3,5)。
4)提示
程序运行后,首先要求用户指定初始报数上限m,然后读取个人的密码。可设n≤30。注意链表中空表和非空表的界限。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include "iostream" using namespace std; struct Person{ int num; int cipher; Person *next; }; Person person[7]; void CirCle(){ for(int i=0;i<7;i++){ person[i].num=i+1; person[i].next=&person[i+1]; } person[6].next=&person[0];//使最后一个人的指针指向第一个,构成循环链表 person[0].cipher=3; person[1].cipher=1; person[2].cipher=7; person[3].cipher=2; person[4].cipher=4; person[5].cipher=8; person[6].cipher=4; } int _tmain(int argc, _TCHAR* argv[]){ CirCle(); int m;//起始的密码值 cin>>m; Person *currentPerson; Person *prePerson; currentPerson=&person[0]; prePerson=&person[6]; //判断链表中是否只有一个结点 while(currentPerson!=prePerson){ for(int i=1;i<m;i++){//移动指针,i<m prePerson=currentPerson; currentPerson=currentPerson->next; } m=currentPerson->cipher; cout<<currentPerson->num<<" "; prePerson->next=currentPerson->next; //修改链表指针,使被删除的节点的前一个结点指向其后一个结点 currentPerson=prePerson->next; } cout<<currentPerson->num<<" "; cout<<prePerson->num; //只有一个结点,两个指针指向同一个结点 system("pause"); return 0; } |