2018年5月28日 星期一

大學程式能力檢定 (CPE) 試題

二哥 6 月份要再次參加 APCS 檢定, 前次的弱點是沒學過樹與圖, 所以實作題沒有全部答題. 除此之外, 字串也是實作題必考項目, 因此週日在鄉下的市圖分館借回 "大學程式能力檢定 (CPE) 密笈" 一書來複習字串處理題目. CPE 的首頁如下, 裡面有歷屆考題 :

https://cpe.cse.nsysu.edu.tw/index.php


6-1 字元與字串 :

例題 6.1.1 :

https://uva.onlinejudge.org/external/100/p10008.pdf

此題要求統計輸入的字串中英文字母不分大小寫出現的次數, 然後按次數由大至小列出字母與其出現之次數. 書上範例是用 C++ 寫的, 我將其改寫為 C 語言版如下 :

#include <stdio.h>
#include <string.h>

int main(void) {
   char str[256], *ustr;         //分別儲存原始輸入字串與轉成大寫後之字串
   int count[256]={0};         //一定要初始化為 0
   printf("請輸入字串\n");
   gets(str);     //不要用 scanf(), 會被空白終止讀取

   ustr=strupr(str);   //將字串內之英文字母全部轉成大寫 (傳回指標)
 
   for (int i=0; i<strlen(str); i++) {  //掃描每一個輸入字元
         count[*(ustr+i)]++;                  //將大寫字串中字母對應之 count 陣列元素增量
         } 
   for (int i=strlen(str); i>0; i--) {         //次數由大到小顯示
         for (char c='A'; c<='Z'; c++) {    //掃描 A~Z 對應之 count 元素是否為此 i
            if (count[c] == i) {printf("%c %d\n", c, count[c]);}  //是舊印出來
            }
         }
   return 0;
   }

上述程式主要使用了 string.h 中的 strupr() 來將字串轉成大寫, 並利用一個 count[256] 陣列來記錄英文字母出現之次數, 雖然配置了 256 個記憶體, 實際上有用到的部分是 A~Z (ASCII 碼 65~90) 共 26 個字母之統計數字. 此處 count 使用 ASCII 碼的 10 進位碼來當索引. 注意, strupr() 會傳回一個字元指標, 因此宣告了一個 ustr 來接收. 其次, 統計次數的陣列一定要初始化為 0, 否則記憶體內之殘存值會破壞統計結果. ASCII 碼參考 :

https://zh.wikipedia.org/wiki/ASCII

執行結果如下 :

請輸入字串
Hello World
L 3
O 2
D 1
E 1
H 1
R 1
W 1

--------------------------------
Process exited after 7.424 seconds with return value 0
請按任意鍵繼續 . . .

注意, 不要用 scanf() 來讀取輸入, 因為 scanf() 一遇到空白就會終止讀取, 因此輸入 Hello World 會只讀到 Hello 而已, gets() 則會一直讀到跳行.


例題 6.1.2 :

https://uva.onlinejudge.org/external/102/p10222.pdf

