C言語なら俺に聞け（入門編）Part 125 [sc](★0)
-
- 1
- 2014/02/16(日) 01:49:14.42
-
C言語の入門者向け解説スレッドです。
★前スレ
C言語なら俺に聞け（入門編）Part 124
http://toro.2ch.net/test/read.cgi/tech/1389096769/
★過去スレ
ttp://makimo.to:8000/cgi-bin/search/search.cgi?q=%82b%8C%BE%8C%EA%82%C8%82%E7%89%B4%82%C9%95%B7%82%AF&andor=AND&sf=0&H=&view=table&D=tech&shw=5000
★教えて欲しいのではなく宿題を丸投げしたいだけなら
↓宿題スレ↓へ行ってください。
C/C++の宿題片付けます 166代目
http://toro.2ch.net/test/read.cgi/tech/1381909900/
★C++言語については避けてください。C++対応明記スレへどうぞ。
★分からない事をなるべく詳しく書いて下さい。
★ソースコードを晒すと答えやすくなるかもしれません。
# 抜粋／整形厳禁、コンパイラに渡したソースをそのまま貼ること。
# サイズが大きい場合はアップローダ等を利用してください。
ttp://codepad.org/
ttp://ideone.com/
★開発環境や動作環境も晒すと答えが早いかもしれません。
★質問者は最初にその質問をした時のレス番号を名前欄に書いて下さい。
【重要】
当たり前の事ですが、2chではコピペ荒らしは禁止されています
-
- 699
- 2014/03/24(月) 19:37:56.84
-
左右の数値比較後 上下の比較で効率的に並ぶからか？
ラディックスソートっぽくうごかせるね
-
- 700
- 2014/03/24(月) 19:39:16.65
-
操作の数で競うのなら総当たりで全ての組み合わせを試して最も操作数が少なかった手順で交換すればいいだけだろう。
-
- 701
- 2014/03/24(月) 19:40:04.26
-
全く分からない…
18と6を比較するのに何故18mod6と6mod6を比較するのでしょうか？
-
- 702
- 2014/03/24(月) 19:41:56.74
-
例えば最初はバブルソートでも何でもいいから一度正解を見つける。
その次にそれにかかった手順数以下で可能なすべての操作の組み合わせを総当たりで試し
最も少ない操作数で達成できたものを最終的な回答として採用する。
こうなるだけだが…。問題設定がおかしいとしか思えん
-
- 703
- 2014/03/24(月) 19:42:36.82
-
アルゴリズムまじで頭の良し悪しが分かる…
全く思いつかない
-
- 704
- 2014/03/24(月) 19:44:38.07
-
「縦3横6計18セルある長方形に１〜18までの要素を1個ずついれて」
なんだから、最適化された処理は
const static ans[3][6] = { { 1,2,3,4,5,6},{7,8,9,10,11,12},{13,14,15,16,17,18}};
だと思うんだけど。固定値だよね？
-
- 705
- 2014/03/24(月) 19:45:33.50
-
行でソートの場合
6
3
1
をソートしたら
1
3
6
になって6は1行目最終列なのに、遠のく事にならないでしょうか？
-
- 706
- 2014/03/24(月) 19:45:34.95
-
>>701
整列されている状態を6で割った余りにしてみろ
縦横バブルソートだと
12...
34...
56...
ってなったら積む
-
- 707
- 2014/03/24(月) 19:47:18.04
-
>>704
与えられた要素をその整列された状態にするのに「上下左右の交換」が最低何回必要かって問題だから
ソートした結果を答えろという問題ではない
-
- 708
- 2014/03/24(月) 19:50:16.45
-
そもそも整列された状態から交換を繰り返さないとダメですね
適当に配置した標本だと元通りできないですね…
>>706
全く分かりません、余りだと詰むんでしょうか？
-
- 709
- 2014/03/24(月) 19:51:49.13
-
「どういうアルゴリズムが最適か」だから整列不能も含めて判断しろってことじゃないの
いずれにしろ問題が曖昧すぎる
-
- 710
- 2014/03/24(月) 19:51:58.70
-
馬鹿には無理
-
- 711
- 2014/03/24(月) 19:52:28.14
-
とりあえず、最初にあまりで比較して最後は要素同士を比較ってことですか？
-
- 712
- 2014/03/24(月) 19:55:26.67
-
>>709
整列可能という前提です、問題に不備がありすいませんでした。
確実に整列できる方法です。
例えばバブルソートの場合どんなパターンでもO(n(n-1)/4)回で整列可能です。
この場合もO(?)回で完全に整列できるのか知りたいです。
元々整列されていた場合早くするというのは最適化問題になりますので
そういう問題ではなくMAXオーダーを求めたいという事です。
-
- 713
- 2014/03/24(月) 20:07:30.14
-
>>708
１ ４ ７ 10 13 16
２ ５ ８ 11 14 17
３ ６ ９ 12 15 18
"縦だけ""横だけ"で値の大小による比較ではソート済み（これ以上の比較は不要で収束している）
が、解の並びではない
-
- 714
- 2014/03/24(月) 20:11:31.94
-
分かりません…
-
- 715
- 2014/03/24(月) 20:15:11.99
-
ID:5KtS3atQ
こいつに何言ってもわかんないだろ
NGに入れとけクズども
-
- 716
- 2014/03/24(月) 20:15:38.42
-
そもそも横 縦とも大小の矛盾が無いけど解は無い例なんて
存在するんでしょうか？
3 4 8 9 10
2 5 12....
..........
こういう事ですよね？
無いと思うのですが
-
- 717
- 2014/03/24(月) 20:16:33.50
-
>>715
おまえは毎日ハロワ通いと転職サイト最低３カ所チェックする
日課を終わらせること。
-
- 718
- 2014/03/24(月) 20:21:10.20
-
ルービックキューブを可能なパターン全てこなしてから、最短手順を求めるやつはいない。
最短に近い攻略法で攻めるだろ。
-
- 719
- 2014/03/24(月) 20:27:54.88
-
結局オーダー回数は理論的に求められないってことでＯＫですか？
そうなるど最適化問題に帰着するんでしょうか
-
- 720
- 2014/03/24(月) 20:29:59.92
-
>>719
なんでそんな結論になったのか・・・
何処にもランダム要素なんて発生し無いのに論理的に求められない理由は無いぞ？
-
- 721
- 2014/03/24(月) 20:32:21.66
-
>>720
この問題はオーダー何回でしょうか？
後最適化問題じゃないけど、早くする方法みたいなのもあれば
例えばバブルソートを双方向バブルソートにするみたいな
最適化ではないですが強化バージョンなので…
-
- 722
- 2014/03/24(月) 20:34:15.30
-
ゴミニートことQZが大発狂中！大発狂中！
ム板を腐らせるゴミは出ていけ！！
-
- 723
- 2014/03/24(月) 20:37:04.61
-
>>721
まず基本的な事から。名前書け。
質問を小出しにするな体系立てて、自分で考えて
わからないことだけ背景含めて説明しながら質問しろ。
-
- 724
- 2014/03/24(月) 20:37:19.07
-
素朴な疑問
ビッグオー表記で O(n^2) ならまだしも O(n(n-1)/4) って意味あるの？
-
- 725
- 2014/03/24(月) 20:43:19.67
-
>>723
背景ですが、頭脳王という番組を見て9マスの正方形の中にある8個の数字の
書いたパズルを並び替えるという問題があってそこから感銘を受けて18マス
ではどうかという問題を思いつきました。
最初は最適化問題でどうしたら最短で解けるかという事を考えましたが
それ以前に少なくとも何回やれば、つまり最大何回やればどんなパターンで
も整列できるのかすら分からないのでそっちから考えたいと思いました。
-
- 726
- 2014/03/24(月) 20:49:27.98
-
>>717
わろたｗｗｗ
-
- 727
- 2014/03/24(月) 20:53:52.27
-
>>725
いや、まずは名前書けよ・・・
-
- 729
- 2014/03/24(月) 20:57:15.33
-
>>725
名前は次から書けばいいとして話を進めるか。
大まかな背景は解った。
で、どこまで考えて結果はどうなって、いまは何に躓いてるんだ？
-
- 730
- 2014/03/24(月) 20:59:09.34
-
ほらみろゴミ（質問者）が調子に乗り出した
もう目も当てられないよこのスレ
-
- 731
- 2014/03/24(月) 21:00:03.14
-
>>728
あれ。2chは初めて？
流石に実名は求めてない。
他人とかぶらなければ全く問題無し。
質問とかの連続した話題の時は、他の人が話題追いやすいように
一番初めに質問したときの番号を埋め込んどくのが正解。
-
- 733
- 2014/03/24(月) 21:09:33.12
-
ゴミ回答するなQZ
お前は不要な存在
-
- 734
- 2014/03/24(月) 21:13:06.28
-
>>732
縦をソートする意図がわかんない
最終的に移動完了させるかたちは一つしかないだろ？
すべての移動は、最終的な位置に近づく用に移動させるべきだ。
ここまでは解るよな。後は考えたら見えるはずだ。
-
- 735
- 2014/03/24(月) 21:18:49.54
-
ろくにCできないゴミが発狂していいスレじゃねえだろ
マジで消えろゴミクズうんこ馬鹿ども
-
- 737
- 2014/03/24(月) 21:29:18.09
-
お前はID真っ赤だ
これ以上質問するなゴミすれになるぞ
-
- 738
- アルゴリズム
- 2014/03/24(月) 21:40:07.75
-
うん？やっぱり要素数18のバブルソートなのかな…
-
- 739
- 2014/03/24(月) 21:48:00.78
-
お前調子のるな
質問者だからって許されることじゃない
-
- 740
- アルゴリズム
- 2014/03/24(月) 21:48:49.36
-
結論出ました。上限回数はバブルソートの回数ですね。
長方形を一列とみなすという事ですが、縦も交換できるから
強化バージョンが作れると思うのですが無理でしょうか？
-
- 742
- 2014/03/24(月) 22:08:40.60
-
これだけレスついて回答しないとか馬鹿だろ
スレを私物化するな、出ていけ
-
- 743
- 2014/03/24(月) 22:09:53.03
-
自分の頭で考えるってことができないんじゃプログラミングは無理
クレクレで出来ることなんてたかが知れてるぞおい
-
- 744
- アルゴリズム
- 2014/03/24(月) 22:18:58.11
-
使える変数はa[17]だけとします
つまり好きな要素を選んだり、選択ソートみたいに最小要素を選んだり
する事はできない。
-
- 745
- 2014/03/24(月) 22:30:34.53
-
チョンの脳なんじゃね？本国に帰れよ
-
- 746
- 2014/03/25(火) 00:11:31.10
-
愚直に1から順番に移動してみた例 :
https://ideone.com/5EgKA2
各値を線形探索しているため遅い。
-
- 747
- 2014/03/25(火) 00:20:15.28
-
>>746
96行も…ありがとうございます
それってバブルソートのアルゴリズム使ってないですか？
-
- 748
- 2014/03/25(火) 00:25:10.02
-
マナーすら守れない奴はこないでね。
回答なんて誰もできないから。
マナーの無い奴に回答すると調子乗って暴れまくるし
ほかの馬鹿がマナー守らなくていいと勘違いするからね。
だから、お前には誰も回答しないんじゃなくて、 "誰も回答できない" んだよ。
-
- 749
- 2014/03/25(火) 00:33:14.10
-
>>747
バブルソートに当たるかどうかは分かりませんが、かなり近い操作はしています。
1. n = 1とする
2. nと一致する横x番目, 縦y番目を検索する
3. nが位置すべきなのは横correct_x番目縦correct_y番目である
4. xがcorrect_xに近づくように隣同士交換する
5. yがcorrect_yに近づくように隣同士交換する
6. n = n + 1して2.へ(n = 18まで繰り返す)
左上から確定していき、初めにxで並び替えるため、左上を絶対に通りません。
従って必ず並び替えられます。
このページを共有する
おすすめワード