repeated_num.c

repeated_num.c

/*
要求：
單筆測資，輸入為一個正整數（保證 int 可存），請輸出這個整數出現次數 2 次以上的數字，並輸出出現的次數。
若沒有任何數字出現 2 次以上，請輸出 "No repeated digit"。
# Sample Input 1
233345
# Sample Output 1
3: 3
# Sample Input 2
12345
# Sample Output 2
No repeated digit
# Sample Input 3
112233
# Sample Output 3
1: 2
2: 2
3: 3
*/
#include <stdio.h>
#include <stdbool.h> /* To use bool */

int main() {
    int n;
    scanf("%d", &n);
    
    int cnt[10] = {0};
    
    while (n > 0) {
        int digit = n % 10;
        cnt[digit]++;
        n = n / 10;
    }
    
    bool any_repeated = false;
    for (int i=0; i<10; i++) {
        if (cnt[i] >= 2) {
            printf("%d: %d\n", i, cnt[i]);
            any_repeated = true;
        }
    }
    
    if (any_repeated == false)
        printf("No repeated digit\n");
    
    return 0;
}

/*
以上是完整程式碼，以下我們一步一步拆解程式
*/

/*
首先，讀入一個 int 後，如何拆解出各個位數的數字。
我們得先有以下前置知識：
123456 / 10 = 12345
123456 % 10 = 6
在 C 中，int 除於（使用符號 /） int 所得到的值是「整除」。
在 C 中，% 是取餘數。
根據上面兩運算，我們可以設計出以下演算法來獲得各個位數的數字。假設輸入是一正整數 n。
1. 用 n % 10 來得到 n 的「個位數」的數字。
2. 將 n / 10 使得 n 的「十位數」變「個位數」、「百位數」變「十位數」、「千位數」變「百位數」……
3. 重覆上述過程，直到 n = 0。
例如：
123456 -> 12345 -> 1234 -> 123 -> 12 -> 1 -> 0
取出 6    取出 5  取出 4  取出 3   2    1
程式可以寫成：
*/
int n;
while (n != 0) {   /* 因為 n 為正整數，所以寫 while (n > 0) 是同義的。*/
    int digit = n % 10;
    printf("%d\n", digit);
    n = n / 10;
}

/*
再來，我們得想一個方法來紀錄各個數字各出現過幾次。
最簡單的方法就是開一個長度為 10 的陣列，
int a[10];
則我們可以用 a[0], a[1], a[2] ... a[9] 來存取陣列各項的值。（注意，C 的陣列索引值是從 0 開始數的）
a[0] 代表 0 這個數字出現過幾次。
a[1] 代表 1 這個數字出現過幾次。
a[2] 代表 2 這個數字出現過幾次。
...
當然，一開始在還沒開始分解輸入時， a 陣列中的每一項都是 0。程式中寫成：int a[10] = {0};
當輸入為 22345 時，我們可以透過上一段的方法將輸入分解成： 5, 4, 3, 2, 2
（注意，我們是從個位數開始分解的，所以得到的數字順序是反過來的）
於是：
a[5] += 1; 拆解輸入得到 5，5 的出現次數加 1
a[4] += 1; 拆解輸入得到 4，4 的出現次數加 1
a[3] += 1; 拆解輸入得到 3，3 的出現次數加 1
a[2] += 1; 拆解輸入得到 2，2 的出現次數加 1
a[2] += 1; 拆解輸入得到 2，2 的出現次數加 1
當我們將輸入的所有位數都拆解出來，並在對應的 a 陣列中記錄後，我們得到 a 陣列為：
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
  0    0   2    1    1    1    0    0    0    0  
到目前為止，程式碼寫成：
*/
int a[10] = {0};

while (n > 0) {
    int digit = n % 10;
    
    a[digit] += 1; /*也可寫成 a[digit]++; */
    
    n = n / 10;
}

/* 如果你想印出 a 陣列來看看，可以這麼寫： */
for (int i=0; i<10; i++)
    printf("%d ", a[i]);
/* will print: 0 0 2 1 1 1 0 0 0 0 */

/*
根據題目，我們得把印出「出現次數 2 次以上的數字」跟「它的出現次數」
既然我們已經有各個數字的出現次數的紀錄（存在 a 陣列裡），我們就直接來看看哪些數字出現 2 次以上，若有，就輸出。
*/
for (int i=0; i<10; i++)
    if (a[i] >= 2)
        printf("%d: %d\n", i, a[i]);

/* 所以整個程式目前為止是這樣：*/
#include <stdio.h>

