約瑟夫演算法

『壹』 約瑟夫環問題的演算法設計是什麼樣子的

來自網路
約瑟夫環是一個數學的應用問題：已知n個人（以編號1，2，3...n分別表示）圍坐在一張圓桌周圍。從編號為k的人開始報數，數到m的那個人出列；他的下一個人又從1開始報數，數到m的那個人又出列；依此規律重復下去，直到圓桌周圍的人全部出列。
這個就是約瑟夫環問題的實際場景，有一種是要通過輸入n,m,k三個正整數，來求出列的序列。這個問題採用的是典型的循環鏈表的數據結構，就是將一個鏈表的尾元素指針指向隊首元素。 p->link=head
解決問題的核心步驟：（程序的基本演算法）
1.建立一個具有n個鏈結點，無頭結點的循環鏈表；
2.確定第1個報數人的位置；
3.不斷地從鏈表中刪除鏈結點，直到鏈表為空。
void JOSEPHUS(int n,int k,int m) //n為總人數，k為第一個開始報數的人，m為出列者喊到的數
{
/* p為當前結點 r為輔助結點，指向p的前驅結點 list為頭節點*/
LinkList p,r,list; /*建立循環鏈表*/
for(int i=0；i<n；i++)
{
p=(LinkList)malloc(sizeof(LNode));
p->data=i;
if(list==NULL)
list=p;
else
r->link=p;
r=p;
}
p->link=list; /*使鏈表循環起來*/
p=list;/*使p指向頭節點*/
/*把當前指針移動到第一個報數的人*/
for(i=0;i<k;i++)
{
r=p；
p=p->link;
}
/*循環地刪除隊列結點*/
while(p->link!=p)
{
for(i=0;i<m-1;i++)
{
r=p;
p=p->link;
}
r->link=p->link;
printf("被刪除的元素：%4d ",p->data);
free(p);
p=r->link;
}
printf("\n最後被刪除的元素是：%4d",P->data);
}

『貳』 怎樣用vb實現約瑟夫環演算法

