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

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

変更履歴

2018/5/31
課題1初出
2018/5/31
課題1テストプログラムをポインタ化
2018/6/14
課題1 const.c の数値の変更

範囲外の場合の年の初期値を変更した。これにより、範囲外で年の 計算式を変える必要が無くなった。 同時に、実行例も差し替えた。 但し、変更前の値に対して作成したプログラムを提出しても同等に評価する。

2018/7/4
課題2初出
2018/7/5
課題1,2の提出期限、条件の付記

課題2

レポート締切日: 2018年7月27日(金)13:00
提出先: 2 号館 3F レポートボックス

なお、遅れレポートは受け取らない

問題

和暦のリストを考えるために以下の構造体を考える。


#include "wareki.h"    
typedef struct wl {
  WAREKI wareki;
  struct wl* next;
} WAREKILIST;

なお、この構造体の定義と、作成する関数のプロトタイプ宣言を定義するヘッ ダファイル wareki2.h は後述する。

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

課題2-1(本来課題1の範疇)

WAREKI 型の構造体を引数として、西暦に変換し、 SEIREKI 型として返す SEIREKI toseireki(WAREKI w); を作成しなさい。 なお、「平成元年1月1日」などありえない日付に関しては、どのように動作し ても良い。

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

テストプログラム2-1


#include <stdio.h>
#include <stdlib.h>
#include "wareki.h"
#include "wareki2.h"

int main(void){
  WAREKI w[]={{3,4,5,1},{4,5,6,2},{5,6,7,3},{0}};
  WAREKI *i;
  for(i=w;i->y!=0;i++){
    printwareki(*i);
    printf("->");
    printseireki(toseireki(*i));
    printf("->");
    printwareki(towareki(toseireki(*i)));
    printf("\n");
  }
  return 0;
}
出力例2-1
大正3年4月5日->西暦1914年4月5日->大正3年4月5日
昭和4年5月6日->西暦1929年5月6日->昭和4年5月6日
平成5年6月7日->西暦1993年6月7日->平成5年6月7日

課題2-2

WAREKILIST の番地を受け取り、線形リストとして和暦を順に表示する void printwarekilist(WAREKILIST* w, char* sep) を作成しなさい。 ただし、次の条件を満たすものとする。

  1. wareki フィールドを表示する
  2. sep の指す文字列をwareki同士の間の区切りとして表示する
  3. next に NULL が入っていれば番兵のノードとし、そのノードの内容は 表示せず、表示を終了する。

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

テストプログラム2-2


#include <stdio.h>
#include <stdlib.h>
#include "wareki.h"
#include "warekilist.h"

int main(void){
  char sep[]="--";
  WAREKILIST w0={0};
  WAREKILIST w1={3,4,5,1};
  WAREKILIST w2={4,5,6,2};
  WAREKILIST w3={5,6,7,3};
  w0.next=NULL;
  w1.next=&w0;
  w2.next=&w1;
  w3.next=&w2;
  printwarekilist(&w0,sep);
  printf("\n");
  printwarekilist(&w1,sep);
  printf("\n");
  printwarekilist(&w2,sep);
  printf("\n");
  printwarekilist(&w3,sep);
  printf("\n");
  return 0;
}
出力例2-2

大正3年4月5日
昭和4年5月6日--大正3年4月5日
平成5年6月7日--昭和4年5月6日--大正3年4月5日

先頭は空行なのに注意

課題2-3

以下の3つの関数を作りなさい。

WAREKILIST* newnode(void)
WAREKILIST 型の領域を一つ作成する。 領域を確保できなかった場合は NULL を返す
WAREKILIST* add(WAREKILIST* p, WAREKI w)
WAREKILIST のポインターと WAREKI の値を受け取り、線形リストのポイン ターの指す位置に受け取った値を追加する。 なお、戻り値は追加した値の入っている WAREKILIST 型の領域の番地とする。 追加できなかった場合は NULL を返す。
void freelist(WAREKILIST* p)
WAREKILISTのポインターを受け取り、ポインターの指している線形リスト すべての領域を開放する。

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

