[前へ]   [目次へ]   [次へ]

やり方を考えてみる(1)(C/C++)

前回までの高低当てゲームをもう少し面白くしてみましょう。
前回までのゲームの弱点は、「ゴールがない」のと「運任せ」な点ですね。
そこで今度は「0〜9までの数がそれぞれ1回ずつ出現して、全て当てればクリア」としてみます。

それぞれ一回ずつしか出現しないようにするので、「前回と同じ」が出ることはなくなります。
なので、「前回と同じ」選択肢は除去してしまいましょう。

さて、「一回ずつしか出現しない」という条件で数値を出現させるということは、
ただのランダムではなく、出現させる値を制御する必要があります。

今回はこの「一回ずつしか出現しない」を作るためのやり方を考えてみようと思います。
いきなり考えようとしても「わからないよー」ってことになるかと思いますが、
関連付けられないだけで実はやり方を知っているってことは結構あるものです。

トランプでも紙に0〜9を書いて10枚のカードを作ってもなんでもいいので、
0〜9または1〜10のカードを一枚ずつ用意してください。
そしてそれを使って「一回ずつしか出現しない10個の数字列」を実践してみてください。

カードをシャッフルしても、一枚ずつ適当に取っていく方法でも上記を満たすことはできます。
割と簡単にできますよね？
これをプログラム上に記述すればいいだけのことなのです。
もう一度最初の状態に戻して、今度は「自分が何をしているか」を細かく確認しながらやってみてください。

注意深く見れば、かなり単純な操作が多いことに気が付くと思います。
それらはこれまでにこの講座で解説した内容だけで十分に対応できるはずです。


とはいえ、慣れがないとなかなか気付けないかもしれません。
私が思いついた方法について、いくつか以下に解説しておきます。
●トランプのように切ってみる(1)
●トランプのように切ってみる(2)
●同じ番号が出ないように適当に選んでみる
●一枚ずつ抜き取ってみる
●適当に交換してみる
解説終点へ

●トランプのように切ってみる(1)
カードを全て重ねて、スタンダードに切ってみる方法です。
「全て重ねられたカード」の中から一部を抜き取り、一番上に重ねていきます。
「全て重ねられたカード」は配列として表現することができます。
int cards[10]={0,1,2,3,4,5,6,7,8,9};
これは、0〜9の10枚のカードが0から重なっている状態と考えることもできます。
配列は「順番に並んでいる、または重なっている集合」と捉えると実践的な扱いがしやすくなります。

この方法では一部を抜き取って一番上に重ねるわけですが、
ここで「一番上」が最初(0番)の要素か最後(9番)の要素かは重要ではありません。
なぜなら「一番下」にカードを戻してもシャッフルとしては成立するからです。
今回は、最初(0番)の要素を「一番上」として扱うことにします。

プログラム上で何枚ものカードを一度に移動させるのは非常に面倒なので、
一枚ずつ移動させていくのが簡単です。
やり方としては、
(1)一時変数を二個作成します。
int n;//カード番号を退避する(手に持つカード)
int index;//抜き取るカード位置を保持する変数
(2)抜き取るカード位置をランダムに決定します。
index=rand()%10;//有効範囲は0〜9
(3)決定した位置からカードを一時変数へ抜きます。
n=cards[index];
(4)0番から抜いた位置までは順番が変わるので、一個ずつずらします。
for(;index;index--)cards[index]=cards[index-1];
(5)最後に、一番上(0番)に手に持ったカード(n)を置きます。
cards[0]=n;
これで、一回分の「カード群から一枚抜いて一番上に戻す」が完成です。

しかし、手順4がなんだかややこしいです。
さらに、この方法は通常何度も繰り返さないと上手くシャッフルできません。
同じやり方である以上、このコードも一回実行しただけでは全然並び変わらず、
手順をそれなりに繰り返す必要があります。

