2 部データ構造とアルゴリズムI レポート課題

本講義では 2 通のレポートで評価します。レポートは A4 の紙を縦に使い、適宜表紙を付けて提出すること。またプログラムは C 言語で作成しなさい。

変更履歴

2017/5/25: 課題1初出
2017/6/15: 課題2初出
2017/7/24: 課題2-4プログラム追加

課題1
課題2

課題2

レポート締切日: 2017年7月26日(水)20:00
提出先: 2 号館 3F レポートボックス

遅れレポートは受けとりません。ご注意下さい。

問題

引き続き、以下の複素数を扱う構造体に加え、複素数の線形リストを作る構造体も定義する。


typedef struct {
  double real;
  double imaginary;
} FUKUSOSU;

typedef struct node {
  struct node* next;
  FUKUSOSU kazu;
} NODE;

なお、この構造体の定義と、課題1で作成したいくつかの関数と、これから作成する関数のプロトタイプ宣言を定義する fukusosu2.h は後述する。

課題1で作成した関数も一部使用する。レポート作成においては、課題1で作成した関数を使用する際には、課題1で作成したことだけを述べ、プログラムの説明は省略してよい。

課題2-1

FUKUSOSU型の複素数を引数とし、絶対値を double 型で返す関数 double iabs(FUKUSOSU a) を作成しなさい。

そして、テストプログラム1と結合して正しく動作していることを確認しなさい。

テストプログラム2-1


#include <stdio.h>
#include "fukusosu2.h"

int main(void){
  FUKUSOSU f[]={{1.0,0},{0,-2.0},{-3.0,4.0},{5.0,-6.0},{0.0,0.0}};
  int i;

  for(i=0; i<(sizeof f)/(sizeof f[0]); i++){
    printFukusosu(f[i]);
    printf("の絶対値は %f\n", iabs(f[i]));
  }
  return 0;
}

出力例2-1

1.000000の絶対値は 1.000000
-2.000000iの絶対値は 2.000000
-3.000000+4.000000iの絶対値は 5.000000
5.000000-6.000000iの絶対値は 7.810250
0.0の絶対値は 0.000000

課題 2-2

複素数FUKUSOSUの線形リストが先頭のNODEのポインタで与えられているとき、課題1で作成した printFukusosu を利用して、すべての要素を表示する void show(NODE* p); を作成しなさい。なお、線形リストの末端は next メンバには NULL が入り、その kazu メンバは無視するとします。

そして、下記のテストプログラム2-2と結合して、正しく動作することを確かめなさい。

テストプログラム2


#include <stdio.h>
#include "fukusosu2.h"

int main(void){
  NODE n0 = {NULL};
  NODE n1 = {&n0,{1.0,0}};
  NODE n2 = {&n1,{0,-2.0}};
  NODE n3 = {&n2,{-3.0,0}};
  NODE n4 = {&n3,{5.0,-6.0}};
  NODE n5 = {&n4,{0.0,0.0}};

  show(&n5);
  printf("\n");
  return 0;
}

出力例2-2

[0.0, 5.000000-6.000000i, -3.000000, -2.000000i, 1.000000]

課題 2-3

動的に空の NODE を作る NODE* newnode(void) を作りなさい。これは、メモリが動的に確保できなかった場合は NULL を返します。また、メモリが確保できたら next メンバには NULL を入れます。

さらにこの newnode 関数を利用し、線形リストの最後に複素数を追加する NODE* add(NODE* p, FUKUSOSU a) を作りなさい。線形リストは先頭のNODEのポインタを受けとるとします。なお、最小の線形リストは空のNODE一つであると仮定してください。また、関数の戻り値は、メモリを正常に確保できたかどうかを示すため、メモリが確保できなかったときは NULL を返し、そうでないときは NULL 以外を返すようにしてください。

そして、下記のテストプログラム2-3と結合して、正しく動作することを確かめなさい。

テストプログラム2-3


#include <stdio.h>
#include "fukusosu2.h"