テストプログラム2-3


#include <stdio.h>
#include <stdlib.h>
#include "wareki.h"
#include "wareki2.h"

int main(void){
  char sep[]="--";
  WAREKILIST* p;
  WAREKILIST* q;
  WAREKI w[]={{3,4,5,1},{4,5,6,2},{5,6,7,3},{0}};
  WAREKI *i;
  if((p=newnode())==NULL) return 1;
  printwarekilist(p,sep);
  printf("\n");
  for(i=w;i->y!=0;i++){
    if((q=add(p,*i))==NULL){
      freelist(p);
      return 1;
    }
    printf("追加項目:");
    printwareki(q->wareki);
    printf(" ");
    printwarekilist(p,sep);
    printf("\n");
  }
  freelist(p);
  return 0;
}
出力例2-3

追加項目:大正3年4月5日 大正3年4月5日
追加項目:昭和4年5月6日 昭和4年5月6日--大正3年4月5日
追加項目:平成5年6月7日 平成5年6月7日--昭和4年5月6日--大正3年4月5日

先頭は空行なのに注意

課題2-4

和暦の線形リストのポインターを受け取り、 和暦と、その間の日数を順に表示する void printnissulist(WAREKILIST* w, char* sep) を作成しなさい。 ただし、次の条件を満たすものとする。

  1. sep の指す文字列をwareki同士の間の区切りとして表示する
  2. 表示の形式は「和暦 sep 日数 sep 和暦 sep 日数 sep 和暦...」とな るようにする
  3. next に NULL が入っていれば番兵のノードとし、そのノードの内容は 表示せず、表示を終了する

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

テストプログラム2-4


#include <stdio.h>
#include <stdlib.h>
#include "wareki.h"
#include "wareki2.h"

int main(void){
  char sep[]=" -- ";
  WAREKI w[]={{3,4,5,1},{4,5,6,2},{5,6,7,3},{0}};
  WAREKI *i;
  WAREKILIST* p;
  WAREKILIST* q;
  if((p=newnode())==NULL) return 1;
  printwarekilist(p,sep);
  printf("\n");
  for(i=w;i->y!=0;i++){
    if((q=add(p,*i))==NULL){
      freelist(p);
      return 1;
    }
    printf("追加項目:");
    printwareki(q->wareki);
    printf(" ");
    printnissulist(p,sep);
    printf("\n");
  }
  freelist(p);
  return 0;
}
出力例2-4

追加項目:大正3年4月5日 大正3年4月5日
追加項目:昭和4年5月6日 昭和4年5月6日 -- -5510日 -- 大正3年4月5日
追加項目:平成5年6月7日 平成5年6月7日 -- -23408日 -- 昭和4年5月6日 -- -5510日 -- 大正3年4月5日

先頭は空行なのに注意

補足

以下、追加のヘッダファイルを示す。

wareki2.h


typedef struct wl {
  WAREKI wareki;
  struct wl* next;
} WAREKILIST;
SEIREKI toseireki(WAREKI w);
void printwarekilist(WAREKILIST* w, char* sep);
WAREKILIST* newnode(void);
WAREKILIST* add(WAREKILIST* p, WAREKI w);
void freelist(WAREKILIST* p);
void printnissulist(WAREKILIST* w, char* sep);

課題1

レポート締切日: 2018年6月15日(金)13:00
提出先: 2 号館 3F レポートボックス

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

なお、遅れレポートは教員に直接提出してください。 遅れた方が有利にならない範囲内で採点します。 遅れレポートの最終期限は7月26日18:10(授業開始時)です。

問題

和暦のカレンダーの関数を作成する

問題1-1

始めに西暦のデータ型 SEIREKI を下記のように定める。


typedef struct {
  int y,m,d;
}SEIREKI;

これを表示する void printseireki(SEIREKI s) を作成せよ。 そして、下記のプログラムと結合し、実行結果を報告せよ。

テストプログラム1-1

