C言語のブログ記事
以前、なんとなく気分転換に短いC言語のプログラムをいくつか書いてみました。
下一桁抽出とか絶対値表示とか最大公約数とかの定番なやつ。
参考にする人がいるかわからないけれど、下に列挙しておきますのでよろしければご利用ください。
プログラマーになるかどうかは別として、コンピュータで食べていこうと思っているならプログラミング言語は勉強して損ないですよ!
(1)キーボードから入力した文字を表示するプログラム
int main(void){
printf("%c" , getchar());
return(0);
}
(2)キーボードから入力した文字を表示するプログラムⅡ
int main(void){
putchar(getchar());
return(0);
}
(3)キーボードからaが入力されるまで入力を続けるプログラム
int main(void){
while(getchar() != 'a');
return(0);
}
(4)1～10までの整数を表示するプログラム
int main(void){
int a;
for(a = 1 ; a <= 10 ; a++)printf("%d\n" , a);
return(0);
}
(5)1～10までの整数を表示するプログラムⅡ
int main(void){
int a = 0;
while(a++ < 10)printf("%d\n", a);
return(0);
}
(6)1～1000までに含まれる3の倍数を表示するプログラム
int main(void){
int a;
for(a = 3 ; a < 1001 ; a += 3)printf("%d\n" , a);
return(0);
}
(7)1～1000までに含まれる3の倍数を表示するプログラムⅡ
int main(void){
int a = 0;
while(a <= 997)printf("%d\n" , a += 3);
return(0);
}
(8)1～1000までに含まれる3の倍数を表示するプログラムⅢ
int main(void){
int a = 3;
while(a < 1001)if(a++ % 3 == 0)printf("%d\n" , a - 1);
return(0);
}
(9)キーボードから入力した整数の絶対値を表示するプログラム
int main(void){
int a;
scanf("%d" , &a);
printf("%d", a > 0 ? a : -a);
return(0);
}
(10)キーボードから入力した整数を100回表示するプログラム
int main(void){
int a , b = 0;
scanf("%d" , &a);
for(b = 0 ; b < 100 ; b++)printf("%d\n" , a);
return(0);
}
(11)キーボードから入力した整数が何の倍数であるかを表示するプログラム
int main(void){
int a , b;
scanf("%d" , &a);
for(b = a ; b > 1 ; b--)if(a % b == 0)printf("%d\n" , b);
return (0);
}
(12)キーボードから入力した整数の一の位だけ表示するプログラム
int main(void){
int a;
scanf("%d" , &a);
printf("%d\n" , a % 10);
return(0);
}
(13)キーボードから入力した整数の下二桁を0にするプログラム
int main(void){
int a;
scanf("%d" , &a);
printf("%d\n", a - a % 100);
return(0);
}
(14)キーボードから入力した整数の階乗を表示するプログラム
int main(void){
int a , sum = 1;
scanf("%d" , &a);
while(a > 1)sum = sum * a--;
printf("%d",sum);
return(0);
}
(15)キーボードから入力した二つの整数の最大公約数を求めるプログラム
int main(void){
int a , b , c;
scanf("%d %d" , &a , &b);
for(c = b ; c > 0 ; c--)if( a % c == 0 && b % c == 0)break;
printf("%d",c);
return (0);
}
(16)キーボードから入力した二つの整数の最小公倍数を求めるプログラム
(intの正の最大を2147483647と仮定)
int main(void){
int a , b , c = 1;
scanf("%d %d" , &a , &b);
while(++c < 2147483648)if(c % a == 0 && c % b == 0)break;
printf("%d" , c);
return (0);
}
以下、おまけとして過去に書いたソート等へのプログラムへのリンク
- 挿入ソート
- シェルソート
- 選択ソート
- バブルソート
- バケットソート
- クイックソート
- クイックソート(再帰)
- ツェラー(Zeller)の公式
- フィボナッチ数列(再帰なし及び再帰あり)
- 階乗(再帰なし及び再帰あり)
こういったC言語の勉強では柴田望洋さんの本がお勧め
昨日紹介しました曜日を求める式「ツェラー(Zeller)の公式」、参考までにC言語で書いてみました。
別に他の言語で書いてもよいのですが、せっかくこのblogにC言語カテゴリがあるので。
#include <stdio.h>
int main(void){
int y,m,d,h;
char *w[7]={"日","月","火","水","木","金","土"};
printf("年を入力してください：");
scanf("%d",&y);
printf("月を入力してください：");
scanf("%d",&m);
printf("日を入力してください：");
scanf("%d",&d);
if(m < 3){
y--;
m+=12;
}
h = (y + y/4 - y/100 + y/400 + (13 * m + 8)/5 + d)%7;
printf("その日は%s曜日です",w[h]);
return 0;
}
とても人気がないように思えながらも、実はC言語を目的としてこのblogに足を運んでくださっている方、かなり多いみたいです。
これまでにソートとして挿入ソート、シェルソート、選択ソート、バブルソート、バケットソート(ビンソート)、クイックソートを紹介してきました。
また、フィボナッチ数列や階乗の再帰呼び出しについても書きましたね。
それら過去の記事に興味がある方はC言語のカテゴリーをご覧ください。
前回の最後にて告知しましたように、今回はクイックソートの再帰呼び出しバージョンです。
詳しい説明は省きますが、区間を分割するたびに自身を呼び出す仕組みになっています。
/* クイックソート関数(再帰版)ここから */
/* data[]:データ格納配列 nlef:ソートする範囲の先頭添字 nrig:ソートする範囲の末尾添字*/
void sort(int data[],int nlef,int nrig){
int i , cen , clef , temp;
if(nlef < nrig){
/*区間の中心を基準値として取得*/
cen = (nlef + nrig) / 2;
/*区間の基準値と区間の先頭を交換*/
temp = data[nlef];
data[nlef] = data[cen];
data[cen] = temp;
clef = nlef;
for(i = nlef + 1 ; i <= nrig ; i++){
/*区間の基準値の右に基準値より小さい数値を並べる*/
if(data[i] < data[nlef]){
temp = data[i];
data[i] = data[clef];
data[clef] = temp;
}
}
/*基準値を自分より小さい数値と大きい数値の間に移動する*/
temp = data[nlef];
data[nlef] = data[clef];
data[clef] = temp;
/*基準値より小さい範囲のソート*/
sort(data , nlef , clef-1);
/*基準値より大きい範囲のソート*/
sort(data , clef+1 , nrig);
}
}
/* クイックソート関数(再帰版)ここまで */
C言語について書くの、非常に久しぶりですね。
このblogにC言語プログラム目当てで来ている方がありがたいことにけっこう多いようなので、早く書こうとは思ってはいたのですが。
C言語のソート紹介シリーズ、挿入ソート、シェルソート、選択ソート、バブルソート、バケットソート(ビンソート)ときまして、今回はクイックソートについて書かせていただきます。
過去の記事に興味がある方は右側のカテゴリより「C言語」をお選びください。
クイックソートの原理について簡単に説明いたします。
並んだデータの中から一つの基準値を選び、それより大きいグループと小さいグループに分割します。
分割したグループの中でまた基準値を選び、それより大きいグループと小さいグループに分割します。
全体が順番通りに並ぶまでこの繰り返しを続けます。
名前にクイックとついています通り、他のソートアルゴリズムに対して高速だと言われています。
ただし、「平均すれば速い」ということであり「すべての場合について他のアルゴリズムより速い」わけではありません。
小規模な場合やある程度整列が済んでいる場合等、クイックソートが不向きなこともあります。
大規模なデータをクイックソートである程度まで並び替え、それから別のソート方法を使うこともあるようです。
データが「86543271」のときの使用例は以下の通りです。
・中心を基準とする。
「865(4)3271」
・基準より小さいものを左、大きいものを右に移動する。
「132(4)6578」
・基準の左右の中心を新たな基準とする。
「1 (3) 2 」4「 6 (5) 78」
・新たな基準を元に、大小で左右に分割する。
「21 (3)」4「(5) 678」
・まだ並べ変わっていない部分「21」について、基準を設けて左右に分割する。
「1(2)」345678
・完成。
「12345678」
以下、C言語で書いたクイックソートのプログラム例です。
一例であり、また、同一の値が存在する場合を考慮しておりません。実際には基準の取り方を工夫する等して、効率の向上を計ります。
ソートを行う関数部分のみです。
/* クイックソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i , p , lef[num] , rig[num] , nlef , nrig , cen , clef , temp;
p = 0;
/*左端と右端の添え字を保持*/
lef[p] = 0;
rig[p] = num - 1;
while(p >= 0){
/*現在の区間の左端と右端を取得*/
nlef = lef[p];
nrig = rig[p];
p--;
/*現在の範囲のソート完了と判断してループの先頭へ*/
if(nlef >= nrig)continue;
/*区間の中心を基準値として取得*/
cen = (nlef + nrig) / 2;
/*区間の基準値と区間の左端を交換*/
temp = data[nlef];
data[nlef] = data[cen];
data[cen] = temp;
clef = nlef;
for(i = nlef + 1 ; i <= nrig ; i++){
/*区間の基準値の右に基準値より小さい数値を並べる */
if(data[i] < data[nlef]){
clef++;
temp = data[i];
data[i] = data[clef];
data[clef] = temp;
}
}
/*基準値を自分より小さい数値と大きい数値の間に移動する*/
temp = data[nlef];
data[nlef] = data[clef];
data[clef] = temp;
/*分割した区間のそれぞれの左端と右端を保持*/
p++;
lef[p] = nlef;
rig[p] = clef-1;
p++;
lef[p] = clef+1;
rig[p] = nrig;
}
}
/* クイックソート関数ここまで */
近日中にクイックソートを再帰で書いたプログラムを掲載する予定です。
C言語のソート紹介シリーズ、挿入ソート、シェルソート、選択ソート、バブルソートと来まして、今回はバケットソート(ビンソート)です。
原理は非常に単純です。
たとえば、1以上100以下の間のランダムな十個の数値をソートしたいとします。
あらかじめ、要素数100の配列を用意しておくのです。すべて初期値は0とします。
そして、十個の数値を一つずつ見て、配列のその数値と同じ添え字の要素の値を1増やします。
十個の数値を見終えたときに、格納値が0ではない要素の添え字だけを見ます。
そして1から(もしくは100から)順番に、格納値の数が0ではない要素の添え字を表示します。
格納値の数が1なら1回、2なら2回、格納値の回数表示します。
これでソートの完了です。
高速ではありますが、ソートする値の上限に合わせて要素を用意するため、非常にメモリ効率が悪い場合があります。
たとえば、並べ替えたい数は5個なのに、その値の範囲が1～30000だったなら、配列は30000個の要素を用意しないといけないのに、実際には多くともそのうちの5個しか使わないわけです。
また、値の範囲がわかっていない場合も使えません。
データが「５４５３１」のときの使用例は以下の通りです。
・配列をすべて0で初期化する。「配列[1]=0 配列[2]=0 配列[3]=0 配列[4]=0 配列[5]=0」
・一番左の数値と同じ配列の値を1増やす。「配列[5]=1」
・左から二番目の数値と同じ配列の値を1増やす。「配列[4]=1」
・左から三番目の数値と同じ配列の値を1増やす。「配列[5]=2」
・左から四番目の数値と同じ配列の値を1増やす。「配列[3]=1」
・左から五番目の数値と同じ配列の値を1増やす。「配列[1]=1」
・結果「配列[1]=1 配列[2]=0 配列[3]=1 配列[4]=1 配列[5]=2」
・格納されている値の数だけ添え字を表示する。「１３４５５」
以下、C言語で書いたバケットソートのプログラムです。
ソートを行う関数部分のみです。
/* バケットソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int max = 101 ;/* max：値の最大値+1 値は0～100と仮定*/
int array[max],i,j,k = 0 ; /* array：バケット */
for(i = 0 ; i < max ; i++)array[i]=0;
for(i = 0 ;i < num ; i++){
array[data[i]]++ ;
}
for(i=0 ; i < max ; i++){
for(j = array[i] ; j > 0 ; j--){
data[k++] = i ;
}
}
}
/* バケットソート関数ここまで */
フィボナッチ数列ってご存知でしょうか？
知らない人の方が多いかもしれないですね。
「今見ている数値が前の二つの数値の和に等しい数列」のことです。
「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;
}
}
}
}
/* バブルソート関数ここまで */
挿入ソート、シェルソートと来まして今回は選択ソート(セレクションソート)を紹介いたします。
選択ソートはとても単純な考え方のソートです。
まず、データの中から最も小さな値を見つけ出してそれを抜き出す。
次に残った中から最も小さな値を見つけ出してそれを抜き出す。
その繰り返しを最後の一つになるまで続けます。
非常に分かりやすいですが、比較回数が多いため、実際にほとんど使われることはないようです。
データが「８５４２６３７１」のときの数値の変化例を以下に書いてみます。
・一番小さい数値を見つけて一番左に持ってくる。「(１)８５４２６３７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１(２)８５４６３７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２(３)８５４６７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３(４)８５６７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３４(５)８６７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３４５(６)８７」
・残った中で一番小さい数値を見つけて残った中の一番左に持ってくる。「１２３４５６(７)８」
以下、C言語で書いた選択ソートのプログラムです。
ソートを行う関数部分のみです。
/* 選択ソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,n,temp;
for(i=0;i<num-1;i++){
n=i;
for(j=i+1;j<num;j++)if(data[j]<data[n])n=j;
/*データの入れ替え*/
temp=data[i];
data[i]=data[n];
data[n]=temp;
}
}
「C言語プログラミング2(挿入ソート)」に続きまして、またソート(つまりばらばらの順番に並んだデータを並べ替えること)のお話です。
今回ご紹介するのはシェルソート(改良挿入ソート)と言いまして、前回の挿入ソートの改良版です。
挿入ソートには「用意されているデータがある程度整列されているときは高速である」という長所がある代わりに「用意されているデータが整列状態と遠いほど低速となる」という欠点があります。
シェルソートはその欠点を改善するため、いきなり全体に挿入ソートをするのではなく、部分毎に挿入ソートを行います。
そして、その部分を徐々に広げていき、最終的にある程度整列された状態で挿入ソートをするというものです。
データが「８５４２６３７１」のときの数値の変化例を以下に書いてみます。
まず、データとデータの間隔を4として挿入ソートを行う。
・1番目の数値と5番目の数値で挿入ソート。「(６)５４２(８)３７１」
・2番目の数値と6番目の数値で挿入ソート。「６(３)４２８(５)７１」
・3番目の数値と7番目の数値を挿入ソート。「６３(４)２８５(７)１」
・4番目の数値と8番目の数値を挿入ソート。「６３４(１)８５７(２)」
次に、データとデータの間隔を2として挿入ソートを行う。
・1番目から3番目と5番目と7番目の数値で挿入ソート。「(４)３(６)１(７)５(８)２」
・2番目から4番目と6番目と8番目の数値で挿入ソート。「４(１)６(２)７(３)８(５)」
次に、データ間隔1として挿入ソートを行う。
・全データでの挿入ソート。「１２３４５６７８」
以下、C言語で書いたシェルソートのプログラムを掲載します。
ソートを行う関数部分のみです。
/* シェルソート関数ここから */
/* data[]:データ格納配列 num:配列要素数 */
void sort(int data[],int num){
int i,j,n,temp;
for(n=num/2;n>0;n=n/2){/*間隔を徐々に狭めていく 最終的には1*/
for(i=n;i<num;i++){/*nで決まっている間隔で一つずつ挿入ソート*/
temp=data[i];
/*temp以下の値が出るまで配列を右にずらす*/
for(j=i;j>n-1;j=j-n){
if(temp>data[j-n])break;
data[j]=data[j-n];
}
data[j]=temp;
}
}
}