約瑟夫問題 算法實現

約瑟夫問題的一種描述是:

編號為1,2,…,n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數)。一開始任選一個正整數作為報數上限值m,從第一個人開始按順時針按順時針方向自1開始順序報數,報到m時停止報數。報m的人出列,將他的密碼做為新的m值,從他在順時針方向上的下一個人開始重新從1報數,如此下去,直至所有人全部出列為止。試設計一個程序求出出列順序。

為簡單起見,
每人密碼即為其序列編號。

這是偶今天上數據結構課程設計的題目

偶在網上找到一些代碼,都有問題
最後在其中一個代碼基礎上修改一下,編譯成功

下面代碼在gcc (GCC) 3.3.5 (Debian 1:3.3.5-13) 下編譯成功
C語言實現。


#include
#include
#include
typedef struct node
{
int data;
struct node *next;
}LNode;

main()
{
LNode* Create(int);
LNode* GetNode(LNode *);
int Print(LNode *,int);
LNode *p;
int n,k,m;
do
{
printf (“Enter Total Number: “);
scanf (“%d”,&n);
}
while (n<=0); do { printf ("Enter Initial Password: "); scanf ("%d",&m); } while(m<=0); p=Create(n); Print(p,m); return 0; }; LNode* Create(int n) { LNode *head=NULL,*cul,*newl; int i=1; while(n+1!=i) { newl=(LNode *)malloc(sizeof(LNode)); if(head==NULL) { head=cul=newl; newl->data=i;
newl->next=head;

}
else
{
newl->data=i;
newl->next=cul->next;
cul->next=newl;
cul=newl;
}
i++;
}

return head;
}

LNode* GetNode(LNode *p)
{
LNode *q,*c;
c=p->next;
for(q=p;q->next!=p;q=q->next);
q->next=p->next;

free (p);
return (c);

}

Print(LNode *p,int m)
{
int i;
printf (“Out Sequence:\n”);
while (p->next!=p)
{

for (i=1;inext;
printf (“%d “,p->data);
p=GetNode(p);
}
m=p->data ;
printf(“%d\n”,p->data);
return 0;

}

3 Replies to “約瑟夫問題 算法實現”

  1. # 半 Says:
    January 8th, 2008 at 9:09 pm e

    問下,學校沒組織參加ACM嗎?

    ごめん、わかりません

    ACM是啥玩意?
    國際計算機組織?

    如果是程序設計競賽之類東西

    偶這種垃圾水平根本不可能參加=V=

Comments are closed.