また、手順全体をループで囲うことを考えると、手順4は二重ループになります。
二重ループは演算数が掛け算になるので、うっかりすると恐ろしい数になります。
外と中ともに10回だとしても100回の
cards[index]=cards[index-1];
が実行されるわけです。
現代のCPUならこの程度の演算は秒速で億はこなせるので100回や10000回ぐらいなんの問題もないのですが、
数千万回ループとかやってる時に二重ループを作ると致命的なことがあるので覚えておいた方がいいです。
インタプリタの場合はC/C++に比べて数十〜数百倍遅いことが多いので100万回程度でも瞬間遅れているようにみえることがあります。

全部まとめると以下のようになるでしょうか。
<  1>
<  2>
<  3>
<  4>
<  5>
<  6>
<  7>
<  8>
<  9>
< 10>
< 11>
< 12>
< 13>
< 14>
< 15>
< 16>
< 17>
< 18>
< 19>
< 20>
< 21>
< 22>
< 23>		#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
   int cards[10]={0,1,2,3,4,5,6,7,8,9};
   int n;//カード番号を退避する(手に持つカード)
   int index;//抜き取るカード位置を保持する変数
   int i;
   srand(time(NULL));
   for(i=0;i<1000;i++){//1000回ぐらい切ってみましょう
      index=rand()%10;//有効範囲は0〜9
      n=cards[index];
      for(;index;index--)cards[index]=cards[index-1];//(1)
      cards[0]=n;
   }
   //どれくらいシャッフルできているか、確認してみます。
   for(i=0;i<10;i++)printf("cards[%d]:%d\n",i,cards[i]);
   //終了待ち
   getchar();
   return 0;
} 
実行例：
cards[0]:6
cards[1]:2
cards[2]:4
cards[3]:7
cards[4]:9
cards[5]:5
cards[6]:3
cards[7]:1
cards[8]:8
cards[9]:0

(1)15行の for(;index;index--)cards[index]=cards[index-1] は何をしているかというと、
「引き抜いた位置より低い要素を一個ずつずらす」ということをします。
index にたとえば2を代入してみます。
条件式は2==真なので実行、 cards[2]=cards[2-1] となり、1番を2番に上書きします。
続いて、 index-- で index は1になり、同様に0番を1番に上書きします。
最後は index が0なので偽となり、ループが終了します。
このパターンでは0が評価されないのが逆に都合よく作用しています。
このように連鎖的に上書きしていくと、結果的に一個ずつずれたようになります。
最後に0番に抜いた要素を代入すれば、入れ替えの完了です。

さて、1000回も切ってる割には、なんか微妙な切れ具合ですね。
偶数と奇数が集合してしまってる感じです。
何回か試してみましたが、やはりなんらかの法則性が出てしまうようです。
でも「一回ずつ」という条件は守られています。

実際にトランプでやっても「切れてないな〜」と感じることがあるように、
このやり方はなかなかキレイにシャッフルできないのです。
数学的に計算すればキレイに切るのに必要な回数は算出できるはずですが、恐らく相当な量が必要でしょう。


●トランプのように切ってみる(2)
トランプの切り方その2です。
カードを二山に分けて混ぜ合わせる切り方でやってみましょう。
今度は二山に分けたカードとして二個の配列から始めてみましょう。
int src1[5]={0,1,2,3,4};
int src2[5]={5,6,7,8,9};
そして、混ぜ合わせた結果を格納する配列を用意します。
int cards[10];
ついでに分けたカードの現在位置を格納する変数を3個用意しておきます。
int src1_used,src2_used,cards_used;

さて、手順としてはどちらかの山をランダムに選択して一枚ずつ結果配列に積んでいきます。
(1)現在位置格納用の変数をクリアします。
src1_used=0;
src2_used=0;
(2)カード総枚数分、10回のループを作成します。
for(cards_used=0;cards_used<10;cards_used++)
(3)乱数と、既に山のカードを使い果たしている場合を考慮して山の選択をします。
if(((src1_used<5)&&(rand()%2))||(src2_used>=5))
(4)(3)が真になった時は、 src1 から src1_used が示す位置のカードを結果配列に入れ、 src1_used を1進めます。
cards[cards_used]=src1[src1_used];
src1_used++;
(5)(3)が偽になった時は、 src2 から src2_used が示す位置のカードを結果配列に入れ、 src2_used を1進めます。
else
cards[cards_used]=src2[src2_used];
src2_used++;
これで、1回のシャッフルの完成です。
二つの山からランダムに一枚づつ抜き出すことで、ある程度のシャッフルになります。
二回以上シャッフルする場合は、結果配列から山1と山2を作り直して続行します。

