式の評価 / Evaluation of Expressions (16 点)

次のテーブルの式の値を計算しなさい。なお、変数 i は int i; と定義されている。
Evaluate the expressions in the table below. i is defined as int i;.

英語の用語 / English Terms (20 点)

プログラミング一般やプログラミング言語 C/C++ において使われる次の英語の用語の日本語訳と説明を書きなさい。日本語訳ではできるだけ片仮名を使わないようにしてください。
Provide Japanese translations (avoiding Katakana where possible) and explanations of the following English terms used with programming in general or the programming languages C/C++.

character encoding
文字コード; 文字がコンピュータ内にバイトで表現されるやり方、例えば UTF-8 や Shift_JIS

relational operator
関係演算子; 数値や文字の比較に使われる演算子、例えば <=, != など

syntax
構文; それぞれの式や文の記述の詳細 (部品の順番、区切り記号の有無や場所)

derived type
派生型; 基本型の組み合わせなどで作られる型、例えば配列、構造体、ポインタ、関数

comparison function
比較関数; 整列のために qsort 関数に渡される、二つの要素の順番を決める関数

extensibility
拡張性; 拡張しやすいかどうかのプログラムの書き方の評価基準

scope
有効範囲; 変数などが使える範囲、例えば関数や複文

standard output
標準出力; プログラムに前もって用意された出力、画面やリダイレクトによってファイルへ

conditional compilation
条件付きコンパイル; プリプロセッサによって、プログラムの一部だけがコンパイルされること

pass by value
値渡し; 関数に参照ではなく引数の値を渡し、関数内の引数の変更は関数の外側に影響無し

入出力 / Input and Output (20 点)

下記のプログラムは学生のデータをテキストファイルからバイナリファイルへコピーする。 テキストファイルは学生毎にちょうど三行となっていて、不完全な学生データはない。 バイナリファイルへの書き込みは大きさ GROUPSIZE の組で行われる。プログラムを完成しなさい。 / The program below copies student data from a text file to a binary file. The text file contains exactly three lines per student; there is no incomplete data. Writing to the binary file is done in groups of GROUPSIZE students. Complete the program.

#include <stdio.h>
#include <string.h  >
#include <stdlib.h>
#define GROUPSIZE 10

typedef struct {
    int  age;
    char name[40];
    char department[40];
} Student;

void get_line (char *buffer, int size, FILE *filep)
{
    fgets(buffer, size, filep      );
    buffer[strlen(buffer) - 1    ] = '\0';           // clear newline character
}

FILE *open_file (char *prompt, char* mode)
{
    char file_name[50];
    FILE *fp;

    printf("%s", prompt);
    get_line(file_name, 50, stdin);

    if ((fp = fopen(file_name, mode)) == NULL) {
        fprintf(stderr, "Cannot open file %s with mode %s.\n", file_name, mode);
        exit(1);
    }
    return fp;
}

int main (void)
{
    FILE *text_fp, *binary_fp;
    Student group[10];
    int i = 0;

    text_fp   = open_file("Name of text file (for input): ",    "r"  );
    binary_fp = open_file("Name of binary file (for output): ", "wb"  );

    while (1) {
        if (fscanf(text_fp, "%d", &group[i].age) != 1)     // read age
            break;
        getc(text_fp);
        get_line(group[i].name   , 40, text_fp);              // read name
        get_line(group[i].department    , 40, text_fp);        // read department
        if (++i >= 10) {
            fwrite(group  , sizeof(Student)   , GROUPSIZE, binary_fp); // write group
            i = 0;
        }
    }
    fwrite(group  , sizeof(Student)   , i  , binary_fp); // write incomplete group

    fclose(text_fp)    ;
    fclose(binary_fp)    ;
    return 0;
}

ライブラリ関数の設計と実装
Design and Implementation of a Library Function (合計 19 点)

unsigned int (0 以上の整数) の配列の最大値を求めるライブラリ関数 maxint を設計、実装しなさい。
Designing and implement a library function maxint that finds the maximum in an array of unsigned ints.

関数の宣言 / Function Declaration (4 点)

unsigned int maxint (unsigned int array[], int length);

