Problem 10015 Joseph's Cousin，吃人遊戲

此題為紐西蘭停電的進階版，因為他不是從頭到尾數同一個數，而是要吃掉第 i 個人，就要數第 i 個質數，直到吃剩最後一個人才停，要輸出這最後一個人在什麼位置。

我用的方法很粗糙，暴力破解，所以執行時間有點長，不過還是過了。

首先建立質數表，數值到 33000，就能把前 3502 的質數找出來：

#define SIZE 33000
int prime[SIZE + 1];
int prime_table[SIZE], prime_table_len = 0;

void makeprime(){
    int i, j;
    prime_table[prime_table_len ++] = 2;
    for(i = 3; i < SIZE; i += 2)
        if(!prime[i]){
            for(j = i + i; j <= SIZE; j += i)
                prime[j] = 1;
            prime_table[prime_table_len ++] = i;
        }
}

再用暴力破解即可，C 語言程式碼如下：

int nextLife(int isLife[], int site, int n)
{
    while (!isLife[site])
    {
        site ++;  
        if (site >= n) site -= n;
    }
    return site;
}

int main()
{
    makeprime();
    int n, i, j, life;
    while (scanf("%d", &n) == 1 && n)
    {
        int isLife[n], nowSite = 0, count;
        for (i = 0; i < n; i ++) /* 初始化 */
            isLife[i] = 1;
        for (i = 0; i < n - 1; i ++)
        {
            count = prime_table[i] - 1;
            
            for (j = 0; j < count; j ++)
            {
                nowSite = nextLife(isLife, nowSite, n);
                nowSite ++;
                if (nowSite >= n) nowSite -= n;
            }
            nowSite = nextLife(isLife, nowSite, n);
            isLife[nowSite] = 0;
        }
        for (i = 0; i < n; i ++)
            if (isLife[i]) { printf("%d\n", i + 1); break; }
        
    }
    return 0;
}

By David.K

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