[過去ﾛｸﾞ] プログラミングのお題スレ Part16 (981ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
1(4): 2019/11/17(日)09:00 ID:xqEdXdr6(1) AAS
プログラミングのお題スレです。
【出題と回答例】
1 名前：デフォルトの名無しさん
お題：お題本文
2 名前：デフォルトの名無しさん
>>1 使用言語
回答本文
結果がある場合はそれも
【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
省11
2(2): 2019/11/17(日)10:53 ID:uilOlN75(1) AAS
>>1 おつ
3(2): 2019/11/17(日)17:37 ID:8gWobnsK(1) AAS
val 乙 = "乙"
prontln(乙)
4(7): 2019/11/18(月)02:35 ID:t9gVOJNg(1) AAS
お題：
https://i.imgur.com/JsMU4uh.jpg
明度が0〜9までのグレーの四角がグラデーション状に横並びにならんでいるとします
この状態だと隣接している四角と四角の明度の差が少ないので境目が見えづらいです
全ての四角同士の明度差ができるだけ大きくなるように並び替えるにはどういうロジックが考えられるでしょう？
四角の数が増えても対応できるような汎用的なロジックが望ましいです
両端は固定のままが理想ですが必須要件ではありません
・ボツ例：1〜4まで一つおきに左右端を入れ替える
(1) 1と8を入れ替える
(2) 2と7はそのまま
省3
5(1): 2019/11/18(月)05:41 ID:8+qUVevR(1) AAS
Σ|a_n - a_{n+1}| を最大化する問題なのか
inf{|a_n - a_{n+1}|} を最大化する問題なのか
どっちなんだ？
6(4): 2019/11/18(月)11:50 ID:BCetHxzu(1) AAS
>>4
力業で確認したら
>>5 の判定ルールで前者後者ともに最大になるのは
[0, 5, 1, 6, 2, 7, 3, 8, 4, 9] だけみたい、前者 41、後者 4
前者だけだとスコア 41 で 576通り、後者だけだとスコア 4 で 2通り
そのもう一つの解は [0, 4, 8, 3, 7, 2, 6, 1, 5, 9] で前者の判定ルールだとスコア 39
[0, 5, 1, 6, 2, 7, 3, 8, 4, 9] を偶数項と奇数項に分けると…
7(2): 2019/11/18(月)18:43 ID:DjoGz+4S(1) AAS
>>4 Java (両端固定ではない
https://ideone.com/tCrXMN
>>6
つまりこういうことかの？
両端固定で奇数個の場合はどうなるんじゃろ
8(4): 2019/11/18(月)20:03 ID:EbN/HVpO(1) AAS
>>4
両端固定で最小隣接差を最大化する条件で回答する。Rですべての並べ方を虱潰しに
調べるのが https://ideone.com/paKF2d で、結果は>>6が言う通りになる。
n = 10 ではすぐに終わるが、それを超えると時間がかなりかかるし、環境によっては
メモリ不足になる。
もう少し効率的に調べるのが https://ideone.com/OsmpbQ で、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
>>4
【nが偶数の場合の>>8の予想を理論的に説明する】(等幅フォントでの表示推奨)
n = 10のとき、最小階差をd >= 6と仮定すると 0: 4, 5, 6, 7, 8
4に隣接できる数はなく、d = 5と仮定すると9だ 1: 5, 6, 7, 8, 9
けなので、数列が途切れてしまって続かない。 2: 6, 7, 8, 9
よってd >= 5はあり得ず、d = 4から調べれば良 3: 7, 8, 9
い。d = 4のとき各数が隣接できる数を列挙する 4: 0, 8, 9
と、右図のようになる。 5: 0, 1, 9
6: 0, 1, 2
7: 0, 1, 2, 3
省12
10: 2019/11/21(木)21:53 ID:1mUnuvuP(2/3) AAS
3と6で候補がそれぞれ2個に絞られたから、それ 0: (4), (5), >6<, >7<, >8<
らが選択確定となり、右図になる。 1: [5], [6], >7<, >8<, >9<
2: [6], 7, >8<, >9<
3: [7], [8], >9<
4: (0), [8], (9)
5: (0), [1], (9)
6: >0<, [1], [2]
7: >0<, >1<, 2, [3]
8: >0<, >1<, >2<, [3], [4]
9: >1<, >2<, >3<, (4), (5)
省15
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%くらいしか短縮されない。
偶数の場合のような図の作成により、調べる組み合わせを減らしていくことは
できるが、プログラムを書くのはかなり面倒そう。
12: 2019/11/21(木)22:40 ID:vr0RSw67(1) AAS
>>4 Squeak Smalltalk。両端固定せず、対称排除なしの虱潰しで。
| min |
min := 0 -> OrderedCollection new.
(0 to: 9) permutationsDo: [:perm |
| curr |
curr := (perm overlappingPairsCollect: #-) abs min.
curr = min key ifTrue: [min value add: perm copy].
curr > min key ifTrue: [min := curr -> (OrderedCollection with: perm copy)]
].
^min value asArray "=> #(#(4 9 3 8 2 7 1 6 0 5) #(5 0 6 1 7 2 8 3 9 4)) "
省1
13: 2019/11/22(金)20:06 ID:EyqF2Cmi(1) AAS
お題：読み手を一瞬戸惑わせよ
https://ideone.com/OCwpPB
14: 2019/11/23(土)05:56 ID:KvoIJqUR(1/2) AAS
https://twitter.com/AtomDynamics16/status/1197979782719229952
キー入力を一定時間ごとに送るソフトを書いたのだけど、やっぱりグレーですか？
パケット改変して無くて、メモ帳ではうまくいってる。
UOクライアントに使うのが怖くて躊躇している。
https://twitter.com/5chan_nel (5ch newer account)
15: 2019/11/23(土)06:01 ID:KvoIJqUR(2/2) AAS
あ、UOスレに書いたものだと・・・。
16: 2019/11/23(土)22:51 ID:ubdNKuk5(1) AAS
>>4を>>11の方式で求めるプログラムを書いてみた: https://ideone.com/14wgia
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では
どんなアルゴリズムを使ってもコンピュータの性能限界をはるかに超えてしまう。
17: 2019/11/24(日)20:41 ID:NMcltmqU(1) AAS
今日は夕焼けが超絶綺麗だったよ。
今まで見たことないくらい。
まだきれいになるだろうか、というのと、これ一回で終わりだろうか。
というのがあった。
18(6): 2019/11/25(月)01:25 ID:SBJvKXmI(1) AAS
お題：Diffアルゴリズムを実装せよ。
差分アルゴリズム、さんぷる。
1:abcdef
2:abdef -> -3:c
3:bcdef -> -1:a,+3:c
4:abcdef -> +1a
以上がオレの考えるアルゴリズムだが、
もっとより良いアルゴリズムが世の中にはあるはずなので、
実装しませんか？
19: 2019/11/25(月)09:24 ID:veETdbiQ(1) AAS
>>18
それはアルゴリズムではなく入力と出力のサンプル。
まあとにかく足された文字は+と位置と足された文字(または文字列？)を出して引かれた文字は-と位置と文字を出す仕様ということだな。
で、位置は先頭が1だと。
後で時間が空いたら考えとく。
20: 2019/11/25(月)22:13 ID:UwQDpJpg(1) AAS
>>18
https://ideone.com/3VET5r
Rには編集前後の文字列のレーベンシュタイン距離を求める便利な関数adistが
備わっていて、1文字の挿入、削除、置換操作が必要な位置をI, D, S、操作が不要な
位置をMで示す文字列を返してくれる。例えば、"abdef" と "bcdef" を与えると、
"DMIMMM" が得られる。あとは、>>18の出力形式にちょっと加工するだけ。
上下前次1-新書関写板覧索設栞歴
あと 961 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.348s*