Home

Programming Tips

使えるアルゴリズムの紹介等をします。

日付のソート 2006/08/29

[2005年12月31日と2006年8月28日はどっちが新しいか]

日付順にソートする事を考えます。
上の表題だと、先に年を見て数字の大きいほう（2006年）が新しいことが分かります。
もし年が同じだと月で判定して、月が同じだと日で判定ということになるでしょう。
この思考をプログラムに組み込んでもいいですが、条件文が多くなってしまうので、もっと簡潔に記述する方法を考えます。

Windowsでファイル名の整理をよくする人なら思いつくと思いますが、年月日を一つの整数にする方法があります。
2005年12月31日なら、20051231。
2006年8月28日なら、20060828。
20051231と20060828を比較すれば20060828のほうが数字が大きいので、日付が新しい事が分かります。
ここで気をつけることは、一桁の月や一桁の日の場合。頭に0をつけて二桁にします。これで桁数を合わせます。
この8桁の数字を一つの整数と見なして大小判定すれば、日付の新しいほうが分かります。
この整数の作り方は、プログラム(C言語)で書けば、
sprintf( date_str, "%04d%02d%02d", year, mon, day );
というようにsprintf関数で整形すればすぐ済みます。
sprintfを使わないのであれば、
int date = 10000*year + 100*mon + day;
と計算する方法もあります。

重複せずにランダムで順列作成 2006/07/07

[0, 5, 1, 2, 4, 3 ]

以下のようなクイズを作る事を考えます。
・全部で一定数の問題があり、全問解けば終了とする。
・問題はランダムで１問ずつ出題される。
・１問解いたら次のページへ行き解答のチェックをして、次の問題が出題される。
・問題は重複せずに出題される。

ポイントは「問題は１問ずつ」で「重複しない」事です。
まず、重複しない順列を作る方法を考えます。

  1. 問題数（MAXと定義）分の要素数を持つ空配列を用意する。
    int q[ MAX ];

  2. その配列に０～MAX-1まで数値を入れます。
    for( i = 0; i < MAX; i++ ){ q[ i ] = i; }

  3. この時点で配列は「0,1,2,...,MAX-1」という数値が入っています。
    次にこの中身を乱数を使用してバラバラに入れ替えます。
    考え方はこのようにします。
    1. 添字が「０」の場所と「０～MAX-1」のどれかの場所を入れ替える。
    2. 添字が「１」の場所と「１～MAX-1」のどれかの場所を入れ替える。
    3. 添字が「２」の場所と「２～MAX-1」のどれかの場所を入れ替える。
    4. 繰り返し。
    5. 添字が「MAX-2」の場所と「MAX-2～MAX-1」のどれかの場所を入れ替える。
    6. 終了。
    これでバラバラになります。以下はプログラムです。
    乱数を使用するのでSeedを与えて初期化を行います。

    srand( 123456789 );
    for( i = 0; i < MAX; i++ ){
     ran = rand() % ( MAX - 1 - i ) + i;
     temp = q[ i ];
     q[ i ] = q[ ran ];
     q[ ran ] = temp;
    }

以上で順列を作ることは出来ましたが、次は１問解いた後に、次のページで２問目を出題させるようにします。
乱数のSeedの設定をしましたが、コンピュータはこのSeedの数値によって乱数のパターンを決定しています。
だから、この値が同じであれば毎回同じ順列が発生します。
よって、１問ずつ問題が出題される場合でも、この乱数のSeedを保持しておけば、 次の問題出題時にこのSeedを使用して問題を同じ順番にする事が出来ます。
１問目は問題番号q[0]、２問目は問題番号q[1]、３問目は問題番号q[2]となっています。

このアルゴリズムを使って作ったのがこのクイズです。
クイズ はるキッチン