#include <stdio.h>
#include "wareki.h"
int main(void){
  SEIREKI s[]={{1858,11,17},
	       {1868,1,25},
	       {1912,7,29},
	       {1912,7,30},
	       {0}};
  SEIREKI *p;
  for(p=s; p->y!=0; p++){
    printseireki(*p);
    printf("\n");
  }
  return 0;
}
出力例1-1
西暦1858年11月17日
西暦1868年1月25日
西暦1912年7月29日
西暦1912年7月30日

問題1-2

和暦を扱うデータ型WAREKIを次のように定義する。


typedef struct {
  int y,m,d;
  int index;
}WAREKI;

このうち、index は下記の配列 char* gengou[] の要素を指す添字である (グレゴリオ歴は明治6年より採用なので、下記の範囲内では月日は西暦と和暦 で一致する) 。


extern char* gengou[];    
char* gengou[]={"範囲外","大正","昭和","平成",NULL};

この時、和暦を表示する関数 void printwareki(WAREKI g) を作成せよ。 但し、和暦では1年は元年と表示すること。 そして、下記のプログラムとさらに課題末尾に掲載している補助プログラム と結合し、実行結果を報告せよ。

テストプログラム1-2

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

int main(void){
  WAREKI w[]={{1,10,25,1},
	      {2,1,1,2},
	      {1,12,31,2},
	      {30,7,30,3},
	      {0}};
  WAREKI *p;
  for(p=w; p->y!=0; p++){
    printwareki(*p);
    printf("\n");
  }
  return 0;
}
出力例1-2
大正元年10月25日
昭和2年1月1日
昭和元年12月31日
平成30年7月30日

問題1-3

修正ユリウス日とは1858年11月17日から数えた日数である。 これを計算する計算式は次で与えられる

  1. d:グレゴリオ歴の日
    m: グレゴリオ歴の月-2。但し1月は11, 2月は 12 とする
    y: グレゴリオ歴の年。但し、1月2月に対しては1減ずる
  2. mjd は以下の和
    1. y×365.25 の整数値
    2. yを400で割った商
    3. m×30.59の整数値
    4. d
    から以下の和
    1. yを100で割った商
    2. 678912
    を引いたものである

この時、西暦(グレゴリオ歴)から修正ユリウス日を計算する関数 int mjd(SEIREKI s) を作成せよ。 但し、和暦では1年は元年と表示すること。 なお、修正ユリウス日から西暦を計算する関数 SEIREKI invmjd(int mjd)は 課題末尾に掲載している補助プログラムに示した。 そして、下記のプログラムとさらに問題1で作成したプログラムと 課題末尾に掲載している補助プログラム とを結合し、実行結果を報告せよ。

テストプログラム1-3

#include <stdio.h>
#include "wareki.h"
int main(void){
  SEIREKI s[]={{1858,11,17},
	       {1868,1,25},
	       {1912,7,29},
	       {1912,7,30},
	       {0}};
  SEIREKI s1;
  SEIREKI *p;
  int i,n;
  for(p=s; p->y!=0; p++){
    printseireki(*p);
    n=mjd(*p);
    printf("の修正ユリウス日は%dで、逆変換すると",n);
    printseireki(invmjd(n));
    printf("となる\n");
  }
  for(i=0;i<100000; i++){
    s1=invmjd(i);
    if(i!=mjd(s1)){
      printseireki(s1);
      printf("\n");
    }
  }  
  return 0;
}
出力例1-3
西暦1858年11月17日の修正ユリウス日は0で、逆変換すると西暦1858年11月17日となる
西暦1868年1月25日の修正ユリウス日は3356で、逆変換すると西暦1868年1月25日となる
西暦1912年7月29日の修正ユリウス日は19612で、逆変換すると西暦1912年7月29日となる
西暦1912年7月30日の修正ユリウス日は19613で、逆変換すると西暦1912年7月30日となる

問題1-4

西暦から和暦に変換する関数 WAREKI towareki(SEIREKI s) を作成せよ。 但し、補助プログラムには以下の配列が定義されているとする。


