4 教科書の例

4.1 1の数を数えるプログラム

教科書 [2]の最初の例は，整数を入力して，その中に含まれている1の数を表示するプログラムである．たとえば，入力した整数が4513101ならば， 3と表示するのである．

これを実現するためには，整数の中にふくまれている1の数を数える必要がある．教科書では以下の手順で，それを行っている．

整数の最下位の桁(一の位)の値を取り出している．ある整数を10で割った余りが最下位の桁の値となる．ある整数をvalueとして，剰余演算子%をつかって，value%10の演算により最下位の桁を取り出している．たとえば， valueの値が4513101の場合，value%10の演算の結果は1となる．
最下位の桁を取り出したので，valueの他の桁を右に1桁ずつシフトさせる． 4513101を451310とするのである．これは，除算演算子を使って， value/10により実現できる．コンピューターでは整数同士のわり算は整数になり，あまりは切り捨てられるからである．
valueの値がゼロになるまでこれを繰り返し，最下位の桁を調べ，1の数をカウントする．

4.1.1 繰り返し文を使う場合

繰り返し文であるforを使って，1の数を数えるプログラムが教科書のList 5-1(p.139-140)である．それを，リスト5に載せる(転載について)．これは，9-11行目にわたっての繰り返し文の実行順序が分かれば，プログラムの動作は分かるであろう．

リスト5 繰り返し文を使った1の数を数えるプログラム(転載について)

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 int num_of_one(int value)
   5 {
   6     int ret;
   7     /* valueを次々に10で割って桁をずらしながら，
   8         最下位の桁が1であるかどうかを調べていく */
   9     for(ret=0;value >0;value /=10)
  10         if(value%10==1)
  11             ++ret;
  12     return ret;
  13 }
  14 
  15 int main(void)
  16 {
  17     int i;
  18 
  19     scanf("%d",&i);
  20     printf("%d中に1は%d個含まれています\n",i,num_of_one(i));
  21     return EXIT_SUCCESS;
  22 }

4.1.2 再帰呼び出しを使う場合

次に，同じ処理をするプログラムを再帰呼び出しを使った例が，教科書のList 5-2(p.140)，プリントのリスト6, 7である(転載について)．最下位の桁を調べると，valueの桁を一つずらして，同じことが続くので，再帰呼び出しを行っている．これも，階乗を計算したときの漸化式のようなものを書くと，以下のようになる．

探索すべき整数valueの値がゼロであれば，処理は終了．
漸化式は，以下のように書ける．

$\displaystyle ($ valueの1の数 $\displaystyle )=($ value $\displaystyle の最下位の桁の1の数) +($ value $\displaystyle の桁を右に一桁ずらした値の1の数)$ (6)

この漸化式もどき通りにC言語の文法を用いて記述すれば，再帰呼び出しのプログラムができあがるのである．

このプログラムで使われている主なテクニックは，以下の通りである．

1行目 unsigned long value

これは，unsigned long int valueと同じで，変数valueの型を符号無し倍々精度整数で定義(予約)している．こうすると，valueは32ビットで，0～4294967295 の整数値を使うことができる．

リスト6 再帰呼び出しを使った1の数を数える関数(転載について)

   1 int num_of_one(unsigned long value)
   2 {
   3     int ret;
   4     /* valueが0桁（もうこれ以上解析する桁がない） */
   5     if(value==0)
   6         return 0;
   7     if(value%10==1)     /* いちばん下の位が1 */
   8         ret=1;
   9     else
  10         ret=0;
  11 
  12     /* 10で割って桁を1つずらし，再びnum_of_one()で調べる */
  13     return ret+num_of_one(value /10);
  14 }

リスト7はリスト5と同じプログラムではあるが，条件演算子²「?」を使ってコンパクトに記述している．

このプログラムで使われている主なテクニックは，以下の通りである．

5行目 ((value%10)==1) ?1:0