int main() {
    int n;
    scanf("%d", n);
    
    int a[10] = {0};
    
    while (n > 0) {
        int digit = n % 10;
        a[digit]++;
        n = n / 10;
    }
    
    for (int i=0; i<10; i++)
        if (a[i] >= 2)
            printf("%d: %d\n", i, a[i]);
    
    return 0;
}

/*
但題目還要求了另一個東西，當沒有任何數字重覆時，要輸出 "No repeated digit"。
我們得如何判斷出沒有任何數字重覆的情況？很直覺地，我們可以想到：
「沒有數字重覆」不就是「每一個數字的出現次數都小 < 2」
也就是 「a 陣列中的每一項都不會 >= 2」。
只要有任何一個數字的出現次數 >= 2，這個輸入就不會是「沒任何數字重覆」的輸入。
至於在程式中得如何實現上面的邏輯，我們會使用到一個非常常用的技巧：多使用一個變數來紀錄。
*/
int flag = 0;
for (int i=0; i<10; i++)
    if (a[i] >= 2)
        flag = 1;

if (flag == 0)
    printf("No repeated digit\n");

/*
我們新增一個變數 int flag; 我們設定 flag 只有可能是二種值：
0 代表 目前為止，沒有發現任何重覆的數字
1 代表 目前為止，已經發現有重覆的數字
flag 的初使值當然是 0。

在已經拆解完輸入的各位數數字後，我們可以來重頭到尾掃一次 a 陣列，看有沒有哪個數字的出現次數是 2 次以上，
若有遇到這種數字，就將 flag 設為 1（無論之前 flag 有沒有已經被設成 1 過）。
當我們掃完 a 陣列後，flag 的值仍然是 0 的話，就代表沒有任何重覆的數字。
例如：
2233
index    |  0    1   2    3    4    5    6    7    8    9
-------------------------------------------------------------
a[index] |  0    0   2    2    0    0    0    0    0    0
flag     |  0    0   1    1    1    1    1    1    1    1 <= 這一 row 代表掃到 a[index] 時，flag 的值
另一個例子：
991230
index    |  0    1   2    3    4    5    6    7    8    9
-------------------------------------------------------------
a[index] |  1    1   1    1    0    0    0    0    0    2
flag     |  0    0   0    0    0    0    0    0    0    1 <= 這一 row 代表掃到 a[index] 時，flag 的值
*/

/*到目前為止，程式寫成：*/
#include <stdio.h>

int main() {
    int n;
    scanf("%d, n);
    
    int a[10] = {0};
    
    while (n > 0) {
        int digit = n % 10;
        a[digit]++;
        n = n / 10;
    }
    
    for (int i=0; i<10; i++)
        if (a[i] >= 2)
            printf("%d: %d\n", i, a[i]);
            
    int flag = 0;
    for (int i=0; i<10; i++)
        if (a[i] >= 2)
            flag = 1;
    
    if (flag == 0)
        printf("No repeated digit\n");
    
    return 0;
}

/*
程式俢改到此已可以完美運作了，但可以寫得更簡短一些，
因為迴圈跟 if 的部分是一樣的，我們可以合併 198~205 行。
*/
#include <stdio.h>

int main() {
    int n;
    scanf("%d, n);
    
    int a[10] = {0};
    
    while (n > 0) {
        int digit = n % 10;
        a[digit]++;
        n = n / 10;
    }
    
    int flag = 0;
    for (int i=0; i<10; i++) {
        if (a[i] >= 2) {
            printf("%d: %d\n", i, a[i]);
            flag = 1;
        }
    }
    
    if (flag == 0)
        printf("No repeated digit\n");
    
    return 0;
}

/*
flag 這種變數，在 C99 或 C++ 中，有另一種有別於 int 的型態非常吻合它的需求：bool
bool 這種變數的值只可能是 true 或 false 中的一種。在型態轉換時，true 會轉成 1，false 會轉成 0。
在 C 中要使用 bool，除了要開使用 C99 來編譯程式外，還要 #include <stdbool.h> 。
另外為了可讀性，將程式中的變數用較有意義的單字重新命名，我們將程式修改成：
*/
#include <stdio.h>
#include <stdbool.h> /* To use bool */

int main() {
    int n;
    scanf("%d", &n);
    
    int cnt[10] = {0};
    
    while (n > 0) {
        int digit = n % 10;
        cnt[digit]++;
        n = n / 10;
    }
    
    bool any_repeated = false;
    for (int i=0; i<10; i++) {
        if (cnt[i] >= 2) {
            printf("%d: %d\n", i, cnt[i]);
            any_repeated = true;
        }
    }
    
    if (any_repeated == false)
        printf("No repeated digit\n");
    
    return 0;
}
/* 這就是教學中最一開始的程式。*/