int main(void){
  NODE* list = newnode();
  FUKUSOSU f[]={{1.0,0},{0,-2.0},{-3.0,4.0},{5.0,-6.0},{0.0,0.0}};
  int i;

  for(i=0; i<(sizeof f)/(sizeof f[0]); i++){
    show(list);
    printf("\n");
    add(list,f[i]);
  } 
  show(list);
  printf("\n");
  return 0;
}

出力例2-3

[]
[1.000000]
[1.000000, -2.000000i]
[1.000000, -2.000000i, -3.000000+4.000000i]
[1.000000, -2.000000i, -3.000000+4.000000i, 5.000000-6.000000i]
[1.000000, -2.000000i, -3.000000+4.000000i, 5.000000-6.000000i, 0.0]

課題 2-4

線形リストとdouble 型の値を受け取り、線形リスト中の複素数のうち、絶対値が受け取った double 型の値より小さい最初の NODE のポインタを返す関数 NODE* lessabs(NODE* p, double t) を作りなさい。線形リストは先頭 NODE のポインタとして受け取るとします。また、目的の複素数が見つからなかった時は NULL を返します。

そして、下記のテストプログラム2-4と結合して、正しく動作することを確かめなさい。

テストプログラム2-4


#include <stdio.h>
#include "fukusosu2.h"

int main(void){
  NODE n0 = {NULL};
  NODE n1 = {&n0,{1.0,0}};
  NODE n2 = {&n1,{0,-2.0}};
  NODE n3 = {&n2,{-3.0,0}};
  NODE n4 = {&n3,{5.0,-6.0}};
  NODE n5 = {&n4,{-1.0,1.0}};
  NODE n6 = {&n5,{0.0,0.0}};
  NODE *p;
  
  for(p=&n6; (p=lessabs(p,3))!=NULL; p=p->next){
    printFukusosu(p->kazu);
    printf("\n");
  }
  return 0;
}

出力例4

0.0
-1.000000+1.000000i
-2.000000i
1.000000

テストプログラム2-4-2

なお、条件をうまく設定していないため、テストプログラム2-4では正常に動作しても、一般のデータではうまく動作しないようにプログラムを組めることが判明した。テストが通るのは最低限であるが、テストが通ることではプログラムが正常であることは必ずしも保証できないため、もう一度、正常に動作するか確認すると良い。さらに、下記のテストプログラムでも正常に動作するか確かめると良い。なお、確かめていなくても、レポート採点では減点をしないが、テストプログラム2-4は通過しても、一般のデータで正常に動作しないプログラムは減点の対象となりうる。


#include <stdio.h>
#include "fukusosu.h"

  NODE n10 = {NULL};
  NODE n11 = {&n10,{1.0,0}};
  NODE n12 = {&n11,{0,-2.0}};
  NODE n13 = {&n12,{-3.0,0}};
  NODE n14 = {&n13,{5.0,-6.0}};
  NODE n15 = {&n14,{-1.0,1.0}};
  NODE n16 = {&n15,{0.0,0.0}};

  NODE n20 = {NULL};
  NODE n21 = {&n20,{5.0,0}};
  NODE n22 = {&n21,{0,-7.0}};
  NODE n23 = {&n22,{-3.0,0}};
  NODE n24 = {&n23,{5.0,-6.0}};
  NODE n25 = {&n24,{-1.0,1.0}};
  NODE n26 = {&n25,{0.0,8.0}};

void printValue(NODE* root){
  NODE* p;
  for(p=root; (p=lessabs(p,3))!=NULL; p=p->next){
    printFukusosu(p->kazu);
    printf("\n");
  }
}
int main(void){
  printValue(&n16);
  printf("---------------\n");
  printValue(&n26);
  return 0;
}

出力例4-2

0.0
-1.000000+1.000000i
-2.000000i
1.000000
---------------
-1.000000+1.000000i

fukusosu2.hについて

