X
プログラミングのお題スレ Part11
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
垢版 |
2018/04/24(火) 20:45:14.49ID:ZY7R7Sru
プログラミングのお題スレです。

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

【出題と回答例】
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/

宿題は宿題スレがあるのでそちらへ。
0477デフォルトの名無しさん
垢版 |
2018/05/18(金) 00:27:29.87
お題

スペース区切りで入力された文字列をすべて含むリング状の文字列を出力し、
その後に、各入力文字列に対応するインデックスと長さを出力せよ

出力文字列の構成・格納順に関しては特に制約は設けない
インデックスと長さは出力文字列の先頭からの最短マッチで求める

[制約] (なくしてもいい)
文字列の構成文字は0と1の二種類とする
入力の各文字列長は最大9文字とする
入力要素数は最大255個とする

[入力例1]
0 1 01 10 111 1001
[出力例1]
01110
(0,1) (1,1) (0,2) (3,2) (1,3) (3,4)

[入力例2]
01 1000 1010 100 0 0010 110 0000 00 0111 101 0100 11 10 111 0110 1101 010 000 1 001 0001 011 1001 1011 1100
[出力例2]
010100001101110
(0,2) (3,4) (1,4) (3,3) (0,1) (14,4) (8,3) (4,4) (4,2) (10,4) (1,3) (2,4) (8,2) (1,2) (11,3) (7,4) (8,4) (0,3) (4,3) (1,1) (6,3) (5,4) (7,3) (13,4) (9,4) (12,4)

関連 >>378 >>419
0478デフォルトの名無しさん
垢版 |
2018/05/18(金) 07:59:42.69ID:C1d8hfuw
>>474
じゃあ競争しよう

私はこれからスタートであまり時間もないので
ちょっと時間がかかるかも知れないけど
0479デフォルトの名無しさん
垢版 |
2018/05/18(金) 08:04:09.35ID:C1d8hfuw
>>477
入力文字列を単純につなげば解の1個だが...

求める文字リングが短いほど良い解っていう条件？
0480デフォルトの名無しさん
垢版 |
2018/05/18(金) 08:20:20.07
>>479
そんな感じです
ほどほどに圧縮できてれば必ずしも最短でなくても
0481デフォルトの名無しさん
垢版 |
2018/05/19(土) 01:06:44.60ID:YJKUc9vG
>>478 です
とりあえずこれだけ出来ました
4770でシングルスレッドのC++で15分くらい
半径を倍にすると16倍くらいは時間がかかりそうなので
マルチスレッド&アセンブラ&AVXでガシガシに最適化したくらいじゃ
大して検索範囲は増えなそう
何かアイデアがないか考え中
----
3 : r=1.178511
4 : r=0.707107
5 : r=5.892557
6 : r=2.500000
7 : r=23.890677
8 : r=1.581139
9 : r=15.320647
10 : r=12.500000
11 : r=57.536370
12 : r=3.535534
13 : r=111.621856
14 : r=62.500000
15 : r=76.603235
16 : r=5.700877
18 : r=32.500000
20 : r=17.677670
24 : r=12.747549
28 : r=88.388348
32 : r=23.505319
36 : r=45.961941
40 : r=63.737744
48 : r=52.559490
64 : r=117.526593
0482デフォルトの名無しさん
垢版 |
2018/05/19(土) 01:35:39.77ID:/t1Y5z0r
ピタゴラス素数(4n+1型の素数、5、13など)は2乗和で表わせて。
逆に、2乗和(X^2+Y^2)は、2とピタゴラス素数の積の表わせる、もしくはこの問題を考える上でそれだけに限定していいとおもってる。

2^i * 5^j * 13^k * ・・・・をピタゴラス合成数と名付けると。
X^2　+　Y^2 = ピタゴラス合成数、の解とその個数は比較的カンタンに求まる。

それを利用して、拡大(縮小)と並行させたやつで、最小半径を与えるのは全て表せるはず。

