詳解約瑟夫環(huán)問題及其相關(guān)的C語言算法實(shí)現(xiàn)

約瑟夫環(huán)問題

N個(gè)人圍成一圈順序編號，從1號開始按1、2、3......順序報(bào)數(shù)，報(bào)p者退出圈外，其余的人再從1、2、3開始報(bào)數(shù)，報(bào)p的人再退出圈外，以此類推。

請按退出順序輸出每個(gè)退出人的原序號

算法思想用數(shù)學(xué)歸納法遞推。

無論是用鏈表實(shí)現(xiàn)還是用數(shù)組實(shí)現(xiàn)都有一個(gè)共同點(diǎn)：要模擬整個(gè)游戲過程，不僅程序?qū)懫饋肀容^煩，而且時(shí)間復(fù)雜度高達(dá)O(nm)，若nm非常大，無法在短時(shí)間內(nèi)計(jì)算出結(jié)果。我們注意到原問題僅僅是要求出最后的勝利者的序號，而不是要讀者模擬整個(gè)過程。因此如果要追求效率，就要打破常規(guī)，實(shí)施一點(diǎn)數(shù)學(xué)策略。

為了討論方便，先把問題稍微改變一下，并不影響原意：

問題描述：n個(gè)人(編號0~(n-1))，從0開始報(bào)數(shù)，報(bào)到(m-1)的退出，剩下的人繼續(xù)從0開始報(bào)數(shù)。求勝利者的編號。

我們知道第一個(gè)人(編號一定是m%n-1) 出列之后，剩下的n-1個(gè)人組成了一個(gè)新的約瑟夫環(huán)(以編號為k=m%n的人開始):

k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2并且從k開始報(bào)0。

現(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：

k???? --> 0

k+1?? --> 1

k+2?? --> 2

...

...

k-2?? --> n-2

k-1?? --> n-1

變換后就完完全全成為了(n-1)個(gè)人報(bào)數(shù)的子問題，假如我們知道這個(gè)子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個(gè)表把這個(gè)x變回去不剛好就是n個(gè)人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k)%n

如何知道(n-1)個(gè)人報(bào)數(shù)的問題的解？對，只要知道(n-2)個(gè)人的解就行了。(n-2)個(gè)人的解呢？當(dāng)然是先求(n-3)的情況——這顯然就是一個(gè)倒推問題！好了，思路出來了，下面寫遞推公式：

令f[i]表示i個(gè)人玩游戲報(bào)m退出最后勝利者的編號，最后的結(jié)果自然是f[n]

遞推公式

f[1]=0;

f[i]=(f[i-1]+m)%i; (i>1)

實(shí)現(xiàn)方法

一、循環(huán)鏈表建立一個(gè)有N個(gè)元素的循環(huán)鏈表，然后從鏈表頭開始遍歷并計(jì)數(shù)，如果基數(shù)i == m，則踢出該元素，繼續(xù)循環(huán)，直到當(dāng)前元素與下一個(gè)元素相同時(shí)退出循環(huán)

#include

#include

#include

typedef struct lnode

{

int pos;

struct lnode *next;

} lnode;

/**

* 構(gòu)建循環(huán)鏈表&&循環(huán)遍歷

*/

void create_ring(lnode **root, int loc, int n)

{

lnode *pre, *current, *new;

current = *root;

pre = NULL;

while (current != NULL) {

pre = current;

current = current->next;

}

new = (lnode *)malloc(sizeof(lnode));

new->pos = loc;

new->next = current;

if (pre == NULL) {

*root = new;

} else {

pre->next = new;

}

// 循環(huán)鏈表

if (loc == n) {

new->next = *root;

}

}

/**

* 約瑟夫環(huán)

*/

void kickoff_ring(lnode *head, int p)

{

int i;

lnode *pre, *pcur;

pre = pcur = head;

while (pcur->next != pcur) {

for (i = 1; i < p; i ++) {

pre = pcur;

pcur = pcur->next;

}

printf("%d ", pcur->pos);

pre->next = pcur->next;

free(pcur);

pcur = pre->next;

}

printf("%d\n", pcur->pos);

free(pcur);

}

void print_ring(lnode *head)

{

lnode *cur;

cur = head;

while (cur->next != head) {

printf("%d ", cur->pos);

cur = cur->next;

}

printf("%d\n", cur->pos);

}

int main()

{

int i, p, n;

lnode *head;

while (scanf("%d %d", &n, &p) != EOF) {

// 構(gòu)建循環(huán)鏈表

for (i = 1, head = NULL; i <= n; i ++)

create_ring(&head, i, n);

// 約瑟夫環(huán)

if (p != 1)

kickoff_ring(head, p);

else

print_ring(head);

}

return 0;

}

/**************************************************************

Problem: 1188

User: wangzhengyi

Language: C

Result: Accepted

Time:110 ms

Memory:912 kb

****************************************************************/

二、數(shù)組模擬思想跟循環(huán)鏈表類似，少了構(gòu)建循環(huán)鏈表的過程

#include

#include

int main()

{

int i, index, p, n, remain, delete[3001], flag[3001] = {0};

while (scanf("%d %d", &n, &p) != EOF) {

remain = n;

index = 0;

while (remain >= 1) {

for (i = 0; i < n; i ++) {

if (flag[i] == 0) {

// 報(bào)數(shù)

index ++;

// 報(bào)p者退出圈外

if (index == p) {

// 退出圈外

flag[i] = 1;

// 重新報(bào)數(shù)

index = 0;

delete[remain - 1] = i + 1;

remain --;

}

}

}

}

// 輸出每個(gè)退出人的序號

for (i = n - 1; i >= 0; i --) {

if (i == 0) {

printf("%d\n", delete[i]);

} else {

printf("%d ", delete[i]);

}

}

}

return 0;

}

三、數(shù)學(xué)推導(dǎo)

#include

int main(void)

{

int i, n, m, last;

while (scanf("%d", &n) != EOF && n != 0) {

// 接收報(bào)數(shù)

scanf("%d", &m);

// 約瑟夫環(huán)問題

for (i = 2, last = 0; i <= n; i ++) {

last = (last + m) % i;

}

printf("%d\n", last + 1);

}

return 0;

}

相關(guān)閱讀:

C#基礎(chǔ)之?dāng)?shù)據(jù)類型轉(zhuǎn)換

Android 異步獲取網(wǎng)絡(luò)圖片并處理導(dǎo)致內(nèi)存溢出問題解決方法

jquery中取消和綁定hover事件的實(shí)現(xiàn)代碼

Spring整合websocket整合應(yīng)用示例(下)

win7系統(tǒng)在word中插入excel公式的方法

JavaScript將數(shù)據(jù)轉(zhuǎn)換成整數(shù)的方法

Android 加密解密字符串詳解

Android列表實(shí)現(xiàn)(3)_自定義列表適配器思路及實(shí)現(xiàn)代碼

Linux系統(tǒng)下Git的基本配置和使用示例

jquery map方法使用示例

詳解在Java的Struts2框架中配置Action的方法

獲取控件大小和設(shè)置調(diào)整控件的位置XY示例

Win10 10074預(yù)覽版鍵盤輸入延遲是什么原因如何解決

mysql分表和分區(qū)的區(qū)別淺析

總結(jié)

以上是生活随笔為你收集整理的c语言约瑟夫环问题,C++_详解约瑟夫环问题及其相关的C语言算法实现，约瑟夫环问题N个人围成一圈 - phpStudy...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。