条件演算子?は，
条件式 ? 式1 : 式2
と書き，条件式が真ならば式1を，偽ならば式2を値として返す．

リスト7 再帰呼び出しを使った1の数を数える関数(転載について)

   1 int num_of_one(unsigned long value)
   2 {
   3     if(value==0)
   4         return 0;
   5     return ( ((value%10)==1) ?1:0) +num_of_one(value/10);
   6 }

4.2 最大公約数を求める

与えられた複数の整数の最大公約数を求めるプログラムである．

4.2.1 繰り返し文

教科書のList 5-3(p.143)のプログラム，プリントのリスト8は繰り返し文を用いて，最大公約数を求めている(転載について)．この方法は単純で，最大公約数を求める2つの整数のあたいのいずれかを選んで，それで割った余りがゼロになるか調べている．そして，割るべき整数を一つずつ減らして，最初に割り切れた整数を最大公約数としている．

リスト8 2つの整数の最大公約数を求める関数(転載について)

   1 int gcd(int a,int b)
   2 {
   3     int i;
   4     for(i=a;i>0;i--)
   5         if(a%i==0 && b%i==0)
   6         break;
   7     return i;
   8 }

4.2.2 再帰呼び出し

教科書のList 5-4(p.145)のプログラム，プリントのリスト9は再帰呼び出しを用いて，2個以上の整数の最大公約数を求めている(転載について)．リスト9 の関数multi_gcd(int n)は，配列N[]に格納されている整数N[0]～ N[n]の最大公約数を求める関数である．このプログラムの内容はそれほど難しくないので，各自，動作を考えること．

このプログラムも漸化式のようなものを考えると，次のようになる．

公約数を求める整数の組が2つの場合は，先のgcd()関数を呼び出して，2つの整数の最大公約数を求める．
漸化式は以下のように書ける．

$\displaystyle 複数最大公約数(\texttt{N[0]}～\texttt{N[n]})=2整数最大公約数\left[ \texttt{N[n]},複数最大公約数(\texttt{N[0]}～\texttt{N[n-1]}) \right]$ (7)

リスト再帰呼び出しを使い複数の整数の最大公約数を求める関数(転載について)

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 
   4 #define MAX 6
   5 int N[MAX]={98,140,84,28,42,126};
   6 
   7 int gcd(int a,int b)
   8 {
   9     int i;
  10     for(i=a;i>0;i--)
  11         if(a%i==0&&b%i==0)
  12             break;
  13     return i;
  14 }
  15 
  16 int multi_gcd(int n)
  17 {
  18     /* n==1（数が2つしかない）の場合は，普通にgcdを呼ぶだけ */
  19     if(n==1)
  20         return gcd(N[0],N[1]);
  21 
  22     /* n>1の場合は，N[n]と，N[0]..N[n-1]のgcd を呼び出す */
  23     return gcd(N[n],multi_gcd(n-1));
  24 }
  25 
  26 int main(void)
  27 {
  28     printf("配列Nの最大公約数は%dです\n",multi_gcd(MAX-1));
  29     return EXIT_SUCCESS;
  30 }

[転載について]
このページ中のリスト5とリスト6,リスト7,リスト8,リスト9のプログラムは，教科書として使用している以下の書籍

書名プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8

著作者紀平拓男・春日伸弥

出版社ソフトバンク　パブリッシング株式会社

から転載しました．この転載に関しては，著者と版元に許諾を得ています．

[Previous: 3 再帰呼び出しを使うためには] [Up: 再帰呼び出し] [Next: 5 練習問題]
[Top:ページの先頭に戻る]

ホームページ: Yamamoto's laboratory
著者: 山本昌志
Yamamoto Masashi
2006-03-23

no counter

書名	プログラミングの宝箱　アルゴリズムとデータ構造 ISBN4-7973-2419-8
著作者	紀平拓男・春日伸弥
出版社	ソフトバンク　パブリッシング株式会社