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

**デフォルトの名無しさん** · 2018/01/01(月) 11:15:04.40

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

前スレ
プログラミングのお題スレ 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/02/20(火) 13:38:26.62

>>346
その場合、正解は全組み合わせを網羅するしかないからなぁ

**デフォルトの名無しさん** · 2018/02/20(火) 17:43:40.13

すべての数独の問題の解答を書けというようなもんだからなｗ

◆QZaw55cn4c · 2018/02/25(日) 00:11:19.18

https://mevius.5ch.net/test/read.cgi/tech/1480579110/375
いったん発信して落ち着こうと考えました
https://ideone.com/Yfr6sz

**デフォルトの名無しさん** · 2018/02/25(日) 14:25:40.59

発信×
発射

**デフォルトの名無しさん** · 2018/02/26(月) 02:41:37.52

簡単なお題

ローマ字入力された文字列を日本語の平仮名の文字列に変換する。
記号はそのままでも良い。
変換不能な文字列を発見したらその部分はエラーとしてわかるように出力する。
同じ音の表現が複数ある場合は一つの表現の平仮名にして良い(SHA と SYA を「しゃ」にする等)。

**デフォルトの名無しさん** · 2018/02/26(月) 10:05:01.91

名詞とかにある母国語綴りとか混雑してると途端に難問になる悪寒。

**デフォルトの名無しさん** · 2018/02/26(月) 10:05:52.33

混在だったわ予測変換のバカぁ

**デフォルトの名無しさん** · 2018/02/26(月) 23:56:09.72

ローマ字変換のルールに幅がありすぎてなぁ……
"tttttte"は"っっっっって"なのかエラーとするのか
"xn"は"ん"なのかエラーとするのか
"patchi"は"パッチ"なのかエラーとするのか
"qi"は"くぃ"なのかエラーなのかとか

**351** · 2018/02/27(火) 02:49:02.65

細かいルールは自分で決めちゃっても良いよ。こういう時はこうなるとコメント等に書いておいてくれれば。

**351** · 2018/03/01(木) 03:35:55.28

自分でお題出しといて解かないのもあれなので一応作った。
結構面倒だな。w

Kotlin
https://paiza.io/projects/0yfrz9O4yGVgr3CPHAmVFw

しかしあまりKotlinらしい書き方ではないような気がする。

**デフォルトの名無しさん** · 2018/03/01(木) 11:25:25.90

こんなんこそ人工知能に学習させればいいのに。

**デフォルトの名無しさん** · 2018/03/01(木) 11:28:37.24

じゃあやってみれば？

**デフォルトの名無しさん** · 2018/03/01(木) 12:00:36.81

人工知能の成果の移植ってどうやるの？

**デフォルトの名無しさん** · 2018/03/01(木) 22:25:45.16

>>359
人工知能同士でお話させる。

**デフォルトの名無しさん** · 2018/03/01(木) 22:41:52.43

性格が同じだと止揚が得られない

**デフォルトの名無しさん** · 2018/03/02(金) 14:30:55.92

気づいたらAI同士で独自言語で話してて慌てて停止ですね。

◆QZaw55cn4c · 2018/03/03(土) 23:57:25.78

>>349
https://mevius.5ch.net/test/read.cgi/tech/1480579110/375
https://mevius.5ch.net/test/read.cgi/tech/1434079972/37

**デフォルトの名無しさん** · 2018/03/04(日) 23:25:09.87

>>362
ガングロギャルはAIだったのかー！

**デフォルトの名無しさん** · 2018/03/06(火) 02:20:28.01

>>362
朝鮮製AIだな

**デフォルトの名無しさん** · 2018/03/10(土) 20:25:13.50

ビット演算のみを用いて四則演算を実装せよ

**デフォルトの名無しさん** · 2018/03/10(土) 20:48:53.52

捕捉
使っていいビット演算 and or not xor ビットシフト
負の数の定義　自由
四則演算の定義域と値域　税数→税数

**デフォルトの名無しさん** · 2018/03/10(土) 20:51:20.98

タイポ
四則演算の定義域と値域　整数 → 整数
使える数値比較 ==
if for whileとかは自由

**デフォルトの名無しさん** · 2018/03/10(土) 20:58:08.58

forとかの制御変数の++とかは？

**デフォルトの名無しさん** · 2018/03/10(土) 21:14:24.05

>>369
そこら辺はOK
ただ、曖昧で恐縮なんだけど、
for(i = 0; ++i0 i < m * n) ++multi
とかでm*ｎを計算したりするのはNGということで

**デフォルトの名無しさん** · 2018/03/10(土) 21:33:07.85

