演習の解答

第一回

演習 1-1

Hello World と表示される

演習 1-2

  1. 
    #include <stdio.h>
    #define N 5
    main(){
      int i,j;
      for(i=0;i<N;i++){
        for(j=0;j<N-i;j++){
          printf("〇");
        }
        printf("\n");
      }
    }
    
  2. 
    #include <stdio.h>
    #define N 4
    main(){
      int i,j;
      for(i=0;i<N;i++){
        for(j=0;j<N-i-1;j++){
          printf(" ");
        }
        for(j=0;j<2*i+1;j++){
          printf("〇");
        }
        printf("\n");
      }
    }
    
  3. 
    #include <stdio.h>
    #define N 3
    main(){
      int i,j;
      for(j=0;j<N+2;j++){
        printf("〇");
      }
      printf("\n");
      for(i=0;i<N;i++){
        printf("〇");
        for(j=0;j<N;j++){
          printf(" ");
        }
        printf("〇\n");
      }
      for(j=0;j<N+2;j++){
        printf("〇");
      }
    }
    

第二回

演習 2-1

  1. 
    #include <stdio.h>
    main(){
      int a[]={5, 2, 6, 3, 1, -1};
      int i,k;
      k=0;
      for(i=0;a[i]!=-1;i++){
        k++;
      }
      printf("%d\n",k);
    }
    
  2. 
    #include <stdio.h>
    main(){
      int a[]={5, 2, 6, 3, 1, -1};
      int i,goukei;
      goukei=0;
      for(i=0;a[i]!=-1;i++){
        goukei+=a[i];
      }
      printf("%d\n",goukei);
    }
    
  3. 
    #include <stdio.h>
    main(){
      int a[]={5, 2, 6, 3, 1, -1};
      int i,k,goukei;
      k=0;
      goukei=0;
      for(i=0;a[i]!=-1;i++){
        k++;
        goukei+=a[i];
      }
      printf("%f\n",(float)goukei/k);
    }
    

第三回

演習 3-1

  1. 
    #include <stdio.h>
    main(){
      char x[]="abc";
      int i,k;
      k=0;
      for(i=0;x[i]!='\0';i++){
        k++;
      }
      printf("%d\n",k);
    }
    
  2. 
    #include <stdio.h>
    main(){
      char x[]="This is a pin.";
      int i,k;
      k=0;
      for(i=0;x[i]!='\0';i++){
        if(a[i]=='i'){
          k++;
        }
      }
      printf("%d\n",k);
    }
    
  3. 
    #include <stdio.h>
    main(){
      char x[]="This is a pin.";
      int i;
      char c;
      for(i=0;x[i]!='\0';i++){
        c=x[i];
        if((c>='a')&&(c<='z')){
          c=c-'a'+'A';
        }
        printf("%c",c);
      }
    }
    
  4. 
    #include <stdio.h>
    main(){
      char x[]="abc";
      char y[]="def";
      char z[50];
      int i,j;
      for(i=0;x[i]!='\0';i++){
        z[i]=x[i];
      }
      for(j=0;y[j]!='\0';j++){
        z[i]=y[j];
        i++;
      }
      z[i]='\0';
      printf("文字列 %s と %s をつなげると %s になる\n",x,y,z);
    }
    