関数の実装 / Function Implementation (10 点)

 
unsigned int
maxint (unsigned int array[], int length)
{
    unsigned int max = 0;
    int i;

    for (i=0; i<length; i++)
        if (max < array[i])
            max = array[i];

    return max;
}
 

特殊なケースへの対応 / Handling of Special Case (3 点)

書いた実装で、長さ 0 の配列への対応とその理由を説明しなさい。
Describe how your implementation handles the case of an array of length 0, and the reason for this solution.

unsigned int の最低の値は 0 である。それが「最大」の演算の単位元なので、配列の長さが 0 の場合、それを返す。

拡張子 / Extensions (2 点)

宣言と実装を書いた各ファイルの拡張子を書きなさい。
Write the extensions of the files where you place the declaration and the implementation.

宣言 / Declaration: .h    実装 / Implementation: .c   

授業へのコメント (合計 6 点)

この授業で一番分かりにくかったことを書きなさい。(具体的に書いてあれば内容にかかわらず 3 点)

@@@@

この授業で一番勉強になったことを簡単に説明しなさい。(具体的に書いてあれば内容にかかわらず 3 点)

@@@@

関数 / Functions (合計 18 点)

三角数 / Triangular Numbers (2 点)

三角数 T_n は 1 から n までの総和である。 関数 calcTri は T_n を計算する。 The triangular number T_n is the sum of the integers from 1 to n. The function calcTri calculates T_n. 例/Example: T₅ = 1+2+3+4+5 = 15.

int calcTri(int n) {
	int i, sum = 0;
	for (i = 1; i <= n; i++)
		sum += i;   
	return sum;
}

最大三角数 / Maximum Triangular Number (4 点)

関数 maxTri は自然数 m (m≧1) が与えられた時，T_n ≦ m を満たす最大の n を返す． / The function maxTri, for any given natural number m (m≧1), returns the largest number n so that T_n ≦ m. 例/Example: maxTri(16) → 5

int   maxTri(int m) {
	int i = 0, ans = 0;
	while (ans <= m  ) {
		i++;
		ans = calcTri(i)   ;
	}
	return i-1  ;
}

三角数の定理 / Triangular Number Theorem (12 点)

あらゆる自然数は3個以下の三角数の和で表せることが証明されている． 次のプログラムは，ある数を入力しその数を3つ以下の三角数で分割して表示するsearchTri関数である． It has been prooven that any natural number can be represented as a sum of 3 or less triangular numbers. The following function searchTri calculates and displays a partition of the input number into 3 or less triangular numbers.

実行例 /
Execution Example
input:  26
answer: 1 (1)
answer: 10 (4)
answer: 15 (5)

#include <stdio.h>
int searchTri(int num, int count  ) {
	int ans, triNum = maxTri(num)   ;
	if (count == 0) return 0;	// 失敗 / failure
	while (1) {
		ans = num - calcTri(triNum)   ;
		if (ans == 0) 	break;	// 成功 / success
		if (searchTri(ans  , count - 1  ) == 0) {
			triNum--   ;
			if (triNum == 0)  return 0;  // 失敗 / failure
		}
		else break  ;  // 成功 / success
	}
	printf("answer: %d   (%d)\n", calcTri(triNum  ), triNum);
	return 1;	// 成功 / success
}

int main(void) {
	int num;
	printf("input:  ");  scanf("%d", &num);
	searchTri(num, 3);
	return 0;
}

Segmentation Fault の理由 / Reasons for Segmentation Fault (14 点)

注意しないと C では segmentation fault が簡単に起こりうる。 下記のそれぞれのプログラム断片について、なぜ segmentation fault が起こりうるのかを説明しなさい。
Without care, in C, segmentation faults can easily occur. For each of the program fragments below, explain the reason for a possible segmentation fault.
(「...」 は (間違いを含まない) 省略されたコードを表す / ... indicates some additional (error-free) code)

  int a[20];
  a[1000] = 40;

  char word[10];
  word[0] = 'a';
  printf("%s", word);

  int *pi = NULL;
  int i = *pi;

  char *function(void) { char text[500];
                        ... return text; }
  ...
  char *my_text = function();
  ...
  my_text[400] = 'q';

  int *pt;
  ...
  free (pt);
  ...
  pt[5] = 42;

  int *large_array;
  large_array = (...)malloc(1000000000);
  large_array[100000] = 15;

  char input[100];
  gets(input);

  char *string;
  strcpy(string, "hello");

