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

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
manana

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

#1

投稿記事 by manana » 3年前

大学で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の範囲で表示されるのでしょうか。
また、コンパイルはできているのですが、コードの中で単純化できたり、良くない書き方をしている箇所がありましたらご指摘お願いします。

アバター
みけCAT
記事: 6227
登録日時: 9年前
住所: 千葉県
連絡を取る:

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

#2

投稿記事 by みけCAT » 3年前

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;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

あんどーなつ

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

#3

投稿記事 by あんどーなつ » 3年前

int first = table[rand() % 13];でいいように思います。私の環境ではRAND_MAXは60000位の数だったと
思いますので、もっと精度を上げたい場合は、ちょっと面倒ですがC++標準ライブラリのstd::randomを使っても
いいと思います。

あんどーなつ

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

#4

投稿記事 by あんどーなつ » 3年前

うーむ、みけ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;
    }

box
記事: 1739
登録日時: 9年前

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

#5

投稿記事 by box » 3年前

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が抜けてる。

というわけで、皆さんからのご指摘のとおり、配列の定義範囲外の領域にアクセスした結果、
おかしなことが起きたのでありましょう。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

アバター
みけCAT
記事: 6227
登録日時: 9年前
住所: 千葉県
連絡を取る:

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

#6

投稿記事 by みけCAT » 3年前

シャッフルのアルゴリズムをより良いものに入れ替えてみました。
「まだ選んでいないものから適当に選んで後ろに出す」というアルゴリズムです。

コード:

#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;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

manana

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

#7

投稿記事 by manana » 3年前

皆さまご回答ありがとうございます。
返信が遅くなりすみません。

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になるのかいまいち理解できませんでした。よろしければここでどういう操作をしているのかお教えください。

manana

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

#8

投稿記事 by manana » 3年前

ああ、インデントを整える前のものを貼ってしまいました・・・。
すみません。

akasann

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

#9

投稿記事 by akasann » 3年前

解決したようですが、作ってみました。プログラミング初心者ですが、こんな感じでもできました。

コード:

#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;
}

アバター
みけCAT
記事: 6227
登録日時: 9年前
住所: 千葉県
連絡を取る:

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

#10

投稿記事 by みけCAT » 3年前

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

コード:

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

アバター
みけCAT
記事: 6227
登録日時: 9年前
住所: 千葉県
連絡を取る:

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

#11

投稿記事 by みけCAT » 3年前

入れ替え対象としてたまたま同じ数を選んでしまうと、「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;
}
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

box
記事: 1739
登録日時: 9年前

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

#12

投稿記事 by box » 3年前

みけCAT さんが書きました:入れ替え対象としてたまたま同じ数を選んでしまうと、「2つの数を選んで入れ替え」たことにならないのでは?
2つの数がたまたま同じであっても、いっこうにかまわないのでは?自分の解釈はそういうことです。
まあ、出題者の意図が正確にはわかりませんので、自分のような部外者があ~だこ~だ言うようなことではないのかもしれません。
バグのないプログラムはない。
プログラムは思ったとおりには動かない。書いたとおりに動く。

manana

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

#13

投稿記事 by manana » 3年前

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

閉鎖

“C言語何でも質問掲示板” へ戻る