題目:http://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=1285

約瑟夫問題

問題描述:

假設有 100(0 ~ 99) 個人圍成一圈, M 為報數值,從第一個人開始報數,數到第 M 個人時,此人就離開圈子,然後離開的下一位繼續重新報數至第 M 個人 ,直到剩下一人為止,請問是第幾個人呢 ?

輸入說明:

請輸入報數 M 的數值

輸出說明:

依照所輸入地 M 印出最後存活的人

範例:

Sample Input

Sample Output

1

99

20

9

11

40

 

一開始宣告一個長度100的字元陣列,並且全部設為'0',

再來就要按照使用者的輸入,開始數

設一個c=0,用迴圈走訪陣列,c漸漸+1

如果c==num,就把'0'設為'A',並且把c歸零

所以還要再加個條件,在走訪時

如果陣列的元素!='A',c才+1

再來當數到陣列中第100個時,這時就會跳出迴圈,但是還沒留下最後一個元素

所以必須讓迴圈再回頭,跑到最後一個出現為止

但這樣迴圈會一直不停的循環下去,

所以要再設定一個計數器,計算離開的人數

到這裡還沒完成找出最後一個動作,要宣告一個變數,

在cP==100時,讓這個變數得到i是多少,

就代表是在陣列的第幾個,而這個位置就是最後一個離開的

但是以上的程式碼是錯的,因為如果是第100個位置的人

是最後一個離開的則i==99會先剪掉100所以

i會是-1,但並沒有第-1個位置,所以要把

  1. if(cP==100)  
  2.         {  
  3.             last=i;  
  4.             break;  
  5.         }  

這個條件移到

 

  1. if(i==99)  
  2.             i-=100; 

的上方

最後在印出last,就完成了

結果

完整程式碼

  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4.   
  5. int main()  
  6. {  
  7.     char arr[100]={'0'};  
  8.     int num;  
  9.     cin>>num;  
  10.     int c=0;  
  11.     int cP=0;  
  12.     int last=0;  
  13.     for(int i=0;i<100;i++)  
  14.     {  
  15.         if(arr[i]!='A')  
  16.             c++;  
  17.         if(c==num)  
  18.         {  
  19.             c=0;  
  20.             arr[i]='A';  
  21.             cP++;  
  22.         }  
  23.         if(cP==100)  
  24.         {  
  25.             last=i;  
  26.             break;  
  27.         }  
  28.         if(i==99)  
  29.             i-=100;  
  30.   
  31.     }  
  32.     cout<<last<<endl;  
  33.     return 0;  
  34. }  

 

若想閱讀相關文章請關注我的粉絲團

小資菜鳥向前衝

https://www.facebook.com/%E5%B0%8F%E8%B3%87%E8%8F%9C%E9%B3%A5%E5%90%91%E5%89%8D%E8%A1%9D-204484273323335/?fref=ts

文章標籤
創作者介紹

cychss6305的部落格

cychss6305 發表在 痞客邦 PIXNET 留言(0) 人氣()