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ではコピペ荒らしは禁止されています
-
- 681
- 2014/03/24(月) 06:53:36.52
-
>>656
学校の宿題じゃないならboostの乱数ライブラリ
-
- 682
- 2014/03/24(月) 11:12:28.50
-
QZバレバレの回答ｷﾀｰ
-
- 683
- ◆QZaw55cn4c
- 2014/03/24(月) 18:58:49.11
-
>>679
>>673 に回答例を挙げておいたから，暇だったらみてね
>>681
そのモンテカルロ法じゃないそうだ
>>682
毎日大変ですね頑張ってください http://hissi.org/read.php/tech/20140324/aU4rT3l1TUo.html
-
- 684
- 2014/03/24(月) 19:02:46.76
-
今、縦3横6計18セルある長方形に１〜18までの要素を1個ずついれて、
下の状態が整列されている状態とする。
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
整列されていない状態の例は以下である。
9 18 3 4 5 13
7 8 1 10 11 6
12 14 15 16 17 2
-
- 685
- 2014/03/24(月) 19:05:01.32
-
任意の整列されていない状態に対して、縦横隣同士を交換して
整列されている状態にする場合、どういうアルゴリズムが最適か？
という問題なんんですがどういうアルゴリズムがいいですか？
プログラムで書けるならそれも教えて下さい。
ソートを使うのがいいですが、隣同士なので体系的なソートの場合
バブルソートしか使えません。
僕の考えは横でバブルソート、縦でバブルソートしか思いつきません。
-
- 686
- 2014/03/24(月) 19:09:29.37
-
QZバレバレの自演質問ｷﾀｰ
まじでくっせえなこのスレ
-
- 687
- 2014/03/24(月) 19:12:05.91
-
それはソートというよりパズルだな。
開いてる箇所が一箇所あって絵柄を揃えるやつとか、ルービックキューブとかの類似物。
-
- 688
- 2014/03/24(月) 19:15:38.56
-
>>685
整列完了までの「時間」を競うのか「操作の数」を競うのかどっち？
-
- 689
- 2014/03/24(月) 19:15:39.15
-
まず要素を6個ずつ3つのグループに分けてグループごとにソート
-
- 690
- 2014/03/24(月) 19:20:01.29
-
縦横隣同士を（比較）交換して整列
A(i,j) に対して比較・交換が許されるのは A(i-1,j) A(i+1,j) A(i,j-1) A(i,j+1) だけか
-
- 691
- 2014/03/24(月) 19:22:30.32
-
Cグラマーのゴミ回答キター
ゴミは目障りだから消えろよ
-
- 692
- 2014/03/24(月) 19:23:11.81
-
6で割った余りの大小で行をソート
ただし余り0は6として
列は数字の大小でソート
これ繰り返せば良いんじゃないの
-
- 693
- 2014/03/24(月) 19:24:05.56
-
逆だ、全体をソートして3つのグループに分けるだった
-
- 694
- 2014/03/24(月) 19:24:35.53
-
CPUの種類が分からなきゃ演算の向き不向きがわからんから回答不能だろ
-
- 695
- 2014/03/24(月) 19:28:35.11
-
おいQZ自演はやめろよ
見苦しいぞ
-
- 696
- 2014/03/24(月) 19:30:13.44
-
変な移動縛りのせいで
収束しない可能性があるね
-
- 697
- 2014/03/24(月) 19:32:28.70
-
>>688
走査の数ですよ
元々整列されている配列ほど走査数は少ないような方法も欲張るなら
求めたいです
-
- 698
- 2014/03/24(月) 19:35:36.37
-
>>692
回答ありがとうございます
なんで6で割った余りなんですか？
直接要素同士を比較しないんですか？
-
- 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は初めて？
流石に実名は求めてない。
他人とかぶらなければ全く問題無し。
質問とかの連続した話題の時は、他の人が話題追いやすいように
一番初めに質問したときの番号を埋め込んどくのが正解。
このページを共有する
おすすめワード