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

■ このスレッドは過去ログ倉庫に格納されています
2018/01/01(月) 11:15:04.40ID:2Vr1CPKy
プログラミングのお題スレです。

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

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

2 名前：デフォルトの名無しさん
　　>>1 使用言語
　　回答本文

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

宿題は宿題スレがあるのでそちらへ。
2018/03/10(土) 20:48:53.52ID:rlKEqJVA
捕捉
使っていいビット演算 and or not xor ビットシフト
負の数の定義　自由
四則演算の定義域と値域　税数→税数
2018/03/10(土) 20:51:20.98ID:rlKEqJVA
タイポ
四則演算の定義域と値域　整数 → 整数
使える数値比較 ==
if for whileとかは自由
2018/03/10(土) 20:58:08.58ID:+HpaswK4
forとかの制御変数の++とかは？
2018/03/10(土) 21:14:24.05ID:rlKEqJVA
>>369
そこら辺はOK
ただ、曖昧で恐縮なんだけど、
for(i = 0; ++i0 i < m * n) ++multi
とかでm*ｎを計算したりするのはNGということで
2018/03/10(土) 21:33:07.85ID:/5GajtRL
適当に考えても除算が思いつかんのだがー
372デフォルトの名無しさん
垢版 |
2018/03/10(土) 22:00:01.41ID:pUOqBlDu
除算以外が実装できていればできるとおもうがな。


逆数と平方根を求める高次収束アルゴリズム
http://www.finetune.co.jp/~lyuka/technote/fract/sqrt.html

逆数法
http://www.nextftp.com/swlabo/m0_pctech/hp_ultraprecision/up_820.htm