第四回

    1. i=2, j=1
    2. i=1. j=0
    3. i=0
  1. #include <stdio.h>
    main(){
      FILE *fh;
      char filename[]="4-2.c";
      int c;
      int n
      if((fh=fopen(filename,"r"))==NULL){
        fprintf(stderr,"ファイル %s を開けませんでした\n",filename);
        return 1;
      }
      n=0;
      while((c=getc(fh))!=EOF){
        n++;
      }
      printf("合計 %d 文字\n",n);
      fclose(fh);
    }
    
  2. #include <stdio.h>
    main(){
      FILE *fh;
      char filename[]="4-3.c";
      int c;
      char x='a';
      int n;
      if((fh=fopen(filename,"r"))==NULL){
        fprintf(stderr,"ファイル %s を開けませんでした\n",filename);
        return 1;
      }
      n=0;
      while((c=getc(fh))!=EOF){
        if(c==x){
          n++;
       }
      }
      printf("%c は合計 %d 文字\n",x,n);
      fclose(fh);
    }
    
  3. #include <stdio.h>
    main(){
      FILE *fh;
      char filename[]="4-4.c";
      int c;
      int n;
      if((fh=fopen(filename,"r"))==NULL){
        fprintf(stderr,"ファイル %s を開けませんでした\n",filename);
        return 1;
      }
      n=0;
      while((c=getc(fh))!=EOF){
        if(c=='\n'){
          n++;
        }
      }
      printf("合計 %d 行\n",n);
      fclose(fh);
    }
    
  4. #include <stdio.h>
    main(){
      FILE *fh;
      char filename[]="4-5.c";
      int c;
      int n;
      if((fh=fopen(filename,"r"))==NULL){
        fprintf(stderr,"ファイル %s を開けませんでした\n",filename);
        return 1;
      }
      n=0;
      while((c=getc(fh))!=EOF){
        n++;    
        if(c=='\n'){
          printf("%d 文字\n",n);
          n=0;
        }
      }   
      if(n!=0){
        printf("%d 文字\n",n);
      }
      fclose(fh);
    }
    
  5. #include <stdio.h>
    main(){
      FILE *fh;
      char filename[]="4-6.c";
      int c;
      int n;
      if((fh=fopen(filename,"r"))==NULL){
        fprintf(stderr,"ファイル %s を開けませんでした\n",filename);
        return 1;
      }
      n=0;
      while((c=getc(fh))!=EOF){
        if(c=='\n'){
          printf("\n");
          n=0;
        }else{
          if(n>=10){
            printf("\n");
            n=0;
          }
          printf("%c",c);
          n++;
        }      
      }      
      fclose(fh);
    }
    
  6. #include <stdio.h>
    #define N 3
    main(){
      FILE* fh;
      int i,j;
      if((fh=fopen("zukai.txt","w"))==NULL){
        fprintf(stderr,"ファイルを開けませんでした\n");
        return 1;
      }
      for(i=0;i<N;i++){
        for(j=0;j<N-i-1;j++){
          fprintf(fh,"  ");
        }
        fprintf(fh,"〇");
        if(i>0){
          for(j=0;j<2*i-1;j++){
    	fprintf(fh,"  ");
          }
          fprintf(fh,"〇");
        }
        fprintf(fh,"\n");
      }
      for(i=N-2;i>=0;i--){
        for(j=0;j<N-i-1;j++){
          fprintf(fh,"  ");
        }
        fprintf(fh,"〇");
        if(i>0){
          for(j=0;j<2*i-1;j++){
    	fprintf(fh,"  ");
          }
          fprintf(fh,"〇");
        }
        fprintf(fh,"\n");
      }
      fclose(fh);
    }
    

第五回

演習 5-1

1
2 1
2 2
0 2

演習 5-2

  1. 
    #include <stdio.h>
    extern double x[];
    void larger(double y){
      int i;
      for(i=0; x[i]!=-1.0 ; i++){
        printf("%f ",x[i]*y);
      }
      printf("\n");
    }
    
  2. 
    double x[]={1.0,3.0,5.0,2.0,-1.0};
    void larger(double y);
    int main(void){
      larger(3.2);
      larger(5.0);
      return 0;
    }
    

    動作結果は以下のとおり

    3.200000 9.600000 16.000000 6.400000 
    5.000000 15.000000 25.000000 10.000000 
    
  3. 
    extern double x[];
    void times(double y){
      int i;
      for(i=0; x[i]!=-1.0; i++){
        x[i]*=y;
      }
    }
    
  4. 
    double x[]={1.0,3.0,5.0,2.0,-1.0};
    void larger(double y);
    void times(double y);
    int main(void){
      times(3.2);
      larger(1.0);
      times(5.0);
      larger(1.0);
      return 0;
    }
    

    実行結果は以下のとおり

    3.200000 9.600000 16.000000 6.400000 
    16.000000 48.000000 80.000000 32.000000 
    

第六回

演習 6-1

  1. 
    void inc(double * x){
      (*x)++;
    }
    
  2. 
    #include <stdio.h>
    int main(void){
      int i;
      double a=0.1;
      for(i=0;i<3;i++){
        inc(&a);
        printf("%f\n",a);
      }
      return 0;
    }
    

演習 6-2


#include <stdio.h>
int main(void){
  char x[]="abcdef";
  char y[50];
  char *p,*q;
  p=x;
  q=y;
  while((*q++=*p++)!='\0');
  printf("%s をコピーした結果 %s となる\n",x,y);
  return 0;
}

