C言語

質問

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

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

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

回答No.12

επιστημη（@episteme） · ベストアンサー

> ANo.10
map使うまでもなし。setで充分。

#include <iostream>
#include <set>
#include <cstdlib>

int main() {
std::set<int> doneNumber;
const int numOfBingo = 200;
// インデックスとしては、1 - 200 じゃなくて、 0 - 199 を使う
while ( doneNumber.size() < numOfBingo ) {
int n = std::rand(); // ひとつ番号を出してみて
// その場号が範囲内かつまだでてなければ出力する
if ( n < numOfBingo && doneNumber.insert(n).second ) {
std::cout << (n + 1) << "\n";
}
}
}

# アルゴリズムは依然として最低ですが ^^;

回答No.16

馬鹿垂 云子（@bakatareunko）

計算量一緒なのに質問1の回答と断定されてもループが一個多くなるからたしかにオーバーヘッド増えるし負けましたすいません勘弁してくださいごめんなさいだからむきにならないでベタ張りしてるのが痛すぎて読む気になれなかったんですごめんなさい無職でもコード書く時間無かったんですすいませんでした０～i(n<100)とかするより1～200にすればiMAXとか余計な変数使わなくて良いからC言語なら7Byte余分にGEEEEEEEEET!とか言わないから許してくださいごめんなさい７Byteは与太じゃないからゆるしてくださいそもそも課題やってください系の質問に書いてる時点で釣りだろとか言いませんのでごめんなさいすいませんでしたゆるしてくださいいろんなところでこういう質問に自分で考えろとか説教たれてる無職が見てていたたまれなかったんですごめんなさいすいません自分も無職でした本当にすいませんでした許してください。

回答No.15

nak777r

No.14 さんへ
質問者さんの質問に回答出来るのは、質問 2 のみだと私は思っています。
なので、私は No.7 No.11 で最適と思われる方法を回答させて頂きました。
他の言語にてソースを提示する事は、質問 2 に関して問題は無いはずです
No.14さんは、質問 1 の回答をされておられる様ですが、それこそ、
それは質問者さんが、自分で考えなければ意味が無い部分の回答だと思いますよ

回答No.14

馬鹿垂 云子（@bakatareunko）

学校の課題ならC以外の言語分かってるとは考えにくいだろうが。
なにベタ書きしてんの?
英語分からない子に英語でこういうんだよって言ってるのと同じだろうが、
手順書くべきだろ。

手っ取り早くCで実装できるのは
・長さ200の配列を用意する、各値はインデックスと同じでかまわない。
・0～199の乱数を複数回発生させる。
・乱数発生2回毎に1回目と2回目の値をインデックスとして配列の内容を入れ替える。
・頭から出力。

回答No.13

麻野 なぎ（@AsanoNagi）

> A No. 12

おお、set::insert() に返り値があるなんて初めて気がつきました。
重複した要素の挿入は、失敗なんですね、扱いとして。なんとなく「無視されるだけ」というイメージでした。

回答No.11

nak777r

No.7 です

No.7で書いた、最適と思われるコードを EXCEL のVBA で書いておきます。
Sub test()
Dim i As Integer
Dim iMax As Integer
Dim n(200) As Integer
Dim r As Integer

iMax = 199
'
'n[200]等の配列を用意し、n[0]～n[199]に 1～200 の数字を入れる
For i = 0 To iMax
n(i) = (1 + i)
Next i
'準備OK

For i = iMax To 0 Step -1
' 0 ～ i の範囲で乱数を発生させる
r = Int((i + 1) * Rnd())

' Sheet1.セルA 列 1行目からに n(r)の中身をセット
Worksheets("Sheet1").Cells(1 + (iMax - i), "A").Value = n(r)

' n(r) に n(i)の値をセット
n(r) = n(i)
Next i
End Sub

これだけです。

回答No.10

麻野 なぎ（@AsanoNagi）

No.5 です。
Ｃ＋＋で（というか、ＳＴＬで）書いてみたもの。

でも、No.5 と見かけが全然変わらないのは、Ｃ＋＋とＳＴＬの素性の良さかな。
ロジックは、あいかわらず「ほぼ最低」ですが。

#include <cstdlib>
#include <iostream>
#include <map>

int main()
{
std::map<int, bool> doneNumber;
const int numOfBingo = 200;

int i;
// インデックスとしては、1 - 200 じゃなくて、 0 - 199 を使う
while(1)
{
int n = std::rand(); // ひとつ番号を出してみて
if (n < numOfBingo) // numOfBingo 未満ならいけそう
{
if (! doneNumber[n]) // その場号がまだでてなければ、
{
doneNumber[n] = true; // 番号がでたという印をつけて
std::cout << (n + 1) << "\n";
}
}
for(i = 0; i < numOfBingo; i++)
{
// 全部の数字が出たかどうか確認するためのループ
if (! doneNumber[i]) break; // まだ出てない数字があれば、ループを抜ける
}

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

return 0;
}

回答No.9

επιστημη（@episteme）

> 課題の答えとして提出するには高度すぎるというような回答が好きです。

では得意満面にC++で。

#include<iostream>
#include <algorithm>
#include <array>
#include <numeric>

using namespace std;

int main() {
array<int,200> bingo;
iota(bingo.begin(), bingo.end(), 1);
random_shuffle(bingo.begin(), bingo.end());
for_each(bingo.begin(), bingo.end(), [](int n) { cout << n << ' '; });
}

回答No.8

okakesan1234

最近は得意満面になって回答ベタ書きする人が増えましたね。
前回見かけたベタ書き解答は誤回答だったですけど…。

質問者さんのためを思うなら、スマートで適切なヒントを出すべきだと思います。

それか、回答としては間違ってないけど
課題の答えとして提出するには高度すぎるというような回答が好きです。

回答No.7

nak777r

多分最適と思える方法
n[200]等の配列を容易し、n[0]～n[199]に 1～200 の数字を入れる
準備OK

１回目１個取り出し
0～199 の範囲で乱数を発生させる
仮に 30 だった場合、
画面に n[30]の中身を表示し（画面 n[30]の中身の 31 を表示）
n[30]に n[199]の値を入れる（n[30] の中身は200になる）

２回目１個取り出し
0～198 の範囲で乱数を発生させる ← 範囲を１個狭める事が重要
仮に 50 だった場合、
画面に n[50]の中身を表示し（画面 n[50]の中身の 51 を表示）
n[50]に n[198]の値を入れる（n[50] の中身は199になる）

３回目１個取り出し
0～197 の範囲で乱数を発生させる ← 範囲を１個狭める事が重要
仮に 197 だった場合、
画面に n[197]の中身を表示し（画面 n[197]の中身の 198 を表示）
n[197]に n[197]の値を入れる（n[197]の中身は変わらない）

最適である理由
事前にシャッフルしない
既に出たか確認しない

回答No.6

gerugugu84

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

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

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