用面向過程的編程方式（C），對某個給定的n=8與m=3，給出被淘汰出列的旅客編號，以及最終的倖存者。
用面向對象的編程風格（C++），重新處理該約瑟夫問題。
談談這兩種編程風格的優點。
二、用C語言解約瑟夫問題
1、單鏈表的創建與輸出
#include<stdio.h>
#include<malloc.h>
#define NULL 0
struct node{ /*定義結構體*/
int data;
struct node *next;
};
typedef struct node NODE;/*將該結構體設置成自定義類型*/
NODE *head;/*定義一個指向該結構體的頭指針*/
NODE *create(int n)/*創建具有n個結點的單鏈表*/
{
NODE *p;
int i=1;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
while(i<=n)
{
p=(NODE *)malloc(sizeof(NODE));
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
}
return(head);
}
void output(NODE *point)/*輸出該鏈表數據域內的值*/
{
NODE *p;
p=point->next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
如果我們寫一段main()函數
void main()
{
head=create(8);
output(head);
}
便可以完成創建和輸出單鏈表的工作。
如果將上述創建單鏈表與輸出單鏈表的工作保存為頭文件link1.h,那麼在今後需要創建輸出類似的單鏈表時，只需寫以下主函數即可。
#inlucde 「link1.h」
void main()
{
head=create(8);
output(head);
}
2、循環單向鏈表的創建與輸出
明白了帶頭指針的單向鏈表的創建與輸出，只需作簡單修改便可處理循環單向鏈表的相關問題。這里我們建立一個新的頭文件link2.h，它包含以下幾段代碼。
#include<stdio.h>
#include<malloc.h>
struct node{
int data;
struct node *next;
};
typedef struct node NODE;
NODE *head;
NODE *create(int n)
{
NODE *p;
int i=1;
p=head=(NODE *)malloc(sizeof(NODE));
head->next=head;/*造循環鏈表時頭指針的指針域設置*/
while(i<=n)
{
p->data=n+1-i;
p->next=head->next;
head->next=p;
i++;
p=(NODE *)malloc(sizeof(NODE));
}
return(head);
}
void output(NODE *point,int n) /*n表示欲輸出多少個結點，由於該鏈表是循環的，可輸出無窮項*/
{
NODE *p;
int i=1;
p=point->next;
while(i<=n)
{
printf("%d ",p->data);
p=p->next;
i++;
}
printf("\n");
}
3、在循環鏈表中刪除結點並輸出被刪結點的相關信息
在頭文件link2.h中增添新函數del(int n,int m),這里的形參n代表起始結點，m代表報數值。
void del(int n,int m)
{
int i;
NODE *p,*q;
p=head;
/*將指針移到起始結點，即第n個結點*/
i=0;
while(i<n)
{
p=p->next;
i++;
}
/*刪除滿足報數值的結點*/
while(p->next!=p)
{
i=1;
while(i<m)/*找到符合報數值結點的前一個結點,即第m-1個結點*/
{
p=p->next;
i++;
}
/*先輸出，後刪除*/
q=p->next;
printf("%d ",q->data);
p->next=q->next;
free(q);
}
printf("\nonly one %d",p->data);/*輸出僅剩的結點*/
}
4、解決約瑟夫問題的主函數
#include <link2.h>
void main()
{
/*number結點個數,item輸出結點的個數,location報數的起始位置,callnum報數值*/
int number,item,location,callnum;
printf("\ninput nose number=");
scanf("%d",&number);
printf("\noutput item=");
scanf("%d",&item);
head=create(number);
output(head,item);
printf("\ninput location=");
scanf("%d",&location);
printf("\ninput callnum=");
scanf("%d",&callnum);
del(location,callnum);
}
三、以類作為結點來處理約瑟夫問題（准C++編程風格）
1、以類作結點的鏈表建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head=NULL,*p,*q;
for(int i=1;i<9;i++)
{
p=new Node;
p->SetData(i);
if(head==NULL)
head=p;
else
q->SetNext(p);
q=p;
}
q=head;
do
{
cout<<"該遊客編號為:"<<q->GetData()<<endl;
q=q->GetNext();
}while(q!=NULL);
q=head;
do
{
q=q->GetNext();
delete head;
head=q;
}while(q!=NULL);
}
2、以類作結點的循環鏈表的建立
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}
q=head;
i=1;
do
{
cout<<"該遊客編號為:"<<q->GetData()<<endl;
q=q->GetNext();
i++;
}while(i<=10);
}
3、解決約瑟夫問題
#include <iostream.h>
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
void SetData(int new_data){data=new_data;}
void SetNext(Node *new_next){next=new_next;}
int GetData(){return data;}
Node *GetNext(){return next;}
};
void main()
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=8;i++)
{
p->SetData(i);
p->SetNext(head);
q->SetNext(p);
q=p;
p=new Node;
}//
p=head;
i=1;
while(i<=8)
{
cout<<p->GetData()<<" "<<endl;
p=p->GetNext();
i++;
}//輸出
cout<<endl;
p=head;
while(p->GetNext()!=p)
{
i=1;
while(i<2)
{
p=p->GetNext();//將欲刪除點的前一個結點
i++;
}
q=p->GetNext();
cout<<q->GetData()<<endl;//刪除循環鏈表上的結點
p->SetNext(q->GetNext());//將q指針域所指結點的地址賦給p的指針域
p=p->GetNext();
delete q;
}//做循環數數出局游戲
cout<<"\nLast One "<<p->GetData()<<endl;
}
四、用標準的面向對象編程風格處理約瑟夫問題（C++編程風格）
//#include "stdafx.h"
#include "iostream.h"
//#define NULL 0
class Node
{
private:
int data;
Node *next;
public:
Node(){data=0;next=NULL;}
Node *Create(int n);//創建含n個結點的循環鏈表
void Output(Node *p,int n);//輸出循環鏈表頭結點為p的後n個結點的信息
Node *Move(Node *p,int n);//將頭結點指針前移到n
//從頭結點為p的循環鏈開始，所用的計數為n進行約瑟夫實驗
void Josephus(Node *p,int n);
};
Node *Node::Create(int n)
{
Node *head,*p,*q;
head=new Node;
q=p=head;
for(int i=1;i<=n;i++)
{
p->data=i;
p->next=head;
q->next=p;
q=p;
p=new Node;
}
return head;
};
void Node::Output(Node *p,int n)
{
int i=1;
while(i<=n)
{
cout<<p->data<<" ";
p=p->next;
i++;
}
};
Node *Node::Move(Node *p,int n)
{
if(n>1)
{
int i=1;
while(i<n)
{
p=p->next;
i++;
}
}
return p;
};
void Node::Josephus(Node *p,int n)
{
Node *q;
while(p->next!=p)
{
p=Move(p,n-1);
q=p->next;
cout<<q->data<<" ";
p->next=q->next;
p=p->next;
delete q;
}
cout<<"\nLast One "<<p->data<<endl;
};
void main()
{ Node A,*head;
head=A.Create(8);
cout<<"\nCirclist is ";
A.Output(head,10);
head=A.Move(head,1);
cout<<"\nJosephus result is "<<endl;
A.Josephus(head,3);
}
五、對兩種編程風格的評述
在進行面向過程的程序設計時，一般首先考慮程序所要實現的功能，然後設計為實現這些功能所必須採取的步驟，這些步驟就是過程。如果一個過程比較復雜而不能直接使用已有的抽象進行實現，則對這個過程進行分解，使分解之後的每一步（更低級的過程）能夠直接對應著一條語句。通過將分解之後的一系列過程封裝在一個函數抽象中，程序員在特定的時刻只關心有限的細節，這個新的函數抽象比其較低級的抽象更接近問題求解的過程，因而，能夠很好地映射問題求解中的過程。如果這個過程出現在許多問題求解中，那麼，這個函數抽象就可能被重復利用。
函數是面向過程程序設計的基礎，按照結構化程序設計的思想，又可將完成某一復雜工作的函數放在一個頭文件，便於我們多次復用。
面向過程的程序設計方法與面向對象的程序設計方法的根本區別在於對待數據和函數的關繫上。
在面向過程的程序設計中，數據只被看作是一種靜態的結構，它只有等待調用函數來對它進行處理。
在面向對象的程序設計中，將數據和對該數據進行合法操作的函數封裝在一起作為一個類的定義。另外，封裝還提供了一種對數據訪問嚴格控制的機制。因此，數據將被隱藏在封裝體中，該封裝體通過操作介面與外界交換信息。
面向對象的思想需要在實踐中不斷摸索和體會，在以後的程序設計中，可主動運用這種思想去實踐。

