C言語編第二十五章 練習問題2
今回は前回予告したように例題を多く揃えようと思います。本当は例題のみにしようかと思ってたんですが、例題を増やすために少し解説を最初にいれます。ASCIIコード今回取り扱おうとしている問題は主にランダムなものを昇順(小→大の並び)にしようというものです。しかし今までの内容では数値しか並べ替える事ができません。文字や文字列を並べ替えるにはどうしたらいいのか。そのためにまずASCIIコードを解説します。コンピュータ上ではアルファベット、平仮名、漢字等いくつかの文字を扱う事ができます。実はこれらは様々な文字コードというものによって可能となっているのですが、その辺は特に深入りしません。文字コードのうちの1つであるASCIIコードはアルファベットのような半角の文字を表現するのに必要なものです。とりあえずASCIIコードを表示するプログラムを載せてみます。int型だというのに%cを使っていますね。これは実行してみるとi = 97の時%dでは97、%cではaが表示されているのが分かるかと思います。ASCIIコード上ではaという文字は97という数字と対応しているという事になります。そしてbは98、cは99、dは100…、zは122です。つまり逆にこういうプログラムを作る事もできるわけです。今度はchar型で%dを使っています。これも実行すると上と同じようにaは97(以下略)となりますね。このようにアルファベットの大小の並びは小さい方からいうと最初がa、最後がzとなるわけです。これならアルファベットも順番に並べ替える事ができますね。 まぁ大文字小文字が混じるとそうもいきませんが…。ちなみにASCIIコードの0~31と127は制御文字というものだそうで、文字化けしてしまってます。また、32はスペース(空白)です。それ以外は普通の文字として認識できるものになっていますね。まぁここではアルファベットも小さい方からA,B,C…,Zやa,b,c…,zと並んでいるということが分かれば十分なので制御文字って何? とか気にするのは止めた方がいいです^^;ソートの方法それでは並べ替え(以下ソート)の方法を解説します。ソートをする手段はいくつかありますが、ここでは選択ソートにしようと思います。理由はいくつかあるソート手段の中でも比較的簡単だからです。では、いつも通り先に選択ソートプログラムの例を示します。main関数選択ソート関数かなり長くなってしまいましたね…。main関数は配列の値を0~NUM - 1まで全て表示するだけなので説明はいらないですね。問題なのは選択ソート関数の方だと思います。まず、戻り値は無しで、引数はソートする対象となる配列です。関数内で宣言されている変数はforループに使う変数i, j。そして最小値が何番目にあるかを覚える変数pos(英語のpositionから)。最後に最小値を保存する変数tmp(英語のtempから)。あとは、forの二重ループ内でソート処理をするということになってます。iが0と1の時の処理を追ってみます。i = 0の時まず、pos = iによってposに仮の最小値の場所としてiを代入します。そしてtmp = a[pos]でtmpに仮の最小値を代入します。次にforループ内に入り、tmpの値と配列の1~NUM - 1の値を比較します。tmp > a[1]は 1 > 3 で偽。 tmp > a[2]は 1 > 6で偽。tmp > a[3]は 1 > 4 で偽。 tmp > a[4]は 1 > 7で偽。tmp > a[5]は 1 > 9 で偽。 tmp > a[6]は 1 > 2で偽。tmp > a[7]は 1 > 0 で真。ここで真になったのでif文の処理が実行されます。posにj(ここでは7)が代入され、tmpにa[pos](ここではa[7]、すなわち0)が代入されます。これでif文の処理は終了。またループに戻ります。tmp > a[8]は 0 > 5 で偽。 tmp > a[9]は 0 > 8 で偽。これで0~NUM - 1までの値の中で最小値はa[7]の0だという事が分かりました。この処理をしていけばループ終了時に必ずposには最小値が何番目か。tmpには最小値が代入されるわけです。そのため、後はa[pos]にa[i](ここではa[7]にa[0])の値を代入。a[i]にtmpの値を代入します。これでa[0]には配列内の最小値が代入されました。さらにa[0]の中の値もa[pos]の所に移動しただけで削除されていません。普通にa[i] = tmpだけを行なってしまうとa[0]に本来あったはずの値は消えてしまいますからね。これはかなり重要な事です。値を入れ替える時は必ず何かに先に代入される方の変数の値を保存しておかないといけません。i = 1の時i = 0の時にも書いたので、forループ以前の所は省略します。forループ内ではtmpの値と配列の2~NUM - 1の値を比較します。(ちなみにtmpの値がNUM - 1の値になった時は比較するものが存在していないので外側のループは i < NUM - 1となっています。)tmp > a[2]は 3 > 6 で偽。 tmp > a[3]は 3 > 4で偽。tmp > a[4]は 3 > 7 で偽。 tmp > a[5]は 3 > 9で偽。tmp > a[6]は 3 > 2 で真。真になったので、if文の処理が実行され、posにはjの値(ここでは6)が代入されます。そして、tmpにはa[pos]の値(ここでは2)が代入されます。tmp > a[7]は 2 > 1 で真。真になったので、posには7、tmpには1が代入されます。tmp > a[8]は 1 > 5 で偽。 tmp > a[9]は 1 > 8 で偽。ここでループを抜けて、後はa[pos]にa[i](ここではa[7]にa[1])の値が代入されa[i]にtmpの値が代入されます。 これでa[1]には配列内で2番目に小さい値が代入された事になります。これで選択ソートがどのような処理で結果的にa[0]に最小値そこから順番に大きな値が代入されていくかが分かっていただけたかと思います。(ちなみに不等号の向きを逆にすると逆にa[0]が最大値になります。)かなり長い前置きになりましたがいよいよ練習問題をいくつか出します。練習問題1:int型配列a[NUM] = {43, 553, 564, 242, 56, 67, 312, 3221, 789, 301}の中からfgets,sscanf関数を使ってどれかを入力し、それが配列で何番目にあるかを表示して下さい。 どれも入力されなかった場合の処理は今回は無視します。(43は1番目とし、NUMは10とする)実行結果1 22:int型配列a[NUM] = {1, 3, 6, 4, 7, 9, 2, 0, 5, 8}を降順(昇順の逆)ソートして下さい(NUMは10とする)。実行結果3:char型配列a[NUM] = {'b', 'd', 'g', 'e', 'h', 'j', 'c', 'a', 'f', 'i'}を昇順ソートして下さい(NUMは10とする)。実行結果4:char型2次元配列a[NUM][LENGTH] = {"ishikawa", "toyama", "fukui", "aichi", "iwate"}を昇順ソートして下さい(NUMは5、LENGTHは10とする)。実行結果5:0~9までの数を20個入力して、それぞれ何個入力されたかを表示して下さい。実行結果解答例ここまで来たらこの第二十五章は終了です。今回はやっぱりソートという実用的なアルゴリズムを覚えていただきたいですね。今回例題は7問用意してたんですが、後2問は私自身が面倒すぎると判断したので止める事にしました。そのため5問になりましたが、一番難しいのは4ですかねぇ…。前回の章の内容を十分理解してれば何とかなると思いますが、やっぱり難しいですからね、4。そして5はパソコン甲子園をやっている際にネット上で発見した面白い問題の簡易版です。上手くやれば相当簡単です^^;ここに書いてあることが分からない場合は記事にコメント、もしくはメールをお願いします。