約瑟夫問題 利用C++解決約瑟夫問題。
這是17世紀的法國數(shù)學家加斯帕在《數(shù)目的游戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)進行直到僅余15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。
*問題分析與算法設計
約瑟夫問題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實現(xiàn)方法。
題目中30個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示。可以使用結(jié)構(gòu)數(shù)組來構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向下一個人的指針，以構(gòu)成環(huán)形的鏈；其二為該人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數(shù)，每數(shù)到9時，將結(jié)構(gòu)中的標記改為0，表示該人已被扔下海了。這樣循環(huán)計數(shù)直到有15個人被扔下海為止。
一般形式
約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數(shù)，第M個將被殺掉，最后剩下一個，其余人都將被殺掉。例如N=6，M=5，被殺掉的人的序號為5，4，6，2，3。最后剩下1號。
假定在圈子里前K個為好人，后K個為壞人，你的任務是確定這樣的最少M，使得所有的壞人在第一個好人之前被殺掉。
C++代碼示例:
#include<iostream>
using namespace std;
void main()
{
int n,m,a[101],k,i,j,num; //計數(shù)器是從1開始的,所以100個人用101
cout<<"請輸入?yún)⒓佑螒虻耐婕胰藬?shù)(不超過100人):";
cin>>n;
cout<<"----------------------------------------"<<endl;
if(n>100)
{
cout<<"玩家太多,請重新登陸此程序!"<<endl;
return;
}
cout<<"輸入游戲中要玩的數(shù)字:";
cin>>m;
cout<<"----------------------------------------"<<endl;
for(i=1;i<=n;i++)
{
a【i】=1;//注意百度百科里不讓使用ASCII里的方括號，這里是中文字符集里的方括號，
}
j=0;
k=0;
for(i=1;i<=n+1;i++){
if(a【i】==1){
j=j+a【i】;
if(j==m)
{
j=0;
a【i】=0;
k++;
}
if(k==n){
num=i;
break;
}
}
if(i==n+1)
i=0;
}
cout<<"最后獲勝的玩家是第 "<<num<<" 號玩家!"<<endl;
cout<<"----------------------------------------"<<endl;
}
寫完密碼約瑟夫就想到原來看到約瑟夫問題的一個數(shù)學解法 很巧妙很簡單 不過只能推出最后一個出列的人
無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點：要模擬整個游戲過程，不僅程序?qū)懫饋肀容^煩，而且時間復雜度高達O(nm)，當n，m非常大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短時間內(nèi)出結(jié)果的。我們注意到原問題僅僅是要求出最后的勝利者的序號，而不是要讀者模擬整個過程。因此如果要追求效率，就要打破常規(guī)，實施一點數(shù)學策略。
為了討論方便，先把問題稍微改變一下，并不影響原意：
問題描述：n個人（編號0~(n-1))，從0開始報數(shù)，報到(m-1)的退出，剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。
我們知道第一個人(編號一定是m mod n-1) 出列之后，剩下的n-1個人組成了一個新的約瑟夫環(huán)（以編號為k=m mod n的人開始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且從k開始報0。
現(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換后就完完全全成為了(n-1)個人報數(shù)的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k) mod n
如何知道(n-1)個人報數(shù)的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是f[n]
遞推公式
f[1]=0;
f=(f+m) mod i; (i>1)
有了這個公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是f[n]。因為實際生活中編號總是從1開始，我們輸出f[n]+1
由于是逐級遞推，不需要保存每個f，程序也是異常簡單：
c++
#include <stdio.h>
int main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
pascal
var n,m,i,s:integer;
begin
write('N M =');
read(n,m);
for i:=2 to n do
s:=(s+m) mod i;
writeln('The winner is ',s+1);
end.
這個算法的時間復雜度為O(n)，相對于模擬算法已經(jīng)有了很大的提高。算n，m等于一百萬，一千萬的情況不是問題了。可見，適當?shù)剡\用數(shù)學策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執(zhí)行效率。
約瑟夫問題10e100版(from vijios)
描述 Description
n個人排成一圈。從某個人開始，按順時針方向依次編號。從編號為1的人開始順時針“一二一”報數(shù)，報到2的人退出圈子。這樣不斷循環(huán)下去，圈子里的人將不斷減少。由于人的個數(shù)是有限的，因此最終會剩下一個人。試問最后剩下的人最開始的編號。
輸入格式 Input Format
一個正整數(shù)n，表示人的個數(shù)。輸入數(shù)據(jù)保證數(shù)字n不超過100位。
輸出格式 Output Format
一個正整數(shù)。它表示經(jīng)過“一二一”報數(shù)后最后剩下的人的編號。
樣例輸入 Sample Input
9
樣例輸出 Sample Output
3
時間限制 Time Limitation
各個測試點1s
注釋 Hint
樣例說明
當n=9時，退出圈子的人的編號依次為：
2 4 6 8 1 5 9 7
最后剩下的人編號為3
初見這道題，可能會想到模擬。可是數(shù)據(jù)實在太大啦！！
我們先拿手來算，可知n分別為1，2，3，4，5，6，7，8...時的結(jié)果是1，1，3，1，3，5，7，1...
有如下規(guī)律：從1到下一個1為一組，每一組中都是從1開始遞增的奇數(shù)，且每組元素的個數(shù)分別為1，2，4...
這樣就好弄了！！
大體思路如下：
①read(a)
②b:=1,c:=1{b為某一組的元素個數(shù)，c為現(xiàn)在所加到的數(shù)}
③while c<a do (b:=b*2,c:=b+c){超過目標時停止加數(shù)}
⑥c:=c-b{退到前一組}
⑦x:=a-c{算出目標為所在組的第幾個元素}
⑧ans:=x*2-1{求出該元素}
⑨write(ans)
有了思路，再加上高精度就可以了。我寫的代碼比較猥瑣，因為是先把上面的思路敲進去，再寫過程，又把一些簡單的過程合到主程序中了，所以有點亂，也有點猥瑣。起提供思路的作用還是完全可以的吧~~~
var a,b,c:array[1..105]of integer;
la,lb,lc,i:integer;
s:string;
procedure incc;
var i:integer;
begin
for i:=1 to 105 do c:=c+b;
for i:=1 to 104 do if c>9 then
begin
c:=c+c div 10;
c:=c mod 10;
end;
end;
function cxiaoa:boolean;
var i:integer;
begin
cxiaoa:=false;
for i:=105 downto 1 do
if c<a then begin cxiaoa:=true;break;end
else if c>a then break;
end;
procedure doubleb;
var i:integer;
begin
for i:=1 to 105 do b:=b*2;
for i:=1 to 104 do if b>9 then
begin
b:=b+b div 10;
b:=b mod 10;
end;
end;
procedure decc;
var i,j:integer;
begin
for i:=1 to 104 do
if c>=b then c:=c-b else
begin
j:=i+1;
while c[j]=0 do inc(j);
while j>i do
begin
c[j]:=c[j]-1;
c[j-1]:=c[j-1]+10;
dec(j);
end;
c:=c-b;
end;
end;
procedure fua;
var i:integer;
begin
for i:=1 to 104 do
if a>c then a:=a-c else
begin
a:=a-1;
a:=a+10;
a:=a-c;
end;
end;
procedure outit;
var i,j:integer;
begin
for i:=1 to 105 do a:=a*2;
for i:=1 to 104 do if a>9 then
begin
a:=a+a div 10;
a:=a mod 10;
end;
if a[1]>0 then a[1]:=a[1]-1 else
begin
j:=2;
while a[j]=0 do inc(j);
while j>1 do
begin
a[j]:=a[j]-1;
a[j-1]:=a[j-1]+10;
dec(j);
end;
a[1]:=a[1]-1;
end;
for i:=105 downto 1 do if a>0 then begin j:=i;break;end;
for i:=j downto 1 do write(a);
end;
begin
readln(s);
la:=length(s);
for i:=la downto 1 do a:=ord(s[la+1-i])-ord('0');
b[1]:=1;
c[1]:=1;
while cxiaoa do
begin
doubleb;
incc;
end;
decc;
fua;
outit;
end.
筆算解決約瑟夫問題
在M比較小的時候 ，可以用筆算的方法求解，
M=2
即N個人圍成一圈，1，2，1，2的報數(shù)，報到2就去死，直到只剩下一個人為止。
當N=2^k的時候，第一個報數(shù)的人就是最后一個死的，
對于任意的自然數(shù)N 都可以表示為N=2^k+t,其中t<n/2
于是當有t個人去死的時候，就只剩下2^k個人 ，這2^k個人中第一個報數(shù)的就是最后去死的。這2^k個人中第一個報數(shù)的人就是2t+1
于是就求出了當M=2時約瑟夫問題的解：
求出不大于N的最大的2的整數(shù)次冪，記為2^k，最后一個去死的人是2(N-2^k)+1
M=3
即N個人圍成一圈，1，2，3，1，2，3的報數(shù)，報到3就去死，直到只剩下一個人為止。
此時要比M=2時要復雜的多
我們以N=2009為例計算
N=2009，M=3時最后被殺死的人記為F(2009,3),或者可以簡單的記為F(2009)
假設現(xiàn)在還剩下n個人，則下一輪將殺死[n/3]個人，[]表示取整，還剩下n-[n/3]個人
設這n個人為a1,a2,...,a(n-1),an
從a1開始報數(shù)，一圈之后，剩下的人為a1,a2,a4,a5,...a(n-n mod 3-1),a(n-n mod 3+1),..,an
于是可得：
1、這一輪中最后一個死的是a(n-n mod 3),下一輪第一個報數(shù)的是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(xiàn)(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(xiàn)(n)=3*[(k-1)/2]+(k-1)mod 2+1
這種算法需要計算 [log(3/2)2009]次 這個數(shù)不大于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(xiàn)(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
謇凝18356568536： C語言編程:約瑟夫問題 -
利辛縣縮小： ______ #include ＂stdio.h＂ main() { int i,k,quit_num,a[30],*p; p=a; for(i=0;i*(p+i)=i+1; printf(＂the position of feijiaotu are:\n＂); quit_num=0; k=0; i=0; while(quit_num{if(*(p+i)!=0)k++; if(k==9) {printf(＂%5d＂,*(p+i)); quit_num++; *(p+i)=0; k=0; } i++; if(i==30)i...
謇凝18356568536： 約瑟夫問題 c語言 -
利辛縣縮小： ______ ＂*＂表示當前數(shù)起位置#include <stdio.h> int main() { int n; int i, j; int pos[30]; for(i = 0; i < 30; i++) pos[i] = i+1; //位置輸入到數(shù)組 i = 0; n = 30; while(n > 15){ i += 8; i %= n; printf(＂扔下第 %d 人\n＂, pos[i]); n --; for(j = i; j < n; j++){ pos[j] = pos[j+1...
謇凝18356568536： 利用C++解決約瑟夫問題. -
利辛縣縮小： ______ 這里補充一下約瑟夫問題的描述:N個人圍成一圈,從第一個開始報數(shù),數(shù)到M的人出隊,然后他的下一位繼續(xù)從1開始報數(shù),數(shù)到M的出隊,如此循環(huán)直到剩下一個人,求最后剩下的那個人最初是隊伍中的第幾位.解決這道題可以采用模擬報數(shù)...
謇凝18356568536： C語言:約瑟夫問題. -
利辛縣縮小： ______ 24 1:0 2:0 3:0 4:0 5:1 6:1 7:1 8:1 9:1 10:0 11:0 12:1 13:0 14:0 15:016:1 17:0 18:1 19:1 20:0 21:0 22:1 23:1 24:1 25:0 26:1 27:1 28:0 29:0 30:1(1為非教徒,0為教徒)Press any ke...
謇凝18356568536： 約瑟夫問題 c語言數(shù)組 -
利辛縣縮小： ______ #include #define N 63 // 猴子數(shù)#define M 5 // 數(shù)數(shù)周期 void main() { // 編號 int arrId[N] = {0}; for (int i=0; i { arrId[i] = i+1; } int nCount = N; int nMod = 1; while (nCount > 1) { nMod = (nMod-1+M)%nCount; if (nMod == 0) nMod = nCount; cout for (int...
謇凝18356568536： C語言解決＂約瑟夫問題＂ -
利辛縣縮小： ______ #include<stdio.h> struct list//建立一個結(jié)構(gòu)體,包括每個人的編號,密碼和下一級的指針 { int id; struct list *next; }; list* input(int n)//鏈表的初始化 { list *p,*q,*l; int i,m; p=new list; l=new list; l->next=NULL; p=l; p->id=1;//第一個人的初始化 for(i=2;i<=n;...
謇凝18356568536： c語言約瑟夫問題 大神幫忙改錯 -
利辛縣縮小： ______ 第一個原因:for(i=1;i<=n;n++) 明顯的錯誤 第二個原因:在while里的for里要加一個判斷如果remain為1要break,不然在繼續(xù)下去的for中很可能把remain變成0,之后就不能輸出了
謇凝18356568536： c語言,約瑟夫問題
利辛縣縮小： ______ /* Note:Your choice is C IDE */ #include ＂stdio.h＂ void main() { int j,c=0,i=0,s=0; int a[80],b[80]; printf(＂N M=\n＂); do{ scanf(＂%d%d＂,&a[i],&b[i]); i++; c++; }while((a[i-1]!=0)&&(b[i-1]!=0)); for(i=0;i<c-1;i++){ for(j=2;j<=a[i];j++) s=(s+b[i])%j; printf(＂%d\n＂,s+1);} return 0; }
謇凝18356568536： ＂約瑟夫環(huán)＂問題如何解??
利辛縣縮小： ______ 無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點:要模擬整個游戲過程,不僅程序?qū)懫饋肀容^煩,而且時間復雜度高達O(nm),當n,m非常大(例如上百萬,上千萬)的時候,幾乎是沒有辦法在短時間內(nèi)出結(jié)果的.我們注意到原問題僅僅是要求出...
謇凝18356568536： C語言 約瑟夫環(huán)問題 -
利辛縣縮小： ______ #include<stdio.h> #include<malloc.h> #define Namelength 10 typedef struct CLNode{ char*name; int ID; int pastword; struct CLNode *next; }child,*ptrchild; ptrchild CreateCList(int n) {int i; ptrchild p,head,rear; printf(＂please input the children ...
*問題分析與算法設計
約瑟夫問題并不難，但求解的方法很多；題目的變化形式也很多。這里給出一種實現(xiàn)方法。
題目中30個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示。可以使用結(jié)構(gòu)數(shù)組來構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向下一個人的指針，以構(gòu)成環(huán)形的鏈；其二為該人是否被扔下海的標記，為1表示還在船上。從第一個人開始對還未扔下海的人進行計數(shù)，每數(shù)到9時，將結(jié)構(gòu)中的標記改為0，表示該人已被扔下海了。這樣循環(huán)計數(shù)直到有15個人被扔下海為止。
一般形式
約瑟夫問題是個有名的問題：N個人圍成一圈，從第一個開始報數(shù)，第M個將被殺掉，最后剩下一個，其余人都將被殺掉。例如N=6，M=5，被殺掉的人的序號為5，4，6，2，3。最后剩下1號。
假定在圈子里前K個為好人，后K個為壞人，你的任務是確定這樣的最少M，使得所有的壞人在第一個好人之前被殺掉。
C++代碼示例:
#include<iostream>
using namespace std;
void main()
{
int n,m,a[101],k,i,j,num; //計數(shù)器是從1開始的,所以100個人用101
cout<<"請輸入?yún)⒓佑螒虻耐婕胰藬?shù)(不超過100人):";
cin>>n;
cout<<"----------------------------------------"<<endl;
if(n>100)
{
cout<<"玩家太多,請重新登陸此程序!"<<endl;
return;
}
cout<<"輸入游戲中要玩的數(shù)字:";
cin>>m;
cout<<"----------------------------------------"<<endl;
for(i=1;i<=n;i++)
{
a【i】=1;//注意百度百科里不讓使用ASCII里的方括號，這里是中文字符集里的方括號，
}
j=0;
k=0;
for(i=1;i<=n+1;i++){
if(a【i】==1){
j=j+a【i】;
if(j==m)
{
j=0;
a【i】=0;
k++;
}
if(k==n){
num=i;
break;
}
}
if(i==n+1)
i=0;
}
cout<<"最后獲勝的玩家是第 "<<num<<" 號玩家!"<<endl;
cout<<"----------------------------------------"<<endl;
}
寫完密碼約瑟夫就想到原來看到約瑟夫問題的一個數(shù)學解法 很巧妙很簡單 不過只能推出最后一個出列的人
無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點：要模擬整個游戲過程，不僅程序?qū)懫饋肀容^煩，而且時間復雜度高達O(nm)，當n，m非常大(例如上百萬，上千萬)的時候，幾乎是沒有辦法在短時間內(nèi)出結(jié)果的。我們注意到原問題僅僅是要求出最后的勝利者的序號，而不是要讀者模擬整個過程。因此如果要追求效率，就要打破常規(guī)，實施一點數(shù)學策略。
為了討論方便，先把問題稍微改變一下，并不影響原意：
問題描述：n個人（編號0~(n-1))，從0開始報數(shù)，報到(m-1)的退出，剩下的人繼續(xù)從0開始報數(shù)。求勝利者的編號。
我們知道第一個人(編號一定是m mod n-1) 出列之后，剩下的n-1個人組成了一個新的約瑟夫環(huán)（以編號為k=m mod n的人開始）:
k k+1 k+2 ... n-2, n-1, 0, 1, 2, ... k-2
并且從k開始報0。
現(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：
k --> 0
k+1 --> 1
k+2 --> 2
...
...
k-2 --> n-2
k-1 --> n-1
變換后就完完全全成為了(n-1)個人報數(shù)的子問題，假如我們知道這個子問題的解：例如x是最終的勝利者，那么根據(jù)上面這個表把這個x變回去不剛好就是n個人情況的解嗎？！！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k) mod n
如何知道(n-1)個人報數(shù)的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的解呢？當然是先求(n-3)的情況 ---- 這顯然就是一個倒推問題！好了，思路出來了，下面寫遞推公式：
令f表示i個人玩游戲報m退出最后勝利者的編號，最后的結(jié)果自然是f[n]
遞推公式
f[1]=0;
f=(f+m) mod i; (i>1)
有了這個公式，我們要做的就是從1-n順序算出f的數(shù)值，最后結(jié)果是f[n]。因為實際生活中編號總是從1開始，我們輸出f[n]+1
由于是逐級遞推，不需要保存每個f，程序也是異常簡單：
c++
#include <stdio.h>
int main()
{
int n, m, i, s=0;
printf ("N M = "); scanf("%d%d", &n, &m);
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %d\n", s+1);
}
pascal
var n,m,i,s:integer;
begin
write('N M =');
read(n,m);
for i:=2 to n do
s:=(s+m) mod i;
writeln('The winner is ',s+1);
end.
這個算法的時間復雜度為O(n)，相對于模擬算法已經(jīng)有了很大的提高。算n，m等于一百萬，一千萬的情況不是問題了。可見，適當?shù)剡\用數(shù)學策略，不僅可以讓編程變得簡單，而且往往會成倍地提高算法執(zhí)行效率。
約瑟夫問題10e100版(from vijios)
描述 Description
n個人排成一圈。從某個人開始，按順時針方向依次編號。從編號為1的人開始順時針“一二一”報數(shù)，報到2的人退出圈子。這樣不斷循環(huán)下去，圈子里的人將不斷減少。由于人的個數(shù)是有限的，因此最終會剩下一個人。試問最后剩下的人最開始的編號。
輸入格式 Input Format
一個正整數(shù)n，表示人的個數(shù)。輸入數(shù)據(jù)保證數(shù)字n不超過100位。
輸出格式 Output Format
一個正整數(shù)。它表示經(jīng)過“一二一”報數(shù)后最后剩下的人的編號。
樣例輸入 Sample Input
9
樣例輸出 Sample Output
3
時間限制 Time Limitation
各個測試點1s
注釋 Hint
樣例說明
當n=9時，退出圈子的人的編號依次為：
2 4 6 8 1 5 9 7
最后剩下的人編號為3
初見這道題，可能會想到模擬。可是數(shù)據(jù)實在太大啦！！
我們先拿手來算，可知n分別為1，2，3，4，5，6，7，8...時的結(jié)果是1，1，3，1，3，5，7，1...
有如下規(guī)律：從1到下一個1為一組，每一組中都是從1開始遞增的奇數(shù)，且每組元素的個數(shù)分別為1，2，4...
這樣就好弄了！！
大體思路如下：
①read(a)
②b:=1,c:=1{b為某一組的元素個數(shù)，c為現(xiàn)在所加到的數(shù)}
③while c<a do (b:=b*2,c:=b+c){超過目標時停止加數(shù)}
⑥c:=c-b{退到前一組}
⑦x:=a-c{算出目標為所在組的第幾個元素}
⑧ans:=x*2-1{求出該元素}
⑨write(ans)
有了思路，再加上高精度就可以了。我寫的代碼比較猥瑣，因為是先把上面的思路敲進去，再寫過程，又把一些簡單的過程合到主程序中了，所以有點亂，也有點猥瑣。起提供思路的作用還是完全可以的吧~~~
var a,b,c:array[1..105]of integer;
la,lb,lc,i:integer;
s:string;
procedure incc;
var i:integer;
begin
for i:=1 to 105 do c:=c+b;
for i:=1 to 104 do if c>9 then
begin
c:=c+c div 10;
c:=c mod 10;
end;
end;
function cxiaoa:boolean;
var i:integer;
begin
cxiaoa:=false;
for i:=105 downto 1 do
if c<a then begin cxiaoa:=true;break;end
else if c>a then break;
end;
procedure doubleb;
var i:integer;
begin
for i:=1 to 105 do b:=b*2;
for i:=1 to 104 do if b>9 then
begin
b:=b+b div 10;
b:=b mod 10;
end;
end;
procedure decc;
var i,j:integer;
begin
for i:=1 to 104 do
if c>=b then c:=c-b else
begin
j:=i+1;
while c[j]=0 do inc(j);
while j>i do
begin
c[j]:=c[j]-1;
c[j-1]:=c[j-1]+10;
dec(j);
end;
c:=c-b;
end;
end;
procedure fua;
var i:integer;
begin
for i:=1 to 104 do
if a>c then a:=a-c else
begin
a:=a-1;
a:=a+10;
a:=a-c;
end;
end;
procedure outit;
var i,j:integer;
begin
for i:=1 to 105 do a:=a*2;
for i:=1 to 104 do if a>9 then
begin
a:=a+a div 10;
a:=a mod 10;
end;
if a[1]>0 then a[1]:=a[1]-1 else
begin
j:=2;
while a[j]=0 do inc(j);
while j>1 do
begin
a[j]:=a[j]-1;
a[j-1]:=a[j-1]+10;
dec(j);
end;
a[1]:=a[1]-1;
end;
for i:=105 downto 1 do if a>0 then begin j:=i;break;end;
for i:=j downto 1 do write(a);
end;
begin
readln(s);
la:=length(s);
for i:=la downto 1 do a:=ord(s[la+1-i])-ord('0');
b[1]:=1;
c[1]:=1;
while cxiaoa do
begin
doubleb;
incc;
end;
decc;
fua;
outit;
end.
筆算解決約瑟夫問題
在M比較小的時候 ，可以用筆算的方法求解，
M=2
即N個人圍成一圈，1，2，1，2的報數(shù)，報到2就去死，直到只剩下一個人為止。
當N=2^k的時候，第一個報數(shù)的人就是最后一個死的，
對于任意的自然數(shù)N 都可以表示為N=2^k+t,其中t<n/2
于是當有t個人去死的時候，就只剩下2^k個人 ，這2^k個人中第一個報數(shù)的就是最后去死的。這2^k個人中第一個報數(shù)的人就是2t+1
于是就求出了當M=2時約瑟夫問題的解：
求出不大于N的最大的2的整數(shù)次冪，記為2^k，最后一個去死的人是2(N-2^k)+1
M=3
即N個人圍成一圈，1，2，3，1，2，3的報數(shù)，報到3就去死，直到只剩下一個人為止。
此時要比M=2時要復雜的多
我們以N=2009為例計算
N=2009，M=3時最后被殺死的人記為F(2009,3),或者可以簡單的記為F(2009)
假設現(xiàn)在還剩下n個人，則下一輪將殺死[n/3]個人，[]表示取整，還剩下n-[n/3]個人
設這n個人為a1,a2,...,a(n-1),an
從a1開始報數(shù)，一圈之后，剩下的人為a1,a2,a4,a5,...a(n-n mod 3-1),a(n-n mod 3+1),..,an
于是可得：
1、這一輪中最后一個死的是a(n-n mod 3),下一輪第一個報數(shù)的是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(xiàn)(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(xiàn)(n)=3*[(k-1)/2]+(k-1)mod 2+1
這種算法需要計算 [log(3/2)2009]次 這個數(shù)不大于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(xiàn)(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
瑟夫問題k個好人k個壞人問題
這是17世紀的法國數(shù)學家加斯帕在《數(shù)目的游戲問題》中講的一個故事：15個教徒和15 個非教徒在深海上遇險，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報數(shù)，每數(shù)到第九個人就將他扔入大海，如此循環(huán)進行直到僅余15個人為止。問怎樣排法...
如何用標記法求解瑟夫問題
include<stdio.h> define M 10 define N 3 \/\/M代表10個學生，N代表數(shù)到3就出去 int used[M];int main(){ int count=0,i,j;for(i=0,j=1;count!=M-1;){ if(!used[i]){ if(0==j%N){ count++;used[i]=1;} j++;} i++;if(i==n) i=0;} i=0;while(used[i]!=0...
求解約瑟夫環(huán)問題 C語言
這個就是約瑟夫環(huán)問題的實際場景，有一種是要通過輸入n,m,k三個正整數(shù)，來求出列的序列。這個問題采用的是典型的循環(huán)鏈表的數(shù)據(jù)結(jié)構(gòu)，就是將一個鏈表的尾元素指針指向隊首元素。p->link=head 解決問題的核心步驟：1.建立一個具有n個鏈結(jié)點，無頭結(jié)點的循環(huán)鏈表 2.確定第1個報數(shù)人的位置 3.不斷...
約瑟夫環(huán)問題 出現(xiàn)錯誤 幫忙看下 請說的詳細些 在線等
這不就是瑟夫環(huán)問題 以下是我做的：（數(shù)據(jù)結(jié)構(gòu)作業(yè)，運行過沒問題）define ERROR 0 define OK 1 include<stdio.h> include<stdlib.h> struct CirNode\/\/定義每個結(jié)點的類型 { int data;\/\/每個人所擁有的密碼 int num;\/\/每個人在圈中的位序 struct CirNode *next;};int a[30];\/\/人數(shù)要求≤3...
聽說全球IP快用玩了。怎么回事啊?IP不是無限的嗎?
據(jù)澳大利亞媒體報道，被譽為“互聯(lián)網(wǎng)之父”的美國網(wǎng)絡工程師文頓·瑟夫日前指出，他所創(chuàng)建的43億個IP地址快要用完了，這被認為是他的“失誤”。瑟夫解釋道：“當初我以為這只是個實驗，43億個IP地址已經(jīng)足夠了，誰會知道需要多少空間呢？”1977年，瑟夫在美國國防部任職時創(chuàng)建了互聯(lián)網(wǎng)通信協(xié)議“IPv4”...
瑟夫-納舒瓦納幼女遭輪奸事件
其中一名46歲的嫌疑人被殘忍地砍去頭顱，僅靠一根筋維系生命，場景觸目驚心。另外兩位受害者也被發(fā)現(xiàn)死在垃圾桶里，這場悲劇令人震驚。約瑟夫的行動雖然無法挽回女兒的損失，但卻表達了他對女兒深深的情感和對罪行的強烈譴責。這起事件揭示了社會問題的嚴重性，也引發(fā)了對法律和道德的深刻反思。
溫頓·瑟夫未來展望
瑟夫團隊正在探索一種新型的互聯(lián)網(wǎng)系統(tǒng)，它能夠?qū)崿F(xiàn)即時的跨星際通信，大大提升通信效率。他們面臨的挑戰(zhàn)包括如何處理遙遠距離帶來的延遲問題，但這正是他們研究的焦點。瑟夫堅信，通過他們的努力，星際網(wǎng)將不僅限于地球與火星之間的通信，而是有望成為連接全宇宙的信息高速公路，使得人類在未來的探索和互動中...
溫頓·瑟夫的靈感來源
在互聯(lián)網(wǎng)同質(zhì)化的今天，估計國內(nèi)的網(wǎng)民都想問他一個問題:是什么讓一個60多歲的“老者”仍能保持不斷創(chuàng)新、敢于創(chuàng)新的激情呢？ “我認為科幻作品可以給我靈感，激發(fā)我的想像力，讓我知道未來有什么可能性。”Cerf博士解釋說，他一直對科幻小說和電影非常著迷，《X戰(zhàn)警》、《指環(huán)王》、《哈利波特》的...
溫頓·瑟夫的未來展望
溫頓?瑟夫透露，他已經(jīng)開始著手研究地球范圍之外的互聯(lián)網(wǎng)發(fā)展之路——星際網(wǎng)，這樣的網(wǎng)絡可以用于控制宇宙飛船，以后，在火星上也能上網(wǎng)。“直到現(xiàn)在，我們一直使用‘太空跟蹤網(wǎng)’，通過無線信號與飛船進行聯(lián)絡。我們要做的是，通過一種互聯(lián)網(wǎng)進行聯(lián)絡。”瑟夫說，他們要克服很多問題，如需要等40分鐘...
TCP\/IP協(xié)議簡史
瑟夫從小就對編程充滿熱情，他的職業(yè)生涯中，從斯坦福大學畢業(yè)后加入IBM，隨后轉(zhuǎn)至加州大學洛杉磯分校攻讀博士學位，那時正值阿帕網(wǎng)的發(fā)展時期。他與鮑伯·卡恩等科學家共同參與了阿帕網(wǎng)的早期開發(fā)，通過“網(wǎng)絡控制協(xié)議”（NCP）和“傳輸控制協(xié)議”（TCP）的研制，解決了電腦間如何有效通信的問題。“包切換”...
相關(guān)評說：
利辛縣縮小： ______ #include ＂stdio.h＂ main() { int i,k,quit_num,a[30],*p; p=a; for(i=0;i*(p+i)=i+1; printf(＂the position of feijiaotu are:\n＂); quit_num=0; k=0; i=0; while(quit_num{if(*(p+i)!=0)k++; if(k==9) {printf(＂%5d＂,*(p+i)); quit_num++; *(p+i)=0; k=0; } i++; if(i==30)i...
利辛縣縮小： ______ ＂*＂表示當前數(shù)起位置#include <stdio.h> int main() { int n; int i, j; int pos[30]; for(i = 0; i < 30; i++) pos[i] = i+1; //位置輸入到數(shù)組 i = 0; n = 30; while(n > 15){ i += 8; i %= n; printf(＂扔下第 %d 人\n＂, pos[i]); n --; for(j = i; j < n; j++){ pos[j] = pos[j+1...
利辛縣縮小： ______ 這里補充一下約瑟夫問題的描述:N個人圍成一圈,從第一個開始報數(shù),數(shù)到M的人出隊,然后他的下一位繼續(xù)從1開始報數(shù),數(shù)到M的出隊,如此循環(huán)直到剩下一個人,求最后剩下的那個人最初是隊伍中的第幾位.解決這道題可以采用模擬報數(shù)...
利辛縣縮小： ______ 24 1:0 2:0 3:0 4:0 5:1 6:1 7:1 8:1 9:1 10:0 11:0 12:1 13:0 14:0 15:016:1 17:0 18:1 19:1 20:0 21:0 22:1 23:1 24:1 25:0 26:1 27:1 28:0 29:0 30:1(1為非教徒,0為教徒)Press any ke...
利辛縣縮小： ______ #include #define N 63 // 猴子數(shù)#define M 5 // 數(shù)數(shù)周期 void main() { // 編號 int arrId[N] = {0}; for (int i=0; i { arrId[i] = i+1; } int nCount = N; int nMod = 1; while (nCount > 1) { nMod = (nMod-1+M)%nCount; if (nMod == 0) nMod = nCount; cout for (int...
利辛縣縮小： ______ #include<stdio.h> struct list//建立一個結(jié)構(gòu)體,包括每個人的編號,密碼和下一級的指針 { int id; struct list *next; }; list* input(int n)//鏈表的初始化 { list *p,*q,*l; int i,m; p=new list; l=new list; l->next=NULL; p=l; p->id=1;//第一個人的初始化 for(i=2;i<=n;...
利辛縣縮小： ______ 第一個原因:for(i=1;i<=n;n++) 明顯的錯誤 第二個原因:在while里的for里要加一個判斷如果remain為1要break,不然在繼續(xù)下去的for中很可能把remain變成0,之后就不能輸出了
利辛縣縮小： ______ /* Note:Your choice is C IDE */ #include ＂stdio.h＂ void main() { int j,c=0,i=0,s=0; int a[80],b[80]; printf(＂N M=\n＂); do{ scanf(＂%d%d＂,&a[i],&b[i]); i++; c++; }while((a[i-1]!=0)&&(b[i-1]!=0)); for(i=0;i<c-1;i++){ for(j=2;j<=a[i];j++) s=(s+b[i])%j; printf(＂%d\n＂,s+1);} return 0; }
利辛縣縮小： ______ 無論是用鏈表實現(xiàn)還是用數(shù)組實現(xiàn)都有一個共同點:要模擬整個游戲過程,不僅程序?qū)懫饋肀容^煩,而且時間復雜度高達O(nm),當n,m非常大(例如上百萬,上千萬)的時候,幾乎是沒有辦法在短時間內(nèi)出結(jié)果的.我們注意到原問題僅僅是要求出...
利辛縣縮小： ______ #include<stdio.h> #include<malloc.h> #define Namelength 10 typedef struct CLNode{ char*name; int ID; int pastword; struct CLNode *next; }child,*ptrchild; ptrchild CreateCList(int n) {int i; ptrchild p,head,rear; printf(＂please input the children ...
