Problem 10789 Prime Frequency，字出現次數是否為質數

Problem 10789 此題要輸入一字串，判斷每個字出現的次數以及它的出現次數是否為質數，如果為質數，則列出此字；反之，則否。

此題只須記錄每字出現以及它的次數，印出時要注意是以ASCII值由小到大排列，除此之外就沒問題了。

先設幾個全域變數：

struct Num
{
    char word;
    int count;
};
struct Num N[201];
int repeatIndex = 0, index = 0;

再來是主程式區塊：

int n, i, j, isPut;
char str[2001], ch;
scanf("%d", &n);
for (i = 0; i < n ; i ++)
{   
    index = 0, isPut = 0;
    memset(str, 0, strlen(str));
    scanf("%s", str);
    for (j = 0;j < strlen(str); j ++)
        insert(str[j]);
    printf("Case %d: ", i + 1);    
    for (j = 0;j < index;j ++)
        if (isPrime(N[j].count)) printf("%c", N[j].word), isPut = 1;
    if (isPut != 1) printf("empty");    
    printf("\n");    
}

最後是函式部分：

void insert (char ch)
{
  int i;
  if ( !checkRepeat(ch))
  {
     N[index].word = ch, N[index].count = 1, index ++;
     for (i = index ; i >= 2; i--)
         if ( !change(i - 1, i - 2)) break;
  }
  else
     N[repeatIndex].count ++;    
}

int checkRepeat (char ch)
{
    for (repeatIndex = 0 ; repeatIndex < index; repeatIndex ++)
    {
        if (N[repeatIndex].word == ch)
           return 1;
    }
    return 0;
}

int change (int i, int j)
{
     struct Num temp;
     int k = (int)N[i].word, h = (int)N[j].word;
     if (N[i].word < N[j].word )
     {
        temp = N[i], N[i] = N[j], N[j] = temp;
        return 1;
     }
     return 0;   
}

int isPrime (int n)
{
    int i; 
    if (n == 1) return 0;
    for (i = 2; i < n; i ++)
        if (n % i == 0) return 0;
    return 1;    
}

By David.K

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

Problem 10812 Beat the Spread!，簡單計算

Problem 10812 此題只須要先做幾個假設再計算，程式就會很好寫。

一隊得分為 x，一隊得分為 y，總和為 s，絕對值差為 d。給定 s 和 d 之值，計算出 x 和 y。
假設 x > y，x 和 y 皆為整數，x + y = s、x - y = d，則 2x = s + d， 2y = s - d。

而須注意的是：s - d 不能為負值，s + d、s - d 不能為奇數，會與上面標紅色部分不符合。

By David.K

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

Problem 11069 A Graph Problem，計算子集合

Problem 11069 此題需要用到費氏(Fibonacci)列數的概念。

本來我想用暴力破解法，當我實際算出他前幾次的值後，才發現這關係。
F₁ = 1，F₂ = 2，F₃ = 2；而 n > 3後，則為F_n-2 + F_n-3，例如：F₄ = F₂ + F₁ = 3。

接下來，就交給你們自己去完成了。

By David.K

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

Problem 484 The Department of Redundancy Department，數值出現次數

Problem 484 此題是輸入一串以空白相間的數值，要你列出每個數值重複出現的次數。

此題我用一個二維陣列就解決了。只需判斷它數值是否有出現即可，有出現則累加；沒出現則加入。

主程式區段程式碼如下：

if ( scanf("%d", &n) < 1) break;
for (i = 0; i < index; i ++ )    
    if (Num[i][0] == n) break;
if (i != index) Num[i][1] ++;
else {    
    Num[index][0] = n, Num[index][1] = 1;
    index ++;
}    

By David.K

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

Problem 10209 Is This Integration ?，計算面積

Problem 10209 為下圖計算三區塊的面積，輸入正方形的寬度，輸出三個數值，第一個數值為畫斜線的面積、第二個數值為佈滿點面積、第三個數值為畫格子的面積。

(以上圖片已經經過修改，如要看真實圖片請至下面點擊題目連結即可。)

此題目必須使用一些三角函數的概念。

首先，以A為圓心，線AD為半徑畫60度圓，定義此點為點E，△ADE構成一個正三角形。接著定義線DE中點為點F，再以A為圓心，線AD為半徑畫30度圓，定義此點為點G。
要先算出△AED面積，已知線AD為 len，D角為60度，線DE為 len/2，利用三角函數概念，得知線AF為 len*sin60，則此三角形面積為 len*len*sin60/2 (以下稱此三角形為 t)。

我們知道A角為60度，則扇形ADE為圓的六分之一，面積為 len*len*PI/6 ，所以弓形DFG面積為 len*len*PI/6 - t (以下稱此弓形為 b)。扇形ADG為圓的十二分之一，面積為 len*len*PI/12，因弓形DFG = 弓形AHG為相同面積，則不規則形ADGH面積為 len*len*PI/12 - b (以下稱此不規則形為 d)。

仔細觀察圖形，畫斜線部分的周圍，圍起四個面積與不規則形ADGH相同的圖形。
則畫斜線的面積為 len*len - 4*d。(以下稱為 areaA)

再仔細觀察圖形，若正方形扣除四分之一圓ADB會變成怎麼樣?(思考一下)
則畫格子的圖形面積為 ( len*len - len*len*PI/4 - d ) * 4。(以下稱為 areaC)

最後，佈滿點圖形的面積為 ( areaC - d )*4

By David.K

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

Problem 10107 What is the Median?，中間數

