- ベストアンサー
並べ替えの最小移動回数
pori_boyの回答
- pori_boy
- ベストアンサー率60% (18/30)
移動しないものに着目すると、これらの数はもとの 順列において必ず昇順に並んでいる必要があります。 よって、与えられた順列から、最長の昇順部分列を 見つけることができれば解は求まります。 例えば、23451なら2345, 31425は345が最長部分列で あり、これ以外のものが移動することになります。 この昇順の最長部分パスも求めるための方法ですが、 グラフ理論についての知識があれば、非巡回有向 グラフ上での最長パス問題に帰着されることが、 動的計画法をご存知でしたら、その手法によって 計算できることが説明できます。 sunasearchさんが、これらの知識をお持ちかどうか わからないので、ひとまずここまでをアドバイスと。 もし、説明が必要でしたら、また書き込みます。
関連するQ&A
- 並べ替えの最小手順について
パンケーキソートに似ているのかもしれませんが、以下の問の最小手順について教えていただければと思います。 (問) いま、1から10までの整数がめちゃくちゃに並んでいる。 例:(9,5,7,3,10,2,1,4,6,8) これを(1,2,3,4,5,6,7,8,9,10)と並べ替えたい。 行える操作は、「ある数1つのみを現在の場所から引き抜いて、別の場所に挿入する。」とする。このときの最小手順を知りたい。 例えば、(1,2,9,3,4,5,6,7,8,10)の場合は、最小手順としては、「9を現在の3番目から引き抜いて、9番目に挿入する」の1手順です。 私自身の最終的な目標としてExcelでこれをやりたいので(いまA列に縦に数字が並んでいて、途中経過がB列、C列・・と示されていく感じで。もちろん自動並べ替えは使わずに)、VBA等で示して頂けるとかなり助かりますが、考え方だけ教えていただけるのでも有難いです。 どうぞ宜しくお願い致します。
- ベストアンサー
- 数学・算数
- 最小回数で応答を得るには
次のような問題を考えます。 送信側：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人より多い場合も想定できるようにしたいですが、今回は 擬似的な問題として、上記のような問題を考えています。 何か他によい方法はないでしょうか？ ご教授頂きたくお願い申し上げます。
- ベストアンサー
- 数学・算数
- 乗算回数最小の冪乗アルゴリズム
断面ｎ次モーメントを計算するプログラムを書いていてふと思ったのですが， X^n を乗算の繰り返しで計算する場合，一般の自然数ｎについて乗算回数最小の アルゴリズムって存在するんでしょうか？ たとえばｎが２の冪乗の場合，２乗を繰り返すと１回ごとに X → X^2 → X^4 → X^8 → X^16 → … となるので，X^n は log2(n) 回の乗算で計算でき，たぶんこれが最小だと思います． その他のｎについてはどうでしょうか？ ｎの素因数分解とか使えばうまくいくんでしょうか？
- ベストアンサー
- 数学・算数
- n!が10の40乗で割り切れるときの最小のn
【問題】 n!が10^40(10の40乗)で割り切れるときの最小のnを求めよ。 【解答】 10=2×5 であるからn!が10で40回割り切れるためには、 n!が5で40回割り切れなければならない。 また、そのときn!は2で40回割り切れる。 n=5 のとき 5の倍数は 5÷5=1 (個) n=5^2 のとき 5の倍数は 25÷5=5 (個) 25÷25=1 (個) n=5^3 のとき 5の倍数は 125÷5=25 (個) 125÷25=5 (個) 125÷125=1 (個) (25+5+1)+(5+1)+1+1+1=40 であるから、求める最小のnは 5^3+5^2+5+5+5=165 解答の意味がよくわかりません。 5で40回、2で40回割り切れるのはわかるが なぜ、n=5,5^2,5^3の場合だけやる？ n=2,2^2,2^3,・・・は考慮しなくてよい？ それに最後の結論の２行がまったく意味不明です。。 ご教授宜しくお願いします。
- 締切済み
- 数学・算数
- バブルソートの交換回数、連結（リンク）リストの短所
バブルソートの交換回数を表す一般的な式（nを用いた式）が分かりません。 具体的には n個のメンバーの場合1ラウンドあたりn/2回の交換なので 全ラウンドでの交換は[(n/2)*{(n-1)/2}]/2=n*(n-1)/8回となるらしいのです。 でも例えば例題で「96 23 87 8 76」というn=5の数字群をバブルソートで並び替えるには、上の式だと並び替える回数は2.5回になってしまいます。小数が出るのはおかしいと思うのですが・・・ この場合交換回数は地道に数えるしかないのでしょうか。 ちなみに比較回数はn(n-1)/2なので10と出せました。 あと連結（リンク）リストの長所は検索できたのですが短所についての記述が見つかりません。 短所はあるのでしょうか、あるならどのような内容なのでしょうか。 一方でもいいので宜しくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- EXCEL連続した回数のカウント
エクセル初心者です。 連続した数字の回数のカウントの仕方が分からず困っております。 A列に0と1が50個並んでいます。 50個の0と1はその並び順が変化します。 1が先頭から5個以上、連続して並んだ時に、その1が連続した回数を特定のセル(例えばB1)に表示するようにしたいのです。 下の例1ではA3から1が8個連続していますので、B1のセルに8が入るようにしたいのです。 並びが変わりますので、先頭のA3が0の例2や、1が5個以上連続しない例3の場合は、B1のセルは空白のままになるようにしたいのです。 1が先頭のA3から5個以上連続した時だけ、その先頭から連続した回数(個数)を数えるようにしたいのです。 どうぞよろしくお願いします。 (例1) A列 B列 C列・・ 1行 2行 3行 1 4行 1 5行 1 6行 1 7行 1 8行 1 9行 1 10行 1 11行 0 12行 0 ・ (例2) A列 B列 C列・・ 1行 2行 3行 0 4行 1 5行 1 6行 1 7行 1 8行 1 9行 1 ・ (例3) A列 B列 C列・・ 1行 2行 3行 1 4行 1 5行 1 6行 1 7行 0 8行 0 ・
- ベストアンサー
- オフィス系ソフト
- 最小固有値に関する定理、公式を教えてください。
最小固有値に関する公式について教えて欲しいのですが、 正定行列Aの任意の固有値をλ(>0),最小固有値をλmin(>0)とするとnに関わらず n・e^(-λ)≦n^(-λmin) みたいな公式ってありますか？？ eは自然対数です。 似たような定理でもいいのであれば教えてください、よろしくおねがいします。
- 締切済み
- 数学・算数
- VBAでの最小値抽出
ExcelのVBAにおいて，最小値の抽出方法の質問です． たとえばA1に変数nがあり，A2にnの関数（例えば=n^4-2n^3+5n-10とか）があるとします． A1を1から100まで動かしたときのA2の最小値を求めたいのですが，これはそのまま1から100まで値をズラっと出力すれば，あとはそこから最小値を探すだけで求まりますが，こういう方法はとらず，一発でこの最小値を1つのセルに出力させたいのです． いろいろわけあって，使用するセルを最小限におさえたく，この方法が知りたいのです． よろしくお願いします．
- ベストアンサー
- Visual Basic
- エクセルで指定範囲の最大値・最小値を求めたい
エクセルで、A列、B列、C列・・・にそれぞれ１００個ずつ数値データがあります。 各列で1番上のデータからｎ番目のデータまでの範囲の最大値・最小値と、 ｎ+１番目のデータから100番目のデータまでの範囲の最大値・最小値をそれぞれ求めたいのです。 ｎの値は列ごとに異なっており、例えばA列のｎ値は[A105]のセルに記入されています。 [A102]＝40のとき、 =MAX(A2:A40) =MAX(A41:A10１) などと個別に範囲指定をせずに、[A105]の値を引用して最大値・最小値を求めるにはどうすればいいでしょうか。
- ベストアンサー
- オフィス系ソフト
お礼
ご回答ありがとうございます。 ＞最長の昇順部分列を見つけることができれば解は求まります。 これで、確かに最長パスを求めれば、最小の移動回数が求められる気がします。 最長パスは、最悪n^2オーダのアルゴリズムを組めば求められると思いますが、それを用いた移動回数が最小であることは保証されますでしょうか？