extern char* gengou[];
extern SEIREKI gannen[];
char* gengou[]={"範囲外","大正","昭和","平成",NULL};
SEIREKI gannen[]={{1,0,0},
                  {1912,7,30},
                  {1926,12,25},
                  {1989,1,8},
                  {-1}};

2016/6/14 範囲外の場合の年の初期値を変更した。これにより、範囲外で年の 計算式を変える必要が無くなった。 同時に、実行例も差し替えた。 但し、変更前の値に対して作成したプログラムを提出しても同等に評価する。

この時、西暦(グレゴリオ歴)を和暦に変換する関数 WAREKI towareki(SEIREKI s) を作成せよ。 そして、下記のプログラムとさらに問題1,2,3で作成したプログラムと 課題末尾に掲載している補助プログラム とを結合し、実行結果を報告せよ。

テストプログラム1-4

#include <stdio.h>
#include "wareki.h"
int main(void){
  SEIREKI range[]={{1912,7,29},
	       {1912,8,1},
	       {1926,12,24},
	       {1927,1,1},
	       {1988,12,31},
	       {1989,1,8},
	       {0}};
  int i;
  SEIREKI s;
  SEIREKI *p;
  for(p=range; p->y!=0; p+=2){
    for(i=mjd(*p); i<=mjd(*(p+1)); i++){
      s=invmjd(i);
      printseireki(s);
      printf(" = ");
      printwareki(towareki(s));
      printf("\n");
    }
  }
  return 0;
}
出力例1-4
西暦1912年7月29日 = 範囲外1912年7月29日
西暦1912年7月30日 = 大正元年7月30日
西暦1912年7月31日 = 大正元年7月31日
西暦1912年8月1日 = 大正元年8月1日
西暦1926年12月24日 = 大正15年12月24日
西暦1926年12月25日 = 昭和元年12月25日
西暦1926年12月26日 = 昭和元年12月26日
西暦1926年12月27日 = 昭和元年12月27日
西暦1926年12月28日 = 昭和元年12月28日
西暦1926年12月29日 = 昭和元年12月29日
西暦1926年12月30日 = 昭和元年12月30日
西暦1926年12月31日 = 昭和元年12月31日
西暦1927年1月1日 = 昭和2年1月1日
西暦1988年12月31日 = 昭和63年12月31日
西暦1989年1月1日 = 昭和64年1月1日
西暦1989年1月2日 = 昭和64年1月2日
西暦1989年1月3日 = 昭和64年1月3日
西暦1989年1月4日 = 昭和64年1月4日
西暦1989年1月5日 = 昭和64年1月5日
西暦1989年1月6日 = 昭和64年1月6日
西暦1989年1月7日 = 昭和64年1月7日
西暦1989年1月8日 = 平成元年1月8日

以下、ヘッダファイルと補助プログラムを示す。

wareki.h


typedef struct {
  int y,m,d;
}SEIREKI;
typedef struct {
  int y,m,d;
  int index;
}WAREKI;
extern char* gengou[];
extern SEIREKI gannen[];
void printseireki(SEIREKI s);
void printwareki(WAREKI w);
int mjd(SEIREKI s);
SEIREKI invmjd(int mjd);
WAREKI towareki(SEIREKI s);

補助プログラム


#include <stdlib.h>
#include "wareki.h"
char* gengou[]={"範囲外","大正","昭和","平成",NULL};
SEIREKI gannen[]={{1,0,0},
                  {1912,7,30},
                  {1926,12,25},
                  {1989,1,8},
                  {-1}};
SEIREKI invmjd(int mjd){
  SEIREKI result;
  int n=mjd+678881;
  int a=4*n+3+4*(int)(0.75*(int)(((double)4*n+1)/146097+1));
  int b=5*(int)((double)(a%1461)/4)+2;
  result.m = (b/153+14)%12+1;
  result.y = a/1461+((result.m<3)?1:0);
  result.d = b%153/5+1;
  return result;
}

レポート作成上の注意

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

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