C言語

課題を解いて欲しいです。。。

パーティでビンゴ大会を行おうとしている。
そのビンゴでは１～n の数字をコンピュータを用いてひとつずつ取り出すのだが、そのプロ
グラムがまだ完成していない。
1. n=200 としたとき、あなたが考えた実行方法をコーディングしなさい。
2. インターネットを用いて最適と思われる方法を探しだし、同様に n=200 としてコーデ
ィングしなさい。
3. 1 と2 の方法について実行時間を計測しなさい。
4. 1 と2 の方法をそれぞれ考察しなさい。
ただし、1、2、共にそれぞれどのような考え方で行ったか、説明を付随する。

全くわからないのでお願いします。

No.6 回答者： gerugugu84 回答日時： 2011/07/01 15:07

１．とりあえず適当に作ってみた

unsigned long random( unsigned long min, unsigned long range )
{
/* 乱数の種を作る */
static unsigned long seed = 0;
if( !seed )
{
time_t ltime;
time( &ltime );
seed = ( unsigned long )ltime;
}

/* 乱数発生のアルゴリズム（テキトーなので考察もなし） */
seed = seed * 123456789 + 123456789;

/* 乱数を指定の範囲内の数値に変換する */
return ( min + seed ) % range;
}

int main(int argc, char* argv[])
{
int ii;
/* 1～200までの数字が入った配列を用意する */
unsigned long numbers[ 200 ];
for( int ii = 0; ii < 200; ii++ )
{
numbers[ ii ] = ii + 1;
}

/*計測するならここで開始*/

/* 乱数で配列をシャッフル（10000万回もいらんかも） */
for( ii = 0; ii < 10000; ii++ )
{
unsigned long pos1 = random( 0, 200 );
unsigned long pos2 = random( 0, 200 );
if( 200 <= pos1 || 200 <= pos2 )
{
return -1;
}

/* 入れ替え */
unsigned long temp = numbers[ pos1 ];
numbers[ pos1 ] = numbers[ pos2 ];
numbers[ pos2 ] = temp;
}

/*計測するならここで終了*/

/* ランダムに入れ替わった配列を表示する */
for( ii = 0; ii < 200; ii++ )
{
printf( "%u\n", numbers[ ii ] );
}

return 0;
}

２．メルセンヌツイスタというアルゴリズムがすごいらしいです。
３．それぞれのアルゴリズムで計測するだけ
４．方法を考察となると、アルゴリズムを理解してないのでわかりません。

No.5 回答者： AsanoNagi 回答日時： 2011/07/01 13:42

かなり最悪に近いソース。

こんなソースでも、最近は一瞬で終わるんだと、ちょっとびっくりした。



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

int main()
{
int doneNumber[200] = {0};
int i;
// インデックスとしては、1 - 200 じゃなくて、 0 - 199 を使う
while(1)
{
int n = rand(); // ひとつ番号を出してみて
if (n < 200) // 200未満ならいけそう
{
if (! doneNumber[n]) // その場号がまだでてなければ、
{
doneNumber[n] = 1; // 番号がでたという印をつけて
printf("%d\n", (n + 1)); // 表示
}
}

for(i = 0; i < 200; i++)
{
// 全部の数字が出たかどうか確認するためのループ
if (! doneNumber[i]) break; // まだ出てない数字があれば、ループを抜ける
}

if (i >= 200) // 全部カウントした == 出てない数字はない
break;
}

return 0;
}

No.4 回答者： deltaforce_1 回答日時： 2011/07/01 11:39

(1)は指摘されている通り、貴方の考えた実行方法でコーディングすると云う事ですから

貴方が何も考えていない状態では１を解く事は不可能です
(2)も回答は一つではなく、貴方が「最適と思った方法」を探し出すのが課題ですね
(3)の実行時間の計測はプログラム的に行うでしょうから、その辺りなら１，２を元に
こちら側で出来るかもしれませんね
(4)は１，２が決まっていない現状でお答えする事が出来ません。

課題を出す側もしっかりと考えられて出しているのでしょう
こうやって質問したり、回答丸写しの人がいる事を想定して出されている問題だと言う事です


・普通のビンゴであれば同じ数字は2度出る事は無い
　条件が付いていないので自由だが、考えるべき
　※プログラムだとたまに2度出る物もあるが、ビンゴとしての意味は無い為
・完全にランダムである事が求められる
・背景としてパーティーなので、それなりの物を。

No.3 回答者： passersby2 回答日時： 2011/07/01 11:11

別解。

実行開始時刻をシステムから得る。
int配列に下記の初期値をループ処理で入れる。
x(1)=1,
x(2)=2,
x(n)=n,
・・・・・・
x(200)=200

ループ100回：
ランダム関数で1～200の間の整数乱数y，zを発生させる。
x(y)の値とx(z)の値を入れ替える。

x(1)～x(200) を出力する。

処理終了時刻をシステムから得る。

No.2 回答者： Tacosan 回答日時： 2011/07/01 10:56

1 に「あなたが考えた実行方法をコーディングしなさい」と書かれているんだから, そこはあなたが考えてください. それとも, あなたは他人が作ったものを「自分が作りました」と偽るつもりですか?

その「実行方法」を書いてくれれば, ひょっとしたら 3 あたりはやってくれる人がいるかもしれんけど.

No.1 回答者： passersby2 回答日時： 2011/07/01 10:52

実行開始時刻をシステムから得る。

int配列を設定し，下記の初期値をループ処理で入れる。
x(1)=1,
x(2)=2,
x(n)=n,
・・・・・・
x(200)=200
また，
出力回数=0

ループ：
出力回数=200ならループを抜ける。
ランダム関数で1～200の間の整数乱数yを発生させる。
x(y)>0 であれば，
求める値=x(y), x(y)=0, 出力回数++
x(y)=0 であれば，x(y)>0 になるまで再帰処理。

処理終了時刻をシステムから得る。