C++ (合計 15 点)

クラスの宣言 / Class Declaration (11 点)

下記のプログラムは、ポケモンのタイプ (一部省略) と身長 (単位： m) を取得し、表示する。空欄 (一部順不同) を埋めることで Pokemon クラスの宣言を完成させなさい。
The program below obtains and displays the type (partial list) and height (unit: m) of Pokémons. Complete the declaration of the Pokemon class below (to some extent, the order is irrelevant).

#include <stdio.h>

typedef enum { Fairy, Fire, Steel, Electric, Ice, Rock, Water } pokeType;

class Pokemon {
  public:
    Pokemon(pokeType inType, double inHeight);   
    int    getType(void);                       
    double getHeight(void);                     
  private:
    pokeType type;     
    double   height;   
};

Pokemon::Pokemon(pokeType inType, double inHeight) {
    type  = inType;  height = inHeight;
}

double Pokemon::getHeight(void) {  return height; }
int Pokemon::getType(void) {  return type; }

int main(void)
{
    Pokemon myPokemon(Electric, 0.4);
    printf("Type: %d\n",    myPokemon.getType()  );
    printf("Height: %lf\n", myPokemon.getHeight());
    return 0;
}

クラスの使用 / Class Use (4 点)

下記のプログラムで各 printf が出力される値をコメントのところに書きなさい。 Write the value output by each printf call after the comment.

#include <stdio.h>

class Data {
  public:
    Data()             { x = 15; }
    void set_x(int xx) { x = xx; }
    int get_x(void)    { return x; }
    int y = 21;
  private:
    int x;
};

int main(void)
{
    int d = 10;  Data myData;
    int b = myData.get_x();  myData.set_x(81);
    int c = myData.y,  a = myData.get_x();

    printf("%d\n", a);   // 81
    printf("%d\n", b);   // 15
    printf("%d\n", c);   // 21
    printf("%d\n", d);   // 10
    return 0;
}

ポインタ / Pointers (合計 22 点)

定義と代入 / Definitions and Assignments (6 点)

説明に対応するコードを書きなさい。 / Write the code corresponding to the explanations.

int 型のポインタ pt / a pointer pt of type int: int *pt;     

double 型のポインタの長さ 50 の配列 ds /
an array ds of size 50 of pointers to double: double *ds[50];    

80 バイトの入力用バッファ b / an input buffer b of 80 bytes: char b[80];    

float 型のポインタ xp へのfloat 型の変数 x のアドレスの代入
assign the address of the variable x of type float to xp (pointer to float): xp = &x;    

int 型のポインタ lp へのint型の配列 ar の先頭アドレスの代入
assign the initial address of the array of ints ar to lp (pointer to int): lp = ar;    

演算子 / Operators (4 点)

次の表を埋めなさい。機能については簡潔に説明しなさい。/ Fill in the table below. For functionality, provide short explanations.

動的なメモリ確保 / Dynamic Memory Acquisition (8 点)

int 型のポインタ p を宣言し、int 200 個分のメモリを動的に確保するとともに、 その先頭アドレスを p に格納するプログラム断片を書きなさい。 ただしエラー処理もすること。
Write a program fragment that defines a pointer p of type int, dynamically acquires memory for 200 ints, and assigns this memory's initial address to p. Make sure to include erro handling code.

int *p;
if (!(p = (int *)malloc(sizeof(int)*200))) {
	fprintf(stderr, "Not enough memory!\n");
	exit(1);
}

ライブラリ関数 / Library Functions (4 点)

動的メモリに関する標準ライブラリ関数のうち小問 9.3 と異なるものを二つ挙げ、機能を簡潔に説明しなさい。
Mention two library functions related to dynamic memory that you have not used in subproblem 10.3, and provide short explanations of their functionality.

realloc: メモリの動的再割当て (族で言うメモリの引っ越し)

free: 動的に確保したメモリの開放