アルゴリズム (1) 問題用紙

アルゴリズム (1) 問題用紙
次の状態遷移図は，与えられた文字列が人名か否かを認識する動作を示している．This state transition diagram
is used to recognize a person’s name.
空白
space
a-z
空白
-1
A-Z
-2
.
-3
space
-4
A-Z
-5
* ‘空白’は空白１文字を表す．
* ‘space’ means a single character representing a space.
プログラム algo.c は，C 言語を用いて上記状態遷移図を実装したものである．なお，このプログラムが受け
入れることのできる文字は ASCII 文字とし，そのアルファベット文字は，次のように順序付けされているも
のとする：..., A, B, ..., Z, ..., a, b,..., z, ... ．問いに答えよ．解答は解答用紙に記述せよ．
The program code ‘algo.c’ is represented in C programming language, and is equivalent to the above state
transition diagram. We assume that the program only accepts a string of the ASCII characters. Upper and
lower case letters are sorted in alphabetical order in ASCII, i.e., ..., A, B, ..., Z, ..., a, b, ..., z, ... . Answer
the questions. Describe your answers on the answer sheet.
/* *** algo.c *** */
#include <stdio.h>
int transit(int state, char c){
int next_state = -state;
switch(state){
case -1:
if(’A’ <= c && c <= ’Z’)
next_state = -2;
break;
case -2:
*** (a) ***
break;
case -3:
if (c == ’Ã’)
next_state = -4;
break;
case -4:
*** (b) ***
break;
case -5:
*** (c) ***
break;
}
return next_state;
}
int tokenize(char buff[]){
/* buff: a buffer storing a person’s name
* and is terminated by the ’\0’ character.
*/
int state, i;
for(state = -1, i = 0; *** (d) ***
&& buff[i] != ’\0’; i++){
state = transit(state, buff[i]);
}
if(state == -5) state = 0;
return state;
}
int main(int argc, char *argv[]){
int state;
state = tokenize(argv[1]);
if(*** (e) ***){
fprintf(stderr, "NotÃaÃperson’sÃname.");
fprintf(stderr, "[error-codeÃ=Ã%d]\n",
state);
}else{
printf("AÃperson’sÃname.\n");
}
}
Q1. *** (a) *** ∼ *** (e) *** の空欄を埋めよ．
Put correct program codes into the five blanks *** (a) *** ∼ *** (e) ***.
Q2. 文字列 T.tSuzuki-01 を与えた場合，プログラムがどの状態で終了するかを答えよ．ここで，t は空白１
文字を表す．
Answer the final state number of the program in the case of putting the ‘T.tSuzuki-01’ string into the
program. Here, ’t’ shows a signle space character.
Q3. 文字列 T.tSuzuki-01 を与えた場合，transit 関数は何回呼び出されたか答えよ．
Answer the number of the function calls of the ‘transit’ in the case of putting the ‘T.tSuzuki-01’ string
into the program.
Q4. 文字列 T.tSuzuki-01 を与えた場合，tokenize 関数はどんな値を返すか答えよ．
Answer the return value of the ‘tokenize’ function in the case of putting the ‘T.tSuzuki-01’ string into
the program.
アルゴリズム (1) 解答用紙
本問を選択 (Select this problem) { する (Yes)，しない (No) }
No.