演習 6-3


#include <stdio.h>
void copy(char *a, char *b){
  while((*b++=*a++)!='\0');
}
int main(void){
  char x[]="abcdef";
  char y[50];
  copy(x,y);
  printf("%s をコピーした結果 %s となる\n",x,y);
  return 0;
}

第七回

演習 7-1

----distance.c----

#include "point.h"
#include <math.h>
double distance(POINT p){
   return sqrt(p.x*p.x+p.y*p.y);
}

演習 7-2

----half.c----

#include "point.h"
void half(POINT *p){
  p->x /= 2;
  p->y /= 2;
}

第八回

演習 8-1

5!=120, 6!=720

演習 8-2

  1. 
    #include <stdio.h>
    int a(int n){
      if(n==0){ return 1; }
      if(n==1){ return 1; }
      return a(n-1)+a(n-2);
    }
    int main(void){
      printf("%d\n",a(20));
      return 0;
    }
    

    10946

  2. 
    #include <stdio.h>
    int a(int n){
      if(n==0){ return 1; }
      if(n==1){ return 1; }
      return a(n-1)+a(n-2);
    }
    int main(void){
      int i;
      for(i=0;i<=50;i++){
        printf("%d\n",a(i));
      }
      return 0;
    }
    
  3. 
    #include <stdio.h>
    #define N 100
    int b[N]={0};
    int a(int n){
      if(b[n]>0){ return b[n];}
      if(n==0){ return 1; }
      if(n==1){ return 1; }
      b[n]=a(n-1)+a(n-2);
      return b[n];
    }
    int main(void){
      printf("%d\n",a(45));
      return 0;
    }
    

    a40=165580141

    但し、演習室の環境だと簡単に求まってしまったため、 a45の値 1836311903 も求めた。

演習 8-3


#include <stdio.h>
int combi(int n, int m){
  if(m==0){ return 1; }
  if(m==n){ return 1; }
  return combi(n-1,m-1)+combi(n-1,m);
}
int main(void){
  printf("%d, %d\n",combi(5,2),combi(20,2));
  return 0;
}

10, 190 が表示される

演習 8-4

hanoi(3,'a','b','c')
move 1 from a to b
move 2 from a to c
move 1 from b to c
move 3 from a to b
move 1 from c to a
move 2 from c to b
move 1 from a to b
hanoi(4,'a','b','c')
move 1 from a to c
move 2 from a to b
move 1 from c to b
move 3 from a to c
move 1 from b to a
move 2 from b to c
move 1 from a to c
move 4 from a to b
move 1 from c to b
move 2 from c to a
move 1 from b to a
move 3 from c to b
move 1 from a to c
move 2 from a to b
move 1 from c to b

第九回

演習 9-1

14種類。

演習 9-2

0110
1010
1101
0010

演習 9-3


#include 
#define MAX 10
int main(void){
  int i,j,degree,kiten;
  int a[MAX][MAX];
  printf("頂点数を入れて下さい。\n");
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&a[i][j];);
    }
  }
  kiten=0;
  for(i=0;i<n;i++){
    degree=0;    
    for(j=0;j<n;j++){
      degree+=a[i][j];
    }
    kiten+=degree%2
  }
  if((kiten==0)||(kiten==2)){
    printf("一筆書きできます。\n");
  }else{
    printf("一筆書きできません。\n");
  }
  return 0;
}

第十回

演習 10-1


#include <stdio.h>
#include <stdlib.h>
int main(void){
  int i,n;
  int *a;
  printf("項目数?");
  scanf("%d",&n);
  if((a=(int*)malloc(n*sizeof(int)))==NULL){
    fprintf(stderr,"メモリーエラー\n");
    return 1;
  }
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  for(i=n-1;i>=0;i--){
    printf("%d\n",a[i]);
  }
  return 0;
}

演習 10-2


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(void){
  char x[]="abcdef";
  char y[]="ghijklmn";
  char *z;
  int i,j;
  int lx,ly;
  lx=strlen(x);
  ly=strlen(y);
  printf("文字列 x=%s(長さ%d) と文字列 y=%s(長さ%d)を結合すると",x,lx,y,ly);
  z=(char*)malloc((lx+ly+1)*sizeof(char));
  for(i=0;x[i]!='\0';i++){
    z[i]=x[i];
  }
  for(j=0;y[j]!='\0';j++){
    z[i+j]=y[j];
  }
  z[i+j]='\0';
  printf("z=%s(長さ%d)になる\n",z,strlen(z));
  return 0;
}

