プログラミングのお題スレ Part21

**デフォルトの名無しさん** · 2022/11/13(日) 19:00:36.84

プログラミングのお題スレです。

【出題と回答例】
1 名前：デフォルトの名無しさん
　　お題：お題本文

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文
　　結果がある場合はそれも

【ソースコードが長くなったら】 (オンラインでコードを実行できる)
https://ideone.com/
http://codepad.org/
http://compileonline.com/
http://rextester.com/runcode
https://runnable.com/
https://code.hackerearth.com/
http://melpon.org/wandbox
https://paiza.io/

宿題は宿題スレがあるのでそちらへ。

※前スレ
プログラミングのお題スレ Part20
https://mevius.5ch.net/test/read.cgi/tech/1624028577/

**デフォルトの名無しさん** · 2022/11/13(日) 19:38:30.54

https://mobile.twitter.com/mashino8

小中学校教諭はマクドナルドのアルバイトと同じ最低賃金でかつ資格は不要。
プログラミングを他人に教えるなら、まず自作プログラミングを模範として開陳すること。
形式よりもデザインの独自性を追求する。「車輪の再発明」はいらない。
https://twitter.com/5chan_nel (5ch newer account)

**デフォルトの名無しさん** · 2022/11/13(日) 20:02:45.09

乙

**デフォルトの名無しさん** · 2022/11/13(日) 20:28:09.14

>>2
日本語でおｋ

**デフォルトの名無しさん** · 2022/11/14(月) 07:52:53.78

それじゃあこのスレがどれだけ実力があるのかお題だすね
物体認識で手を認識させたときの指先のトラッキングをやってみてください
物体認識のモデルはすでに学習済みと仮定あとはカメラで写ってる指先の特徴点のポイントを取得するだけです

**デフォルトの名無しさん** · 2022/11/14(月) 07:58:49.75

じゃあその学習済みモデルくれよ…

**デフォルトの名無しさん** · 2022/11/14(月) 09:49:45.14

>>6
たしかに…無いとテストとかもできんもんな…

**デフォルトの名無しさん** · 2022/11/14(月) 20:06:53.85

お題：自然数nが奇数かどうかチェックする関数oddを定義せよ

c
https://ideone.com/gdiEYq
//int odd(int n) {return n & 1;}
int odd(int);
int even(int n) {return n == 0 ? 1 : odd(n - 1);}
int odd(int n) {return n == 0 ? 0 : even(n - 1);}

ocaml
https://ideone.com/LYsHsF
let rec even = function 0 -> true | n -> odd (n - 1)
and odd = function 0 -> false | n -> even (n - 1)

**デフォルトの名無しさん** · 2022/11/14(月) 20:10:03.72

>>8
自分で書くのかよ

**デフォルトの名無しさん** · 2022/11/14(月) 20:46:27.81

かなり昔に寿司問題というのがあってそれが難しかった記憶だが
問題を忘れた

**デフォルトの名無しさん** · 2022/11/14(月) 20:49:33.61

検索したら見つかった、これ

回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。
コンベアは毎秒1皿分の速度で流れ、目の前の皿を取るか取らないかを選ぶことができる。
皿取ると同時に食べ始め、食べている間は次の皿を取ることができない。
私が取る以外、皿は追加されたり無くなったりしない。
コンベアの状態が次のような文字列で与えられる。　
"31_2"
数字はその皿を食べ終えるのにかかる秒数を表し、_は皿がないことを表す。1文字目が目の前にあり毎秒、左へ回転する。
例えば、"31_2"で最初の皿を食べたとき食べ終わった時の状態は、"2_1_"となる。

すべての寿司を食べ終えるまで最短何秒かかるか求めよ。
"12_3" > 6秒
"313__" > 8秒
"4_35_1264_23_434" > 60秒
"123456789123456789" > 98秒
"88967472612377988186" > 149秒
"19898693316679441672" > 170秒
"93769682716711132249893" > ?

**デフォルトの名無しさん** · 2022/11/14(月) 22:20:48.72

1から3999までのローマ数字が与えられるのでそれを算用数字で表示する
例
IV -> 4
XLIX -> 49
CDXLIII -> 443

**デフォルトの名無しさん** · 2022/11/15(火) 06:20:24.94

>>11
昔私が高速で求める方法を見つけたヤツだね
おぼえてます

**デフォルトの名無しさん** · 2022/11/15(火) 08:17:52.42

>>11
コレ多項式オーダーとかで行けるんですか？
やはり指数オーダーはかかる？