『叄』 關於約瑟夫問題，求一段C語言演算法

學會網路嘛騷年
網路知道上面就有人提供啊
http://..com/link?url=_0yG2pbWSKpFL5nvgJNWLOUnuW-b8fkPn2rc-roZlK
我測試過，devc上面可以運行

『肆』 數學上的約瑟夫問題怎麼解

在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
-----來自網路

『伍』 什麼是約瑟夫法則

約瑟夫演算法：n個人圍成一圈，每人有一個各不相同的編號，選擇一

個人作為起點，然後順時針從1到k數數，每數到k的人退出圈子，圈

子縮小，然後從下一個人繼續從1到k數數，重復上面過程。求最後推

出圈子的那個人原來的編號。

約瑟夫演算法可以用循環鏈表和數組來解(這兩個我會)，下面2個程序

都是用來解決該演算法的，其中第（2）直接給出答案，每個程序都有

證明和講解，

程序1(遞歸法):
#include <stdio.h>
#include <stdlib.h>

int main(void)
{
int n;
int m;
int i = 0;
int p;

scanf("%d%d", &n, &m);

while (++i <= n )
{
p = i * m;
while (p>n)
{
p = p - n + (p-n-1) / (m-1);
}

printf("%d\n", p);
}

return 0;
}

程序2(遞推法):
#include <stdio.h>

int main(void)
{
int i;
int s = 0;
int n;
int m;

scanf("%d%d", &n, &m);

for (i = 2; i <= n; i++)
{
s = (s + m) % i;
}

printf("最後的獲勝者是: %d\n", s + 1);

return 0;
}

