本講義では 2 通のレポートで評価します。 レポートは A4 の紙を縦に使い、適宜表紙を付けて提出すること。 またプログラムは C 言語で作成しなさい。
なお、遅れレポートは原則受けとりません。
大きな数を扱うため、線形リストによる実装を考える。 但し、簡単のため、リストの要素一つには10進数一桁だけを記憶することとする。 いま、次の構造体と、関数が定義されているとする。
typedef struct bignum {
int number;
struct bignum* next;
} Bignum;
Bignum* init(int n);
void freeBignum(Bignum* b);
char* bignumtostring(Bignum* b);
Bignum* add(Bignum* x, Bignum* y);
Bignum* mul(Bignum* x, Bignum* y);
Bignum* factorial(int n);
#include <stdlib.h>
#include "bignum.h"
Bignum* init(int n){
int u;
Bignum* item = malloc(sizeof(Bignum));
if(item!=NULL){
u=n/10;
item->number=n%10;
if(u==0){
item->next = NULL;
}else{
item -> next = init(u);
}
}
return item;
}
void freeBignum(Bignum* b){
if(b->next==NULL) return;
freeBignum(b->next);
free(b);
}
なお、以下のテストプログラムでは、簡単のためにメモリーを確保したかのチェック を省いている。 メモリーのチェックを含む厳密なテストプログラムは別に示す。
Bignum のポインターを与えられたら、その文字列表現を返す関数
char* bignumtostring(Bignum* b)
を作りなさい。
そして、次のプログラムと結合し、テストしなさい。
#include <stdio.h>
#include <stdlib.h>
#include "bignum.h"
#define N 4
int main(void){
int i;
Bignum* b[N];
char* s[N];
b[0]=init(0);
b[1]=init(2);
b[2]=init(2000);
b[3]=init(1234567890);
for(i=0;i<N;i++){
printf("%s, ",s[i]=bignumtostring(b[i]));
}
printf("\n");
for(i=N-1;i>=0; i--){
free(s[i]);
freeBignum(b[i]);
}
return 0;
}
0, 2, 2000, 1234567890,
二つの Bignum 型のポインターを受け取り、それを足した値を示す Bignum 型
のポインターを返す関数
Bignum* add(Bignum* x, Bignum* y)
を作成しなさい。
そして、次のテストプログラムで動作を確認しなさい。
#include <stdio.h>
#include <stdlib.h>
#include "bignum.h"
#define N 8
int main(void){
int i=0;
Bignum* b[N];
char* s[N];
b[i++]=init(0);
b[i++]=init(2);
b[i++]=init(2000);
b[i++]=init(1234567890);
b[i++]=add(b[0],b[1]);
b[i++]=add(b[2],b[3]);
b[i++]=add(b[3],b[2]);
b[i++]=add(b[3],b[3]);
for(i=0;i<N;i++){
s[i]=bignumtostring(b[i]);
}
printf("%s + %s = %s\n",s[0],s[1],s[4]);
printf("%s + %s = %s\n",s[2],s[3],s[5]);
printf("%s + %s = %s\n",s[3],s[2],s[6]);
printf("%s + %s = %s\n",s[3],s[3],s[7]);
for(i=N-1;i>=0; i--){
free(s[i]);
freeBignum(b[i]);
}
return 0;
}
0 + 2 = 2 2000 + 1234567890 = 1234569890 1234567890 + 2000 = 1234569890 1234567890 + 1234567890 = 2469135780
二つの Bignum 型のポインターを受け取り、それを掛けた足した値を示す Bignum 型
のポインターを返す関数
Bignum* mul(Bignum* x, Bignum* y)
を作成しなさい。
そして、次のテストプログラムで動作を確認しなさい。
#include <stdio.h>
#include <stdlib.h>
#include "bignum.h"
#define N 8
int main(void){
int i=0;
Bignum* b[N];
char* s[N];
b[i++]=init(0);
b[i++]=init(2);
b[i++]=init(2000);
b[i++]=init(1234567890);
b[i++]=mul(b[0],b[1]);
b[i++]=mul(b[2],b[3]);
b[i++]=mul(b[3],b[2]);
b[i++]=mul(b[3],b[3]);
for(i=0;i<N;i++){
s[i]=bignumtostring(b[i]);
}
printf("%s * %s = %s\n",s[0],s[1],s[4]);
printf("%s * %s = %s\n",s[2],s[3],s[5]);
printf("%s * %s = %s\n",s[3],s[2],s[6]);
printf("%s * %s = %s\n",s[3],s[3],s[7]);
for(i=N-1;i>=0; i--){
free(s[i]);
freeBignum(b[i]);
}
return 0;
}
0 * 2 = 2 2000 * 1234567890 = 2469135780000 1234567890 * 2000 = 2469135780000 1234567890 * 1234567890 = 1524157875019052100
100! を求めなさい。
なお、Bignum の表現の長さを返す関数
int length(Bignum* b)
を作成すると見通しが良くなる。
本課題では、 strcmp などの文字列関係の組み込み関数を使用してはい けない。 また、解答法として、分割コンパイルによる別ファイルにプログラムを書く方 法と、下記のテストプログラムに関数を追記する方法の二通りがあるがどちら でも良い。 プログラムの解説は、自分で作成した関数について行うこと。 こちらで提供したテストプログラムの説明は基本的には不要である。 但し、自分で作成した関数を説明するのに必要な内容には言及すること。
なお、遅れレポートは教員に直接提出してください。 遅れた方が有利にならない範囲内で採点します。
さて、個人情報を扱うため、名前と数値の組を配列で管理したい。 そのため、次のような構造体を作成した。
typedef struct {
char* name;
int data;
} Person;
Person の配列に対して、各要素を一行ずつ出力する printAccount 関数を作 りなさい。 但し、 Person の配列において、 name 要素が NULL のものは番兵として扱い なさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。 (person.h は後述)
#include <stdio.h>
#include "person.h"
int main(void){
Person account[] = { {"sakamoto"},{"naoshi"},
{"kobayashi"},{"yoshifumi"},{NULL}};
printAccount(account);
return 0;
}
sakamoto: 0 naoshi: 0 kobayashi: 0 yoshifumi: 0
Person の配列に対して、文字列の配列を与えると、Person の各要素を文字列 で初期化する touroku 関数を作りなさい。 但し、文字列の配列の最後の要素は NULL を番兵として置くこととする。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。
#include <stdio.h>
#include "person.h"
#define N 4
int main(void){
char* member[]={"kobayashi","yoshifumi","sakamoto","naoshi",NULL};
Person account[N+1];
touroku(member,account);
printAccount(account);
return 0;
}
kobayashi: 0 yoshifumi: 0 sakamoto: 0 naoshi: 0
二つの文字列を与え、両方の内容が完全に一致したら 1, 異なれば 0 を返す match 関数を作りなさい。 さらに、その match 関数を使用して、文字列と Person の配列を渡すと、そ の文字列と同じ内容の name が存在したら Person の要素のポインターを返し、 無ければ NULL を返す login 関数を作りなさい。 そして、次のテストプログラムと結合し、正常な出力が得られることを確認しなさい。
#include <stdio.h>
#include <string.h>
#include "person.h"
typedef struct {
char* a;
char* b;
int result;
} TEST;
int main(void){
TEST test[]={{"","",1},
{"","abc",0},
{"abc","",0},
{"abc","abc",1},
{"ab","abc",0},
{"abc","ab",0},
{"abc","abd",0},
{NULL,NULL,-1}};
TEST* p;
for(p=test; p->result!=-1; p++){
printf("%s, %s, %d:",p->a, p->b, p->result);
printf("%d\n", match(strdup(p->a), strdup(p->b)));
}
return 0;
}
, , 1:1 , abc, 0:0 abc, , 0:0 abc, abc, 1:1 ab, abc, 0:0 abc, ab, 0:0 abc, abd, 0:0
#include <stdio.h>
#include <string.h>
w#include "person.h"
#define N 4
int main(void){
char* member[] = {"sakamoto" ,"naoshi", "kobayashi", "yoshifumi", NULL};
char** m;
char* people[] = {"sakamoto", "sakamoto", "kobayashi", "yoshifumi",
"kobayashi","motohashi", "sakamoto", NULL};
Person account[N+1];
Person* p;
touroku(member,account);
printAccount(account);
for(m=people;*m!=NULL;m++){
p=login(strdup(*m),account);
/* if(p!=NULL) p->data+=i++; 2012/6/7 訂正 */
if(p!=NULL) p->data++;
}
printAccount(account);
return 0;
}
sakamoto: 0 naoshi: 0 kobayashi: 0 yoshifumi: 0 sakamoto: 3 naoshi: 0 kobayashi: 2 yoshifumi: 1
person.h は次のように上記の構造体と作るべき関数のすべてのプロトタイプ 宣言が入っているファイルとする。
typedef struct {
char* name;
int data;
} Person;
void printAccount(Person* account);
void touroku(char** names, Person* member);
int match(char*s, char*t);
Person* login(char* name, Person* member);