今回の鍵は手順3の条件分岐ですね。
ここで、 src1_used と src2_used はそれぞれの山から使った枚数を示しています。
山の枚数はそれぞれ5枚なので、これらの変数が5になっている時は山のカードを全て使い果たしていることになります。
したがって、 ((src1_used<5)&&(rand()%2)) は「山1から使った枚数が5未満=山1にカードが残っている」とき、
「乱数を使って二択分岐させる」ということになります。
さらに、 (src2_used>=5) がOR(片方または両方が真の時真)条件に指定されています。
これは「山2から使った枚数が5以上=山2を使い切っている」とき、「常に山1を選択する」ということになります。
なんで「〜が5」じゃなくて「5以上」にしてあるかというと、6などが入っている状況が万一発生した時に暴走しないようにするためです。

カードの総数とループ回数は一致させてあるので、「山1も山2も使い切っている」という状況はないはずです。
そのため、その条件は省略されています。

今回の分を全部まとめると以下のようになるでしょうか。
<  1>
<  2>
<  3>
<  4>
<  5>
<  6>
<  7>
<  8>
<  9>
< 10>
< 11>
< 12>
< 13>
< 14>
< 15>
< 16>
< 17>
< 18>
< 19>
< 20>
< 21>
< 22>
< 23>
< 24>
< 25>
< 26>
< 27>
< 28>
< 29>
< 30>
< 31>
< 32>
< 33>
< 34>
< 35>
< 36>
< 37>
< 38>
< 39>		#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
   int src1[5]={0,1,2,3,4};
   int src2[5]={5,6,7,8,9};
   int cards[10];
   int src1_used,src2_used,cards_used;
   int i;
   
   srand(time(NULL));
   for(i=0;i<200;i++){//今回は200回ぐらい切ってみましょう
      src1_used=0;
      src2_used=0;
      for(cards_used=0;cards_used<10;cards_used++){
         if(((src1_used<5)&&(rand()%2))||(src2_used>=5)){
            cards[cards_used]=src1[src1_used];
            src1_used++;
         }
         else{
            cards[cards_used]=src2[src2_used];
            src2_used++;
         }
      }
      for(cards_used=0;cards_used<5;cards_used++){//(1)山1を作り直します
         src1[cards_used]=cards[cards_used];
      }
      for(;cards_used<10;cards_used++){//(2)山2を作り直します
         src2[cards_used-5]=cards[cards_used];//(3)
      }
   }
   //どれくらいシャッフルできているか、確認してみます。
   for(i=0;i<10;i++)printf("cards[%d]:%d\n",i,cards[i]);
   //終了待ち
   getchar();
   return 0;
} 
実行例：
cards[0]:3
cards[1]:8
cards[2]:5
cards[3]:6
cards[4]:2
cards[5]:9
cards[6]:0
cards[7]:7
cards[8]:1
cards[9]:4

(1)27行の山1作り直しは、結果配列の頭5枚をそのままコピーしています。
(2)30行の山2作り直しは、直前のループで cards_used は5になっているので、初期化式を省略しています。
(3)31行は、 cards_used が5〜9の範囲でループするのに対して、 src2 は0〜4の要素しかないので、
位置あわせ用の-5が付いていますが、結果配列の後ろ5枚をコピーしています。

さて、今回のソースは先ほどに比べて長くて少々複雑ですが、シャッフル数を1/5にしている割には、
ホドホドに切れている感じです。数回試すと法則性が出る時もありますが、先の手法ほど強くはありません。

