ページ 11

配列内の数字のシャッフル

Posted: 2016年10月26日(水) 15:39
by manana
大学でC言語を学び始めた者です。ポインタについてはまだ詳しい事は学んでいません。
配列に1から13までの数をセットし、「乱数で2つの数を選んで入れ替える」 作業を50回行い、結果を表示するプログラムを作る、という課題が出たので書いてみたのですが、実行結果が

./a.out
5 7 1 0 4 6 2 8 10 13 11 9 3
./a.out
10 4 6 3 9 13 1 7 0 5 11 2 12
./a.out
4 8 6 10 12 9 7 11 13 1 3 0 2

のように1~13ではなく0~13の範囲で表示されてしまいます。

以下が自分の書いたコードになります。

コード:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

 int main(void) {
   int i;
   int table[13] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
   srand((unsigned)time(NULL));

   for (i=0;i<50;i++) {
   int first = table[(int)(rand()/(1.0+RAND_MAX)*13)+1];
   int second = table[(int)(rand()/(1.0+RAND_MAX)*13)+1];

   int temp = table[first];
   int temp2 = table[second];
   table[first] = temp2;
   table[second] = temp;
   }

   for (i=0;i<13;i++) {
       printf("%d ", table[i]);
     }

   printf("\n");

     return 0;
 }
自分で見直してもなぜ実行結果に0が含まれてしまうのかわかりません。
どこをどのように直せば1~13の範囲で表示されるのでしょうか。
また、コンパイルはできているのですが、コードの中で単純化できたり、良くない書き方をしている箇所がありましたらご指摘お願いします。

Re: 配列内の数字のシャッフル

Posted: 2016年10月26日(水) 16:37
by みけCAT
11~12行目の
manana さんが書きました:

コード:

   int first = table[(int)(rand()/(1.0+RAND_MAX)*13)+1];
   int second = table[(int)(rand()/(1.0+RAND_MAX)*13)+1];
で配列の範囲外の値を読み取ることがあり、未定義動作になります。
そこの初期値がたまたま0だったのでしょう。
さらにややこしいことに、乱数を直接交換する位置にするのではなく、ここで読み取った値を位置として使用しているので、このtable[13]の初期値がたまたま0という条件では最初の要素も交換の対象になったのですね。
余計な足し算と配列へのアクセスを消して

コード:

   int first = (int)(rand()/(1.0+RAND_MAX)*13);
   int second = (int)(rand()/(1.0+RAND_MAX)*13);
とすることで、交換対象として有効な位置が得られるでしょう。

また、13というマジックナンバーをプログラム中で何度も書くのは良くないでしょう。
インデントも整えるといいでしょう。

コード:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(void) {
   int i;
   int table[13] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
   int num = sizeof(table) / sizeof(*table);
   srand((unsigned)time(NULL));

   for (i=0;i<50;i++) {
      int first = (int)(rand()/(1.0+RAND_MAX)*num);
      int second = (int)(rand()/(1.0+RAND_MAX)*num);


      int temp = table[first];
      int temp2 = table[second];
      table[first] = temp2;
      table[second] = temp;
   }

   for (i=0;i<num;i++) {
      printf("%d ", table[i]);
   }

   printf("\n");

   return 0;
}

Re: 配列内の数字のシャッフル

Posted: 2016年10月26日(水) 16:59
by あんどーなつ
int first = table[rand() % 13];でいいように思います。私の環境ではRAND_MAXは60000位の数だったと
思いますので、もっと精度を上げたい場合は、ちょっと面倒ですがC++標準ライブラリのstd::randomを使っても
いいと思います。

Re: 配列内の数字のシャッフル

Posted: 2016年10月26日(水) 17:47
by あんどーなつ
うーむ、みけCATさんから回答いただいているので横やりを入れるのもあれですけど、
元のプログラムがちょっと変ですね。

元のプログラムの10~18行目は、
こっちのほうがすっきりしていると思います。

コード:

    for (i=0;i<50;i++) {
      int i1 = rand() % 13;
      int i2 = rand() % 13;
      int temp = table[i1];
      table[i1] = table[i2];
      table[i2] = temp;
    }

Re: 配列内の数字のシャッフル

Posted: 2016年10月26日(水) 18:27
by box
manana さんが書きました: ./a.out
5 7 1 0 4 6 2 8 10 13 11 9 3
12が抜けてる。
manana さんが書きました: ./a.out
10 4 6 3 9 13 1 7 0 5 11 2 12
8が抜けてる。
manana さんが書きました: ./a.out
4 8 6 10 12 9 7 11 13 1 3 0 2
5が抜けてる。

というわけで、皆さんからのご指摘のとおり、配列の定義範囲外の領域にアクセスした結果、
おかしなことが起きたのでありましょう。

Re: 配列内の数字のシャッフル

Posted: 2016年10月26日(水) 22:18
by みけCAT
シャッフルのアルゴリズムをより良いものに入れ替えてみました。
「まだ選んでいないものから適当に選んで後ろに出す」というアルゴリズムです。