具体的には、上の解が求まっていれば、
(mx + a)^2　+　(my +b)^2 = ピタゴラス合成数、の解と個数もそれなりの低コストでもとまる。
mの剰余を考えれば、解があるaとbの範囲も限定できる。
0483デフォルトの名無しさん
垢版 |
2018/05/19(土) 01:54:04.51ID:YJKUc9vG
ノーヒント、全て自力で求めようと思ってたんだけど
だから競争って

まあいいや
使えそうなら使わせていただきます
0484デフォルトの名無しさん
垢版 |
2018/05/19(土) 03:42:04.50ID:/t1Y5z0r
ピタゴラス素数は2乗和であらわせて。
(a^2 + b^2) (x^2 + y^2) = (ax + by)^2 + (bx - ay)^2 が常に成立するので、

ピタゴラス素数と　2 = 1^2 + 1^2 の積で、新たな2乗和の式が作り出せる。
この式から、解とその個数も求まるはず。

しかし、これがわかっても最小値を求めるのは簡単ではないとおもう。かなりの計算量がいるはず。
0485デフォルトの名無しさん
垢版 |
2018/05/19(土) 03:53:23.91ID:/t1Y5z0r
z = x + yiという複素数でいうと、このノルムは|
0486デフォルトの名無しさん
垢版 |
2018/05/19(土) 03:56:11.86ID:/t1Y5z0r
z = x + yiという複素数でいうと、ノルムは|z|^2 = x^2 + y^2 であって
|z||w| = |zw|を満たすので、
>>484の式は、新たな複素数　zwを作り出すことと一緒。
0487デフォルトの名無しさん
垢版 |
2018/05/19(土) 07:41:40.76ID:b7x1I7X/
お題

ケブンリッジジェネレータ

知らない人のために解説すると、人間の認識力の問題で単語の最初と最後が正しいと途中の文字順序が違っていても正しい単語と見間違えるというのがある。
例えば「よこうそ」は「ようこそ」と見間違える。「およはう」は「おはよう」と見間違える。(これは違うと分かっていても見えてしまうという、空耳アワーの歌みたいでもある)。

以前2chでこのことについてケブンリッジで発見されたというような内容の文章がコピペされて広まり一時期有名になりそれ用の変換をするケブンリッジジェネレータのページ(JavaScriptで作られてたと思う)が作られたりもしていた。
今はもうないようだが今回のお題はこれである。つまり、入力された単語の最初と最後はそのままで途中の文字順序をランダムに入れ替えた結果を出力する。
日本語の文章は普通は単語と単語の間にスペースがないが、これについては処理を簡単にするためにスペースありで入力された文章しか正常に処理しないということにして良い。
0488デフォルトの名無しさん
垢版 |
2018/05/19(土) 08:22:43.57ID:VUe7Kazw
>>487 Ruby
str = <<~EOT
Alice was beginning to get very tired of sitting by her sister on the bank,
and of having nothing to do: once or twice she had peeped into the book
her sister was reading, but it had no pictures or conversations in it,
'and what is the use of a book,' thought Alice 'without pictures or
conversations?'
EOT

puts str.gsub(/(?<=\b\w)\w*(?=\w\b)/){|m| m.chars.shuffle.join}
#=>
Aclie was bngneniig to get very terid of sntitig by her seistr on the bnak,
and of hnvaig nnthoig to do: ocne or twcie she had ppeeed into the book
her sitser was rniadeg, but it had no piteucrs or cinsoentravos in it,
'and waht is the use of a book,' tohught Aclie 'wtihuot pricetus or
coenrovanstis?'
0491デフォルトの名無しさん
垢版 |
2018/05/21(月) 12:42:55.71ID:DBB0b89i
>>487 Squeak/Pharo Smalltalk

| input nonLetters |

