約瑟夫問題的實作
n個人圍成一個圈，每個人分别标注為1、2、...、n，要求從1号從1開始報數，報到k的人出圈，接着下一個人又從1開始報數，如此循環，直到隻剩最後一個人時，該人即為勝利者。例如當n=10,k=4時，依次出列的人分别為4、8、2、7、3、10，9、1、6、5，則5号位置的人為勝利者。給定n個人，請你程式設計計算出最後勝利者标号數。（要求用單循環連結清單完成。）
輸入
第一行為人數n;
第二行為報數k。
輸出
輸出最後勝利者的标号數。
樣例輸入
10
4
樣例輸出
5
#include<stdio.h>
#include<malloc.h>
struct LinkNode
{
int data;
struct LinkNode *next;
};
int main()
{
int n,k;
struct LinkNode *head,*p1,*p2,*p;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++)
{
if(i==1)//建立頭結點
{
head=p1=p2=(struct LinkNode*)malloc(sizeof(struct LinkNode));
}
p1->data=i;//儲存資料
if(i<n)
{
p2=(struct LinkNode*)malloc(sizeof(struct LinkNode));
p1->next=p2;
p1=p2;
}
if(i==n)//設定最後一個結點的next為頭結點，這樣就是一個循環連結清單
{
p1->next=head;
}
}
p=head;
int t=0;
for(int i=1; ; )
{
if(i%k==0&&p->data!=0)//模拟報數 1%k= ，表示輪到此結點報數，p->data！=0，表示 此結點未報過數
{
if(t<n-1)
{
p->data=0;//這個結點已經報過數，辨別為0
t++;
i++;
}
else
{
printf("%d",p->data);
break;
}
}
else if(p->data!=0)
{
i++;
}
p=p->next;
}
}
/*
#include<stdio.h>
int main()
{
int n,k;
int a[1000]={0};
int t=0;
scanf("%d %d",&n,&k);
int j=0;
for(int i=n;i>1; )
{
for( ; ;j++)
{
j=j%n;
if(a[j]==0)
t++;
t=t%k;
if(t==0&&a[j]!=1)
{
a[j]=1;
i--;
}
if(i==1)
break;
}
}
for(int i=0;i<n;i++)
if(a[i]==0)
printf("%d",i+1);
}
*/