コード:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(void) {
   int i;
   int table[13] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
   int num = sizeof(table) / sizeof(*table);
   srand((unsigned)time(NULL));

   for (i=num-1;i>0;i--) {
      int pos = (int)(rand()/(1.0+RAND_MAX)*(i+1));

      int temp = table[pos];
      table[pos] = table[i];
      table[i] = temp;
   }

   for (i=0;i<num;i++) {
      printf("%d ", table[i]);
   }

   printf("\n");

   return 0;
}

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 15:34
by manana
皆さまご回答ありがとうございます。
返信が遅くなりすみません。

RAND_MAXで配列の定義範囲外にアクセスしてしまっていたのですね。
謎が解けて少し安心しました。

みけCATさんとあんどーなつさんより頂いたアドバイスを元に次のように書き直して数回試したところ、1~13のみの実行結果が得られました!

コード:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(void) {
   int i;
   int table[13] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
   int num = sizeof(table)/sizeof(*table);
   srand((unsigned)time(NULL));

   for (i=0;i<50;i++) {
   int first = rand() % num;
   int second = rand() % num;

   int temp = table[first];
   table[first] = table[second];
   table[second] = temp;
   }

   for (i=0;i<num;i++) {
       printf("%d ", table[i]);
   }

   printf("\n");

   return 0;
 }
実行結果:
./a.out
9 13 8 10 4 6 12 2 1 7 5 3 11
./a.out
13 12 11 9 5 2 8 6 10 7 3 1 4
./a.out
12 4 9 10 7 3 1 13 8 11 2 5 6
./a.out
6 11 12 2 5 9 1 4 13 3 10 7 8

6番目の書き込みでみけCATさんよりご提示いただいたプログラムは、今回の課題の「50回入れ替える動作」にどう適用したらいいいかわからず、参考にするのを断念してしまいました、すみません・・・。
そして、上手くいってホッとしているのですが、
みけCAT さんが書きました:

コード:

   int num = sizeof(table) / sizeof(*table);
この部分で今回使う13という数字の立場を他者から見てわかりやすくしているのでしょうか?どうしてこれが13になるのかいまいち理解できませんでした。よろしければここでどういう操作をしているのかお教えください。

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 15:41
by manana
ああ、インデントを整える前のものを貼ってしまいました・・・。
すみません。

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 18:21
by akasann
解決したようですが、作ってみました。プログラミング初心者ですが、こんな感じでもできました。

コード:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main(void){
	int i,a[13]={1,2,3,4,5,6,7,8,9,10,11,12,13},temp,f,s;
	srand((unsigned)time(NULL));

	for(i=0;i<50;i++){
		f=rand()%13;
		s=rand()%13;
		
		temp=a[f]; a[f]=a[s]; a[s]=temp;
	}

	for(i=0;i<13;i++)
		printf("%3d",a[i]);
	puts("\n");

	return 0;
}

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 18:32
by みけCAT
manana さんが書きました:6番目の書き込みでみけCATさんよりご提示いただいたプログラムは、今回の課題の「50回入れ替える動作」にどう適用したらいいいかわからず、参考にするのを断念してしまいました、すみません・・・。
入れ替えを50回行うという条件があったのですね。
すいません、見落としていました。
manana さんが書きました:
みけCAT さんが書きました:

コード:

   int num = sizeof(table) / sizeof(*table);
この部分で今回使う13という数字の立場を他者から見てわかりやすくしているのでしょうか?どうしてこれが13になるのかいまいち理解できませんでした。よろしければここでどういう操作をしているのかお教えください。
「配列全体のサイズ」を「1要素あたりのサイズ」で割ることで、配列の要素数を求めています。

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 18:37
by みけCAT
入れ替え対象としてたまたま同じ数を選んでしまうと、「2つの数を選んで入れ替え」たことにならないのでは?
というわけで、2番目の位置を決める時に最初に決めた位置を抜かすようにした改良版。

コード:

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main(void) {
   int i;
   int table[13] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
   int num = sizeof(table)/sizeof(*table);
   srand((unsigned)time(NULL));

   for (i=0;i<50;i++) {
      int first = rand() % num;
      int second = rand() % (num-1);
      if (first <= second) second++;

      int temp = table[first];
      table[first] = table[second];
      table[second] = temp;
   }

   for (i=0;i<num;i++) {
      printf("%d ", table[i]);
   }

   printf("\n");

   return 0;
}

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 19:03
by box
みけCAT さんが書きました:入れ替え対象としてたまたま同じ数を選んでしまうと、「2つの数を選んで入れ替え」たことにならないのでは?
2つの数がたまたま同じであっても、いっこうにかまわないのでは?自分の解釈はそういうことです。
まあ、出題者の意図が正確にはわかりませんので、自分のような部外者があ~だこ~だ言うようなことではないのかもしれません。

Re: 配列内の数字のシャッフル

Posted: 2016年10月28日(金) 20:31
by manana
わかりやすく教えていただけて、助かります。
新たにプログラムを考えてくださった方もありがとうございます。
box さんが書きました:
みけCAT さんが書きました:入れ替え対象としてたまたま同じ数を選んでしまうと、「2つの数を選んで入れ替え」たことにならないのでは?
2つの数がたまたま同じであっても、いっこうにかまわないのでは?自分の解釈はそういうことです。
まあ、出題者の意図が正確にはわかりませんので、自分のような部外者があ~だこ~だ言うようなことではないのかもしれません。
別々の、とは書いていなかったのでどちらの可能性もありますね。
両パターン提出してみます。
皆さま、ありがとうございました!