fukusosu2.h は次のように上記の構造体と作るべき関数のすべてのプロトタイプ宣言が入っているファイルとする。


typedef struct {
  double real;
  double imaginary;
} FUKUSOSU;

typedef struct node {
  struct node* next;
  FUKUSOSU kazu;
} NODE ;

void printFukusosu(FUKUSOSU f);
FUKUSOSU mult(FUKUSOSU a, FUKUSOSU b);
FUKUSOSU kyoyaku(FUKUSOSU a);
/* FUKUSOSU div(FUKUSOSU a, FUKUSOSU b); */
double iabs(FUKUSOSU a);
void show(NODE* p);
NODE* newnode(void);
NODE* add(NODE* p, FUKUSOSU a);
NODE* lessabs(NODE* p, double t);

課題1

レポート締切日: 2017年6月14日(水)20:00
提出先: 2 号館 3F レポートボックス

解答法として、分割コンパイルによる別ファイルにプログラムを書く方法と、下記のテストプログラムに関数を追記する方法の二通りがあるがどちらでも良い。プログラムの解説は、自分で作成した関数について行うこと。こちらで提供したテストプログラムの説明は基本的には不要である。但し、自分で作成した関数を説明するのに必要な内容には言及すること。

なお、遅れレポートは教員に直接提出してください。遅れた方が有利にならない範囲内で採点します。

問題

複素数を取り扱う構造体として次を用意した。


typedef struct {
  double real;
  double imaginary;
} FUKUSOSU;

なお、fukusosu.h は後述する。

課題1-1

FUKUSOSU 型を受け取り、「実部 + 虚部i」と表示する void printFukusosu(FUKUSOSU f) 作りなさい。

そして、テストプログラム1-1と結合して正しく動作していることを確認しなさい。

テストプログラム1-1


#include <stdio.h>
#include "fukusosu.h"

int main(void){
  FUKUSOSU f[]={{1.0,0},{0,-2.0},{-3.0,4.0},{5.0,-6.0},{0.0,0.0}};
  int i;

  for(i=0; i<(sizeof f)/(sizeof f[0]); i++){
    printFukusosu(f[i]);
    printf("\n");
  }
  return 0;
}

出力例1-1

1.000000
-2.000000i
-3.000000+4.000000i
5.000000-6.000000i
0.0

注意

出力において、空白の有無、有効数字の桁数や小数点以下の不要な 0 の個数などは、出力例1のようにならなくても問題ない。一方、不要な+(プラス)記号や、実部、虚部の不要な0は出力してはいけない。

課題 1-2

FUKUSOSU 型の値を二つ受け取り、その積を返す関数 FUKUSOSU mult(FUKUSOSU a, FUKUSOSU b) を作りなさい。

そして、下記のテストプログラム1-2と結合して、正しく動作することを確かめなさい。

テストプログラム1-2


#include <stdio.h>
#include "fukusosu.h"

int main(void){
  FUKUSOSU f[]={{1.0,0},{0,-2.0},{-3.0,0},{5.0,-6.0},{0.0,0.0}};
  FUKUSOSU g[]={{2.0,0},{0,-5.0},{0,4.0},{-2.0,1.0},{0.0,0.0}};
  int i;

  for(i=0; i<(sizeof f)/(sizeof f[0]); i++){
    printf("(");
    printFukusosu(f[i]);
    printf(") * (");
    printFukusosu(g[i]);
    printf(") = ");
    printFukusosu(mult(f[i],g[i]));
    printf("\n");
  }
  return 0;
}

出力例1-2

(1.000000) * (2.000000) = 2.000000
(-2.000000i) * (-5.000000i) = -10.000000
(-3.000000) * (4.000000i) = -12.000000i
(5.000000-6.000000i) * (-2.000000+1.000000i) = -4.000000+17.000000i
(0.0) * (0.0) = 0.0

課題 1-3

FUKUSOSU 型を受け取り、共役複素数を返す関数 FUKUSOSU kyoyaku(FUKUSOSU a) を作りなさい。

