Question

使用循环单链表解决约瑟夫问题

~~
设n个人围坐在一张桌子周围，现从某个人开始报数，数到m的人出列（即离开座位，不参加以后的报数），接着从出列的下一个人从新从1 报数，数到m的人出列，如此下去知道所有人都出列为止，试求出他们的出列次序。

Answer 1

　　约瑟夫问题（有时也称为约瑟夫斯置换，是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。又称“丢手绢问题”）
　　笔算解决约瑟夫问题
　　在M比较小的时候 ，可以用笔算的方法求解，
　　M=2
　　即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。
　　当N=2^k的时候，第一个报数的人就是最后一个死的，
　　对于任意的自然数N 都可以表示为N=2^k+t，其中t<n/2
　　于是当有t个人去死的时候，就只剩下2^k个人 ，这2^k个人中第一个报数的就是最后去死的。这2^k个人中第一个报数的人就是2t+1
　　于是就求出了当M=2时约瑟夫问题的解：
　　求出不大于N的最大的2的整数次幂，记为2^k，最后一个去死的人是2(N-2^k)+1
　　M=3
　　即N个人围成一圈，1，2，3，1，2，3的报数，报到3就去死，直到只剩下一个人为止。
　　此时要比M=2时要复杂的多
　　我们以N=2009为例计算
　　N=2009，M=3时最后被杀死的人记为F（2009,3），或者可以简单的记为F（2009）
　　假设这种情况下还剩下n个人，则下一轮将杀死[n/3]个人，[]表示取整，还剩下n-[n/3]个人
　　设这n个人为a1,a2,...,a(n-1）,an
　　从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1）,a(n-n mod 3+1）,..,an
　　于是可得：
　　1、这一轮中最后一个死的是a(n-n mod 3），下一轮第一个报数的是a(n-n mod 3+1）
　　2、若3|n，则最后死的人为新一轮的第F(n-[n/3]）个人
　　若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-（n mod 3）人
　　若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-（n mod 3）人
　　3、新一轮第k个人对应原来的第 3*[(k-1）/2]+(k-1）mod 2+1个人
　　综合1，2，3可得：
　　F（1）=1,F（2）=2,F（3）=2,F（4）=1,F（5）=4，F（6）=1，
　　当f(n-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-（n mod 3），F(n)=3*[(k-1）/2]+(k-1）mod 2+1
　　当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-（n mod 3） ，F(n)=3*[(k-1）/2]+(k-1）mod 2+1
　　这种算法需要计算 [log（3/2）2009]次 这个数不大于22，可以用笔算了
　　于是：
　　第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人，
　　第二圈，杀死446人，还剩下894人
　　第三圈，杀死298人，还剩下596人
　　第四圈，杀死198人，还剩下398人
　　第五圈，杀死132人，还剩下266人
　　第六圈，杀死88人，还剩下178人
　　第七圈，杀死59人，还剩下119人
　　第八圈，杀死39人，还剩下80人
　　第九圈，杀死26人，还剩下54人
　　第十圈，杀死18人，还剩36人
　　十一圈，杀死12人，还剩24人
　　十二圈，杀死8人，还剩16人
　　十三圈，杀死5人，还剩11人
　　十四圈，杀死3人，还剩8人
　　十五圈，杀死2人，还剩6人
　　F（1）=1,F（2）=2,F（3）=2,F（4）=1,F（5）=4，F（6）=1，
　　然后逆推回去
　　F（8）=7 F（11）=7 F（16）=8 f（24）=11 f（36）=16 f（54）=23 f（80）=31 f（119）=43 f（178）=62 f（266）=89 f（398）=130
　　F（596）=191 F（894）=286 F（1340）=425 F（2009）=634

Answer 2

typedef struct node
{
int num,code;
struct node *next;
}lnode;
void main()
{
int i,j,key,n; /*i,j为记数器,key为输入的密码,n为人的总个数*/
lnode *p,*s,*head;
head=(lnode *)malloc(sizeof(lnode)); /*为头结点分配空间*/
p=head;
printf("Please enter the num of the person:"); /*输入人的总个数*/
scanf("%d",&n);
for(i=1;i<=n;i++)
{
printf("Person %d",i);
printf(" code: ");
scanf("%d",&key); /*输入各个人的密码*/
s=p;
p=(lnode *)malloc(sizeof(lnode)); /*创建新的结点*/
s->next=p;
p->num=i;
p->code=key;
}
p->next=head->next;
p=head;
head=head->next;
free(p);

p=head;
do
{
printf("\nPerson%d Code:%d",p->num,p->code); /*输出链表*/
p=p->next;
}while(p!=head);

printf("\nPlease enter your first key:"); /*输入第一个数*/
scanf("%d",&key);
do
{
j=1; /*j为记数数*/
p=head;
while(j<key)
{
s=p;
p=p->next;
j++;
}
i=p->num;
key=p->code;
printf("\nThe out of the num:");
printf("Person%d",i);
s->next=p->next;
head=p->next; /*重新定义head,下次循环的开始结点*/
free(p);
n--; /*每循环一次人是减1*/
}while(n>0);
getch();
}