此題為字元解碼問題, 鍵盤輸入 "k[r dyt I[o", 要將其解碼輸出為 "how are you". 觀察其編碼規則為字元在鍵盤位置往左兩格即為輸出之字元, 例如 k 往左兩鍵為 h, 而 [ 往左兩格為 o.

解題方法是建立一個鍵盤字元組成之字串 "`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./", 然後掃描輸入的字元, 利用 strchr() 函數找出此字元在鍵盤字串中的位置, 將其索引減 2 即得到解碼字元. C 語言程式碼如下 :

#include <stdio.h>
#include <string.h>

int main(void) {
    char str[256];        //儲存輸入字串
    char *pstr;             //儲存轉成小寫的字串
    char kb[]="`1234567890-=qwertyuiop[]\\asdfghjkl;'zxcvbnm,./";
    printf("請輸入字串\n");
    gets(str);                //不要用 scanf(), 會被空白終止讀取
    pstr=strlwr(str);     //將輸入字串轉成小寫 (傳回指標)
    for (int i=0; i<strlen(str); i++) {  //掃描每一個輸入字元
         char *p=strchr(kb, *(pstr+i));   //在 kb 字串中搜尋字元, 傳回其位址
         if (p) {      //有找到 : 輸出其前兩格字元
             printf("%c", *(p-2));     //指標往前移兩格
             }
         else {        //沒找到 : 輸出原始字元
             printf("%c", str[i]);
             }
         }
    return 0; 
    }

此程式中使用 str[256] 陣列儲存原始輸入字串, 指標 pstr 指向將輸入字串以 strlwr() 函數轉成小寫後之字串, 陣列 kb 則儲存鍵盤字元依序排列組成之字串. 注意, 倒斜線必須用兩個 "\\" 來表示其本身, 否則後面的 a 字元會變成脫逸字元而找不到.

首先用 gets() 讀入字串存在 str 裡, 然後呼叫 strlwr() 將原始字串轉成小寫 (因為 kb 中全部都用小寫), 最後用 for 迴圈拜訪字串字串中的每一個字元, 並呼叫 strchr() 在 kb 字串中尋找此字元, 有找的話會傳回此字元在 kb 字串中的位址 (指標), 將指標往前移兩格即可找到解碼字元, 沒找到就輸出原始字元 : 

執行結果如下 :

請輸入字串
k[r dyt I[o
how are you
--------------------------------
Process exited with return value 0
Press any key to continue . . .
此題要求將輸入的整數 n (小於 2000000000) 每一位數遞迴相加, 直到變成個位數為止, 例如輸入 1234, 第一輪相加 1+2+3+4=10, 第二輪相加 1+0=1 即為答案, 主要是數字字元轉成整數問題. 依題義輸入整數小於 2000000000 為 10 位數, 可用一個 n[11] 陣列來儲存所輸入之數字字元 (ASCII 碼為 48~57), 只要將數字字元減掉 48 即可得到相對應之整數數字.


#include <stdio.h>
#include <string.h>

int main(void) {
   char n[11]={0};    //預設為 '0'
   printf("請輸入數字 (小於 2000000000)\n");
   scanf("%s", n);   
   int F=0;
 
   while (strlen(n) != 1) {   //還沒變個位數
       int F=0;
       for (int i=0; i<strlen(n); i++) {  //掃描每一個輸入字元
           F += n[i]-48;  //ASCII 字元轉成數字疊加
           } 
       memset(n, '\0', 11);
      sprintf(n, "%d", F);
       }
   printf("%s\n", n);
   return 0;
   }

執行結果如下 :

請輸入數字 (小於 2000000000)
47
2

--------------------------------
Process exited after 23.14 seconds with return value 0
請按任意鍵繼續 . . .


例題 6.1.4 :

https://uva.onlinejudge.org/external/102/p10252.pdf

此題要求輸入兩個字串, 比較兩字串中字元, 按照字母順序列出兩字串中同時出現之字元. 演算的方法與上面 6.1.1 類似, 即利用整數陣列來儲存字串中每個字元出現的次數, 並以 ASCII 碼作為陣列索引以利存取. 只要掃瞄兩個計數陣列中字元次數同時不為 0 者, 即為兩字串中同時都出現之字元. C 程式改寫如下 :

#include <stdio.h>
#include <string.h>

int main(void) {
    char a[1001], b[1001];    //儲存輸入的兩個字串
    counta[123]={0}, countb[123]={0};  //務必初始化為 0
    printf("請輸入兩行字串\n");
    gets(a);     //讀入第一個字串
    gets(b);     //讀入第二個字串
    for (int i=0; i<strlen(a); i++) {  //統計 a 字串裡字元出現之次數
        counta[a[i]]++;
        }
    for (int i=0; i<strlen(b); i++) {  //統計 b 字串裡字元出現之次數
        countb[b[i]]++;
        } 
    for (int i=97; i<123; i++) {  //掃描 a~z 字元
        if (counta[i] > 0 && countb[i] > 0) {   //列出兩者次數皆大於 0 者
            printf("%c", i);
            }
        }       
    return 0; 
    }


執行結果如下 :

請輸入兩行字串
retty
omen

-------------------------------
rocess exited with return value 0
ress any key to continue . . .

請輸入兩行字串
alking
own
w
-------------------------------
rocess exited with return value 0
ress any key to continue . . .

請輸入兩行字串
the
street
et
--------------------------------
Process exited with return value 0
Press any key to continue . . .

~未完待續

參考 :

[C]scanf字串空白錯誤
C語言字符串函數大全
C语言tolower()函数:将大写字母转换为小写字母
http://dhcp.tcgs.tc.edu.tw/c/p009.htm
經典c程式100例 91-100
C語言考古題 & C的解題 -- 程式設計學習入門

沒有留言 :