黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

配列の並び替えゲームを作成する

今回は配列の中身を並び替えて行くような簡単なゲームを作成したい。


問題





尚問題を解く上で、以下の配列(集合)の各要素を出力する関数void array_printf(int array)を断り無しに使って良い。


問題の解説


要件(i)を満たす


まず問題文の(i)「n=9」の要件を満たす事を考えよう。もちろん各ループの部分等に9と書いても良いが、要素数が変更になった時などに不便そうだ。ここで後で要件が変更になっても良いような設計を心がけたいのでdefineを使い、「#define PLONLEM_NUMBER 9」と定義すれば良い。今度は問題の集合A={1,2,3,4,5,6,7,8,9}と集合Bは、配列ないしは構造体を使って以下のように定義すれば良い。


要件(ii):配列を入れ替える関数array_swapを定義する


以下のプログラムは配列の参照渡しというテクニックを使い、配列の(i-1)番目と(j-1)番目(集合Bのi番目とj番目)を入れ替える関数を実装した。



一方、本プログラムを呼び出す時はarray_swap(配列名)、構造体内に配列がある場合はarray_swap(構造体名.配列名)と言うように定義して行く。実行すると配列の(i-1)番目と(j-1)番目が入れ替わっているのが分かるはずだ。

要件(iii)後半を満たす


まず問題文の「尚,1<=i<=9,1<=j<=9以外の数字が入力されたときは...」以下の部分を実現できる関数int input_check(int value)を定義しよう。入力した値が0〜8の時は、そのまんま入力値を返す。又そうでない時は0を返せばよいはずだ。ここまでを関数として書くと以下のようになる。


判定に必要な関数int array_checkを用意


今度はゲームを終了するかどうかの判定を行う関数int array_check(int answer,int question)を作成して行く。ここで、int answer,int question[]の各要素の値が一致している個数を数え、それらが配列の要素数PLOBLEM_LENGTHと一致するならば1を、そうでない場合は0を返す関数を製作すればよい。


要件(iii)前半を満たす


ここまでで、ゲームに必要な部品は全てそろった。後はゲームの主な部分を設計していく。残りは問題文の「Bの要素のi番目とj番目を入れ替え、Aと一致するまで続けるゲームを考える」「iとjは手入力で指定できるようにする」部分の設計を行えば良い。主な流れはarray_check関数で配列の確認。1文字目、2文字目の入力と確認。配列を入れ替えると言った順序で作業が進む。これらのルーチンをフローチャートにまとめると、以下のようになる。





ソースコード


上記の作業工程により設計に必要な説明は終了したので、ソースコードを掲載していく。


実行結果の検証(デバッグ)


検証(デバッグ)の要件


デバッグで確認するべき事柄は以下のようになる。



  • 関数input_checkの例外の動作:入力に0〜8以外を入力したとき、きちんと0が入力されているか?

  • 関数array_swapの動作:きちんと配列が入れ替わっているか?

  • 関数array_checkの動作:二つの配列の順序が一致したとき、ゲームが終了するか?

関数input_checkの動作確認


まず1文字目,2文字目にそれぞれ-1を入力してみる。同じ値を入力すると配列の0番目と0番目をswapすると言う事となり、同じ配列が返されれば良い。実際に入力すると、以下に同じ配列が返されている。依って関数input_checkの例外処理は無事行われている事が分かる。




関数array_swap,array_checkの動作確認


次は実際にゲームをプレイしてみて、きちんと配列が入れ替わっているか?ゲームが終了するかの確認を行って行く。今回ゲームのルーチンにwhile文を用いているので、無限ループになっていないかが心配な所だ。今回の場合、配列Bを複数回入れ替えて配列A={1,2,3,4,5,6,7,8,9}と一致させていく。そこで以下のように検証したところ、複数回の配列の入れ替えを行った所、2つの配列は一致し、ゲームが終了した事が確認された。




後書き


今回配列(集合)の2つの要素を入れ替えるゲームを作成したが、これは数学の置換と言う分野にあたる。置換とは、例えば6つの要素からなる集合:M の要素を1から6までの番号で表して,M={1,2,3,4,5 6} とする。基本となる元の並び方(順列)を,1,2,3,4,5,6とし,これに任意の順番を換えた並び(←元通りの1,2,3,4,5,6 の並びも含める),例えば,2,3,4,5,6,1 の順にそれぞれ要素を置き換える変換(=写像)σ:1→2,2→3,3→4,4→5,5→6,6→1を6文字の置換という。ここで一般に置換とは、n個の要素からなる集合l_n={1,2,.........,n\がある。ここで有限個の要素からなる集合l_n={1,2.........,n}からM自身の1対1写像,σ:1 ->i,2 -> j,........,n -> kを置換と言う。尚以上の説明は、「ときわ台学/代数入門/置換群、対称群」を参考にした。


又今回の事例のように集合の2つの要素を入れ替えるような操作を互換と言う。例えば15パズルなども升目の2つの絵柄を入れ替えて、ゲームを進めて行くのでこれも互換である。又並び替え(互換)の問題を作るとき、互換を何回行っても解決できないケースを存在する。「カードのシャッフルなど/教務エッセイ(算数):日能研」15パズルの最後の2つを入れ替えた状態でスタートすると、どうやっても直せない現象が存在する。問題を設計する上でも、こういった現象が起こらないような問題の設計を心がけたい。


最後に本問題を置換や互換を使って定義しなおした物を紹介したい。読者の皆様の参考になれば幸いである。