Problem 10637 Coprimes，互質

此題用回溯演算法就可解決。這一開始我怎麼寫都寫不出來，答案的順序錯誤，結果我上網找了一下，原來找尋這些互質的數要由小到大，而且找的下一個數要比前一個相等或來的大。

還有一點，要建構互質表，不然很容易就超過時間了，網友 藍ㄚ有兩種解題方法 ，我從這裡參考的。

所以一開始建立互質表，C 語言程式碼如下：

#define SIZE 101

int print[SIZE];
int GCD[SIZE][SIZE];
int S, t;

int gcd(int a,int b)  
{  
 if (a % b == 0){ return b;} 
 return gcd(b, a % b);
}

主程式內 ....
int a, b, n;
for(a = 1; a < SIZE; a ++)
    for(b = 1; b < SIZE; b ++)
        GCD[a][b] = gcd(a,b);

最後寫一函式，利用回溯演算法將每一種可能的方法全部試過，如果超過我們所定義數值，只有剛好等於我們定義數值，才會被列出。

void find (int index, int n, int sum)
{
    int i, j;
    if (index == t && sum == S)
    {
        printf("%d", print[0]);
        for (i = 1; i < index; i ++)
            printf(" %d", print[i]);
        printf("\n");
        return;
        
    }
    if (sum >= S) return;
    for (; n <= S - sum; n ++)
    {
           for (j = 0; j < index; j ++)
               if (GCD[print[j]][n] != 1) break;
               
           if (j == index && S - sum >= n)
           {
               print[index] = n;
               find(index + 1, n, sum + n);
           }
    }
    
}

最後在主程是如此呼叫：

scanf("%d", &n);
for (i = 1; i <= n; i ++)
{
    scanf("%d %d", &S ,&t);
    printf("Case %d:\n", i);
    find(0, 1, 0);
}

By David.K

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

Problem 10696 f91

此題為簡單題一枚。依照題目給的公式：

    *  If N ≤ 100, then f91(N) = f91(f91(N+11));
   * If N ≥ 101, then f91(N) = N-10.

我們可以拿 92 來做例子：
f91(92) = f91(f91(92 + 11)) = f91(f91(103)) = f91(93) = f91(f91(93 + 11)) = f91(94) = ...... = f91(101) = 91。
以上例子證明小於 101 之數，此遞迴函式必定將他調整為 91。
所以只要小於 101 之數為 91，大於等於 101 之數為此數減 10。
By David.K

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

Problem 10684 The jackpot，賭博

此題需要用到動態規畫。告知一連串的賭局輸贏金額，要你求出在任一段連續賭局中，能獲得的最多金幣，只需輸出金幣數值即可。

只需利用動態規劃將較佳數值往後推，推到陣列結束，在找出陣列內最大值即可。這裡也用到了輸入優化的方法。C 語言程式碼如下：

#define SIZE 10001

int money[SIZE], record[SIZE];

int getInt()  
{  
    char ch;  
    int n = 0, isNegative = 0;
    while(ch = getchar())  
        if(ch != ' ' && ch != '\n') break;
    if (ch == '-') isNegative = 1;
    else n = ch - 48;
    while( ch = getchar())   
    {  
        if(ch == ' ' || ch == '\n') break;  
        n = n * 10 + ch - 48;  
    }  
    if(isNegative) return -n;
    return n;  
}

主程式內 ....
while (n = getInt())
{
    for (i = 0; i < n; i ++)
        money[i] = 0, record[i] = 0;
    int max = 0;  
    money[0] = getInt();
    if (money[0] <= 0)
       record[0] = 0; 
    else 
       record[0] = money[0], max = money[0];
    for (i = 1; i < n; i ++)
    {
        money[i] = getInt();
        record[i] = money[i] < money[i] + record[i - 1] ? 
             money[i] + record[i - 1] : money[i];
        if (record[i] > max) max = record[i];
    }
    if (max == 0) puts("Losing streak.");
    else printf ("The maximum winning streak is %d.\n", max);
}

By David.K

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