適当に考えても除算が思いつかんのだがー

**デフォルトの名無しさん** · 2018/03/10(土) 22:00:01.41

除算以外が実装できていればできるとおもうがな。

逆数と平方根を求める高次収束アルゴリズム
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.30

数値比較が==以外使えないのがつらい
バグがある除算はできたん・・・

**デフォルトの名無しさん** · 2018/03/10(土) 23:07:42.57

-2147483648が絡んだ除算が(´・ω・`)

**デフォルトの名無しさん** · 2018/03/10(土) 23:28:46.81

ＣＯＲＤＩＣはどうだろうか

**デフォルトの名無しさん** · 2018/03/10(土) 23:37:45.42

>>366 Java
https://ideone.com/JpWs5z
やっとでけた

**デフォルトの名無しさん** · 2018/03/12(月) 09:24:59.54

あ、そーか。xorした結果がビット単位の結果になってandした結果がシフトレフトして足す値か。

**デフォルトの名無しさん** · 2018/03/13(火) 02:05:51.70

お題：
ある会社の社員Ａ君は下記のＣ言語のコードで変数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.37

>>378
出題者ですが状況が変わりました
A君はあと51回キーを叩くと死ぬようになりました
なのでコードの制限は50文字以内に変更してください
一応安価付けときます

**デフォルトの名無しさん** · 2018/03/13(火) 04:24:03.46

>>378
for(i=2;a>1;printf("%d\n",i),a/=i)for(;a%i;i++);

**デフォルトの名無しさん** · 2018/03/13(火) 04:39:43.81

>>380
すごい48文字でできたんだ
恐れ入りました
ちなみにforの条件のa>1はaでも大丈夫だから46文字になるね

**デフォルトの名無しさん** · 2018/03/13(火) 05:18:44.02

括弧や%のShiftキー分で死ぬんじゃない？ｗ

**デフォルトの名無しさん** · 2018/03/13(火) 05:36:35.30

>>382
するどい！死んだわｗ

**デフォルトの名無しさん** · 2018/03/13(火) 06:07:28.04

>>381
＞ちなみにforの条件のa>1はaでも大丈夫だから46文字になるね

終了しないことを許容することによる短縮か…

**デフォルトの名無しさん** · 2018/03/13(火) 06:08:19.20

いや、終了しなくていいなら ;a>1; は ;; で ok か

**デフォルトの名無しさん** · 2018/03/13(火) 06:11:22.12

>>384
ごめんそれは今俺も気づいてこれダメじゃんと思ってた
もうだめだ俺ポンコツだ

**デフォルトの名無しさん** · 2018/03/13(火) 09:31:38.72

お前のお題つまんない二度とくんな

**デフォルトの名無しさん** · 2018/03/13(火) 12:46:32.28

#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.94

お題：考えられる数列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

◆QZaw55cn4c · 2018/03/13(火) 13:27:27.25

>>389
1, 2, 3
くらいですかね、これを計算で出すのはしんどいなあ

**デフォルトの名無しさん** · 2018/03/13(火) 13:29:32.40

log(ab)=log(a)+log(b)だからログ関係なくナイカ?

a1<a2<・・・・<anで、Σai =Πaiを満たすってことだろ。

**デフォルトの名無しさん** · 2018/03/13(火) 14:19:23.53

まず{a_n}が上に有界な時点で∀i , j ∈ N i < j; a_i < a_j が成り立たないから問題として破綻している

**デフォルトの名無しさん** · 2018/03/13(火) 14:19:24.28

a+b+c = abcならば、c = (a+b)/(ab-1)だから、これが整数になるようなやつ見つければいいかと。
たとえば(2+3)/(2*3-1) = 1。

**デフォルトの名無しさん** · 2018/03/13(火) 14:21:35.93

それは増加数列を言いたかったんじゃないか。　a1<a2<・・・・<an
∀i , j 　i<j ならばai < ajでは?

**デフォルトの名無しさん** · 2018/03/13(火) 14:45:44.02

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.86

一応、数列は全部で7個になるはず
8個目はa_61が1152921504069976064>1.15×10^18で上限だから
数列の並び方は>>394でお願い、任意の並び方にしちゃうと組み合わせ爆発が発生するかなって思って付けた制約なので

**デフォルトの名無しさん** · 2018/03/13(火) 14:59:51.72

ん？

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

An で割って

n-1
Π Ai < n
i=1

で左辺は (n-1)! 以上だから n はたかだか 3 じゃない？

**デフォルトの名無しさん** · 2018/03/13(火) 15:02:02.69

……あ、やっべ
これお題として成立していないことに気付いた

**デフォルトの名無しさん** · 2018/03/13(火) 15:04:01.62

ごめんなさい、このお題は無しで
完全数の導出問題のつもりだったけど、aの要素を1個にするだけで10^18通りの解がある
twitterで流れてきた話を投げるべきではないな……反省して暫くお題出さないです

**デフォルトの名無しさん** · 2018/03/13(火) 15:07:29.90

>>394
それなら解はaの位数が１か、a = {1, 2, 3} のみだね
ってプログラミングで解く問題でもないと思うんだけど

**デフォルトの名無しさん** · 2018/03/13(火) 18:03:31.33

1,2,4,7,14
1,2,4,8,16,31,62,124,248
など

**デフォルトの名無しさん** · 2018/03/13(火) 18:25:02.81

お父さんそれは違う問題の答えでしょ

**デフォルトの名無しさん** · 2018/03/13(火) 18:39:09.17

何の話をしているのかサッパリわからんのだが、どうやら終わったようなのでまあいいか。

**デフォルトの名無しさん** · 2018/03/14(水) 00:28:33.06

出題者が出題内容を理解してなさそうだからサッパリわからない人がいても当然

**デフォルトの名無しさん** · 2018/03/17(土) 13:11:23.04

お題
任意の実数の総有効桁数を2にせよ
丸め方法は問わない
R
https://ideone.com/cpLlLw

**デフォルトの名無しさん** · 2018/03/17(土) 15:16:51.53

>>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

**デフォルトの名無しさん** · 2018/03/17(土) 19:33:28.44

>>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.09

>>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.76

解答としては>>408を推す
他は文字列化しただけで実数を変換できてない

**デフォルトの名無しさん** · 2018/03/18(日) 04:27:15.50

>>405
Kotlin
https://paiza.io/projects/5jjVrOJVlXeQrkvnsmBNNg

**デフォルトの名無しさん** · 2018/03/18(日) 11:47:23.87

任意のx > 0 に対して x を有効桁数n(n ∈ N)で表わした数 c は
r = 10^([log10(x)] - n + 1)
とおくと
c = [x / r] * r
なんだけど、これを丸め誤差を考慮して簡単に解析的に修正するのはちょっと骨が折れるね

**デフォルトの名無しさん** · 2018/03/18(日) 12:55:07.22

それ既に>>408でほぼ既出

**デフォルトの名無しさん** · 2018/03/22(木) 18:13:48.94

まずは大学入試以前に、中学高校の入試問題や公務員試験などを人工知能で解かせたい。
そして現在の人工知能に何が出来て何が出来ないのかを知りたい。

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

↑
人工知能の先生方がこんなんでは、どこで誰に学んだらいいのかわからない！

**デフォルトの名無しさん** · 2018/03/22(木) 18:58:31.89

批判に対して女性差別だと返してるところが何だかなあって感じ。
男だったらそもそも人目に触れるポジションにさえ来れていないだろうから、確かに批判はされないんだろうけど。

**デフォルトの名無しさん** · 2018/03/22(木) 19:36:56.32

日本はアセンブラの国。

**デフォルトの名無しさん** · 2018/03/22(木) 20:23:41.20

【史上初】　　　テレパシーで演説　　　≪≪マイトＬーヤ≫≫　　　月面ウサギを公表　　　【ＵＦＯ】
http://rosie.5ch.net/test/read.cgi/liveplus/1521681235/l50

**デフォルトの名無しさん** · 2018/03/23(金) 17:24:50.97

日本の国、まさにPC-98を中心としているアセンブラの国であるぞということを国民の皆さんにしっかりと承知をして戴く

**デフォルトの名無しさん** · 2018/03/24(土) 18:48:50.24

いいからさっさとお題出せよ

**デフォルトの名無しさん** · 2018/03/25(日) 10:48:10.09

日本語の単語がひらがなで与えられる。
これらを用いてしりとりをしたときに最も長く続くケースで使われる単語の数を出力せよ。
ただし；
・一行目は与えられる単語の数(1以上100000以下)
・「ん」から始まる単語はない
・「ゐゑぁぃぅぇぉゃゅょゎー」を含む単語はない

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

*sample output*
7
(えいいくららあゆゆばばたああなごごはん)

**デフォルトの名無しさん** · 2018/03/25(日) 12:27:22.28

よく分かんないんだけど巡回セールスマン問題？

**デフォルトの名無しさん** · 2018/03/25(日) 12:34:50.41

ウィキってみたら同じNP困難問題ではあるけどナップサック問題に近いのかな？

**デフォルトの名無しさん** · 2018/03/25(日) 12:58:44.89

動的計画法？？？
なんかめんどいからオナニーでもしよっと

**デフォルトの名無しさん** · 2018/03/25(日) 13:04:27.26

俺もしりとりのお題出そうと思って色々考えた挙句止めたんだよな。何で止めたんだっけかなあ？
まあいいか。

**デフォルトの名無しさん** · 2018/03/25(日) 14:59:33.86

あなご　ごりら　らあゆ　ゆば　ばばあ　あなご
とか永久に続いちゃう場合は？

**デフォルトの名無しさん** · 2018/03/25(日) 15:13:47.39

一度使った単語は、使わないようにすれば？

**デフォルトの名無しさん** · 2018/03/25(日) 15:13:49.64

>>424
同じ単語は高々1回しか使えないということで

**デフォルトの名無しさん** · 2018/03/25(日) 15:24:25.42

>>424
しりとりのルールも知らないのか

**デフォルトの名無しさん** · 2018/03/25(日) 15:59:34.89

input
6
けんばんはーもにか
かみのけ
もうないでしよ
あるよ
けっこんしよう
うん

output
？

**デフォルトの名無しさん** · 2018/03/25(日) 18:50:35.30

>>428
けんばんはーもにか　→　かみのけ　→　けっこんしよう　→　うん
以外に考えられるの？

**デフォルトの名無しさん** · 2018/03/25(日) 20:17:28.76

>>429
///

**デフォルトの名無しさん** · 2018/03/25(日) 20:41:22.44

>>429
「足し算のプログラムを書け、入力は3と4」
という問いに「7しかないでしょ」と答えてるようなもんだぞそれ

**デフォルトの名無しさん** · 2018/03/25(日) 20:51:42.25

アウトプットは赤ちゃんでした

**デフォルトの名無しさん** · 2018/03/25(日) 21:23:06.15

>>431
いや>>428は問題の不備を指摘してるように見えたんだけど違うの
違うならなんなの？

**デフォルトの名無しさん** · 2018/03/25(日) 21:33:15.53

すまんすまんよく読んでなかった

どんな不備？
outputは4で良さそうに思えるが

**デフォルトの名無しさん** · 2018/03/25(日) 21:55:06.19

>>428
・「ゐゑぁぃぅぇぉゃゅょゎー」を含む単語はない
>けんばんはーもにか
'ー'

'を' とか 'う゛'(Unicodeでは1文字) は含むんだろうか？
濁音・半濁音の扱いもローカルルールがあるようだけど？

**デフォルトの名無しさん** · 2018/03/25(日) 22:52:38.78

>>419
Kotlin
https://paiza.io/projects/3JlXbCwKoxeWq4adKPrlaw

**デフォルトの名無しさん** · 2018/03/25(日) 22:56:05.59

>>428

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

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

出力
単語数: 4
けんばんはーもにか
かみのけ
けっこんしよう
うん

**デフォルトの名無しさん** · 2018/03/25(日) 22:58:48.24

なるほど
お題としては数字とかアルファベットのが見通しがいいな

**デフォルトの名無しさん** · 2018/03/26(月) 20:54:56.37

プログラマ名乗っていい？

◆QZaw55cn4c · 2018/03/26(月) 20:56:27.32

>>439
どうぞ：－）

**デフォルトの名無しさん** · 2018/03/26(月) 21:54:41.90

>>419
https://ideone.com/TCBMbc
C++。サンプルは解けたが相変わらず日本語表示には厳しいな。
こんな感じでいい？

**デフォルトの名無しさん** · 2018/03/26(月) 22:45:31.40

そういえば、必ず”ん”で終わらなければならないっていう制約はないよね。
言葉が尽きても負けなんだし。

**デフォルトの名無しさん** · 2018/03/27(火) 01:45:16.06

すげぇ
しりとりは普通に組むとオーダーが大きくなるからなぁ
お題の単語数10^5に対応するプログラム書ける気がしない
辺は少ないし、これ最大流で解けるんだっけ？

**デフォルトの名無しさん** · 2018/03/27(火) 02:13:31.11

あんまり、オーダー爆発起こすとちょっと大変だな。
次に続く単語数の数が多いほど爆発する。
最大N!だけど、そういうケースは少ないよ。

**デフォルトの名無しさん** · 2018/03/27(火) 03:46:37.52

最適化閃いたけど、無理筋やった。
3変数ごにょごにょするだけで枝切できるかと思ったんだけど。

**デフォルトの名無しさん** · 2018/03/27(火) 05:36:02.02

再帰使わない解を見たいな