**デフォルトの名無しさん** · 2022/11/15(火) 12:07:08.40

寿司問題はやり方考えたが確認はしてない
再帰的に解けると想定
寿司2個を食べ終わる時間で寿司1個であるかのようにみなす　(寿司セット)　
たとえば寿司3個の場合なら、最も最短時間の寿司セットを作って寿司2個の場合に帰着させたら解けるはず
最も最短時間の寿司セットというは合ってるか不明だが、そういうやり方で少ない寿司の場合にもっていけるはず

**デフォルトの名無しさん** · 2022/11/15(火) 12:09:32.73

とりあえず寿司3個の場合をランダムか総当りで生成して、2個を連結させる方法が正しいのか確認できそうだがしていない

**デフォルトの名無しさん** · 2022/11/15(火) 12:25:07.74

>>14
たしかリニアオーダーでいける

**デフォルトの名無しさん** · 2022/11/15(火) 13:28:00.47

Part9-413にコードがある

いろんな定義と証明が書いてあるメモが見つかったけど意味わからん

**デフォルトの名無しさん** · 2022/11/15(火) 14:16:46.10

>>15はべつの言い方でいうと与えられたレーンで食べる順を確定させられるペアを見つけるってことだが
総時間が短いものか、空き時間が短いものか、空き時間が短いうちで最も最長のものか、そういういった組み合わせが考えられるが
正解があるかは不明

19 · 2022/11/15(火) 16:22:52.97

単に空の時間が少ないようにペアをあわせていけば解ける気がしてきた
空は0として　"313__"の場合はこうなって解ける
2行目への変化だと1秒と3秒の寿司を食べるとして4秒の寿司へ変わる
次は4秒寿司と3秒寿司が続けて食べられて7秒寿司へ
最後は一秒まって7秒寿司をたべて8秒で終わる

31300
34000
07000

19 · 2022/11/15(火) 16:42:03.18

これもやってみたら手動で正解できた　　"123456789123456789" > 98秒

123456789123456789
303456789303456789
703056789703056789
709050789709050789
0090C07890090C0789
009000J89009000J89
0090000X90090000X9
00I0000XI0000000X0
00I0000YI000000000
00I0000Z0000000000
00W000000000000000

10以上の数値は英字で置き換えた
C 12
J 19
X 27
Y 54
Z 73
W 96

**デフォルトの名無しさん** · 2022/11/15(火) 17:18:07.63

食べる、食べない＝パス、の2択で再帰じゃないの？
食う　カレントが値分後方へ移動、パス連続中フラグdisable
パス　カレントが1つ後方へ移動、パス連続中フラグenable、パス連続可能回数セット
パスが連続出来る回数に制限があるので有限
9からパスし続けて良いのは8回まで。9回パスしたら9を食えてるよねって話
パスした次がより少ない値ならばパス連続可能回数は少ない方で上書き
> "93769682716711132249893"
だと1番目の9はパス連続可能回数8でパスした場合、2番目の3にカレントが移りパス連続可能回数は-1されて7
3のパス連続可能回数は2、7と比較し少ない方の2が上書きされる
パスした場合3番目の7へカレントを移しパス連続可能回数1
7のパス連続可能回数6と比較し少ない1
更にパスした場合、4番目の6
6の5と0を比較しパス連続可能回数0となり、ここではパスは選べない
パス連続中フラグとパス連続可能回数の2つのステータスが要る
フラグは能動的にパスしたのか食うものが無くて次に移動したかの区別

という解釈なんだけど間違ってる？もっと良い方法あるの？

**デフォルトの名無しさん** · 2022/11/15(火) 18:45:27.83

2択で再帰なら必然的に指数オーダーになるんじゃね

19 · 2022/11/15(火) 19:36:17.27

上でいってるやつをコードにした
一個結果がちがってるが　よく検討していない

Python
https://ideone.com/yXUVxt

**デフォルトの名無しさん** · 2022/11/15(火) 19:43:49.49

可能性としては、このアルゴリズム自体が最小値を出す可能性があるだけでかならずしも最小値ではないだとおもう

**デフォルトの名無しさん** · 2022/11/15(火) 19:49:17.64

http://ideone.com/FrRkof

5年前のコード

**デフォルトの名無しさん** · 2022/11/15(火) 19:57:19.27

Pythonって{}がないの見ずらいよな

**デフォルトの名無しさん** · 2022/11/15(火) 21:23:24.85

>>25
可能性だけならただの乱数でもある

**デフォルトの名無しさん** · 2022/11/15(火) 21:35:09.43