除算 (デジタル) - Wikipedia
数値的（ディジタル）な除算アルゴリズムはいくつか存在する。それらのアルゴリズムは、低速な除算と高速な除算の2つに分類できる。
高速な除算技法
ニュートン-ラプソン除算
ゴールドシュミット除算
二項定理
2018/03/10(土) 22:13:39.30ID:/5GajtRL
数値比較が==以外使えないのがつらい
バグがある除算はできたん・・・
2018/03/10(土) 23:07:42.57ID:/5GajtRL
-2147483648が絡んだ除算が(´・ω・`)
2018/03/10(土) 23:28:46.81ID:UlddhHbz
ＣＯＲＤＩＣはどうだろうか
2018/03/10(土) 23:37:45.42ID:/5GajtRL
>>366 Java
https://ideone.com/JpWs5z
やっとでけた
377デフォルトの名無しさん
垢版 |
2018/03/12(月) 09:24:59.54ID:NWFe9xfW
あ、そーか。xorした結果がビット単位の結果になってandした結果がシフトレフトして足す値か。
378デフォルトの名無しさん
垢版 |
2018/03/13(火) 02:05:51.70ID:6d1W0dlg
お題：
ある会社の社員Ａ君は下記のＣ言語のコードで変数aを素因数分解したものを画面に表示したい
しかしＡ君は心身ともに限界な状態であり、あと53回キーを叩くと過労で死んでしまう
どうにかして52文字以内（記号、スペースを含む）で/*こちら*/の部分を入るaの素因数を全て表示するプログラムを考えろ
ただし表示にはprintf関数を使い、一つの素因数ごとに改行すること

#include<stdio.h>

int main(void){
int i=0;
int a=720;/*任意の値*/

/*こちら*/

return 0;
}
2018/03/13(火) 02:35:29.37ID:6d1W0dlg
>>378
出題者ですが状況が変わりました
A君はあと51回キーを叩くと死ぬようになりました
なのでコードの制限は50文字以内に変更してください
一応安価付けときます
2018/03/13(火) 04:24:03.46ID:XvP7o12C
>>378
for(i=2;a>1;printf("%d\n",i),a/=i)for(;a%i;i++);
2018/03/13(火) 04:39:43.81ID:6d1W0dlg
>>380
すごい48文字でできたんだ
恐れ入りました
ちなみにforの条件のa>1はaでも大丈夫だから46文字になるね
2018/03/13(火) 05:18:44.02ID:9P1VPgp7
括弧や%のShiftキー分で死ぬんじゃない？ｗ
2018/03/13(火) 05:36:35.30ID:XvP7o12C
>>382
するどい！死んだわｗ
2018/03/13(火) 06:07:28.04ID:YnPl4ahZ
>>381
＞ちなみにforの条件のa>1はaでも大丈夫だから46文字になるね

終了しないことを許容することによる短縮か…
2018/03/13(火) 06:08:19.20ID:YnPl4ahZ
いや、終了しなくていいなら ;a>1; は ;; で ok か
2018/03/13(火) 06:11:22.12ID:6d1W0dlg
>>384
ごめんそれは今俺も気づいてこれダメじゃんと思ってた
もうだめだ俺ポンコツだ
2018/03/13(火) 09:31:38.72ID:yNzlrAYA
お前のお題つまんない二度とくんな
388デフォルトの名無しさん
垢版 |
2018/03/13(火) 12:46:32.28ID:5qOlO1LI
#include<stdio.h>

int main(void){
int i=0;
int a=720;/*任意の値*/

for(i=2;a>1;printf("%d\n",i),a/=i)for(;犯人はヤス・・・

return 0;
}
2018/03/13(火) 13:13:00.94ID:9lP0H3zv
お題：考えられる数列aを全て求め、出力せよ
ただし、数列aは次の式を満たす(Nは自然数全体)
a⊆N
∀i,j∈N,i<j;a_i<a_j
log(Σa_i)=Σlog(a_i)
∀i;1≦a_i≦10^18
2018/03/13(火) 13:27:27.25ID:4gb3BCLn
>>389
1, 2, 3
くらいですかね、これを計算で出すのはしんどいなあ
391デフォルトの名無しさん
垢版 |
2018/03/13(火) 13:29:32.40ID:dxwUZMkD
log(ab)=log(a)+log(b)だからログ関係なくナイカ?

a1<a2<・・・・<anで、Σai =Πaiを満たすってことだろ。
2018/03/13(火) 14:19:23.53ID:m5NKtYrG
まず{a_n}が上に有界な時点で∀i , j ∈ N i < j; a_i < a_j が成り立たないから問題として破綻している
393デフォルトの名無しさん
垢版 |
2018/03/13(火) 14:19:24.28ID:dxwUZMkD
a+b+c = abcならば、c = (a+b)/(ab-1)だから、これが整数になるようなやつ見つければいいかと。
たとえば(2+3)/(2*3-1) = 1。
394デフォルトの名無しさん
垢版 |
2018/03/13(火) 14:21:35.93ID:dxwUZMkD
それは増加数列を言いたかったんじゃないか。　a1<a2<・・・・<an
∀i , j 　i<j ならばai < ajでは?
395デフォルトの名無しさん
垢版 |
2018/03/13(火) 14:45:44.02ID:dxwUZMkD
4変数のときを考えると。
上と同様に、d = (a+b+c)/(abc-1)となるから。
これは分母のほうがデカイはずで、分子を割り切るならd=1に限るか?
そうすると、abc = 1 + a+b+c　か。
aについて解くと、a = ( 1 + b + c) /( bc - 1 ) か。
これが再び1ではダメで、しかし分母のほうがデカイはずだから割り切るならa=2に限るか?
2bc - 2 = 1 + b + c　か。
bについて解くと、b = (3 + c)/(2c-1)か。c=4ならば、b=1になるが?
2018/03/13(火) 14:56:18.86ID:9lP0H3zv
一応、数列は全部で7個になるはず
8個目はa_61が1152921504069976064>1.15×10^18で上限だから
数列の並び方は>>394でお願い、任意の並び方にしちゃうと組み合わせ爆発が発生するかなって思って付けた制約なので
2018/03/13(火) 14:59:51.72ID:23dHbGxb
ん？

n
ΠAi = ΣAi < n An
i=1

An で割って

n-1
Π Ai < n
i=1

で左辺は (n-1)! 以上だから n はたかだか 3 じゃない？
2018/03/13(火) 15:02:02.69ID:9lP0H3zv
……あ、やっべ
これお題として成立していないことに気付いた
2018/03/13(火) 15:04:01.62ID:9lP0H3zv
ごめんなさい、このお題は無しで
完全数の導出問題のつもりだったけど、aの要素を1個にするだけで10^18通りの解がある
twitterで流れてきた話を投げるべきではないな……反省して暫くお題出さないです
2018/03/13(火) 15:07:29.90ID:m5NKtYrG
>>394
それなら解はaの位数が１か、a = {1, 2, 3} のみだね
ってプログラミングで解く問題でもないと思うんだけど
2018/03/13(火) 18:03:31.33ID:9lP0H3zv
1,2,4,7,14
1,2,4,8,16,31,62,124,248
など
2018/03/13(火) 18:25:02.81ID:g+hlSIUf
お父さんそれは違う問題の答えでしょ
403デフォルトの名無しさん
垢版 |
2018/03/13(火) 18:39:09.17ID:LC30GjQR
何の話をしているのかサッパリわからんのだが、どうやら終わったようなのでまあいいか。
2018/03/14(水) 00:28:33.06ID:ZLNkomk9
出題者が出題内容を理解してなさそうだからサッパリわからない人がいても当然
2018/03/17(土) 13:11:23.04ID:B5dRO7D1
お題
任意の実数の総有効桁数を2にせよ
丸め方法は問わない
R
https://ideone.com/cpLlLw
2018/03/17(土) 15:16:51.53ID:weRxBwBT
>>405 Ruby

[12345,
12.34,
1.234,
0.0123].each{|i|puts"%.1e"%i}
#=>
1.2e+04
1.2e+01
1.2e+00
1.2e-02
407デフォルトの名無しさん
垢版 |
2018/03/17(土) 19:33:28.44ID:/yJWANaR
>>405
>>406とほぼ同じ。perlでコマンドラインからそのまま実行。

$ perl -e 'for(12345,12.34,1.234,.0123){printf("%.1e\n",$_)}'
1.2e+04
1.2e+01
1.2e+00
1.2e-02
$

printf()の%e使わないで自分で何とかするやつ作った方が良いかな?
2018/03/17(土) 21:20:46.09ID:weRxBwBT
>>405 Ruby sprintfフォーマット使わない場合

[12345,
12.34,
1.234,
0.0123].each{|i|p i.floor(1-Math.log10(i).floor)}
#=>
12000
12
1.2
0.012
2018/03/18(日) 03:14:20.76ID:95A2sExk
解答としては>>408を推す
他は文字列化しただけで実数を変換できてない
2018/03/18(日) 04:27:15.50ID:NOJvpmK1
>>405
Kotlin
https://paiza.io/projects/5jjVrOJVlXeQrkvnsmBNNg
2018/03/18(日) 11:47:23.87ID:i8EJZcPC
任意のx > 0 に対して x を有効桁数n(n ∈ N)で表わした数 c は
r = 10^([log10(x)] - n + 1)
とおくと
c = [x / r] * r
なんだけど、これを丸め誤差を考慮して簡単に解析的に修正するのはちょっと骨が折れるね
2018/03/18(日) 12:55:07.22ID:95A2sExk
それ既に>>408でほぼ既出
413デフォルトの名無しさん
垢版 |
2018/03/22(木) 18:13:48.94ID:DIDy9yz3
まずは大学入試以前に、中学高校の入試問題や公務員試験などを人工知能で解かせたい。
そして現在の人工知能に何が出来て何が出来ないのかを知りたい。

新井紀子教授のAIやコンピュータに関する知識は素人に毛が生えた程度
新井紀子教授の『AI vs. 教科書が読めない子どもたち』という本が大変売れているようです。
私も本を購入し精読させていただきました。
一言で感想を言うと、新井紀子教授のAI技術に関する知識はせいぜいAI関連ニュースに詳しい人レベルであり、
そのベースであるコンピュータに関する知識もほぼ素人だということがわかりました。
https://mywarstory.tokyo/inconvenient-truth/

↑
人工知能の先生方がこんなんでは、どこで誰に学んだらいいのかわからない！
414デフォルトの名無しさん
垢版 |
2018/03/22(木) 18:58:31.89ID:tiDItZ1f
批判に対して女性差別だと返してるところが何だかなあって感じ。
男だったらそもそも人目に触れるポジションにさえ来れていないだろうから、確かに批判はされないんだろうけど。
2018/03/22(木) 19:36:56.32ID:cv696+3f
日本はアセンブラの国。
416デフォルトの名無しさん
垢版 |
2018/03/22(木) 20:23:41.20ID:PncCzcJH
【史上初】　　　テレパシーで演説　　　≪≪マイトＬーヤ≫≫　　　月面ウサギを公表　　　【ＵＦＯ】
http://rosie.5ch.net/test/read.cgi/liveplus/1521681235/l50
2018/03/23(金) 17:24:50.97ID:IDjk8I5l
日本の国、まさにPC-98を中心としているアセンブラの国であるぞということを国民の皆さんにしっかりと承知をして戴く
418デフォルトの名無しさん
垢版 |
2018/03/24(土) 18:48:50.24
いいからさっさとお題出せよ
2018/03/25(日) 10:48:10.09ID:ICJzh6RG
日本語の単語がひらがなで与えられる。
これらを用いてしりとりをしたときに最も長く続くケースで使われる単語の数を出力せよ。
ただし；
・一行目は与えられる単語の数(1以上100000以下)
・「ん」から始まる単語はない
・「ゐゑぁぃぅぇぉゃゅょゎー」を含む単語はない

*sample input*
10
あなご
いくら
うなぎ
えい
おくら
かしゆうなつつ
ごはん
ばたあ
ゆば
らあゆ

*sample output*
7
(えい いくら らあゆ ゆば ばたあ あなご ごはん)
420デフォルトの名無しさん
垢版 |
2018/03/25(日) 12:27:22.28
よく分かんないんだけど巡回セールスマン問題？
421デフォルトの名無しさん
垢版 |
2018/03/25(日) 12:34:50.41
ウィキってみたら同じNP困難問題ではあるけどナップサック問題に近いのかな？
422デフォルトの名無しさん
垢版 |
2018/03/25(日) 12:58:44.89
動的計画法？？？
なんかめんどいからオナニーでもしよっと
423デフォルトの名無しさん
垢版 |
2018/03/25(日) 13:04:27.26ID:r2Id4T4+
俺もしりとりのお題出そうと思って色々考えた挙句止めたんだよな。何で止めたんだっけかなあ？
まあいいか。
2018/03/25(日) 14:59:33.86ID:nZ0DOyRs
あなご　ごりら　らあゆ　ゆば　ばばあ　あなご
とか永久に続いちゃう場合は？
2018/03/25(日) 15:13:47.39ID:PARYDGAE
一度使った単語は、使わないようにすれば？
2018/03/25(日) 15:13:49.64ID:ICJzh6RG
>>424
同じ単語は高々1回しか使えないということで
427デフォルトの名無しさん
垢版 |
2018/03/25(日) 15:24:25.42
>>424
しりとりのルールも知らないのか
2018/03/25(日) 15:59:34.89ID:Wi9Zk4mn
input
6
けんばんはーもにか
かみのけ
もうないでしよ
あるよ
けっこんしよう
うん

output
？
2018/03/25(日) 18:50:35.30ID:ZFL51Okg
>>428
けんばんはーもにか　→　かみのけ　→　けっこんしよう　→　うん
以外に考えられるの？
430デフォルトの名無しさん
垢版 |
2018/03/25(日) 20:17:28.76
>>429
///
2018/03/25(日) 20:41:22.44ID:Qy9e8iWO
>>429
「足し算のプログラムを書け、入力は3と4」
という問いに「7しかないでしょ」と答えてるようなもんだぞそれ
2018/03/25(日) 20:51:42.25ID:1ylF9qbh
アウトプットは赤ちゃんでした
2018/03/25(日) 21:23:06.15ID:ZFL51Okg
>>431
いや>>428は問題の不備を指摘してるように見えたんだけど違うの
違うならなんなの？
2018/03/25(日) 21:33:15.53ID:lfdSZ5QO
すまんすまんよく読んでなかった

どんな不備？
outputは4で良さそうに思えるが
2018/03/25(日) 21:55:06.19ID:Y0AA7BVa
>>428
・「ゐゑぁぃぅぇぉゃゅょゎー」を含む単語はない
>けんばんはーもにか
'ー'

'を' とか 'う゛'(Unicodeでは1文字) は含むんだろうか？
濁音・半濁音の扱いもローカルルールがあるようだけど？
2018/03/25(日) 22:52:38.78ID:r2Id4T4+
>>419
Kotlin
https://paiza.io/projects/3JlXbCwKoxeWq4adKPrlaw
2018/03/25(日) 22:56:05.59ID:r2Id4T4+
>>428

>>436のプログラムでこうなった。

入力
単語数: 6
けんばんはーもにか
かみのけ
もうないでしよ
あるよ
けっこんしよう
うん

出力
単語数: 4
けんばんはーもにか
かみのけ
けっこんしよう
うん
2018/03/25(日) 22:58:48.24ID:Qy9e8iWO
なるほど
お題としては数字とかアルファベットのが見通しがいいな
2018/03/26(月) 20:54:56.37ID:bouVP8Z1
プログラマ名乗っていい？
2018/03/26(月) 20:56:27.32ID:dvRuSlEv
>>439
どうぞ：−）
2018/03/26(月) 21:54:41.90ID:bouVP8Z1
>>419
https://ideone.com/TCBMbc
C++。サンプルは解けたが相変わらず日本語表示には厳しいな。
こんな感じでいい？
2018/03/26(月) 22:45:31.40ID:bouVP8Z1
そういえば、必ず”ん”で終わらなければならないっていう制約はないよね。
言葉が尽きても負けなんだし。
2018/03/27(火) 01:45:16.06ID:Kzq8gSOx
すげぇ
しりとりは普通に組むとオーダーが大きくなるからなぁ
お題の単語数10^5に対応するプログラム書ける気がしない
辺は少ないし、これ最大流で解けるんだっけ？
2018/03/27(火) 02:13:31.11ID:6oSpwfuc
あんまり、オーダー爆発起こすとちょっと大変だな。
次に続く単語数の数が多いほど爆発する。
最大N!だけど、そういうケースは少ないよ。
2018/03/27(火) 03:46:37.52ID:6oSpwfuc
最適化閃いたけど、無理筋やった。
3変数ごにょごにょするだけで枝切できるかと思ったんだけど。
446デフォルトの名無しさん
垢版 |
2018/03/27(火) 05:36:02.02
再帰使わない解を見たいな
2018/03/27(火) 07:06:00.62ID:wPClF3oP
>>419
https://ideone.com/LYz9cE
ひらがなは 7bit程度で表せるので、頭と尻だけ数値化、頭でテーブルを分けた。
2018/03/27(火) 07:10:55.86ID:6oSpwfuc
>>446
スタックを展開するだけだからなぁ。
めんどくさいけど、理論は楽。
2018/03/27(火) 12:16:29.94ID:wPClF3oP
https://ideone.com/29wlkp
全探査しなくてもいいので、同じ階層に'あかい','あおい','あさい'など頭と尻が同じ語は枝刈り出来る。
2018/03/27(火) 15:10:13.58ID:04A2frTi
>>444
＞最大N!だけど、そういうケースは少ないよ。

可能な末尾の文字の種類をRとすると次の語を選ぶ選び方は(先頭は与えられているので)末尾違いの高々R
(中間が異なるものからはどれを選んでもいいので先頭のを選べばいい)

先頭の文字別にリストにでも格納しておけば N 単語での計算量は高々 O(N ^ R)
451デフォルトの名無しさん
垢版 |
2018/03/30(金) 08:34:52.77ID:Vv6lbhFT
お題
桁の並びが大きい順になっている数をすべてもとめる
2018/03/30(金) 08:35:45.83ID:QER2k9uu
意味不明。
453デフォルトの名無しさん
垢版 |
2018/03/30(金) 08:51:48.50ID:h7HIobcW
9876543210の各桁を表示する・しない、で2^10-1(=1023)通りってことかの？
2018/03/30(金) 08:58:40.80ID:HHYSbDrZ
>>451 Ruby

(1..10).each{|i| puts [*0..9].reverse.combination(i).map(&:join)}
2018/03/30(金) 09:14:47.35ID:QER2k9uu
あーそういうことか
456デフォルトの名無しさん
垢版 |
2018/03/30(金) 09:39:19.40ID:TlFsJGTt
rubyがわからないのでわからん
どういうこと？
今スマホでアクセスしてるから試すのもできない
2018/03/30(金) 09:42:37.75ID:h7HIobcW
すまほでもコピペしてideoneで試せるんじゃね？
https://ideone.com/ihH1LH
458デフォルトの名無しさん
垢版 |
2018/03/30(金) 09:51:09.95ID:TlFsJGTt
>>457
おお。動いた。
あー。そういう意味か。
2018/03/30(金) 20:28:56.47ID:whZFBFFl
お題： n!の末尾の0の個数を数える
たとえば、n = 9のとき9! = 362880なので末尾の0の個数は1
n = 10 のとき 10! = 3628800なので末尾の0の個数は2
制限事項：　gmpなどのライブラリは使用不可。以下の5問を合計1.8秒以内で。

n = 132 , # = ?
n = 743 , # = ?
n = 54321 , # = ?
n = 2147483647 , # = ?
n = 4294967296 , # = ?
2018/03/30(金) 20:39:11.33ID:HHYSbDrZ
>>459 Ruby 0.015秒くらい

[132, 743, 54321, 2147483647, 4294967296].each{|n| puts "n = %d => #%d" % [n, (1..log(n, 5)).map{|i| n / 5**i}.sum]}

# output
n = 132 => #32
n = 743 => #183
n = 54321 => #13576
n = 2147483647 => #536870902
n = 4294967296 => #1073741816
2018/03/30(金) 21:43:34.36ID:sxHgkaP9
>>459
https://ideone.com/sSfH5w

＞以下の5問を合計1.8秒以内で。
は未達成、これは難しい‥‥
462デフォルトの名無しさん
垢版 |
2018/03/30(金) 21:47:51.34ID:9xE1BuhJ
面白いね

何かお題が出て(>>451)それに対して意味不明の即答’>>452)、
まぁそれはそれでごもっともと思ったらrubyのコード(>>454)が出て、
その後はあーだこーだとレスが続いてく

前スレから見始めた初心者だけど、
未知の課題に対するコーディング能力ってやっぱり大事だ
2018/03/30(金) 21:49:03.26ID:sxHgkaP9
>>460
なるほどねえ
2018/03/31(土) 04:32:05.81ID:8va89mAu
>>451
https://ideone.com/SLwoYB
https://ideone451.com/AGDBWO
C++。普通に解いたら20秒くらいかかるからさらに脳筋な方法で解こうと思ったらメモリ足りなかった。
とはいえ階乗では解きたくないし。まぁいいか。
2018/03/31(土) 05:34:00.26ID:8va89mAu
省メモリで解こうと思ったらGCCに匙投げられた。
コンパイルタイムはこれからやな。
https://ideone.com/CScvWR
2018/03/31(土) 05:44:58.45ID:1thwAW7O
ruby のを J に移植してみた

入力
(2,#d)$d,>(3 : '+/<.y%5^1+i.<.5^.y') each d=.132 743 54321 2147483647 4294967296

結果
+--+---+-----+---------+----------+
|32|183|13576|536870902|1073741816|
+--+---+-----+---------+----------+

5を数える他の有力なやり方ってどんなだろう
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況