程序1證明：
假設數到第p個數時遇到的數,和數到第x個數到遇到的數一樣,且p -

n < x < p,而且x % m != 0, 否則會被跳過和第個p數遇到的數肯定

不一樣,那麼說明數了x個數之後再數一圈就數到了第p個數,而數一圈

數過的數應該是n減去要跳過的數,因為已經數過了x個數,所以要跳過

[x / m]個數( []表示取整數部分 ),所以x + n - [x / m] = p
問題轉化為: p - n = x - [x / m]...(1),且 x % m != 0, p - n <

x < p, 求解x
因為x % m != 0 => x / m - 1 < [x / m] < x / m
=> x - x / m + 1 > x - [x / m] > x - x / m
=> [x - x / m + 1] >= x - [x / m] > [x - x / m]
=> [x - x / m] + 1 >= x - [x / m] > [x - x / m]
=> [x - x / m] + 1 >= x - [x / m] >= [x - x /

m] + 1
=> [x - x / m] + 1 = x - [x / m]
( 代入(1)式 )=> p - n - 1 = [x - x / m] = [x * ( m - 1 ) /

m] ... (2)
因為x % m !=0 且 ( m - 1 ) % m != 0 => ( x * ( m - 1 ) ) %

m != 0
由(2)式 => 0 < x * ( m - 1 ) - m * ( p - n - 1 ) <= m - 1
由左邊: => m * ( p - n - 1 ) < x * ( m - 1 )
=> m * ( p - n - 1 ) / ( m - 1 ) < x
=> [m * ( p - n - 1 ) / ( m - 1 )] < x
=> [m * ( p - n - 1 ) / ( m - 1 )] + 1 <= x ...(3)
由右邊: => x * ( m - 1 ) - ( m - 1 ) <= m * ( p - n - 1 )
=> ( x - 1 ) * ( m - 1 ) <= m * ( p - n - 1 )
=> x - 1 <= m * ( p - n - 1 ) / ( m - 1 )
=> x - 1 <= [m * ( p - n - 1 ) / ( m - 1 )]
=> x <= m * ( p - n - 1 ) / ( m - 1 ) + 1 ...(4)
由(3),(4) => x = [m * ( p - n - 1 ) / ( m - 1 )] + 1
= [ p - n - 1 + ( p - n - 1 ) / ( m - 1 )] +

1
= p - n - 1 + [( p - n - 1 ) / ( m - 1 )] + 1
= p - n + [( p - n - 1 ) / ( m - 1 )]
由於計算機算整數除法直接就取整了,所以遞歸時就寫成
p = p - n + ( p - n - 1 ) / ( m - 1 )

程序2證明：
Josephus(約瑟夫)問題的數學方法(轉)約瑟夫 （轉）

無論是用鏈表實現還是用數組實現都有一個共同點：要模擬整個

游戲過程，不僅程序寫起來比較煩，而且時間復雜度高達O(nm)，當n

，m非常大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短時間

內出結果的。我們注意到原問題僅僅是要求出最後的勝利者的序號，

而不是要讀者模擬整個過程。因此如果要追求效率，就要打破常規，

實施一點數學策略。
為了討論方便，先把問題稍微改變一下，並不影響原意：

問題描述：n個人（編號0~(n-1))，從0開始報數，報到(m-1)的退出

，剩下的人繼續從0開始報數。求勝利者的編號。

我們知道第一個人(編號一定是m%n-1) 出列之後，剩下的n-1個人組

成了一個新的約瑟夫環（以編號為k=m%n的人開始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
並且從k開始報0。

現在我們把他們的編號做一下轉換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1

變換後就完完全全成為了(n-1)個人報數的子問題，假如我們知道這

個子問題的解：例如x是最終的勝利者，那麼根據上面這個表把這個x

變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相

信大家都可以推出來：x『=(x+k)%n

如何知道(n-1)個人報數的問題的解？對，只要知道(n-2)個人的解就

行了。(n-2)個人的解呢？當然是先求(n-3)的情況 ---- 這顯然就是