input := 'Alice was beginning to get very tired of sitting by her sister on the bank,
and of having nothing to do: once or twice she had peeped into the book
her sister was reading, but it had no pictures or conversations in it,
''and what is the use of a book,'' thought Alice ''without pictures or
conversations?'''.

nonLetters := input reject: #isLetter.
(input findTokens: nonLetters keep: nonLetters) inject: '' into: [:acc :token |
(token first isLetter and: [token size > 1])
ifTrue: [acc, (token first: 1), token allButFirst allButLast shuffled, (token last: 1)]
ifFalse: [acc, token]
]

"=> Ailce was beingnnig to get vrey tierd of sttinig by her seitsr on the bank,
and of hvanig nohintg to do: once or twice she had peeepd into the book
her seitsr was riaendg, but it had no piercuts or coitnevnarsos in it,
'and what is the use of a book,' thuoght Alice 'wtiohut ptriecus or
ctnaseinroovs?' "
0493デフォルトの名無しさん
垢版 |
2018/05/21(月) 20:02:50.47ID:I0TPptnw
>>482
やってみたけど、
馬鹿正直に検索するのと大して変わらんね
半径1000以下を全て検索するのは厳しそう

円周を検索するする昔ながらのアルゴリズムは優秀だ
0494デフォルトの名無しさん
垢版 |
2018/05/21(月) 21:16:17.93ID:FH7zIseK
円周を検索するする昔ながらのアルゴリズムとは?
0495デフォルトの名無しさん
垢版 |
2018/05/21(月) 21:24:09.15ID:dve0ZlFL
>>487 Squeak/Pharo Smalltalk 日本語文章処理例

| input nonLetters |

input := '以前2ch で このこと に ついて ケブンリッジ で はっけん された と いうような ないよう の ぶんしょう が コピペ されて ひろまり
いちじき ゆうめい になり それよう の へんかん を する ケブンリッジ ジェネレータ の ページ(Java Script で つくられ てたと 思う)が つくられ たりも していた。
今 は もうない ようだが こんかい の お題 は これ である。つまり、にゅうりょく された 単語 の さいしょ と 最後 は そのまま で とちゅう の もじじゅんじょ を ランダム に いれかえ た 結果 を しゅつりょく する。
にほんご の ぶんしょう は 普通 は 単語 と 単語 の 間 に スペース が ないが、これ に ついては 処理 を かんたん に するため に スペース あり で にゅうりょく された ぶんしょう しか せいじょう に 処理 しない ということ に してよい。'.

nonLetters := input reject: #isLetter.
(input findTokens: nonLetters keep: nonLetters) inject: '' into: [:acc :token |
(token first isLetter and: [token size > 1])
ifTrue: [acc, (token first: 1), token allButFirst allButLast shuffled, (token last: 1)]
ifFalse: [acc, token]
]

"=> 以前2ch で このこと に ついて ケブリンッジ で はっけん された と いうような なよいう の ぶんょしう が コピペ されて ひろまり
いちじき ゆうめい になり そよれう の へかんん を する ケンブッリジ ジレェーネタ の ページ(Jvaa Spcirt で つくられ てたと 思う)が つくられ たりも しいてた。
今 は もうない ようだが こんかい の お題 は これ である。つまり、にりゅうょく された 単語 の さしいょ と 最後 は そのまま で とちゅう の もゅんじじじょ を ラダンム に いかれえ た 結果 を しょゅつりく する。
にほんご の ぶんしょう は 普通 は 単語 と 単語 の 間 に スペース が ないが、これ に ついては 処理 を かんたん に すたるめ に スーペス あり で にゅうりょく された ぶしんょう しか せょじいう に 処理 しない といこうと に してよい。"
0496デフォルトの名無しさん
垢版 |
2018/05/21(月) 21:36:05.44
>>495
ランダムに入れ替えるのはいいけど、元の単語と同じ並びは排除しないと期待外れの出力になるね
0497デフォルトの名無しさん
垢版 |
2018/05/21(月) 22:08:38.80ID:GTjH0Q6M
完全にランダムなんだから、結果が同じ並びでもそのまま出力するのが筋だろ
変更するなら日本語の文章の方だ
0498デフォルトの名無しさん
垢版 |
2018/05/21(月) 22:24:50.52ID:dve0ZlFL
>>487 Squeak/Pharo Smalltalk 同じ並びは排除

| input nonLetters |

input := '以前2ch で このこと に ついて ケブンリッジ で はっけん された と いうような ないよう の ぶんしょう が コピペ されて ひろまり
いちじき ゆうめい になり それよう の へんかん を する ケブンリッジ ジェネレータ の ページ(Java Script で つくられ てたと 思う)が つくられ たりも していた。
今 は もうない ようだが こんかい の お題 は これ である。つまり、にゅうりょく された 単語 の さいしょ と 最後 は そのまま で とちゅう の もじじゅんじょ を ランダム に いれかえ た 結果 を しゅつりょく する。
にほんご の ぶんしょう は 普通 は 単語 と 単語 の 間 に スペース が ないが、これ に ついては 処理 を かんたん に するため に スペース あり で にゅうりょく された ぶんしょう'.

nonLetters := input reject: #isLetter.
(input findTokens: nonLetters keep: nonLetters)
inject: ''
into: [:acc :token |
| middle |
(token first isLetter and: [token size > 3
and: [(middle := token copyFrom: 2 to: token size - 1) asSet size > 1]])
ifTrue: [
| shuffled |
[(shuffled := middle shuffled) = middle] whileTrue.
acc, (token first: 1), shuffled, (token last: 1)]
ifFalse: [acc, token]]

"=> 以前2ch で ここのと に ついて ケンブッリジ で はけっん された と いううよな なよいう の ぶしょんう が コピペ されて ひまろり
いじちき ゆめうい になり そよれう の へかんん を する ケリンッブジ ジネレェータ の ページ(Jvaa Srcpit で つらくれ てたと 思う)が つらくれ たりも しいてた。
今 は もなうい よだうが こかんい の お題 は これ である。つまり、にりょうゅく された 単語 の さしいょ と 最後 は そまのま で とゅちう の もじじんゅじょ を ラダンム に いかれえ た 結果 を しょつゅりく する。
にんほご の ぶしんょう は 普通 は 単語 と 単語 の 間 に スーペス が ないが、これ に つていは 処理 を かたんん に すたるめ に スーペス あり で にうりょゅく された ぶょんしう"
0499デフォルトの名無しさん
垢版 |
2018/05/21(月) 22:46:17.95ID:ivTUanMr
単語の最初と最後が正しいと途中の文字順序が違っていても正しい単語と見間違える
というのは無いこともないが、やっぱりおかしな単語はおかしく見えるな
0501デフォルトの名無しさん
垢版 |
2018/05/23(水) 19:05:30.98ID:Au5e7VGg
僕の知り合いの知り合いができたパソコン一台でお金持ちになれるやり方
役に立つかもしれません
グーグルで検索するといいかも『ネットで稼ぐ方法　モニアレフヌノ』

AI2XF
0502デフォルトの名無しさん
垢版 |
2018/05/23(水) 22:43:13.42ID:0Sl9hrHV
僕の 知合いりの 知合りいが できた パコソン 一台で お持れちにな金る やり方
役立につ かまれもしせん
グルグーで 検るす索と いかいも 『 ネットぐ方稼で法 モヌレアフニノ 』

AXI2F
0503デフォルトの名無しさん
垢版 |
2018/05/24(木) 09:41:04.28ID:c64g4uzw
荒しだけの２連投か
0504デフォルトの名無しさん
垢版 |
2018/05/25(金) 03:35:14.49ID:thcmSanV
よく読み比べてみるとよい
0505デフォルトの名無しさん
垢版 |
2018/05/27(日) 20:01:12.45ID:zozk6gzj
荒らし業者の連投規制回避の小さな変更

さっさとアク禁になれ
0506デフォルトの名無しさん
垢版 |
2018/05/27(日) 20:37:36.93ID:Yc9D3hww
2個目はどう考えても業者じゃなくてスレ住人だろ…
業者はアク禁になってほしいのは同意
0510デフォルトの名無しさん
垢版 |
2018/05/28(月) 09:38:09.76ID:KmDsu5r7
人間の認識力はそんなもんなんだろうな。ちょっと似てると同じと判断しまう。そうやって脳は省力化してエネルギーあまり使わないようにしてるのかも知れない。脳を動かすには糖分沢山必要だからな。
0511デフォルトの名無しさん
垢版 |
2018/05/28(月) 11:55:04.24
単なる老化
0512デフォルトの名無しさん
垢版 |
2018/05/28(月) 16:45:42.01ID:3CvuwD8l
逆に言えばいちいち全部の文字を正確に認識してたらちょっと誤字脱字や書き損じがあっただけで意味がわからなってしまうぞ
0513デフォルトの名無しさん
垢版 |
2018/05/28(月) 19:20:35.39ID:wGAafxHd
わからなって
0515デフォルトの名無しさん
垢版 |
2018/05/28(月) 21:24:04.06ID:GjCLG5ws
ういね
0525デフォルトの名無しさん
垢版 |
2018/06/04(月) 21:34:02.48ID:i7Qhv+/y
あ、ごめん。テキストファイルじゃなくて標準入力からでもいい。
何処から入力するかはたいした問題ではない。
0528デフォルトの名無しさん
垢版 |
2018/06/04(月) 23:19:04.56ID:hdRuAjud
昔仕事で MUA 作った時に >>526 にある
folding white space をぶち込んでくる送信元がいて苦労した記憶が…
0529デフォルトの名無しさん
垢版 |
2018/06/05(火) 00:27:36.36ID:xCctA/+R
>>526
ここはお題スレだから不毛で良いんだよ。パズルを解くようなもんなんだから。
0531デフォルトの名無しさん
垢版 |
2018/06/18(月) 23:54:29.00ID:2+ok0PtZ
お題: バイオリズム計算

計算結果の出力だけでも良いが、なんだったらアスキーアートやGUIで波形の絵を出したりしても良い。その辺は自由。

バイオリズムとは何かについては Wikipedia 参照。
https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%82%AA%E3%83%AA%E3%82%BA%E3%83%A0

実際に計算して図を出すサイトもある。
https://keisan.casio.jp/exec/system/1231994137
0533デフォルトの名無しさん
垢版 |
2018/06/22(金) 00:11:10.49ID:3MP35Wby
お題：
ある数値nが与えられた時に、次の条件を満たす２つの数値a,bを求め、表示するプログラムを作成しなさい。
●aとbの最小公倍数がnとなる
●a<bかつaとbの差(b-a)が最小となる

例：n= 360→a= 36,b= 40
　　n=1000→a=125,b=200


例が間違ってたらゴメン
0541デフォルトの名無しさん
垢版 |
2018/06/23(土) 00:40:06.00ID:5Wb6fwhK
数学板じゃなくてもさすがに最小公倍数くらいは
このスレならみんな知ってると思ってた
0542 ◆QZaw55cn4c
垢版 |
2018/06/23(土) 01:29:42.07ID:OlLfOCSW
>>541
公倍数は最小公倍数の倍数
公約数は最大公約数の約数

…当たり前のように思えて実際の証明は結構イメージしにくく、一回読んだだけではよくわからないのでした…
0543デフォルトの名無しさん
垢版 |
2018/06/23(土) 01:40:18.34ID:gWvFlQcl
お題：標準入力からhtmlが一行ずつ与えられるのでh1,h2などのhタグを階層化して出力しなさい。タグ内のテキストも一緒に出力し、タグ内にimgが含まれていたらそのaltを出力しなさい。

出力例：
h1 5ちゃんねるにようこそ
....h2 クソスレ乙
........h3 逝ってよし
....h2 ｵﾏｴﾓﾅー
0546デフォルトの名無しさん
垢版 |
2018/06/25(月) 15:39:38.08ID:NIfex5vk
任意の文字列を含む有効なビットコインのアドレスを生成するプログラムを作成せよ。有効な形式のアドレスでなければブロックチェーンエクスプローラで検索しても認識されない。ビットコインアドレスの形式については下記サイトを参照。
https://qiita.com/pokochi/items/4d536a4a24067505abea

例:下記サイトの二番目にあるようなアドレス、
https://bitflyer.com/ja-jp/glossary/address
0547533
垢版 |
2018/06/27(水) 00:31:17.62ID:vFJz85Ce
>>533
C++(使ってるのはほとんどCですが)
https://ideone.com/S4H5Mo

自分の考えてたアルゴリズムをCで記述してみました。
模範解答、とはとても言えない代物です。もっと改良の余地がありますし、バグも取りきれてないかもしれません。

それと>533出題時に考えてたアルゴリズム（手計算でやってましたが）を↓に記述してみました。
こちらは明確に誤った答が出されてしまいます。参考程度に orz
https://ideone.com/HdfYPe
↓
0553デフォルトの名無しさん
垢版 |
2018/06/29(金) 09:46:26.83ID:8O35Zxb2
やれるものならやってみろ。

などと挑発してみるとアホが大漁に釣れるかも知れない。
0555デフォルトの名無しさん
垢版 |
2018/06/29(金) 10:00:35.27ID:8O35Zxb2
問題は釣れるのがアホなのでものすごく頑張った揚げ句たいしたものができない率が非常に高いことにある。
0556デフォルトの名無しさん
垢版 |
2018/06/29(金) 14:17:42.63ID:1XSLHtbi
やっとできた～
0563デフォルトの名無しさん
垢版 |
2018/07/03(火) 10:14:17.19ID:2Hrfam1D
>>561>>562
それなんてエロゲ、じゃない、なんて言語？
0565デフォルトの名無しさん
垢版 |
2018/07/04(水) 21:23:39.48ID:N4SCi1OC
情報オリンピックの問題って組合せ最適化ばかりなのかなぁ？
ttps://www.ioi-jp.org/joi/problem_archive-light.html
0566デフォルトの名無しさん
垢版 |
2018/07/04(水) 21:52:08.71ID:gFgZc5FG
VXU
0569デフォルトの名無しさん
垢版 |
2018/07/08(日) 08:40:53.67ID:PyVF6x+z
鈴木貫太郎
灘中　中学入試　整数問題
https://youtu.be/okKan0C_--E

問1
4つの異なる数字、1, 3, 9, x から、
異なる数字を取り出して並べる、3桁の整数は24個あり、それらの平均値は555 である時、x は何の数字か？

問2
5桁の36の倍数で、2, 3, 5 のどれもが、
いずれかの桁に、1回以上現れる整数のうち、最小のものを求めよ

答え、問1 : 7、問2 : 13,572
0571デフォルトの名無しさん
垢版 |
2018/07/09(月) 14:21:35.87ID:RPo/jFjY
灘中の問題は、以下の性質を使うものが多い

2 の倍数は、下1桁が偶数
4 の倍数は、下2桁が4の倍数

3 の倍数は、各桁の数字を足したものが、3の倍数
9 の倍数は、各桁の数字を足したものが、9の倍数

だから数字を因数分解して、これらに該当するかどうかで、問題を判別できる
0572デフォルトの名無しさん
垢版 |
2018/07/09(月) 16:13:07.36ID:OMEWQnbN
いただきぃ！！
https://goo.gl/uAcy7u
0573569
垢版 |
2018/07/11(水) 18:04:55.63ID:I//Y0R5O
>>569
問1 を、Ruby で作った。
問2 は、難しくて作れない

nums_3 = [1, 3, 9]
nums_4 = nums_3 + [0]

(0..9).each do |num|
next if nums_3.include? num # 含まれていれば

nums_4[-1] = num

sum = 0
nums_4.permutation(3) { |a, b, c| sum += (a*100 + b*10 + c) }

puts num if sum == 24 * 555 #=> 7
end
0574デフォルトの名無しさん
垢版 |
2018/07/11(水) 18:38:10.32ID:XuPZzMyT
じゃあ問2を酷いコードで
>>569 Java
java.util.stream.IntStream.range(10000, 100000).filter(i -> i % 36 == 0).mapToObj(Integer::toString).filter(s -> s.matches("(?=.*2)(?=.*3)(?=.*5).*")).findFirst().ifPresent(System.out::println);
0575デフォルトの名無しさん
垢版 |
2018/07/11(水) 21:04:09.51ID:9T5mO0zj
コンピュータを使ってブルートフォースで答えを探す方法はわかってもコンピュータを使わずに数学的に解く方法が思い浮かばない。
しかしそれを小学生が解いて入学するという現実。orz
■ このスレッドは過去ログ倉庫に格納されています
ニューススポーツなんでも実況