深入理解約瑟夫環(huán)的數(shù)學優(yōu)化方法
更新時間:2013年05月24日 09:36:51 作者:
本篇文章是對約瑟夫環(huán)的數(shù)學優(yōu)化方法進行了詳細的分析介紹,需要的朋友參考下
首先,約瑟夫環(huán)的數(shù)學優(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)在我們把他們的編號做一下轉換:
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)個人的解呢?當然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題!好了,思路出來了,下面寫遞推公式:
令f表示i個人玩游戲報m退出最后勝利者的編號,最后的結果自然是f[n].
遞推公式: f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
完整的實現(xiàn)代碼如下:
/*
約瑟夫環(huán)遞推公式:令f[i]表示i個人玩游戲報m退出最后勝利者的編號,最后的結果自然是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的出列,最后的勝者下標為%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)在我們把他們的編號做一下轉換:
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)個人的解呢?當然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題!好了,思路出來了,下面寫遞推公式:
令f表示i個人玩游戲報m退出最后勝利者的編號,最后的結果自然是f[n].
遞推公式: f[1]=0; f[i]=(f[i-1]+m)%i; (i>1)
完整的實現(xiàn)代碼如下:
復制代碼 代碼如下:
/*
約瑟夫環(huán)遞推公式:令f[i]表示i個人玩游戲報m退出最后勝利者的編號,最后的結果自然是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的出列,最后的勝者下標為%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");
}
您可能感興趣的文章:
- 一個報數(shù)游戲js版(約瑟夫環(huán)問題)
- 約瑟夫環(huán)問題(數(shù)組法)c語言實現(xiàn)
- C++循環(huán)鏈表之約瑟夫環(huán)的實現(xiàn)方法
- 詳解約瑟夫環(huán)問題及其相關的C語言算法實現(xiàn)
- java 實現(xiàn)約瑟夫環(huán)的實例代碼
- python超簡單解決約瑟夫環(huán)問題
- php解決約瑟夫環(huán)示例
- 批處理解約瑟夫環(huán)應用題代碼
- 約瑟夫環(huán)問題的PHP實現(xiàn) 使用PHP數(shù)組內部指針操作函數(shù)
- javascript循環(huán)鏈表之約瑟夫環(huán)的實現(xiàn)方法
相關文章
C語言中socket相關網(wǎng)絡編程函數(shù)小結
這篇文章主要介紹了C語言中socket相關網(wǎng)絡編程函數(shù)小結,是C語言入門學習中的基礎知識,需要的朋友可以參考下2015-09-09