一個倒推問題！好了，思路出來了，下面寫遞推公式：

令f[i]表示i個人玩游戲報m退出最後勝利者的編號，最後的結果自然

是f[n]

遞推公式
f[1]=0;
f[i]=(f[i-1]+m)%i; (i>1)

『陸』 Java約瑟夫經典循環演算法

下面是我用c#寫的，其實原理都一樣，樓主自己研究下吧

Console.WriteLine("請輸入參與游戲的人數：");
int numPerson = int.Parse(Console.ReadLine());

Console.WriteLine("請輸入游戲退出的規則數：");
int ruleNum = int.Parse(Console.ReadLine());

bool[] person = new bool[numPerson]; //定義每個人是否退出開關，默認為否
int callNum = 0; //報數
int total = 0; //記錄已經退出的人數
int index = -1; //報數的循環游標

while (true) {

index++; //從第一個人開始
index %= numPerson; //確保數組不越界，當游標指向最後一個數組元素以後，從頭開始

if (!person[index]) { //第index個人沒有退出時，則進行報數

callNum++;
}
if (callNum == ruleNum) { //當第index個人報數的數字與規則數相同時，則開關打開，退出報數

person[index] = true;
total++; //退出的總人數更新
callNum = 0; //為下一個人報數更新數據
Console.WriteLine("玩家{0}退出",index+1);
}
if ((numPerson - total) == 1) { //當游戲玩家只剩下一個的時候結束游戲

for (int i = 0; i < person.Length; i++) {

if (person[i] == false) { // 判斷退出開關依然是否的玩家

Console.WriteLine("最後剩下的玩家是第：{0}位",i + 1); //輸出實際的玩家號
break;
}
}
break;
}
}

『柒』 約瑟夫環的演算法例子

遞歸法： #include<stdio.h>#include<stdlib.h>struct_Node{intdata;struct_Node*next;};typedefstruct_Nodenode_t;typedefstruct_Linklist{node_t*phead;node_t*ptail;intlen;}Linklist;staticnode_t*GetNode(inti)//新建並初始化節點{node_t*pNode;pNode=(node_t*)malloc(sizeof(node_t));if(!pNode){printf(Error,thememoryisnotenough! );exit(-1);}pNode->data=i;pNode->next=NULL;returnpNode;}voidinit_list(Linklist*plist)//用第一個節點初始化循環單鏈表{node_t*p;p=GetNode(1);//printf(TheNewNodeis:%d ,p->data);//****TEST****plist->phead=p;plist->ptail=p;p->next=plist->phead;plist->len=1;}staticvoidCreate_List(Linklist*plist,intn)//把其餘數據添加到循環單鏈表中{inti=0;node_t*pNew;for(i=2;i<=n;i++){pNew=GetNode(i);/********TEST********printf(TheNewNodeis:%d ,pNew->data);********TEST********/plist->ptail->next=pNew;plist->ptail=pNew;pNew->next=plist->phead;plist->len++;}printf(Completesthee-! );}voidPrint_List(Linklist*plist)//輸出鏈表內容{node_t*pCur=plist->phead;do{printf(The%dperson. ,pCur->data);pCur=pCur->next;}while(pCur!=plist->phead);printf(ThelengthoftheList:%d ,plist->len);}約瑟夫回環函數實現voidjoseph(Linklist*plist,intm)//約瑟夫回環函數實現{node_t*pPre=plist->ptail;node_t*pCur=plist->phead;inti;while(plist->len!=1){i=0;while(i<m-1){pPre=pPre->next;i++;}pCur=pPre->next;pPre->next=pCur->next;free(pCur);plist->len--;}printf(Thelastoneis:%d ,pPre->data);}intmain(){intn=0;printf(:);scanf(%d,&n);intm=0;printf(PleaseinputtheStoppoint:);scanf(%d,&m);LinklistpList;init_list(&pList);Create_List(&pList,n);Print_List(&pList);joseph(&pList,m);return0;}