先ほども言ったように、ループ内のコードは「ソース上の行数×ループ数」分の処理があるので、
「1000回ループする1行」と「200回ループする5行」は、
1行当たりの処理量が同じと仮定するならば同じ処理量ということになります。
大量にループする行の記述は慎重に検討しないと、一回の演算数差が目に見える処理時間差として現れることもあります。
(特に動画やゲームでのピクセル単位の処理とかは、ループ数が簡単に秒速数千万に達するのでシャレになりません)


●同じ番号が出ないように適当に選んでみる
次は頭で考えながら紙に書いていくイメージの方法です。
適当に値を考えて、今まで選択していなければ採用し、既に選択していたら再度値を考え直します。

方法としては、適当な値の生成には乱数を使い、
それが結果配列に含まれていないことを確認しながら結果配列に積んでいきます。

必要な変数を定義します。
結果配列
int cards[10];
一時変数
int i,n,cnt;

(1)結果配列に格納している枚数を示す変数 cnt を初期化します。
cnt=0;
(2)結果配列に空きがある限りループさせます。
while(cnt<10)
(3)乱数を使って値を生成します。
n=rand()%10;
(4)生成した値が既に結果配列にないことを確認します。
for(i=0;i<cnt;i++)if(n==cards[i])break;
(5) (4)の結果が「見つからない」の場合だけ結果配列を更新し、 cnt を進めます。
if(i==cnt){
   cards[cnt]=n;
   cnt++;
}

今回のポイントは(4)(5)の判定です。
(4)はまず既に結果配列に入れているカード全てと生成した値を比較して、
同じ値があったらその場でループを終了させます。
ここでポイントなのは break が実行された場合は i<cnt を満たしたままループが終了する点です。
逆に、 break が実行されずにループが終了すれば i<cnt が満たされない状態、
加えて i は必ず1づつ増えるので i==cnt になっているわけです。

この条件が(5)の判定に繋がるわけです。
また、(5)で cnt が増えない=(4)で同値があった場合は、
同じ条件でループが再実行されることになり、結果として(4)で同値が見つからない条件を満たすまで進みません。

今回の分を全部まとめると以下のようになるでしょうか。
<  1>
<  2>
<  3>
<  4>
<  5>
<  6>
<  7>
<  8>
<  9>
< 10>
< 11>
< 12>
< 13>
< 14>
< 15>
< 16>
< 17>
< 18>
< 19>
< 20>
< 21>
< 22>
< 23>
< 24>
< 25>
< 26>
< 27>
< 28>
< 29>
< 30>
< 31>
< 32>		#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
   int cards[10];
   int i,n,cnt;
   
   srand(time(NULL));
   cnt=0;
   while(cnt<10){
      n=rand()%10;
      for(i=0;i<cnt;i++)if(n==cards[i])break;
      /*↑の行は↓と同義です(一行構文に一行構文が繋がっているだけ)
      for(i=0;i<cnt;i++){
         if(n==cards[i]){
            break;
         }
      }
      注釈ここまで*/
      if(i==cnt){
         cards[cnt]=n;
         cnt++;
      }
   }
   //どれくらいシャッフルできているか、確認してみます。
   for(i=0;i<10;i++)printf("cards[%d]:%d\n",i,cards[i]);
   //終了待ち
   getchar();
   return 0;
} 
実行例：
cards[0]:9
cards[1]:0
cards[2]:1
cards[3]:2
cards[4]:6
cards[5]:5
cards[6]:4
cards[7]:7
cards[8]:3
cards[9]:8

プログラムは非常に単純なのですが、ランダム性は微妙な感じです。
配列を並べ替えるタイプではないので、全体を繰り返す意味もありません。

またこの方法はカードの総数が増えると急速に処理量が増大します。
何故かと言えば、終盤になると選択できる要素が減少し、再試行率が上昇します。
最後に至っては「1/カード総数」でしか成功できません。
総数が増えると成功率が低い終盤が長くなるため、どんどん処理量が増えていくというわけです。

そのためこの方法はカード総数が非常に少ない場合でしかこの方法は使えないのです。


