比較の回数を少なくする方法
- 比較の回数を少なくする方法について考えています。例えば、10個のリンゴの大きさに順位を付けたい場合、天秤にのせて重さを比較する方法を考えています。しかし、どのように比較すればよいかわかりません。また、リンゴの数が増えた場合の比較の回数の求め方も知りたいです。
- 現在、10個のリンゴの大きさの順位を求めるために天秤を用いて比較していますが、比較回数を少なくしたいです。リンゴの大きさにはユニークな値があり、絶対的な値を求めることはできません。そのため、天秤を使用してリンゴの重さを比較することで順位を求めたいです。どのような方法がありますか？また、リンゴの数が増えた場合の比較回数も知りたいです。
- リンゴの大きさに順位を付けるために、天秤を使用して比較していますが、比較回数を少なくしたいです。リンゴの大きさにはユニークな値があり、絶対的な値を取得する方法はありません。そのため、リンゴの重さを比較して順位を求める方法を考えています。どのような方法がありますか？また、リンゴの数が増えた場合の比較回数も知りたいです。
- ベストアンサー
比較の回数を少なくする方法
例えば、１０個のリンゴがあるとします。リンゴの大きさに同じ物は無いと仮定します。（大きさはユニーク） その１０個のリンゴの大きさに順位を付けたいのですが、絶対的な値を取得する「計り」の様な装置は無く、天秤にのせて重さの比較をする事により、順位を求めたいです。（天秤にはリンゴをひとつずつしか乗せられないとします。） 比較の作業をなるべく少なくしたいです。どのように比較したらよいでしょうか？ また、示した例ではリンゴは１０個でしたが、リンゴの数がｎ個になった時の比較の回数の求め方も知りたいです。 以下、完結できてませんが自分のこれまでの考えです。 ＡＢＣＤＥＦＧＨＩＪ Ａ□■■■■■■■■■ Ｂ□□■■■■■■■■ Ｃ□□□■■■■■■■ Ｄ□□□□■■■■■■ Ｅ□□□□□■■■■■ Ｆ□□□□□□■■■■ Ｇ□□□□□□□■■■ Ｈ□□□□□□□□■■ Ｉ□□□□□□□□□■ リンゴをA～Jとした場合、■の部分の比較をすれば良いかと考え、 比較回数は、N＊N/2 - Nかなと思ったのですのですが、もっと少ない比較で答えを求める事が可能かと思いました。 なぜかと言うと、例えば、A：B比較後にB：C比較の結果がA＜B、B＜CならA-C比較は不用になると考えたからです。 A：B、B：C比較の結果がA＞B、B＜Cになれば、A：Cの比較は必要になるので確立的要素も必要になるのかとも思います。 どのようなご指導でもかまいません、○○について調べろなどのキーワードをくださるだけでもありがたいです。 以上、よろしくご指導の程、お願い申し上げます。
- 小林 K太郎（@kingfruits）
- お礼率66% (211/319)
- 数学・算数
- 回答数7
- ありがとう数7
- みんなの回答 （7）
- 専門家の回答
質問者が選んだベストアンサー
どうして「ソートについて調べても、あまり役に立たたないというのが実感なんです。」と思うのか不思議です。 n個のものがあれば，その並び方の数はn!個あります。m回比較して順位が確定するとすれば2^m>=n!です。つまりm>=ceiling(log(n!))ですね。(対数の底は2だとしています。ceilingはそれ以上の整数で最も小さい数です。) n=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16に対して ceiling(log(n!))=0,1,3,5,7,10,13,,16,19,22,26,29,33,37,41,45 ですからceiling(log(n!))回で順位が確定する方法があれば，それが最低の回数だと分かるのです。 Ford-Johnson アルゴリズムを使えば比較の回数は F(n)=0,1,3,5,7,10,13,16,19,22,26,30,34,38,42,46 F(n)=Σ[k=1からnまで](ceiling(log(k*3/4))) ですからnが11までなら最低回数であることが保証されます。（実はn=12,13,14,15でも最低回数ということが証明されているらしい。） 「実際のこれをパソコンを使ってシステム化」しようとすると，あまりネット上に情報がないので難しいかもしれない。 でも，例えばマージソートを使えば M(n)=0,1,3,5,8,11,14,17,21,25,29,33,37,41,45,49 で順位付けが完了します。そんなに悪くないでしょ。 一般的なnに対して最も比較回数が少ない方法はわかっていません。したがってプログラム化するにはある程度妥協する必要があります。あなたが対象としているnはどの程度の数なんでしょうか？
その他の回答 (6)
- kmee
- ベストアンサー率55% (1857/3366)
繰り返しになるところもありますが。 「順位」という相対的な値を求めるのが、ソートです。 300gのリンゴが「何番目」になるかは、他のリンゴ次第です。 比較ソートで比較するのは、2値の「相対的な関係」です。 ソートのプログラムによくでてくるコードに、次のようなものがあります。 if A[ j ] < A[ i ] then コンピュータでやっているので、内部では数値計算しているかもしれません。 しかし、やっているのは、 A[j]とA[i]のどちらが大きいか、天秤で調べるようなものです。 「<」という演算子に惑わされているのなら、こういうことです。 if 「A[ j ] と A[ i ] を天秤に乗せて、A[j]が上になった」 then 画像の比較なら、こういうことです if 「A[ j ] と A[ i ] を表示したら、A[j]が『良い』と判断された」 then ifの中にこれだけの処理を書ける言語はあまりありませんが、 「Aj と Ai を表示して、Ajが『良い』と判断されたらTrue」という関数 ImageCompareを定義すれば if ImageCompare(A[ j ], A[ i ] ) then という、ごくありふれたコードになります。 ソートのアルゴリズムは、一般化すれば次の通りです 1. 目的の合致した Ai, Aj を選ぶ 2. Ai, Aj の大小関係を比較する 3. 2.の結果によって(入れ替え等の)処理を行う。あるいは、何もしない 4. 1～3を必要な回数繰り返す アルゴリズムの違いは、1,3,4の違いです。 1の違いは、 どんな組み合わせで調べるのか、同じ Ai,Aj の組合せを何回評価する可能性があるのか、に関係します。 4の「必要な回数」は、1に依存します。 アルゴリズムの選択を間違えれば、 同じ組合せを何回も評価しなければならない上、比較の総回数も増えます。 アルゴリズムをよく調べてください。効率のいいソートでは、同じ組合せを比較しないように工夫されています。 挿入ソートでは、比較は常に「これまでに順位が決定した物」と「これから順位を決めようとしている物」の組合せです。 マージソートは、トーナメント戦を、負けたチームを吸収しながら勝ち進む感じになります。比較対象は常に「敵チーム」であり、一度対戦した相手は「自チーム」になるので、二度と対戦することはありません。 ソートのアルゴリズム自体は、コンピュータとは関係ありません。 比較回数、組み合わせ、順序等が関係する、数学の一分野です。
お礼
ご認識のあるとおり、繰り返しのご回答でしたね。 ですが、ごかいとうありがとうございました。
- ask-it-aurora
- ベストアンサー率66% (86/130)
御節介とは思いますが，やっぱりソートが何なのかわかっていないようなので老婆心ながらもう一度回答させてもらいます． たぶんあなたの頭のなかではソートアルゴリズムとは次のようになっているのではないかと想像します． [目的] リストの要素を一列になるように並び替えたい [束縛] コンピュータの計算時間を短くしたい [仮定] 計算時間は比較回数に比例する [結論] 比較回数がなるべく少なくなる方法を探そう この比較回数がなるべく少なくなる方法というのが先人たちが工夫してきたソートアルゴリズムたちです． さて以前の質問(参考URL) を見ると本当にしたいことはリンゴの例とは少し違うように思われます．が，もし一定の設定を満たすならば話は同じです： [目的] 大量にある画像を優劣をつけ，一列に並び替えたい [束縛] 比較をする人間への負担を少なくしたい [仮定] 負担は比較回数に比例する [結論] 比較回数がなるべく少なくなる方法を探そう なのでこれはソートの問題です． で，その一定の条件ですがそれは「順序」が全順序であることです．自然言語の「順序」と数学者の使う「順序」という言葉は同じですが，細部が異なります．実際に使うときには本当に全順序になっていると見做してよいのかを検討すべきです．自然言語の「順序」に対応する概念としては半順序（数学者の言う順序は普通コレ），全順序，擬順序などがあります．定義はご自分で調べてください．もし別の順序だったのならソレ用のアルゴリズムを考えるべきです（し，そもそもこれらのどれにもならないかもしれません．人間の負担は一旦，無視して小さな予備実験を行い，どんなデータと向き合っているのかをまずハッキリさせては？）
お礼
ask-it-auroraさん、ご回答ありがとうございます。 測定対象に、相対的な値をつける事が目的です。相対的な値がついてしまえば、ソートについて悩む事は全くないのです。 なので、ソートのロジックに何を採用するかなどは、どうでも好い問題と思えてしまうのですが、比較によって相対的な値を求めるという事の本質がソートであると言う事なのでしょうか。。。
補足
ん～ ＞御節介とは思いますが 本人がそういうだけの事はあるかな。 といった回答でした。 ですがご回答ありがとうございました。
- kmee
- ベストアンサー率55% (1857/3366)
「順位を付ける」ことと「順番に並べる」ことは等価です。 「1位を 求める」ことは「先頭にくるものを探す」ことです。 ソートのプログラムにも、実際に並び変えるのではなく、順位にあたる番号を付与する、というものもあります。 今回の問題は「ソート」について調べるのが正解です。
お礼
kmeeさん、ご回答ありがとうございます。 これはソートの問題であると、他の回答者様の多くもそうご回答頂いたのですが、実際のこれをパソコンを使ってシステム化しようと考えると、なにか違和感を感じるのです。ソートについて調べてみると、コンピューターでソートを行ううえでのアルゴリズムである前提が多く、比較は確かに処理時間を左右するコストであり、比較回数が少ないというのは一つの指標となっているのですが、私が求めているのは、仮に処理全体で所用する時間が遅くても、比較の回数そのものが少ない事が優先されるのです。絶対的な値の取得が、もし済んでいて、それがデータ化されてコンピュータに取り込まれている状態であれば、ソートのアルゴリズムが何であれ処理時間は非常に短い時間であり、それは二つのリンゴを天秤にかけて比較する時間とくらべたら、無に等しい時間です。 なので、ソートを行う過程で、出題に示したようなA：Bの比較を実施した後は、B：Aの比較はしたくないのは無論、A:B、B：Cの比較後、A：Cの比較が不用であれば、そのような比較を人間に求めないようなサポートをコンピュータにやらせたいというのが真の目的です。 と、いいますか、簡素に申し上げれば、ソートについて調べても、あまり役に立たたないというのが実感なんです。
- f272
- ベストアンサー率46% (8018/17137)
10個の並べ替えなら全部で22回の比較で十分です。 キーワードは「Ford-Johnson アルゴリズム」です。
お礼
f272さん、ご回答ありがとうございます。 「Ford-Johnson アルゴリズム」で調べてみます。
- ask-it-aurora
- ベストアンサー率66% (86/130)
> これはソートの問題だとお考えですか？ はい．ソートというとGIFアニメでよくあるピョコピョコ並び替えるのをイメージしがちですが，並び替えというイメージに引きずられないようにもっと抽象的に考えればいいと思います．つまりソートとは「有限集合上に与えられている未知の全順序を決定するアルゴリズム」なので，リンゴ10個の重さの順位づけもソートの問題です． 現実の試合などはするたびに結果が変わり得ますし，相性があって全順序にならなかったりするのでその限りではありませんが．
お礼
ask-it-auroraさん、度々、ご回答ありがとうございました。
- ask-it-aurora
- ベストアンサー率66% (86/130)
検索すべきキーワードは「比較ソート」です．たとえば「マージソート」なんかがお手軽だと思います（僕は手でテストの解答用紙を番号順に並べるときにこんな感じでやりました．）比較回数は大体N*ln(N)くらいです．これについても「計算時間 アルゴリズム」などと検索すればいろいろでるでしょう．
補足
ask-it-auroraさん、ご回答ありがとうございます。 私も当初はソートの問題かと思ってたのですが、これはソートの問題ではないような気がしてきまして、このような質問を数学のカテゴリでしてみました。 まったくもって入れ替えの事を考える必要はなく、比較することにより、最終的な相対的な値を求める事が目的なのです。同じ値どうしによる比較を重複して行いたくないのが目的です。他の例で例えるならば、計りによるリンゴの計測でなく、計測は「試合」のような物と考えてほしいのです。同じ相手との試合をする事無く、一位からビリまで順位をつけるにはどうしたらよいかという問題です。 こう補足してもこれはソートの問題だとお考えですか？
関連するQ&A
- 比較回数が少なくなるソート
大量にある画像に人間が優劣を判定し、その結果をソートしたいです。（順位を付けたい） 画像はすでにデジタルデータ化されてパソコンの中にあります。 二つの画像を人間に見せて判断を求める事を繰り返すプログラムを作成しようと思うのですが、人間が行う操作（比較の判断）をなるべく少なくする為には、どのようなソートのアルゴリズムを選択したら良いでしょうか？ ソートのアルゴリズムの説明などを読むと、例えば、「バブルソート」及び「選択ソート」ではｎ(ｎ－１)／２の比較が必要になるそうですが、この比較の回数が最も少ない方法を探しています。 また、例えばA,B,Cの比較に置いて、 A＞B、B＞Cの比較後にはAとCは比較せずともA＞Cの関係が成り立つのですが、こういった事も考慮した上での比較回数の最も少ないソートの方法が知りたいです。 以上、ご指導のほど、よろしくお願い申し上げます。
- ベストアンサー
- その他（プログラミング・開発）
- 単純挿入ソート法の要素の比較回数についての問題
単純挿入ソート法の要素の比較回数、移動回数についての問題 『単純挿入ソート法は、シャトルソート法とも呼ばれ、挿入とシフトを用いるソートである。 下図（添付図）はこのソート法の１ステップを示している。 配列a[0],…,a[n-1]があって、a[i]より前の部分がソートされている。 ここで、a[i]の値をwとする。 a[0],…,a[i-1]の 部分で、w が入るべき位置を探す。 この位置をj とする。配列の範囲 a[j],…,a[j-1]をa[j+1],…,a[i] ヘシフト する。最後に、wをa[j]に格納する。 このような操作を、最後まで繰り返す。 以下の問に答えよ。 問(1)～(3) 省略 問(4)単純挿入ソート法で要素の比較回数のオーダーを答えなさい。ただし、配列の要素数を n とする。 問(5)単純挿入ソート法で要素の移動回数のオーダーを答えなさい。ただし、 配列の要素数を n とする。』 問(1)～(3)は単純挿入ソート法で配列を昇順にソートするC言語で記述されたプログラムに関する問題なのですがそちらは解けました。 問(4)は比較回数のオーダーを S とすると、最悪の場合 n(n-1)/2 回 比較を行う必要があるので、S=n(n-1)/2 問(5)は移動回数のオーダーを T とすると、最悪の場合 n(n-1)/2 回 移動を行う必要があるので、T=n(n-1)/2 と考えているのですが自信がありません。 そもそもここで問われているオーダーとは回数のことをいってるのか、そうではないのかが分かりません。 どなたか説明していただけますと大変助かります。解答以外にもこの問題に関連することに対してのアドバイスなどがありましたら答えてくださると嬉しいです。 時間がなくて少し焦っています。どうか何卒よろしくお願いします。
- 締切済み
- C・C++・C#
- Tukey法による多重比較
今SPSSでTukey法による多重比較をしました。 a）経験群 b）経験しそうになった群 c）非経験群 の三つのある得点の平均を比較しました。 すると、結果が a）n=6,Mean=68.67,SD=7.941 b）n=32,Mean=63.28,SD=11.535 c）n=259,Mean=57.33,SD=12.293 と出まして、 b>c という有意差が出ました。 b>cと出てるのに、何故a>cとはならないのでしょうか？ nが小さいからでしょうか？ まだまだ統計学を理解しきれていません。 ご教授願います。
- ベストアンサー
- その他（学問・教育）
- クイックソート キー比較回数をカウント
クイックソートでキー比較回数をカウントする。 以下のように書いたのですが、 22行目(C++;)の状態ではまだ何かが足りないらしいのですが、何が足りないのか教えてください。 /* ここからプログラム */ #include <stdio.h> #define N 10 /* 配列aの要素数 */ static int a[N] = { 7, 20, 1, 18, 9, 15, 24, 10, 3, 12}; int main() { __int i, j; /* ループカウンタ */ __int temp; /* 交換用 */ __int pivot; /* 基準値 */ __int C = 0; /* キー比較回数C */ __int M = 0; /* データ置換回数M */ __i = 0; /* iを先頭要素番号 */ __j = N - 1; /* jを末尾要素番号 */ __pivot = a[j / 2]; /* 任意の要素を取り出し基準値 */ __while (i <= j){ ____C++; /* 22行目,キー比較回数カウント */ ____while (a[i] < pivot) /* a[i] >= pivot が見つかるまで */ ______i++; /* iを増加 */ ____while (a[j] > pivot) /* a[j] <= pivot が見つかるまで */ ______j--; /* jを減少 */ ____if (i < j && a[i] != a[j]) { /* i < j かつ a[i]≠a[j] ならば */ ______temp = a[i]; /* a[i]とa[j]を交換 */ ______a[i] = a[j]; ______a[j] = temp; ______M++; /* データ置換回数回数カウント */ ______i++; /* iを増加 */ ______j--; /* jを減少 */ ____} ____if (i == j || a[i] == a[j]){ /* i = j かつ a[i] = a[j] ならば */ ______i++; /* iを増加 */ ______j--; /* jを減少 */ ____} __} /* ここから結果表示 */ __for (i = 0; i < N; i++) ____printf("%3d ", a[i]); __printf("\n"); __printf(" キー比較回数 : %3d回\n データ置換回数: %3d回\n", C, M); /* ここまで結果表示 */ __return 0; } /* ここまでプログラム */
- 締切済み
- C・C++・C#
- 配列の比較について・・・困ってます・・。
ご質問させていただきます。 これは、fin2というファイルから数値を抜き出し配列に格納して、finの文字列と比較し、その文字列のある場所で配列の数値と比較し、合致したら、ある出力をするというものなんですが、 配列に格納した数値が、 a[1]=[123] b=[234] a[1]=[345] b=[400] というふうに増えていくときは問題ないですが、途中でたとえば a[n]=100 b[n]=400 a[n+1]=300 b[n+1]=358 という風にn+1番目のaより、n番目のbが大きいときに、止まってしまうんです、これをうまく処理して最後まで比較させたいんですが、どうしてもうまくいきません。どなたかたすけてください。やはり、 n==b[yabu]の処理の後になんか書けばいいんでしょうか？長々と申し訳ございませんでした。 if(fin2!=NULL) { int yabu=0; for(int i=0; fgets(c,CHARMAX,fin2)!=NULL;i++) { sscanf(c,"%d%*c%*c%d",&a[yabu],&b[yabu]); fprintf(fout2,"%d::::::::::::::%d:%d\n",yabu,a[yabu],b[yabu]); yabu++; } } int yabu=0; n=0; while(fgetc(fin)!=EOF) { n++; if(n==a[yabu]) { fprintf(fout2,"A "); } else if(n==b[yabu]) { fprintf(fout2,"B "); yabu++;} else {fprintf(fout2,"C "); } } printf("%d\n",yabu);
- ベストアンサー
- C・C++・C#
- 比較回数と交換回数表示について
クイックソートとバブルソートの比較回数と交換回数を確認するため以下のようなプログラムを作成しました。 #include <stdio.h> #define SIZE 32 short bubble_sort(short s[],int x); short quick_sort(short s[],int y,int z); void show(short s[],int n); short bubble_sort(short s[],int x){ //バブルソート int i,j,count,sum; short tmp; count=0; sum=0; for(i=0; i<SIZE; i++){ for(j=i+1; j<SIZE; j++){ count++; if(s[i] > s[j]){ tmp=s[i]; s[i]=s[j]; s[j]=tmp; sum++; } } } show(s,SIZE); printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum); } short quick_sort(short s[],int left,int right){ //クイックソート int i, j,tmp,count,sum; int point; i = left; j = right; point = s[(left + right) / 2]; count=0; sum=0; while (right!=1) { count++; while (s[i] < point) i++; count++; while (point < s[j]) j--; if (i >= j) break; tmp=s[i]; s[i]=s[j]; s[j]=tmp; i++; j--; sum++; } show(s,SIZE); printf("\n比較回数:%d回\n交換回数:%d回\n",count,sum); if (left < i - 1) quick_sort(s, left, i - 1); if (j + 1 < right) quick_sort(s, j + 1, right); } void show(short s[], int n) { int i; for (i = 0; i < n ; i++){ printf("%d ", s[i]); } printf("\n"); } int main(void){ short s[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28}; printf("ソート前:\n"); show(s,SIZE); printf("バブルソート後:\n"); bubble_sort(s,SIZE); printf("\n"); short t[SIZE] ={25,29,1,32,14,22,26,3,15,27,5,7,24,12,31,23,6,20,10,8,18,16,11,30,13,2,4,21,17,19,9,28}; printf("ソート前:\n"); show(t, SIZE); printf("ソート中:\n"); quick_sort(t,0,SIZE-1); printf("クイックソート後:\n"); show(t,SIZE); } これを動かして頂ければ分かるとは思いますが、バブルソートの時のような結果（途中経過なしで最終結果と比較回数と交換回数の表示）を クイックソートでも出したいのですが、うまく出せずに困っています。 どのようにすれば良いのかご指導いただけませんでしょうか？また、実行環境が会社にしかないので、 できれば結果も頂けるとありがたいです。失礼ですみませんがよろしくお願い致します。
- 締切済み
- C・C++・C#
- 数字の並び換えの最適手順
Ｎ個の異なる数字があります。これを大小の順にならべ換えます。 最適手順数は計算上はＬｏｇ（Ｎ！）／Ｌｏｇ（２）です。 その最適手順の一般化は可能でしょうか。 例１：Ｎ＝４のとき Ａ、Ｂ，Ｃ，Ｄと４個の数字があって １回目 ＡとＢを比較 結果Ａ＞Ｂが判明 ２回目 ＣとＤを比較 結果Ｃ＞Ｄが判明 ３回目 ＡとＣを比較 結果Ａ＞Ｃが判明 ４回目 ＢとＣを比較する Ｂ＞Ｃのときは、Ａ，Ｂ，Ｃ，Ｄとなって並び替え終了。 こういう都合の良い結果での並び換え終了は手順からはずします。 Ｃ＞Ｂのとき ５回目 ＢとＤを比較する Ｂ＞Ｄのとき Ａ、Ｃ，Ｂ，Ｄ で終了 Ｄ＞Ｂのとき Ａ，Ｃ、Ｄ、Ｂ で終了 例２：Ｎ＝５のとき Ａ、Ｂ，Ｃ，Ｄ、Ｅと４個の数字があって １回目 ＡとＢを比較 結果Ａ＞Ｂが判明 ２回目 ＣとＤを比較 結果Ｃ＞Ｄが判明 ３回目 ＡとＣを比較 結果Ａ＞Ｃが判明 ４回目 ＥとＣを比較 ５回目 Ｅ＞ＣのときＥとＡを比較、Ｃ＞ＥのときＥとＤを比較 ６回目 ここから場合わけひどくなります。 例としてＡ＞Ｅ＞Ｃ＞ＤのときＢとＣを比較 ７回目Ｂ＞ＣのときＢとＥを比較、Ｃ＞ＢのときＢとＤを比較 例３：Ｎ＝６であれば１０回、Ｎ＝７であれば１３回でした。 これらはＮ＝５の手順のあと６個目、７個目の位置決めするだけ。
- 締切済み
- 数学・算数
- n個の異なる分銅と天秤ばかりを用いた問題
n個の相異なる重さの分銅の重さをA_n[g]とする。(A_nは整数とする) 1個の天秤ばかりとこれらの分銅を用いて、無限にある液体（粉末でもいい）からX[g]を測って取り出す場合、天秤ばかりを使用する最小の回数Nを求める問題を考えます。 この場合、X=Σ_(1～n)B_n A_nとなるような自然数｛B_1,B_2,…,B_n｝を導入すると、 2^N-1≦min｛max(B_1,B_2,…,B_n)｝＜2^N で表されるNが最小試行回数となる。 上記の結論で間違いないでしょうか？
- 締切済み
- 数学・算数
- 再起呼び出しの回数をカウントするプログラム
現在学校の課題で プログラムを組んでるんですが ちょっとよくわからないことがあるので教えてください 再起呼び出しの回数をカウントして その回数を返したいのですが 例えば coid honoi(int n,char a,char b,char c) { int count=0; if (n>0) { hanoi(n-1,a,c,b); count++; } } のようなプログラムを組むと hanoi(n-1,a,c,b) を呼び出すと、countが再度 0 に戻され count=1 になってしまいます。 同様に if() { int count=0; hanoi(); count++ } としても、count=1のままでした。 再起呼び出しをするたびに、この count値を増やしていくには どのようにプログラムを書けばよいのでしょうか？ まだCは初心者レベルなので 易しめにご説明ください。 よろしくお願いします。
- ベストアンサー
- C・C++・C#
- 最小回数で応答を得るには
次のような問題を考えます。 送信側：1人，受信側：4人（A，B，C，D）いる。 送信側は、受信側4人それぞれの情報を獲得したい。 受信側は、応答として、0、1で返答し、1がYES、0がNoを表すものとする。 送信側が得られる受信の情報は、関数ask(・)から返される値である。 関数ask(・) 入力：4人のだれに聞くか N1,N2,N3,N4（例：N1=1,N2=0,N3=1,N4=0）1で聞く，0で聞かない 出力：入力で指定した受信側の応答のOR情報（一人でもYESだったら、1が返される） 但し、1回目：A，2回目：B，3回目：C，4回目：Dという聞き方はなしとし、初回は4人全員に聞く ものとする。 いま、A=1，B=1，C=1，D=1であるとして、送信側は最小何回で受信側A～Dのそれぞれの 情報を知ることができるか？ いま、自分が考えている方法は、 1回目：入力 N1=1、N2=1、N3=1、N4=1（対象全員） 出力 1 送信側は、4人のだれかがYESと言っていることを確認。 2回目：入力 N1=1、N2=1、N3=0、N4=0（対象A,B） 出力 1 送信側は、4人のうち、A,BがYESと言っていることを確認。 しかし、そうなると、C,DもYESの可能性がある。 3回目：入力 N1=0、N2=0、N3=1、N4=1（対象C,D） 出力 1 送信側は、4人のうち、C,DがYESと言っていることを確認。 4回目：入力 N1=0、N2=1、N3=1、N4=0（対象B,C） 出力 1 送信側は、4人のうち、B,CがYESと言っていることを確認。 5回目：入力 N1=1、N2=0、N3=0、N4=1（対象A,D） 出力 1 送信側は、4人のうち、A,DがYESと言っていることを確認。 ですが，あまり効率的であると思えません。ORをとっているので、上記でもし、1回目に1、 2回目に0が返されれば、3回目以降は、C,Dのみに聞けばよいと思い、この方法にしましたが、 A～D全員が1である状況なので、この方法では効果がないと感じています。 実際には、A～Dは4人より多い場合も想定できるようにしたいですが、今回は 擬似的な問題として、上記のような問題を考えています。 何か他によい方法はないでしょうか？ ご教授頂きたくお願い申し上げます。
- ベストアンサー
- 数学・算数
補足
＞あなたが対象としているnはどの程度の数なんでしょうか？ ん～ 実は言いたくないのですが、（言うと何が目的がばれそうで。。ｗ）かなり大きな値です。 比較に所用する時間は一ヶ月以上とかですねｗ