非遞歸法： #include<stdio.h>#defineM200intmaininttemp=0;intb=1,k=0;for(inti=1;i<=M;i++)temp=b+3*k;if(i==temp)//規則2：若上一組數字為最後保留號與人數相等，則下一數從2開始記。b=2;k=0;continue;elseif(i-temp==1）//規則1：若上一組數字為最後保留號比人數少一，則下一數從1開始記。{b=1;k=0;continue;}k++;printf(%d%d,M,temp);return0;【php模擬】php有非常完善的數據結構模擬方案,可以非常簡潔的解決這樣的問題.當然數量級太大那還是使用數學方法吧!$m>$n的情況也能行,想優化效率不知道該怎麼寫了.請大神補充吧!functionking($n,$m){$monkey=range(1,$n);//模擬建立一個連續數組$i=0;while(count($monkey)>1){$i+=1;//開始查數$head=array_shift($monkey);//直接一個一個出列最前面的猴子if($i%$m!=0){array_push($monkey,$head);//如果沒數到m或m的倍數,則把該猴放回尾部去.}//否則就拋棄掉了}return$monkey[0];}echo'剩餘',king(3,4),'號猴子'; （defun josephus-main )
（let (lt (make-array 20 :fill-pointer 0)
（dotimes (var 20）
（vector-push var lt)
（josephus-loop lt)
（defun josephus-loop(lt)
（if (= (length lt) 1）
（progn
（format t ~a~% lt)
（return-from josephus-loop)
（if (>= (length lt) 5）
（progn
（let (setv (remove (elt lt 4）lt)
（josephus-loop setv)
（progn
（let (setv (remove (elt lt (if (= (length lt) (- 4 (length lt) (- 4 (length lt) 1） (- 4 (length lt) lt)
（josephus-loop setv) program Josephus(input,output);
type pointer=^nodetype;
nodetype=record
data:integer;
link:pointer
end;
var head,next,last:pointer;
i,n,s,j,m,k:integer;
begin
writeln('請輸入組成約瑟夫環的人數：');
read(n);
new(head);
head^.data :=1;
last:=head;
for i:=2 to n do
begin
new(next);
next^.data :=i;
last^.link :=next;
last:=next
end;
last^.link :=head;
next:=head;
repeat
begin
writeln(next^.data);
next:=next^.link
end;
until next=head;
readln;
next:=head;
writeln('請輸入第一個報數人的位置：');
read(s);
j:=1;
if s<=n
then
while j<s do
begin
next:=next^.link ;
j:=j+1
end
else writeln('你的輸入有誤');
writeln('請輸入出列人的位置：');
read(m);
while next^.link <>next do
begin
k:=1;
while k<m do
begin
last:=next;
next:=next^.link ;
k:=k+1
end;
writeln(next^.data);
last^.link :=next.link ;
next:=next^.link
end;
writeln(next^.data);
readln;
readln
end. define('N',1000);//總數define('P',rand(1,N));//開始報數的位置define('M',rand(1,N/2));//報數的間距/***方法一：通過循環遍歷得到結果*如果N,M比較大的話，此方法不建議使用，因為實在太LOW了*/functiongetSucessUserNum(){$data=range(0,N);unset($data[0]);if(empty($data))returnfalse;//第一個開始報數的位置$p=P;while(count($data)>1){for($i=1;$i<M;$i++){$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);$p++;$p=($p==N)?$p:$p%N;}$p=(isset($data[$p]))?$p:getExistNumPosition($data,$p);unset($data[$p]);$p=($p==N)?1:$p+1;}$data=array_values($data);echo<br>successfulnum:.$data[0].<br><br>;}/***獲取下一個報數存在的下標*$data當前存在的數據*$p上一個報名數的下標*/functiongetExistNumPosition($data,$p){if(isset($data[$p]))return$p;$p++;$p=($p==N)?$p:$p%N;returngetExistNumPosition($data,$p);}/***方法二：通過演算法得到結果*此方法比方法一快多了，不行自己試一下*/functiongetSucessUserNum(){$data=range(1,N);if(empty($data))returnfalse;//第一個報數的位置$start_p=(P-1);while(count($data)>1){//報到數出列的位置$del_p=($start_p+M-1)%count($data);if(isset($data[$del_p])){unset($data[$del_p]);}else{break;}//數組從新排序$data=array_values($data);$new_count=count($data);//計算出在新的$data中，開始報數的位置$start_p=($del_p>=$new_count)?($del_p%$new_count):$del_p;}echo<br>successfulnum:.$data[0].<br><br>;}

『捌』 約瑟夫環（c語言版數據結構） 下面是約瑟夫環的代碼，跪求大神幫忙寫出代碼對應的演算法！越詳細越好！

#include <stdlib.h>
#include <stdio.h>
#include <Math.h>
typedef struct node
{int number;
int password;
struct node* next;
}Node,*Linklist;
Linklist CreateLinklist(int amount)
{int i;
Node *s=NULL,*r=NULL;
Linklist L=NULL,R=NULL;
for(i=0;i<amount;i++)
{
s=(Node*)malloc(sizeof(Node));
if(s==NULL)
{printf("空間申請失敗!");
exit(0);
}
s->number=i+1;
s->password=rand()%10+1;
printf("%4d的密碼%4d\n",s->number,s->password);
if(i==0)
{L=s;r=s;}
else {r->next=s;
r=s;
}
}
R=r;
r->next=L;
return(R);
}
void DeleteLinklist(Linklist R,int start,int amount,int num)
{Node *position=NULL,*p=NULL,*q=NULL;
int i,k,secret;
position=R;
secret=start;
for(i=num;i<=amount;i++)
{p=position;
for(k=1;k<secret;k++)
{p=p->next;}
q=p->next;
p->next=q->next;
secret=q->password;
printf("%5d",q->number);
if(i%10==0)
{printf("\n");}
position=p;
free(q);
}
}
int main()
{int amount,start,num;
Linklist R=NULL;
printf("\n請輸入總人數：");
scanf("%d",&amount);
R=CreateLinklist(amount);
printf("\n請輸入開始位置：");
scanf("%d",&start);
printf("\n請輸入開始密碼：");
scanf("%d",&num);
DeleteLinklist(R,start,amount,num);
return(1);
}

『玖』 約瑟夫演算法：n個人圍成一圈，每人有一個各不相同的編號，選擇一個人作一個

自已找到了，在錢能的書里的！￣

//***************************
//** Josephus問題解法1 **
//** jose1.cpp **
//***************************

#include <iostream.h>

void main()
{
//建立小孩數組
const int num=10; //小孩數
int interval; //每次數interval個小孩，便讓該小孩離開
int a[num]; //小孩數組
//給小孩編號
for(int i=0; i<num; i++) //小孩的編號只與小孩數有關
a[i]=i+1;
//輸入數小孩間隔
cout <<"please input the interval: "; //輸入一個數小孩個數
cin >>interval;
//將全體參加的小孩輸出
for(int i=0; i<num; i++) //順序輸出開始時的小孩編號
cout <<a[i] <<",";
cout <<endl;

int k=1; //標識處理第k個離開的小孩
int i=-1; //數組下標(下一個值0就是第一個小孩的下標)
//處理獲勝前的小孩
while(1){
//在圈中數interval個小孩
for(int j=0; j<interval; ){
i=(i+1)%num; //對下標加1求模
if(a[i]!=0) //如果該元素的小孩在圈中，則承認數數有效
j++;
}
if(k==num) break; //該小孩是最後一個(勝利者)嗎？
cout <<a[i] <<","; //輸出離開的小孩之編號
a[i]=0; //標識該小孩已離開
k++; //准備處理下一個圈中小孩
}
//break語句跳轉到此
cout <<"\nNo." <<a[i] <<" boy've won.\n"; //輸出勝利者
}

『拾』 循環單鏈表解決約瑟夫問題演算法

用一組地址任意的存儲單元存放線性表中的數據元素。 以元素(數據元素的映象) + 指針(指示後繼元素存儲位置) = 結點 (表示數據元素 或 數據元素的映象) 以「結點的序列」表示線性表 稱作線性鏈表（單鏈表） 單鏈表是一種順序存取的結構，為找第 i 個數據元素，必須先找到第 i-1 個數據元素。 因此，查找第 i 個數據元素的基本操作為：移動指針，比較 j 和 i 單鏈表 1、鏈接存儲方法 鏈接方式存儲的線性表簡稱為鏈表（Linked List）。 鏈表的具體存儲表示為： ① 用一組任意的存儲單元來存放線性表的結點（這組存儲單元既可以是連續的，也可以是不連續的） ② 鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其後繼結點的地址（或位置）信息（稱為指針（pointer）或鏈(link)） 注意： 鏈式存儲是最常用的存儲方式之一，它不僅可用來表示線性表，而且可用來表示各種非線性的數據結構。 2、鏈表的結點結構 ┌──┬──┐ │data│next│ └──┴──┘ data域--存放結點值的數據域 next域--存放結點的直接後繼的地址（位置）的指針域（鏈域） 注意： ①鏈表通過每個結點的鏈域將線性表的n個結點按其邏輯順序鏈接在一起的。 ②每個結點只有一個鏈域的鏈表稱為單鏈表（Single Linked List）。 【例】線性表（bat，cat，eat，fat，hat，jat，lat，mat）的單鏈表示如示意圖 3、頭指針head和終端結點指針域的表示 單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。 注意： 鏈表由頭指針唯一確定，單鏈表可以用頭指針的名字來命名。 【例】頭指針名是head的鏈表可稱為表head。 終端結點無後繼，故終端結點的指針域為空，即NULL。 4、單鏈表的一般圖示法 由於我們常常只注重結點間的邏輯順序，不關心每個結點的實際位置，可以用箭頭來表示鏈域中的指針，線性表（bat，cat，fat，hat，jat，lat，mat）的單鏈表就可以表示為下圖形式。 5、單鏈表類型描述 typedef char DataType; //假設結點的數據域類型為字元 typedef struct node{ //結點類型定義 DataType data; //結點的數據域 struct node *next;//結點的指針域 }ListNode typedef ListNode *LinkList; ListNode *p; LinkList head; 注意： ①*LinkList和ListNode是不同名字的同一個指針類型（命名的不同是為了概念上更明確） ②*LinkList類型的指針變數head表示它是單鏈表的頭指針 ③ListNode類型的指針變數p表示它是指向某一結點的指針 6、指針變數和結點變數 ┌────┬────────────┬─────────────┐ ││ 指針變數 │ 結點變數 │ ├────┼────────────┼─────────────┤ │ 定義 │在變數說明部分顯式定義 │在程序執行時，通過標准 │ ││ │函數malloc生成 │ ├────┼────────────┼─────────────┤ │ 取值 │ 非空時，存放某類型結點 │實際存放結點各域內容 │ │ │的地址 ││ ├────┼────────────┼─────────────┤ │操作方式│ 通過指針變數名訪問 │ 通過指針生成、訪問和釋放 │ └────┴────────────┴─────────────┘ ①生成結點變數的標准函數 p=( ListNode *)malloc(sizeof(ListNode))； //函數malloc分配一個類型為ListNode的結點變數的空間,並將其首地址放入指針變數p中 ②釋放結點變數空間的標准函數 free(p)；//釋放p所指的結點變數空間 ③結點分量的訪問 利用結點變數的名字*p訪問結點分量 方法一：(*p).data和(*p).next 方法二：p-﹥data和p-﹥next ④指針變數p和結點變數*p的關系 指針變數p的值——結點地址 結點變數*p的值——結點內容 (*p).data的值——p指針所指結點的data域的值 (*p).next的值——*p後繼結點的地址 *((*p).next)——*p後繼結點 注意： ① 若指針變數p的值為空（NULL），則它不指向任何結點。此時，若通過*p來訪問結點就意味著訪問一個不存在的變數，從而引起程序的錯誤。 ② 有關指針類型的意義和說明方式的詳細解釋 可見，在鏈表中插入結點只需要修改指針。但同時，若要在第 i 個結點之前插入元素，修改的是第 i-1 個結點的指針。 因此，在單鏈表中第 i 個結點之前進行插入的基本操作為: 找到線性表中第i-1個結點，然後修改其指向後繼的指針。