深入理解約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法
更新時間：2013年05月24日 09:36:51 作者：
本篇文章是對約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
首先，約瑟夫環(huán)的數(shù)學(xué)優(yōu)化方法為：
為了討論方便，先把問題稍微改變一下，并不影響原意：問題描述：n個人（編號0~(n-1))，從0開始報數(shù)，報到(m-1)的退出，剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。
我們知道第一個人(編號一定是(m-1)%n) 出列之后，剩下的n-1個人組成了一個新的約瑟夫環(huán)（以編號為k=m%n的人開始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且從k開始報0?，F(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：
k --> 0 k+1 --> 1 k+2 --> 2
n-1 --> n-1-k 0--> n-k
... ...
k-3 --> n-3 k-2 --> n-2
序列1： 1, 2, 3, 4, …, n-2, n-1, n
序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n
序列3： k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1
序列4：1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1
變換后就完完全全成為了(n-1)個人報數(shù)的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎？??！變回去的公式很簡單，相信大家都可以推出來：
∵ k=m%n;
∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n
∴x'= (x+ m%n)%n = (x+m)%n 得到 x‘=(x+m)%n
如何知道(n-1)個人報數(shù)的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當(dāng)然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是f[n].
遞推公式: f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
完整的實現(xiàn)代碼如下：
/*
約瑟夫環(huán)遞推公式：令f[i]表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是f[n]
遞推公式 f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
*/
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
int n, m,i, f[20]={0};
scanf("%d %d",&n,&m);
for(i=2;i<=n;i++)
{
f[i]=(f[i-1]+m)%i;
printf("%d個人報數(shù)，報到%d的出列，最后的勝者下標(biāo)為%d\n", i,m,f[i]);
}
printf("The winner is %d\n", f[n]+1);
system("pause");
}
優(yōu)化后的代碼為：
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
int n, m,i, s=0;
scanf("%d %d",&n,&m);
for(i=2;i<=n;i++)
{
s=(s+m)%i;
}
printf("The winner is %d\n", s+1);
system("pause");
}
為了討論方便，先把問題稍微改變一下，并不影響原意：問題描述：n個人（編號0~(n-1))，從0開始報數(shù)，報到(m-1)的退出，剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。
我們知道第一個人(編號一定是(m-1)%n) 出列之后，剩下的n-1個人組成了一個新的約瑟夫環(huán)（以編號為k=m%n的人開始）: k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2 并且從k開始報0?，F(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：
k --> 0 k+1 --> 1 k+2 --> 2
n-1 --> n-1-k 0--> n-k
... ...
k-3 --> n-3 k-2 --> n-2
序列1： 1, 2, 3, 4, …, n-2, n-1, n
序列2： 1, 2, 3, 4, … k-1, k+1, …, n-2, n-1, n
序列3： k+1, k+2, k+3, …, n-2, n-1, n, 1, 2, 3,…, k-2, k-1
序列4：1, 2, 3, 4, …, 5, 6, 7, 8, …, n-2, n-1
變換后就完完全全成為了(n-1)個人報數(shù)的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎？??！變回去的公式很簡單，相信大家都可以推出來：
∵ k=m%n;
∴ x' = x+k = x+ m%n ; 而 x+ m%n 可能大于n
∴x'= (x+ m%n)%n = (x+m)%n 得到 x‘=(x+m)%n
如何知道(n-1)個人報數(shù)的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當(dāng)然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是f[n].
遞推公式: f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
完整的實現(xiàn)代碼如下：
復(fù)制代碼 代碼如下:
/*
約瑟夫環(huán)遞推公式：令f[i]表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是f[n]
遞推公式 f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
*/
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
int n, m,i, f[20]={0};
scanf("%d %d",&n,&m);
for(i=2;i<=n;i++)
{
f[i]=(f[i-1]+m)%i;
printf("%d個人報數(shù)，報到%d的出列，最后的勝者下標(biāo)為%d\n", i,m,f[i]);
}
printf("The winner is %d\n", f[n]+1);
system("pause");
}
優(yōu)化后的代碼為：
復(fù)制代碼 代碼如下:
#include "stdio.h"
#include "stdlib.h"
int main(void)
{
int n, m,i, s=0;
scanf("%d %d",&n,&m);
for(i=2;i<=n;i++)
{
s=(s+m)%i;
}
printf("The winner is %d\n", s+1);
system("pause");
}
您可能感興趣的文章:
- 一個報數(shù)游戲js版(約瑟夫環(huán)問題)
- 約瑟夫環(huán)問題(數(shù)組法)c語言實現(xiàn)
- C++循環(huán)鏈表之約瑟夫環(huán)的實現(xiàn)方法
- 詳解約瑟夫環(huán)問題及其相關(guān)的C語言算法實現(xiàn)
- java 實現(xiàn)約瑟夫環(huán)的實例代碼
- python超簡單解決約瑟夫環(huán)問題
- php解決約瑟夫環(huán)示例
- 批處理解約瑟夫環(huán)應(yīng)用題代碼
- 約瑟夫環(huán)問題的PHP實現(xiàn) 使用PHP數(shù)組內(nèi)部指針操作函數(shù)
- javascript循環(huán)鏈表之約瑟夫環(huán)的實現(xiàn)方法
相關(guān)文章
本文介紹的線程池采用C++語言，在windows平臺下實現(xiàn)。本著技術(shù)分享的精神寫作本文同時公布源代碼。歡迎大家指出該線程池存在的問題并對當(dāng)前性能進(jìn)行討論。2015-03-03
C語言菜鳥基礎(chǔ)教程之單精度浮點數(shù)與雙精度浮點數(shù)
在C語言中，單精度浮點數(shù)（float）和雙精度浮點數(shù)（double）類型都是用來儲存實數(shù)的，雙精度是用記憶較多，有效數(shù)字較多，數(shù)值范圍較大。2017-10-10
C++?構(gòu)造函數(shù)和析構(gòu)函數(shù)(Constructors?&?Destructors)詳解
由于global?object的誕生比程序進(jìn)入更早點,所以global?object的constructor執(zhí)行的時間更早于程序的進(jìn)入點,所謂的default?constructor就是沒有指定任何的參數(shù)的constructor,這篇文章主要介紹了C++?構(gòu)造函數(shù)和析構(gòu)函數(shù)的相關(guān)知識,需要的朋友可以參考下2024-05-05
C++中Cbitmap,HBitmap,Bitmap區(qū)別及聯(lián)系
這篇文章主要介紹了C++中Cbitmap,HBitmap,Bitmap區(qū)別及聯(lián)系的相關(guān)資料,需要的朋友可以參考下2015-06-06
大家好，本篇文章主要講的是C語言責(zé)任鏈模式示例代碼，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2022-01-01
本篇文章是對遍歷二叉樹的各種操作進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語言是一門結(jié)構(gòu)化的程序設(shè)計語言，當(dāng)C語言用來描述生活中的事物時，會用到三種結(jié)構(gòu)：順序結(jié)構(gòu)（不去贅述），選擇結(jié)構(gòu)（對應(yīng)分支語句），循環(huán)結(jié)構(gòu)（對應(yīng)循環(huán)語句），分支語句：分支語句分為兩種，一種是if語句，一種是switch語句2021-10-10
C++實現(xiàn)LeetCode(170.兩數(shù)之和之三 - 數(shù)據(jù)結(jié)構(gòu)設(shè)計)
這篇文章主要介紹了C++實現(xiàn)LeetCode(170.兩數(shù)之和之三 - 數(shù)據(jù)結(jié)構(gòu)設(shè)計),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了C++變量和基本類型,,一定要注意局部變量與全局變量的作用范圍,需要的朋友可以參考下,希望能夠給你帶來幫助2021-10-10
Eclipse中C++連接mysql數(shù)據(jù)庫
這篇文章主要為大家詳細(xì)介紹了Eclipse中C++連接mysql數(shù)據(jù)庫 ，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06