●一枚ずつ抜き取ってみる
今度はカードを横に並べて、適当に一枚づつ抜き取ってみます。
この時、抜き取った後にできた穴を埋めるために一番右に配置したカードを抜いた場所に置きなおすことにします。

方法としては、適当に一枚選択してそれを結果配列に積み、
ついで選択した位置に最後のカードを置きなおして、カード残数を減らします。

必要な変数を定義します。
山札配列
int src[10]={0,1,2,3,4,5,6,7,8,9};
結果配列
int cards[10];
一時変数
int n,srccnt;

(1)山札がある限りループさせます。
srccnt は山札の残数です。
for(srccnt=10;srccnt;srccnt--)
(2)乱数を使って要素番号を生成します。
n=rand()%srccnt;
(3)結果配列に(2)で生成した要素番号の要素を代入します。
cards[10-srccnt]=src[n];
(4)抜いた要素に最後の要素を再配置します。
src[n]=src[srccnt-1];

今回のポイントは「一枚抜くごとに山札の有効範囲が減っていく」ということです。
最初は10枚山札があるので0〜9に有効な番号が格納されていますが、
1枚抜くと9番の要素に格納されている番号は無効と考えます。
まさに山札が減っているかのように扱うわけです。
これを意味するのが(2)の剰余算で、「山札残数で割ったあまり」とすることで実現しています。

とはいえ、それだけだと最後以外を選択すると選択済みの要素ではなく最後の要素がなくなってしまうので、
選択した要素に最後の要素を持ってきます。これが(4)です。
srccnt-1 となっているのは、「最後の要素」は「残数-1」だからです。

(3)の cards[10-srccnt] の srccnt は初回10で1づつ減っていくので、
結果的に0から順番にアクセスします。
また、 srccnt が0の場合は先にループが終了するので cards[10-0] にアクセスすることはありません。


今回の分を全部まとめると以下のようになるでしょうか。
<  1>
<  2>
<  3>
<  4>
<  5>
<  6>
<  7>
<  8>
<  9>
< 10>
< 11>
< 12>
< 13>
< 14>
< 15>
< 16>
< 17>
< 18>
< 19>
< 20>
< 21>
< 22>		#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
   int src[10]={0,1,2,3,4,5,6,7,8,9},cards[10];
   int n,srccnt;
   int i;
   
   srand(time(NULL));
   for(srccnt=10;srccnt;srccnt--){
      n=rand()%srccnt;
      cards[10-srccnt]=src[n];
      src[n]=src[srccnt-1];
   }
   //どれくらいシャッフルできているか、確認してみます。
   for(i=0;i<10;i++)printf("cards[%d]:%d\n",i,cards[i]);
   //終了待ち
   getchar();
   return 0;
} 
実行例：
cards[0]:6
cards[1]:8
cards[2]:7
cards[3]:5
cards[4]:1
cards[5]:4
cards[6]:9
cards[7]:3
cards[8]:2
cards[9]:0

やってることは少々ややこしいですが、プログラムとしては短めです。
ループ数も枚数分と少ない割には、まぁまぁ切れていると言えるでしょう。


●適当に交換してみる
今度は山札の中から適当に二枚選んでそれらを入れ替える方法です。

方法としては、二回乱数を生成してそれらの番号のカードを交換します。

必要な変数を定義します。
山札配列
int cards[10]={0,1,2,3,4,5,6,7,8,9};
一時変数
int n1,n2,n3;

(1)乱数を使って要素番号を二個生成します。
n1=rand()%10;
n2=rand()%10;
(2)1個目の要素の値を一時変数に保存します。
n3=cards[n1];
(3)1個目の要素に2個目の要素の値を代入します。
cards[n1]=cards[n2];
(4)2個目の要素に最初に保存しておいた値を代入します。
cards[n2]=n3;

これで一回分です。
これを適当な数ループさせてシャッフルします。

