[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (981ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
8(4): 2019/11/18(月)20:03 ID:EbN/HVpO(1) AAS
>>4
両端固定で最小隣接差を最大化する条件で回答する。Rですべての並べ方を虱潰しに
調べるのが 外部ﾘﾝｸ:ideone.com で、結果は>>6が言う通りになる。
n = 10 ではすぐに終わるが、それを超えると時間がかなりかかるし、環境によっては
メモリ不足になる。
もう少し効率的に調べるのが 外部ﾘﾝｸ:ideone.com で、n = 16 までは
すぐに終わる。それを超えると時間がかかるように段々なるので、さらなる効率化が
必要。
n = 10 と n = 16 の結果から、nが偶数の場合は>>6が言うように規則性が見られ、
nが大きくなっても並べ方は常に2通りで、例えば n = 256 のときは
省3
9(3): 2019/11/21(木)21:52 ID:1mUnuvuP(1/3) AAS
AA省
10: 2019/11/21(木)21:53 ID:1mUnuvuP(2/3) AAS
AA省
11(1): 2019/11/21(木)21:54 ID:1mUnuvuP(3/3) AAS
nが奇数の場合にも偶数の場合と似たようにしてd >= (n - 1) / 2 はあり得ず、
d = (n - 1) / 2 - 1 から調べれば良いことが分かるが、偶数の場合と違い
選択確定できる数はない。>>8の元請け関数のforループの開始値をnではなく
n %/% 2 - 1に置き換えるだけでは、実行時間は5〜6%くらいしか短縮されない。
偶数の場合のような図の作成により、調べる組み合わせを減らしていくことは
できるが、プログラムを書くのはかなり面倒そう。
16: 2019/11/23(土)22:51 ID:ubdNKuk5(1) AAS
>>4を>>11の方式で求めるプログラムを書いてみた: 外部ﾘﾝｸ:ideone.com
nが偶数の場合、n = 8までは>>8の2番目のプログラムと比べて遅いが、n = 10, 12,
14, 16, 18, 20ではそれぞれ1.78倍、7.16倍、49.8倍、327倍、3120倍、30800倍の
速度になり、差がどんどん開いていく。n = 256でも1秒未満で求められる。
nが奇数の場合、n = 11までは遅いが、n = 13で同程度になり、n = 15, 17, 19, 21では
それぞれ3.25倍、12.6倍、58.8倍、325倍の速度で、差がやはりどんどん開いていく。
nが2大きくなるごとに並べ方の通り数が2倍以上に増えるようなので、n = 255では
どんなアルゴリズムを使ってもコンピュータの性能限界をはるかに超えてしまう。
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.038s