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

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

課題1

レポート締切日: 2010年6月23日(木)20:00
提出先: 7 号館 3F レポートボックス

次の 4 つの課題を合わせて行い、報告しなさい。

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

行列の演算を行うパッケージを作成したい。 そのため、次のような構造体を作成した。 


typedef struct {
  int row;
  int column;
  double **array;
} MATIX;

また、2×2の正方行列を作成する関数を次のように作成した。 


#include <stdlib.h>
MATRIX* create2x2(double a, double b, double c, double d){
  MATRIX *m;
  if((m= malloc(sizeof(MATRIX)))==NULL){
    return NULL;
  }
  m->row=2;
  m->column=2;
  if((m->array= malloc(sizeof(double*)*2))==NULL){
    free(m);
    return NULL;
  }
  if((m->array[0]=malloc(sizeof(double)*2))==NULL){
    free(m->array);
    free(m);
    return NULL;
  }
  if((m->array[1]=malloc(sizeof(double)*2))==NULL){
    free(m->array[0]);
    free(m->array);
    free(m);
    return NULL;
  }
  m->array[0][0]=a;
  m->array[0][1]=b;
  m->array[1][0]=c;
  m->array[1][1]=d;
  return m;
}

さらに、作成した行列を free する関数 freeMatrix を作成した。 


void freeMatrix(MATRIX* m){
  int i;
  for(i=0;i<m->row;i++){
    free(m->array[i]);
  }
  free(m->array);
  free(m);
}

課題1-1

行列の表示を行う関数 void printMatrix(MATRIX* m)を作成しなさい。 但し、数値を横に並べる場合、空白で区切らず、タブ記号 '\t' で区切りなさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。

テストプログラム


#define G (999)
/* 学籍番号の下3桁を記入する。先頭の 0 は省く */
MATRIX* create2x2(double a, double b, double c, double d);
void printMatrix(MATRIX* m);
int main(void){
  MATRIX* a;
  if((a = create2x2(G+1,G+2,G+3,G+4))==NULL){
    return -1;
  }
  printMatrix(a);
  freeMatrix(a);
  return 0;
}
出力例
1000.000000	1001.000000	
1002.000000	1003.000000

課題 1-2

3×3の正方行列を作成する MATRIX* create3x3(double a,double b,double c,double d,double e,double f,double g,double h,double i) を作成しなさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。 


#define G (999)
/* 学籍番号の下3桁を記入する。先頭の 0 は省く */
void printMatrix(MATRIX* m);
MATRIX* create3x3(double a, double b, double c, double d,double e,double f, double g,double h, double i);
int main(void){
  MATRIX* a;
  MATRIX* b;
  if((a = create2x2(G+1,G+2,G+3,G+4))==NULL){
    return -1;
  }
  if((b= create3x3(G+1,2,3,4,5,6,7,8,9))==NULL){
    printMatrix(a);
    return -1;
  }
  printMatrix(a);
  printMatrix(b);
  freeMatrix(b);
  freeMatrix(a);
  return 0;
}
出力例
1000.000000	1001.000000	
1002.000000	1003.000000	
1000.000000	2.000000	3.000000	
4.000000	5.000000	6.000000	
7.000000	8.000000	9.000000

課題 1-3

1行2列のベクトルと、 2行1列のベクトルを作る関数 MATRIX* create1x2(double a, double b) と MATRIX* create2x1(double a, double b) を作成しなさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。 


#define G (999)
/* 学籍番号の下3桁を記入する。先頭の 0 は省く */

void printMatrix(MATRIX* m);
MATRIX* create1x2(double a, double b);
MATRIX* create2x1(double a, double b);
int main(void){
  MATRIX* a;
  MATRIX* b;
  if((a = create1x2(G+1,G+2))==NULL){
    return -1;
  }
  if((b= create2x1(G+3,G+4))==NULL){
    printMatrix(a);
    return -1;
  }
  printMatrix(a);
  printMatrix(b);
  freeMatrix(b);
  freeMatrix(a);
  return 0;
}
出力例
1000.000000	1001.000000	
1002.000000	
1003.000000

課題 1-4

行列の積を求める関数 MATRIX* multiply(MATRIX* a, MATRIX* b) を作成しなさい。 なお、行列の型が合わずに積を求められない場合は Type mismatch という表示を標準エラー出力に出し、 NULL を返しなさい。

そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。

テストプログラム


#define G (999)
/* 学籍番号の下3桁を記入する。先頭の 0 は省く */
MATRIX* create1x2(double a, double b);
MATRIX* create2x1(double a, double b);
MATRIX* create2x2(double a, double b, double c, double d);
MATRIX* multiply(MATRIX* a, MATRIX* b);
void printMatrix(MATRIX* m);
int main(void){
  MATRIX *a;
  MATRIX *b;
  MATRIX *c;
  MATRIX *x;
  MATRIX *y;
  if((a = create1x2(G+1,2))==NULL){
    return -1;
  }
  if((b = create2x1(3,4))==NULL){
    freeMatrix(a);
    return -1;
  }
  if((c = create2x2(1,2,3,4))==NULL){
    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  if((x=multiply(a,a))!=NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  if((x=multiply(a,b))==NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  printMatrix(x);
  freeMatrix(x);
  if((x=multiply(b,b))!=NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  if((x=multiply(b,a))==NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  printMatrix(x);
  freeMatrix(x);
  if((x=multiply(c,a))!=NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  if((x=multiply(a,c))==NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  printMatrix(x);
  freeMatrix(x);
  if((x=multiply(b,c))!=NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  if((x=multiply(c,b))==NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  printMatrix(x);
  freeMatrix(x);
  if((x=multiply(c,c))==NULL){
    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  if((y=multiply(x,c))==NULL){
    freeMatrix(x);    freeMatrix(c);    freeMatrix(b);    freeMatrix(a);
    return -1;
  }
  printMatrix(y);
  freeMatrix(y);  freeMatrix(x);  freeMatrix(c);  freeMatrix(b);  freeMatrix(a);
  return 0;
}
出力例
Type mismatch
3008.000000	
Type mismatch
3000.000000	6.000000	
4000.000000	8.000000	
Type mismatch
1006.000000	2008.000000	
Type mismatch
11.000000	
25.000000	
37.000000	54.000000	
81.000000	118.000000

レポート作成上の注意

  1. レポートはグラフの表現など特殊な事情がない限り、必ず白黒で作成する こと。
  2. プログラミングのレポートでは必ずプログラムの説明をすること。その時 に、一行一行を日本語に直訳するのではなく、プログラムを機能毎に区分し、 機能の実現方法を説明すること。 プログラムに一行ずつコメントを入れてもプログラムの説明とは見なしません。
  3. 「問題を解きなさい」という問に対して「解きました。合ってました」は 正解ではありません。 「プログラムを作りなさい」という問題については、作成の手順の説明をする こと。 「テストしなさい」という問題についてはテストの手法、合否判定の基準、結 果の検討などを説明しなさい。
  4. プログラムが短くて説明がしづらい場合は、ポインタなどの関係を図示す るなどして工夫してください。
  5. 出力例は個々に異なりますので、手計算であらかじめ正しい値の求め方を 示し、値を提示してテストの合否を判定しなさい。
  6. レポートは手書きでも良いですが、プログラムの実行結果だけは必ずコン ピュータの出力の印刷にして下さい。
  7. 考察は必ず書いて下さい。ネタがない人は以下を参考にして下さい。
坂本直志 <[email protected]>
東京電機大学工学部情報通信工学科