そして、下記のテストプログラム1-3と結合して、正しく動作することを確かめなさい。

テストプログラム1-3


#include <stdio.h>
#include "fukusosu.h"

int main(void){
  FUKUSOSU f[]={{1.0,0},{0,-2.0},{-3.0,4.0},{5.0,-6.0},{0.0,0.0}};
  int i;

  for(i=0; i<(sizeof f)/(sizeof f[0]); i++){
    printFukusosu(f[i]);
    printf("の共役は");
    printFukusosu(kyoyaku(f[i]));
    printf("\n");
  }
  return 0;
}

出力例1-3

1.000000の共役は1.000000
-2.000000iの共役は2.000000i
-3.000000+4.000000iの共役は-3.000000-4.000000i
5.000000-6.000000iの共役は5.000000+6.000000i
0.0の共役は0.0

課題 1-4

FUKUSOSU 型の値を二つ受け取り、その商を返す関数 FUKUSOSU div(FUKUSOSU a, FUKUSOSU b) を作りなさい。なお、以前の課題で作成した関数を呼び出して使用してよい。

そして、下記のテストプログラム1-4と結合して、正しく動作することを確かめなさい。

テストプログラム1-4


#include <stdio.h>
#include "fukusosu.h"

int main(void){
  FUKUSOSU f[]={{1.0,0},{0,-2.0},{-3.0,0},{5.0,-6.0},{0.0,0.0}};
  FUKUSOSU g[]={{2.0,0},{0,-5.0},{0,4.0},{-2.0,1.0},{0.0,1.0}};
  int i;

  for(i=0; i<(sizeof f)/(sizeof f[0]); i++){
    printf("(");
    printFukusosu(f[i]);
    printf(") / (");
printFukusosu(g[i]);
    printf(") = ");
    printFukusosu(div(f[i],g[i]));
    printf("\n");
  }
  return 0;
}

出力例1-4

(1.000000) / (2.000000) = 0.500000
(-2.000000i) / (-5.000000i) = 0.400000
(-3.000000) / (4.000000i) = 0.750000i
(5.000000-6.000000i) / (-2.000000+1.000000i) = -3.200000+1.400000i
(0.0) / (1.000000i) = 0.0

fukusosu.hについて

fukusosu.h は次のように上記の構造体と作るべき関数のすべてのプロトタイプ宣言が入っているファイルとする。


typedef struct {
  double real;
  double imaginary;
} FUKUSOSU;

void printFukusosu(FUKUSOSU f);
FUKUSOSU mult(FUKUSOSU a, FUKUSOSU b);
FUKUSOSU kyoyaku(FUKUSOSU a);
FUKUSOSU div(FUKUSOSU a, FUKUSOSU b);

レポート作成上の注意

レポートはグラフの表現など特殊な事情がない限り、必ず白黒で作成すること。
プログラミングのレポートでは必ずプログラムの説明をすること。その時に、一行一行を日本語に直訳するのではなく、プログラムを機能毎に区分し、機能の実現方法を説明すること。プログラムに一行ずつコメントを入れてもプログラムの説明とは見なしません。
「問題を解きなさい」という問に対して「解きました。合ってました」は正解ではありません。「プログラムを作りなさい」という問題については、作成の手順の説明をすること。「テストしなさい」という問題についてはテストの手法、合否判定の基準、結果の検討などを説明しなさい。
プログラムが短くて説明がしづらい場合は、ポインタなどの関係を図示するなどして工夫してください。
出力例は個々に異なりますので、手計算であらかじめ正しい値の求め方を示し、値を提示してテストの合否を判定しなさい。
レポートは手書きでも良いですが、プログラムの実行結果だけは必ずコンピュータの出力の印刷にして下さい。
考察は必ず書いて下さい。ネタがない人は以下を参考にして下さい。
- 途中失敗を経験した場合、その失敗した内容となぜ失敗したのか
- ポインタ、関数、配列などの仕組みについて、新しく分かったこと

坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科