第十一回

演習 11-1


#include <stdio.h>
#include <stdlib.h>
typedef struct node {
  struct node *next;
  char *data;
} NODE;
typedef struct list {
  NODE *top,*bottom;
} LIST;
LIST* newlist(void){
  LIST* l;
  NODE* n;
  if((l=(LIST*)malloc(sizeof(LIST)))==NULL){
    return NULL;
  }
  if((n=(NODE*)malloc(sizeof(NODE)))!=NULL){
    free(l);
    return NULL;
  }
  n->next=NULL;
  l->top=l->bottom=n;
  return l;
}
int add(LIST *list, char *value){
  NODE *newnode;
  if((newnode=(NODE*)malloc(sizeof(NODE)))==NULL){
    return 0;
  }
  newnode->next=NULL;
  list->bottom->next=newnode;
  list->bottom->data=value;
  list->bottom=newnode;
  return 1;
}
void show(LIST *list){
  NODE *p;
  for(p=list->top; p!=list->bottom; p=p->next){
    printf("%s\n",p->data);
  }
}
void dellist(LIST *list){
  NODE *p,*q;
  p=list->top;
  do{
    q=p;
    p=p->next;
    free(q);
  }while(p!=NULL);
  free(list);
}
int main(void){
  LIST *list;
  list=newlist();
  if(list==NULL){
    return 1;
  }
  add(list,"abc");
  add(list,"def");
  add(list,"ghi");
  show(list);
  dellist(list);
  return 0;
}

演習 11-2


#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define SIZE 80
char buffer[SIZE+1];
typedef struct lst {
  char *item;
  struct lst *next;
} LIST;
LIST* newnode(void){
  LIST *p;
  if((p=(LIST *)malloc(sizeof(LIST)))==NULL){
    return NULL;
  }
  p->next=NULL;
  return p;
}
int add(LIST *p,char *c){
  if(p->next == NULL){
    if((p->next=newnode())==NULL){
      return 0;
    }
    p->item=c;
    return 1;
  }else{
    return add(p->next,c);
  }
}  
void reverseshow(LIST *p){
  if(p->next != NULL){
    reverseshow(p->next);
    printf("%s\n",p->item);
  }
}
#define nullcheck(p) if((p)==NULL){fprintf(stderr,"メモリーエラー\n");return 2;}
int main(void){
  int c;
  int i=0;
  char filename[]="input.txt";
  char *p;
  FILE *fh;
  LIST *l;
  if((fh=fopen(filename,"r"))==NULL){
    fprintf(stderr,"ファイル %s がありません。\n",filename);
    return 1;
  }
  nullcheck(l=newnode());
  while((c=getc(fh))!=EOF){
    if(c!='\n'){
      if(i<SIZE){
        buffer[i++]=c;
      }
    }else{
      buffer[i]='\0';
      nullcheck(p=strdup(buffer));
      if(add(l,p)){fprintf(stderr,"メモリーエラー\n");return 2;}
      i=0;
    }
  }
  reverseshow(l);
  fclose(fh);
}

第十二回

演習 12-1

次のように出力される

def
ghi
abc

演習 12-2

構造体 LIST 内の item の型を char にするため、いくつかの場所の型も直す必要がある。