(2)〜(4)は一般的な「値の交換」に当たります。
このような処理は比較的よく出現するため、
慣習的に「 swap 」という名前の関数として書いてあることがあります。
この例なら swap(cards[n1],cards[n2]) と書いてあれば(2)〜(4)相当という意味と解釈できます。
ただしC/C++には標準でこの関数は存在しないため、このまま書いてもエラーになります。
このような記述を見つけた時は、実際には(2)〜(4)のようなことをすると思ってください。


今回の分を全部まとめると以下のようになるでしょうか。
<  1>
<  2>
<  3>
<  4>
<  5>
<  6>
<  7>
<  8>
<  9>
< 10>
< 11>
< 12>
< 13>
< 14>
< 15>
< 16>
< 17>
< 18>
< 19>
< 20>
< 21>
< 22>
< 23>		#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(void)
{
   int cards[10]={0,1,2,3,4,5,6,7,8,9};
   int n1,n2,n3,i;
   
   srand(time(NULL));
   for(i=0;i<1000;i++){//1000回シャッフル
      n1=rand()%10;
      n2=rand()%10;
      n3=cards[n1];
      cards[n1]=cards[n2];
      cards[n2]=n3;
   }
   //どれくらいシャッフルできているか、確認してみます。
   for(i=0;i<10;i++)printf("cards[%d]:%d\n",i,cards[i]);
   //終了待ち
   getchar();
   return 0;
} 
実行例：
cards[0]:5
cards[1]:1
cards[2]:0
cards[3]:8
cards[4]:4
cards[5]:9
cards[6]:7
cards[7]:6
cards[8]:3
cards[9]:2

1000回シャッフルでは、まぁまぁ切れている感じです。
今回の手法の中ではもっとも単純なコードであることが利点でしょうか。



さて、ここまで5種類の方法を試してみました。
一口にシャッフルと言っても、作りもやり方も性能もイロイロです。
同じ処理をしても速いプログラムと遅いプログラムがあったりするのは、
この辺に起因していることが多いです。

もちろん、効率の良い方法を選んだ方がいいプログラムになるわけですが、
計算精度優先、メモリ消費量優先、実行速度優先など、
その時々の状況にあわせてやり方を変えるというのもまた必要なことです。
そのためにも、やり方を数多く「思いつける」ことが重要になります。
多くのやり方を思いつければそれだけ選択肢が増え、より適したやり方を使いやすくなります。

「物事を分解すること」、それがやり方を導く手段です。
ネットで検索すればあらかたのやり方は見つけられる時代ではありますが、
常に自力で考えること、先人の見つけた方法は「何故それでいいのか」を追求すること、
それらを怠らなければだんだんとやり方は自力で探し出せるようになってくるはずです。
間違ってもコピペで済まそうとか考えてはいけません。
そういう考えでいると自力で考えなければいけない場面でどうにもならなくなってしまいます。
コピペから経験値は得られないと思いましょう。

ここまでの手法は、割合単純な方法なので、比較的思いつきやすい手法です。
シャッフルの手法はこれら以外にも多数存在するものの、
大抵の用途であれば簡素なコードであっても問題ない程度にはシャッフルできると思います。

さて、これらの中から比較的性能の良かった「一枚ずつ抜き取ってみる」の改訂版を作ってみます。
「一枚ずつ抜き取ってみる」手法は処理量、シャッフル特性ともに良好な結果を示していますが、
配列を二個使用するため、要素数が多いとメモリ消費が大きくなります。
別にそういうものと割り切ってしまってもいいといえばいいのかもしれませんが、
この手法はうまくすれば配列を一個にしても同じ特性でシャッフルできます。

既にこれまでの最長記録を軽く突破してしまっているので、
「一枚ずつ抜き取ってみる」方法を配列一個で実現する方法を御題にしようと思います。
ネット上で探すとまんま答えがあったりしますが、探しちゃダメですよ？(笑)
ヒントは、「使わなくなった配列の領域」です。

次回は、上記の方法を考えてみます。

[前へ]   [目次へ]   [次へ]

プログラミング講座 総合目次

最終更新 2008/10/17