>>26
修正しておなじやつ全部解けたけど、最小値を出す保証はないとおもう

https://ideone.com/SGX9y8

**デフォルトの名無しさん** · 2022/11/15(火) 21:45:59.70

大局的なこと、試行錯誤はやらずに空レーンでの待ちが少なくなるように2個セットをつくり続けて寿司個数が少ない場合に帰着させるだけ
これで正解が出させるほうが不思議

**デフォルトの名無しさん** · 2022/11/15(火) 21:59:09.72

2_22
とか合う？

**デフォルトの名無しさん** · 2022/11/15(火) 22:11:55.75

>>31
それ自分だと9秒になるが、>>26だと8秒になるな
しかし、どうやっても8秒だと無理とおもうが
人間の試行錯誤で

**デフォルトの名無しさん** · 2022/11/15(火) 22:47:43.33

>>32
これじゃダメ？
1: *_22（取る）
2: _*22（食べる）
3: __22（休み）
4: __2*（取る）
5: *_2_（食べる）
6: _*2_（休み）
7: __*_（取る）
8: ___*（食べる）

**デフォルトの名無しさん** · 2022/11/15(火) 23:06:20.13

>>33
8を確認できたよ

**デフォルトの名無しさん** · 2022/11/15(火) 23:13:48.23

今上がってる
24
26
29
が線形時間で動くコード？

**デフォルトの名無しさん** · 2022/11/15(火) 23:14:58.48

空なしで連続して食べれるなら食べてしまうやり方で失敗する例が2_22か
これがあるならば待ちで0か1で食べれるのに2以上待たないと駄目な例もありそうだ
ややこしい

**デフォルトの名無しさん** · 2022/11/15(火) 23:57:32.70

これリニアオーダーで動くアルゴリズムがある事実証できてるの？
>>22はリニアになるの？

**デフォルトの名無しさん** · 2022/11/16(水) 00:21:37.28

リニアは完成しません

**デフォルトの名無しさん** · 2022/11/16(水) 03:02:11.82

連続食いアルゴリズムだと
2_22　よりも3_22や3_23の簡単だが
9以下が言えたら8では出来ないかチェックするために
寿司の総和時間が7、8となるように元の寿司を巨大化させ再チェックすればいいか
計算量はちょっと増えるがこれで見逃しはなくなるはず

**デフォルトの名無しさん** · 2022/11/16(水) 05:56:24.40

>>35
>>26は線形時間で最小値を返す

**デフォルトの名無しさん** · 2022/11/16(水) 06:53:13.58

>>40
すいません
数学的な証明おながいします

**デフォルトの名無しさん** · 2022/11/16(水) 12:57:24.30

寿司をわざとデカくして連続食い優先アルゴリズムで、食べ飛ばしに対応させようとしたけど
たとえばこれだと今の寿司の時間の合計は41で、
合計が59になるように寿司増量するやり方は相当あって、その組み合わせを生成するだけでも困難な数だった
この方針は断念すべきか

"4_35_1264_23_434" > 60秒

**デフォルトの名無しさん** · 2022/11/16(水) 13:03:55.89

>>29と同じアルゴリズムと同じPythonだが
重複するコードとforを別の記述してコンパクト化
最小値候補を見つけるにすぎない、最小値を確定させるのは断念するか

https://ideone.com/1Y1x6Y

**デフォルトの名無しさん** · 2022/11/16(水) 16:16:26.72

>>26は解読できないが
これは探索しないと無理な気がしてきたが
リストが与えられたときに確実に連結させされるペアを
探索なしで静的に確定させられるならnのオーダーといえるだろうが無理な気がしてきた

**デフォルトの名無しさん** · 2022/11/16(水) 17:53:26.07

今のところ>>26が最小解をリニアオーダーで与える事の証明上がってこないけど5年前は誰かその証明つけてたん？

**デフォルトの名無しさん** · 2022/11/16(水) 18:08:13.75

寿司問題ってもう5年前か
時間が経つのはあっという間だな

**デフォルトの名無しさん** · 2022/11/16(水) 18:09:58.47

https://ideone.com/qPsn3a

5年前のメモです
証明が非常に簡略化して書いてあります
(書いた本人でも解読に時間がかかる)
またコードにコメントで計算量が書いてあります
参考にしてください

**デフォルトの名無しさん** · 2022/11/16(水) 18:16:29.54

コレはわかんないな
なんかの基準で候補を絞ってその中で1番短いの見つけてるっぽいけど、その絞り込んだ候補の中に必ず最小元がある事の証明はコードだけではわからないよ