#include <stdio.h>
#include <stdlib.h>
typedef struct lst {
  struct lst *next;
  char item;
} LIST;
LIST *stackpointer=NULL;
LIST* push(char i){
  LIST *newnode=(LIST *)malloc(sizeof(LIST));
  if(newnode==NULL){
    return NULL;
  }
  newnode->item=i;
  newnode->next=stackpointer;
  stackpointer=newnode;
  return newnode;
}
char pop(void){
  LIST *d=stackpointer;
  char i=stackpointer->item;
  stackpointer=stackpointer->next;
  free(d);
  return i;
}
int empty(void){
  return stackpointer==NULL;
}
int main(void){
  FILE *f;
  int c;
  int kazu=0;
  char file[]="samp1.c";
  if((f=fopen(file,"r"))==NULL){
    fprintf(stderr,"ファイル %s を開けませんでした\n",file);
    return 9;
  }
  while((c=getc(f))!=EOF){
    if((c=='(')||(c=='{')||(c=='[')){
      push(c);
    }else if(c==')'){
      if(empty()){
        fprintf(stderr,"閉じ括弧が多過ぎます。\n");
	fclose(f);
	return 1;
      }
      if(pop()!='('){
        fprintf(stderr,"閉じ括弧が合ってません。\n");
        fclose(f);
        return 4;
      }
    }else if(c=='}'){
      if(empty()){
        fprintf(stderr,"閉じ括弧が多過ぎます。\n");
        fclose(f);
        return 1;
      } 
      if(pop()!='{'){
        fprintf(stderr,"閉じ括弧が合ってません。\n");
        fclose(f);
        return 4;
      }
    }else if(c==']'){
      if(empty()){
        fprintf(stderr,"閉じ括弧が多過ぎます。\n");
        fclose(f);
        return 1;
      }
      if(pop()!='['){
        fprintf(stderr,"閉じ括弧が合ってません。\n");
        fclose(f);
        return 4;
      }
    }
  }
  fclose(f);
  if(empty()){
    fprintf(stderr,"括弧は正常です。\n");
    return 0;
  }else{
    fprintf(stderr,"閉じ括弧が足りません。\n");
    return 2;
  }
}

演習 12-3

入力する数を一桁の整数に制限した。 講義中出たエラーは、空白などを読み込んだとき、文字の判定の前に pop していたためスタックがエラーを出したもの。


#include <stdio.h>
#include <stdlib.h>
typedef struct lst {
  struct lst *next;
  int item;
} LIST;
LIST *stackpointer=NULL;
LIST* push(int i){
  LIST *newnode=(LIST *)malloc(sizeof(LIST));
  if(newnode==NULL){
    return NULL;
  }
  newnode->item=i;
  newnode->next=stackpointer;
  stackpointer=newnode;
  return newnode;
}
int pop(void){
  LIST *d=stackpointer;
  int i=stackpointer->item;
  stackpointer=stackpointer->next;
  free(d);
  return i;
}
int empty(void){
  return stackpointer==NULL;
}
int main(void){
  int c,x,y;
  while((c=getchar())!=EOF){
    if(c>='0' && c<='9'){
      push(c-'0');
    }else{
      switch(c){
      case '+':
	y=pop();
	x=pop();
	push(x+y);
	printf("%d\n",x+y);
	break;
      }
    }
  }
  return 0;
}

第十三回

演習 13-1

作成中

演習 13-2

show 関数を以下のように書き直す。


void show(TREE *t){
  if(t!=NULL){
    show(t->right);
    printf("%s: %d\n",t->id,t->key);
    show(t->left);
  }
}

演習 13-3

演習 13-4


TREE* find(TREE *t, int key){
  if(t==NULL){
    return NULL;
  }
  if(t->key == key){
    return t;
  }
  if(key < t->key){
    return find(t->left, key);
  }else{
    return find(t->right, key);
  }
}

演習 13-5


int main(void){
  TREE *t=NULL;
  char *data[]={"abc","def","efg","abc","abc","efg",NULL};
  int i;
  for(i=0; data[i]!=NULL; i++){
    set(&t,data[i],get(t,data[i])+1);
  }
  show(t);
  return 0;
}

第十四回

演習 14-1


#include <stdio.h>
int a[11]={4,6,3,1,9,7,5,0,2,6,8};
void printarray(void){
  int i;
  for(i=0;i<11;i++){
    printf("%d ",a[i]);
  }
  printf("\n");
}
void partition(int s, int t){
  if(s<t){
    int val = a[s];
    int i=s+1,j=t;
    int tmp;
    while(i<=j){
      while((i<=t)&&(val>=a[i])){i++;}
      while((j>=s+1)&&(val<a[j])){j--;}
      if(i<j){
	tmp=a[i];
	a[i]=a[j];
	a[j]=tmp;
      }
    }
    if(i-1>=s+1){
      tmp=a[s];
      a[s]=a[i-1];
      a[i-1]=tmp;
    }
    partition(s,i-2);
    partition(j+1,t);
  }
}
int main(void){
  printarray();
  partition(0,10);
  printarray();
  return 0;
}

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科