Problem 10008 What's Cryptanalysis?

此題就是將所有出現過的字母轉換成大寫紀錄它出現的次數以及將它排序(先比次數、再比字母大小)。

首先建一個結構(struct)並且創建陣列 w，內容有一 char 紀錄字母和一 int 紀錄字母出現次數。寫一個 check(char ch) 函式檢查字母是否出現在結構陣列 w 內。寫一 insert(char ch) 函式使用 check(char ch) 檢查後，如果有出現此字母，就累加並且將此字母的出現次數與前面的字母比較，若相等，則比字母大小；如果沒有出現，則加入，並且與前面的比較字母大小。C 語言程式碼如下：

struct Word
{
    char ch;
    int count;
};

struct Word w[26], c;
int index = 0, repeatIndex ;

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

void insert(char ch)
{
    int i; 
    if (check(ch))
    {
       w[index].count = 1, w[index].ch = ch;
       index ++;
       for (i = index - 1; i >= 1; i --)
           if (w[i].ch < w[i - 1].ch && w[i].count >= w[i - 1].count)
              c = w[i], w[i] = w[i - 1], w[i - 1] = c;
           else break;   
    }
    else 
    {
         w[repeatIndex].count ++;
         for (i = repeatIndex; i >= 1; i --)
             if (w[i].count > w[i - 1].count || 
                 w[i].count == w[i - 1].count && w[i].ch < w[i - 1].ch)
                 c = w[i], w[i] = w[i - 1], w[i - 1] = c;
             else break;    
    }
}

最後再將每個字母傳入 insert(char ch) 就可以了。主程式 C 語言程式碼如下：

int n, i, lineCount = 0;
char ch;
scanf("%d", &n);
getchar();
while (1)
{
    ch = getchar();
    if (isalpha(ch))
    {
       ch = toupper(ch);
       insert(ch);
    }
    /* printf("%c", ch); */
    if (ch == '\n')
    {
       lineCount ++;
       if (lineCount == n)
       { 
           print();
           break;
       }
    }
}

最後別忘記要印出。

By David.K

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