約瑟夫問題的實現

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); } */

?

總結

以上是生活随笔為你收集整理的西南科技大学OJ题 约瑟夫问题的实现0956的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。