C言語: 2007年2月アーカイブ
フィボナッチ数列ってご存知でしょうか？
知らない人の方が多いかもしれないですね。
「今見ている数値が前の二つの数値の和に等しい数列」のことです。
「1,1,2,3,5,8,13……」たとえば、5を見ると、前の二つの数値「2」「3」の和になっています(一つ目と二つ目は1と定義しています)。
このフィボナッチ数列、ある種、クリエイターサイトにすごい適した話題です。
フィボナッチ数列の隣同士の値の比は、黄金比に収束するのです。
黄金比、きっとデザイン系の方は制作中にかなり気にしているのではないでしょうか。
縦横の比率が1:1.618、美術品や自然界に多く見られる値で、人間の目に非常に美しく映ると言われています。
さらには白銀比というものもあるそうです。こちらは初耳でした。
ひまわりの種を螺旋に沿って数えると、フィボナッチ数列と等しいそうです。
という前置きはそろそろ終わりとしまして、今回はフィボナッチ数列のC言語プログラミングを紹介します。
前回、階乗処理について紹介しましたので、同じ階層構造仲間ということですね。
以下、フィボナッチ数列にて指定された項番の値を返す関数です。
/* フィボナッチ数列関数ここから */
/* n:値を知りたい項番 */
/* わかりやすさのため、data[0]は使用していません */
int feb(int n){
int i,data[n+1];
if(n < 3)return (1);
data[1] = data[2] = 1;
for(i = 3 ; i < n+1 ; i++){
data[i] = data[i-1] + data[i-2];
}
return (data[n]);
}
/* フィボナッチ数列関数ここまで */
フィボナッチ数列についても階乗と同様、再帰呼び出し(自分で自分を呼ぶ)の考え方を使用すると、プログラムを簡潔にできます。
再帰を使用したフィボナッチ数列関数は以下の通りです。
/* フィボナッチ数列関数ここから */
/* n:値を知りたい項番 */
int feb(int n){
if(n == 1)return(1);
else{
if(n == 2) return (1);
else return feb(n-1) + feb(n-2);
}
}
/* フィボナッチ数列関数ここまで */
質問がございましたら質問掲示板にお書き込みください。
青春B 質問掲示板
Wikipedia フィボナッチ数列
Wikipedia 再帰呼び出し
Wikipedia 黄金比
Wikipedia 白銀比
Wikipedia C言語
C言語プログラミング、ずっとソートばかり書いてきましたのでたまには違うものを……。
今回は階乗のプログラミングです。
階乗という単語、ご存知でしょうか？
数式で書くならば、たとえば「5!」これは5を大声で叫べと言っているわけではなくて、5の階乗を意味します。
つまり
5!=5×4×3×2×1=120
階段状に乗算を繰り返すということです。
これをC言語で書くと、以下のようになります。
/* 階乗関数ここから */
/* n:階乗する数値 */
int kaijou(int n){
int i,sum=1;
for(i=n;i>0;i--)sum=sum*i;
return sum;
}
/* 階乗関数ここまで */
sumという変数を1で初期化して、それにn～1までを掛け合わせています。
結果上は繰り返しを「i>0」ではなく「i>1」としても変わらないですが、階乗の意味を重視してここでは1まで乗じています。
再帰という考え方を使用すると、これをさらに簡潔に書くことが可能です。
再帰とは自分で自分を呼び出すという考え方です。
再帰を使った階乗プログラムは以下の通りです。
/* 階乗関数ここから */
/* n:階乗する数値 */
int kaijou(int n){
if(n>0)return(n * kaijou(n-1));
else return (1);
}
/* 階乗関数ここまで */
つまり、5!を求めるとき
5!→5×4!→5×4×3!→5×4×3×2!→5×4×3×2×1!→5×4×3×2×1×1
と階層的に処理しています。
C言語のソート紹介シリーズ、挿入ソート、シェルソート、選択ソートと来て今回はバブルソート(基本交換法)を紹介いたします。
計算時間が遅いため実用的ではないです。
ただ、非常に簡潔な仕組みのため、ソートという操作の概念を理解しやすいかと思います。
たとえば、最後尾に最も大きい値、先頭に最も小さい値を持ってきたい場合……先頭とその次を比べて順番が逆だったら入れ替え、先頭の次とそのさらに次を比べて順番が逆だったら入れ替え……これを最後まで繰り返すと最後尾に最も大きな値が来ます。再び同じことを今度は先頭から最後尾の一つ前まで繰り返せば、最後尾に一番大きい数、最後尾の一つ前に二番目に大きい数が来ます。これを全体が順番通りになるまで繰り返すのがバブルソートです。
データが「８５４２６３７１」のときの数値の変化例は以下の通りです。
・左から順番に隣り合った文字同士を比べる。大きい方が右に行くように交換していく。結果、一番大きい数値が一番右に来る。「５４２６３７１(８)」
・残った中で一番大きい数値が残った中の一番右に来る。「４２５３６１(７)８」
・残った中で一番大きい数値が残った中の一番右に来る。「２４３５１(６)７８」
・残った中で一番大きい数値が残った中の一番右に来る。「２３４１(５)６７８」
・残った中で一番大きい数値が残った中の一番右に来る。「２３１(４)５６７８」
・残った中で一番大きい数値が残った中の一番右に来る。「２１(３)４５６７８」
・残った中で一番大きい数値が残った中の一番右に来る。「１(２)３４５６７８」
以下、C言語で書いたバブルソートのプログラムです。
ソートを行う関数部分のみです。
/* バブルソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,temp;
for(i=num-1;i>0;i--){
for(j=0;j<i;j++){
if(data[j]>data[j+1]){
/*データの入れ替え*/
temp=data[j];
data[j]=data[j+1];
data[j+1]=temp;
}
}
}
}
/* バブルソート関数ここまで */