Problem 10107 當你每輸入一個數，輸出到目前為止已輸入的數之中間數。

此題概念並不難，當輸入的數量為偶數，則取中間兩個數的平均和，例如：{1 ,4 ,5 ,8 ,9 ,29}中，數量為 6 ，6/2 = 3，也就是位置在3和4的數的平均和，(5+8)/2 = 6.5，則中間數為 6；而輸入的數量為奇數，則取排在中間的那一個數，例如：{1 ,4 , 6, 7, 9}，數量為 5， 5/2 = 2.5，也就是位置在 3 的數，則為中間數為6。

首先，題目有說他會輸入小於10000個數來測試，所以必須建立一個陣列來存放：

#define MAXLEN 10000
int Median[MAXLEN] ; 

每輸入一個值，就必須馬上存放：

if ( scanf("%d", &n) < 1) break;
Median[index] = n, index ++;

依照以上程式碼，可以看出每新增一個值，就會將它擺在目前陣列的最後一個位置。

接下來就可以將陣列排序了。一般來說，都會使用「氣泡排序法」來排序，但我可以告訴你：那是行不通的。因為「氣泡排序法」的效能為：若 n 個數要排序一次，需要 (n-1) + (n-2) + ... + 1 = n*(n-1)/2 次，效能非常之差，題目若真的有10000個數，則需要算上(n為1則0次、n為2則1次、...)...你們自己慢慢算...，絕對超過 3 秒。

既然我們知道每新增一個值就會將它擺在目前陣列的最後一個位置，只需要將最後一個索引值和它前一個索引值比較，如果小於前一個索引值，則交換其值；反之，則否。如此類推， n 個數要排序一次最多不過 n-1 次，比起「氣泡排序法」效能好太多了。

函式程式碼如下：

void Sort (int m[],int index) // index 為目前筆數
{
   int i, temp;
   for (i = index - 1; i >= 0 ; i --)
       if (m[i] < m[i - 1])
       {
           temp = m[i] ;
           m[i] = m[i - 1];
           m[i - 1] = temp;
       }   
}

用此方法，才用了 0.040 秒。

By David.k

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

Problem 10071 Back to High School Physics，粒子移動距離

Problem 10071 定義粒子在 t 秒後速度為 v ，而在 2t 秒，移動的距離為多少。

此題只需將公式導出來即可。
加速度 a = v / t = m / t²，則 v = m / t ，m = v * t， 2m 為其解。

By David.K

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

Problem 10220 I Love Big Numbers !，階乘數字的累加

Problem 10220 是輸入一個 n 值，將 n! (n 的階乘)計算出來後，再將它每個位數累加。

例如：n 值為5，5! = 120，1 + 2 + 0 = 3，則輸出 3。
此題與 Problem 623 非常相似，只是輸出需要稍作改變，將要印出來的值用一個整數累加即可。

主程式區段程式碼如下：

for (i = MAXLEN - 1; i > 0; i --)
  if (Factorial[n][i] != 0)
     break;
for (; i >= 0; i --)
  total += Factorial[n][i];
printf("%d\n", total);

By David.K

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

Problem 10082 WERTYU，修正錯字

Problem 10082 是要將打錯的字修正回來。

常見的打字錯誤就是手擺到不對的位置，此題很顯然地手是擺到右邊一格鍵上，首先，我們必須建立一個函式來處理這些錯誤的字元並修正，只需用到 if-else 判斷式就可以了。

函式區段程式碼如下：

char Correct (char ch)
{
  if (ch == '1') return '`';
  else if (ch == '2') return '1';
  else if (ch == '3') return '2';
  else if (ch == '4') return '3';
  else if (ch == '5') return '4';
  else if (ch == '6') return '5';
  else if (ch == '7') return '6';
  else if (ch == '8') return '7';
  else if (ch == '9') return '8';
  else if (ch == '0') return '9';
  else if (ch == '-') return '0';
  .....
  .....
}

主程式內只需要將每個字元丟入函式修正後輸出即可。

主程式區段程式碼如下：

while(1) {
  char str[100] = {"\0"};
  int i = 0;
  gets(str);
  if(str[0]=='\0') break;
  for (i = 0; str[i]; i ++)
      printf("%c", Correct(str[i]));
  printf("\n");  
}

By David.K

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

Problem 623 500!，階乘

Problem 623 題目要求是要輸入一整數 n，輸出 n! (n 的階乘)。

此題難在不能直接輸入一個整數 n ，再接著算出答案。因為光是500階乘就有1135長度的數字，何況題目還有個假設說「輸入的 n 值應該是不會超過 1000。」，可想而知，1000階乘的數字有多長了吧(1000階乘有2568長度) !

再來，做這種相乘一定需要用到陣列，但如果每輸入一次 n 值就要重算一次，那就太花時間了，所以必須使用一個二維陣列來記錄每個階乘的結果，也就是說，1~1000階乘算一次就可以了，只要輸入 n 值，就可依其位置將結果列出來。

首先先定義最大長度以及陣列要儲存幾個結果：

#define MAXLEN 2569
#define MAXROW 1001
int Factorial[MAXROW][MAXLEN] = {0};

以下為此題重點程式碼：

Factorial[0][0] = 1, Factorial[1][0] = 1 ;
   for (i = 2; i < MAXROW; i ++)
       for (j = 0; j < MAXLEN; j++){
           Factorial[i][j] += Factorial[i - 1][j] * i;
           if (Factorial[i][j] >= 10)
               Factorial[i][j + 1] += Factorial[i][j] / 10, Factorial[i][j] %= 10;
       }

By David.K

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