Problem 130 Roman Roulette，生死遊戲

Problem 130 此題是要算出從第幾個位置開始數，才會讓你存活下來。

一開始我設了兩個整數陣列，依照給予的 n 值做為陣列的長度，如同以下程式碼設定以及初始化：

int isLife[n], NO[n];
for (s = 0; s < n; s ++)
    isLife[s] = 1, NO[s] = s + 1;

isLife 陣列為是否有存活，NO 陣列為人的編號。因為殺掉第一個人後就要交換位置，所以我用 isLife[NO[nowSite] - 1] (nowSite 為目前位置)來判斷這個人有沒有死亡。再來，讓 nowSite 持續累加，等於 n 時則變 0，再設定一個整數 count，當 nowSite 這位置的人存活時累加 count，而 count mod (k-1) 時若等於 0 時，則表示在 NO[nowSite] 這個編號的人即將被殺，也就是 isLife[NO[nowSite] - 1] = 0。在這指令之後，就要做交換位置的動作，而找到要交換位置的人，跟上面的做法雷同，程式碼貼在以下，給大家參考，但我相信還有更好的方法。

以下為主程式區段程式碼：

for (i = 0; i < n; i ++)
{
    for (s = 0; s < n; s ++)
        isLife[s] = 1, NO[s] = s + 1;
    int nowSite = i, count = 0, nowLife = n;
    while (nowLife != 1)
    {
        nowSite ++;
        if (nowSite == n)
            nowSite = 0;
        if (isLife[NO[nowSite] - 1])
        {
           count ++;
           if (count % (k-1) == 0)
           {      
               isLife[NO[nowSite] - 1] = 0;
               nowLife --, count = 0;
               if (nowLife == 1) break;
               int changeSite = nowSite, r;
               while (1)
               {
                   changeSite ++;
                   if (changeSite == n)
                       changeSite = 0;
                   if (isLife[NO[changeSite] - 1])
                   {
                       count ++;
                       if (count % k == 0)
                       {
                           r = NO[nowSite];
                           NO[nowSite] = NO[changeSite];
                           NO[changeSite] = r;
                           count = 0;
                           while (1)
                           {
                               nowSite ++;
                               if (nowSite == n)
                                   nowSite = 0;
                               if (isLife[NO[nowSite] - 1])
                                   break;
                           }
                           break; 
                       }
                   }        
               }
           }    
        }   
    }
    if (isLife[0])
    {
        printf("%d\n", i + 1);
        break;              
    }
}

By David.K

p130題目連結
回ACM題庫目錄
回首頁