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

**デフォルトの名無しさん** · 2018/02/18(日) 22:02:27.62

>>335
全部整数だねー

**デフォルトの名無しさん** · 2018/02/19(月) 09:54:55.43

>>318 Ruby 愚直に計算
https://ideone.com/nkoK67

**デフォルトの名無しさん** · 2018/02/20(火) 00:15:19.18

1 5 8 2 ? ? 7 6 ?
? ? 7 ? ? ? 8 ? ?
6 4 ? ? ? 8 ? ? ?

8 ? 6 4 ? ? 5 7 ?
? 2 ? ? ? 6 ? 1 ?
? ? ? ? ? 5 6 ? 9

4 ? ? ? 1 ? ? ? ?
? 9 ? ? ? ? 1 ? 7
7 ? 1 ? ? 2 ? ? 5

この問題はどのぐらい簡単?

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

問題に矛盾があるから解けない。
http://www.sudoku.name/sudoku-solver/jp
あたり参考にしとけ。

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

158293764
937641852
642758391
816429573
529376418
374185629
485917236
293564187
761832945
と出たが...

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

矛盾はないでしょ。解1つしかないしだし
難度でいえば、基本ルール(縦、横、3*3でかぶらない)だけでとけるから一番簡単な部類なんじゃない

**デフォルトの名無しさん** · 2018/02/20(火) 04:21:35.97

? ? 1 ? ? ? 9 ? ?
3 ? ? 9 ? 1 8 2 ?
7 ? ? ? ? ? 1 4 5

1 ? ? ? ? 2 ? 3 ?
4 ? ? ? ? 7 5 ? ?
8 7 6 ? 4 ? 2 ? ?

9 ? ? 7 ? 6 ? ? ?
? ? 8 ? ? 9 ? ? ?
? 1 7 ? 2 ? 6 ? ?

これはもう少し難しい?

**デフォルトの名無しさん** · 2018/02/20(火) 05:25:37.29

>>342
唯一解を仮定するか背理法使わないと解けないから中～上級くらいじゃない
てか数独スレで聞けばいいじゃん

**デフォルトの名無しさん** · 2018/02/20(火) 10:50:28.73

数独はどれほど難しくてもこのスレで公開されたプログラム等を使えばほとんど瞬時に答えが出てしまうわけで、難易度判定は答えを求めるのとは違う何かが必要なのではないか？

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

人間と同じ様に候補を消して行くだけで解けるのは初級～中級を予め埋まってる多さで分けて、総当たりでしか解けないのを上級、
答えが複数あって全て解くのをスペシャル級としたらいい。
でもどれも一瞬で解けちゃうんだけどね。
むしろ画像認識でカメラから問題を入力してくれよ。

**デフォルトの名無しさん** · 2018/02/20(火) 13:24:13.36

全部空欄の数独以上の難問はないことになるな

**デフォルトの名無しさん** · 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

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

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

>>419
https://ideone.com/LYz9cE
ひらがなは 7bit程度で表せるので、頭と尻だけ数値化、頭でテーブルを分けた。

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

>>446
スタックを展開するだけだからなぁ。
めんどくさいけど、理論は楽。

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

https://ideone.com/29wlkp
全探査しなくてもいいので、同じ階層に'あかい','あおい','あさい'など頭と尻が同じ語は枝刈り出来る。

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

>>444
＞最大N!だけど、そういうケースは少ないよ。

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

先頭の文字別にリストにでも格納しておけば N 単語での計算量は高々 O(N ^ R)

**デフォルトの名無しさん** · 2018/03/30(金) 08:34:52.77

お題
桁の並びが大きい順になっている数をすべてもとめる

**デフォルトの名無しさん** · 2018/03/30(金) 08:35:45.83

意味不明。

**デフォルトの名無しさん** · 2018/03/30(金) 08:51:48.50

9876543210の各桁を表示する・しない、で2^10-1(=1023)通りってことかの？

**デフォルトの名無しさん** · 2018/03/30(金) 08:58:40.80

>>451 Ruby

(1..10).each{|i| puts [*0..9].reverse.combination(i).map(&:join)}

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

あーそういうことか

**デフォルトの名無しさん** · 2018/03/30(金) 09:39:19.40

rubyがわからないのでわからん
どういうこと？
今スマホでアクセスしてるから試すのもできない

**デフォルトの名無しさん** · 2018/03/30(金) 09:42:37.75

すまほでもコピペしてideoneで試せるんじゃね？
https://ideone.com/ihH1LH

**デフォルトの名無しさん** · 2018/03/30(金) 09:51:09.95

>>457
おお。動いた。
あー。そういう意味か。

**デフォルトの名無しさん** · 2018/03/30(金) 20:28:56.47

お題： 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.33

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

◆QZaw55cn4c · 2018/03/30(金) 21:43:34.36

>>459
https://ideone.com/sSfH5w

＞以下の5問を合計1.8秒以内で。
は未達成、これは難しい‥‥

**デフォルトの名無しさん** · 2018/03/30(金) 21:47:51.34

面白いね

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

前スレから見始めた初心者だけど、
未知の課題に対するコーディング能力ってやっぱり大事だ

◆QZaw55cn4c · 2018/03/30(金) 21:49:03.26

>>460
なるほどねえ

**デフォルトの名無しさん** · 2018/03/31(土) 04:32:05.81

>>451
https://ideone.com/SLwoYB
https://ideone451.com/AGDBWO
C++。普通に解いたら20秒くらいかかるからさらに脳筋な方法で解こうと思ったらメモリ足りなかった。
とはいえ階乗では解きたくないし。まぁいいか。

**デフォルトの名無しさん** · 2018/03/31(土) 05:34:00.26

省メモリで解こうと思ったらGCCに匙投げられた。
コンパイルタイムはこれからやな。
https://ideone.com/CScvWR

**デフォルトの名無しさん** · 2018/03/31(土) 05:44:58.45

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を数える他の有力なやり方ってどんなだろう

**デフォルトの名無しさん** · 2018/03/31(土) 05:45:55.95

コピペミス
結果は
132 743 54321 2147483647 4294967296
32 183 13576 536870902 1073741816

が正しかった (どうでもいいか)

**デフォルトの名無しさん** · 2018/03/31(土) 05:48:43.09

ちなみに頭の(2,#d)$d,>がないと>>466の出力となる

**デフォルトの名無しさん** · 2018/03/31(土) 05:56:26.94

int count(unsigned int n){
int sum=0;
while(n){
n/=5;
sum+=n;
}
return sum;
}

この関数を５個の整数値に対して実行するのに
1.8秒以上かかるのかよｗ
（アセンブラでやる限り）8bitマイコンでもそこまで
かからない希ガスｗ

**デフォルトの名無しさん** · 2018/03/31(土) 05:58:47.42

それただのlog5

**デフォルトの名無しさん** · 2018/03/31(土) 06:00:14.81

違うかn足してるからいいのか

**デフォルトの名無しさん** · 2018/03/31(土) 18:37:28.47

俺の頭ではいまだにやり方がわからない。
既に1.8日を超えたような気がする。

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

n!を素因数分解した時の5の指数が求める数だから
Σ{k∈N}[n/5^k] を計算すればいいだけ

**デフォルトの名無しさん** · 2018/03/31(土) 23:35:26.94

>>473
意味分からん暗号書くなや

**デフォルトの名無しさん** · 2018/04/01(日) 00:08:24.40

Σ 総和
∈ 左は右の元である
N 自然数
[ ] 越えない最大の整数
/ 除算
^ べき乗

**デフォルトの名無しさん** · 2018/04/01(日) 02:06:20.43

記号の優先順位も書けや
あと{}の意味はぶくなや

**デフォルトの名無しさん** · 2018/04/01(日) 07:11:43.66

そんなのだから文系ってバカにされるんだぞ？

**デフォルトの名無しさん** · 2018/04/01(日) 07:16:13.39

意味わからん暗号て。。。
論理と集合やらんかったのか？
まだ習ってない歳なの？

**デフォルトの名無しさん** · 2018/04/01(日) 07:36:56.40

高卒にはつらい文字だ。

**デフォルトの名無しさん** · 2018/04/01(日) 07:50:55.11

こういう数式をTEX記法でup出来るサイトなかったっけ？

**デフォルトの名無しさん** · 2018/04/01(日) 09:35:03.69

>>477
文系だからではなく、元々バカなだけだろううな。
今時は普通なら、知らん事は自分で調べる。

**デフォルトの名無しさん** · 2018/04/01(日) 09:49:03.09

そもそも「素因数分解した時の5の指数」が分からんし！
なんでそれが0の数と関係あるのかも分からんし！
文系を迫害すんなや

◆QZaw55cn4c · 2018/04/01(日) 10:40:13.62

>>480
mediawiki を採用しているところですね
でも自分で mediawiki をビルドしようとすると、TeX 表記導入のところで嵌ります、うまくいかない

**デフォルトの名無しさん** · 2018/04/01(日) 13:21:09.52

これ分からなくなって八つ当たりしてんな、一旦ROMって落ち着けよ
10!=3628800=36288x10^2のように、後ろの0の数は10が何個掛けられているかで決まる
10=2x5だから2と5の掛けられている数のうち小さい方とも言えるな
で、一例として10!=1x2x3x4x5x6x7x8x9x10=2^8x3^4x5^2x7=2^6x3^4x7x(2^2x5^2)だから、0が2つ付くと言える
どう考えても2の素因数は5の素因数より多くなるので5の素因数の数だけ分かれば良い
この時、5の素因数の数はnが5の倍数になった時(n/5)+nが5^2の倍数になった時(n/(5^2))+…と計算すれば求まる端数切り捨てな

**デフォルトの名無しさん** · 2018/04/01(日) 14:01:25.37

>>484
> どう考えても2の素因数は5の素因数より多くなる

そうとは限らないじゃん
2の素因数の数も数えなきゃ不正確じゃん

**KAC** · 2018/04/01(日) 14:29:21.34

>>485
それを主張するなら、2の方が多くなる事例をあげるか、証明するかしないと。

**デフォルトの名無しさん** · 2018/04/01(日) 14:50:31.82

多い分には問題がない

**デフォルトの名無しさん** · 2018/04/01(日) 15:21:10.32

>>485
任意の2以上の整数nとする. n!に対して素数kの素因数の数が F(n, k) になる事は機知とする.
F(n, k) = [n/k] + [n/(k^2)] + ...
またガウス記号の定義([x] は x を超えない最大の整数)から任意の実数 x に対して,
x - 1 < [x] <= x　　……☆.
m_k を n/(k^m_k) >= 1 となる最大の整数とすると,
n/(k^m_k) >= 1 ⇔ n < k^m_k ⇔ log_k(n) >= m_k　なので, m_k = [log_k(n)].
また m_k より大きな任意の整数 i に対して n/(k^i) < 1 なので, [n/(k^i)] = 0.
従って, F(n, k) = [n/k] + [n/(k^2)] + ... + [n/(k^m_k)].
さて, ☆より
F(n, 5) <= n/5 + n/(5^2) + ... + n/(5^m_5)
= n*(1/5)*(1 - 1/(5^m_5))/(1 - 1/5)
= n*(1 - 1/(5^m_5))/(5 - 1)
= n*(1 - 1/(5^[log_5(n)]))/(5 - 1)
<= n*(1 - 1/(5^log_5(n)))/(5 - 1)
= (n - 1)/4,
F(n, 2) > n/2 - 1 + n/(2^2) - 1 + ... + n/(2^m_2)
= n*(1/2)*(1 - 1/(2^m_2))/(1 - 1/2) + (-1)*m_2
= n*(1 - 1/(2^m_2)) - m_2
> n*(1 - 1/(2^(log_2(n) - 1))) - log_2(n)
= n - log_2(n) - 2.
依って2以上の任意の整数nに対して,
F(n, 5) <= (n - 1)/4 < n - log_2(n) - 2 < F(n, 2)
となり題意は示された.
((n - 1)/4 < n - log_2(n) - 2 は増減表を書くなりして確かめて)

**デフォルトの名無しさん** · 2018/04/01(日) 15:34:29.77

a,bをとりあえず非負実数
[a]をaを超えない最大の整数として
a>=b→[a]>=[b]
[a+b]>=[a]+[b]
はすぐにわかる。
n!を割る2べき数の最大指数は1からnまでに偶数が[n/2]個
あることより[n/2]以上であることもすぐわかる

5^m<=n<5^(m+1)として
[n/5]+[n/5^2]+...+[n/5^m]
<=[n/5+n/5^2+...+n/5^m]
<=[n/5+n/5^2+...]=[n/4]<=[n/2]<=n!を割る2べき数の最大指数

◆QZaw55cn4c · 2018/04/01(日) 15:46:35.74

>>486
「素因数 2 の数は素因数 5 の数よりも多い」
を使うのなら証明は使う側がしないといけないだろう？一定の範囲では 2の倍数の方が 5 の倍数よりも多いとはわかるが、素因数の数について正確なことをいえるかな？

**デフォルトの名無しさん** · 2018/04/01(日) 15:47:58.83

[n/5]+2[n/5^2]+3[n/5^3]+...+m[n/5^m]
を評価しなければいけなかった（。。）

mを非負整数とするときm[a]<=[am]
だから
[n/5]+2[n/5^2]+3[n/5^3]+...+m[n/5^m]<=
[n/5]+[2n/5^2]+[3n/5^3]+...+[mn/5^m]<=
[n/5+2n/5^2+...+mn/5^m+...]<=
[n (1/5)(1+2(1/5)+3(1/5)^2+....)]
=[n(1/5)/(1-1/5)^2]
=[5n/16]<=[n/2]
あとは同じ 👀
Rock54: Caution(BBR-MD5:0be15ced7fbdb9fdb4d0ce1929c1b82f)

**デフォルトの名無しさん** · 2018/04/01(日) 16:14:16.83

なんか長々と書かせちゃってごめん
正の整数の全範囲が対象じゃなくてあくまで「n!」だってこと忘れてたわ

**デフォルトの名無しさん** · 2018/04/01(日) 18:24:24.96

勘違い

**デフォルトの名無しさん** · 2018/04/01(日) 18:24:43.79

>>491は無視して

**デフォルトの名無しさん** · 2018/04/01(日) 22:04:20.90

>>462
>未知の課題に対するコーディング能力
とか言ってるが、高校数学ではよくある問題だぞ？

ttp://examist.jp/mathematics/integer/kaijyou-soinsu/
ttp://www.geocities.jp/math12345go/math-qa/kaijou.htm
ttps://www.school-turnup.com/p-12594/
ttps://www.shinko-keirin.co.jp/keirinkan/tea/kou/jissen/sugaku/201603/index.html

高卒なんて言い訳になんねーよ

**デフォルトの名無しさん** · 2018/04/01(日) 22:25:21.45

>>495
数I・Aで100点だったが、数II・Bで0点取って、数III・Cは選択しなかった俺に謝れ

**デフォルトの名無しさん** · 2018/04/02(月) 01:59:38.46

お題そのものが数学のお題だったということだな。

**デフォルトの名無しさん** · 2018/04/02(月) 07:50:16.86

プログラミング的には、n!を割る最大の5のべき乗の指数が最大の2のべき乗の指数
を超えないということを使わずに（＝知らずに）
それでも十分な速度（実質>>469程度の処理しかしない）なものが書けるかということが課題

高校レベルの課題に見えて実は決してそうじゃないな

**KAC** · 2018/04/02(月) 08:54:14.80

>>498
設計したこと無いの？

**デフォルトの名無しさん** · 2018/04/02(月) 09:32:15.39

select max(m) from select m where 10^m|n!
と同レベルの可読性だが
やることは割り算しながら足し算となるコードなんて
そもそもあるのかよw

**デフォルトの名無しさん** · 2018/04/02(月) 12:18:57.87

>>498
>知らずに十分な速度
その程度なら2の個数も数えるだけだから簡単だし高速だと思う
が、普通はちょっと考えて5だけで良いなと5だけ数えるコードを書くんじゃないかな
何も知らず何も考えず計算機任せの力技ってのだけがプログラミングじゃないでしょ。

**デフォルトの名無しさん** · 2018/04/02(月) 12:28:13.55

高校レベルの数学をすっかり忘れたおぢさんにやさしく教えておくれ。

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

素因数の数が
m := [log(n)/log(k)]として
　m
　Σ[n/k^i]
i=1
明らかにmも[]の中もkに対して(広義)単調減少なんだから
素数が大きくなるほどn!のその素因数の数が減ることも明確というお話

**デフォルトの名無しさん** · 2018/04/03(火) 00:32:23.81

>>503
ご覧ください、これがアスペです

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

>>498
中学生が手計算で出来るレベルだ
数学苦手でしょ？

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

>>502
1～132の整数の中に5の倍数は何個ある？
1～132の整数の中に25の倍数は何個ある？
1～132の整数の中に125の倍数は何個ある？
1～132の整数の中に625の倍数は何個ある？
...

132の階乗を素数の積で表したとき
5は何回出てくるる？

132の階乗の右に並ぶ0の数は？

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

何時までやってんだよｗ

**デフォルトの名無しさん** · 2018/04/03(火) 09:25:43.98

>>506
132という値を出した理由は？
5,25,125,625を出した理由は？

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

こんだけ話題が伸びてる問題なのに出題後高々10分でほぼ理想的なコードが掛かれてるってのが面白いな

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

個々の住人数学が滅茶苦茶できてコードが3割みたいな人いるからな。

**デフォルトの名無しさん** · 2018/04/03(火) 10:49:30.76

>>508
> 132という値を出した理由は？
１問目の数値からから

> 5,25,125,625を出した理由は？
考えてみよう

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

俺は理想的なコードは割って足すループの方だ
可読性だなんだの風潮はあるが、ああいう一工夫がこういうプログラミングの煌めき

と思う

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

何が煌きだよｗ
定石（じょうしき）だろｗ

**デフォルトの名無しさん** · 2018/04/03(火) 22:23:56.22

>>510
というか至極単純なコードならついついゴルフしたくなってしまうというか

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

お題
与えられたデータを間引きして小さいな順に並べる
間引くデータの個数の最小値を求める

**デフォルトの名無しさん** · 2018/04/03(火) 22:58:26.43

日本語でおｋ

**デフォルトの名無しさん** · 2018/04/03(火) 23:00:28.05

任意の有限長の実数列に対し
単調増加列の中で最大長となる部分列を求めよ

って感じ？

**デフォルトの名無しさん** · 2018/04/03(火) 23:07:35.66

要素数の最大はどれくらい？

**デフォルトの名無しさん** · 2018/04/03(火) 23:31:42.00

>>509
すぐに「n!の末尾の0の個数」などをｸﾞｸﾞって
WEBに書かれている方式をコーディングするか、
自分の頭で方式から考えはじめるかの違いだろうな

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

まさかな…

**デフォルトの名無しさん** · 2018/04/04(水) 00:25:41.22

>>513
そのわりには>>469に至るまで出てきてないわけだが
コロンブスの卵にケチ付けた奴みたいだな

**デフォルトの名無しさん** · 2018/04/04(水) 00:27:47.47

>>515
1,1,1の場合、0個で良いのか？

**デフォルトの名無しさん** · 2018/04/04(水) 00:42:07.59

>>519
ググるような問題か？
普通に義務教育を出てれば一瞬でわかると思うのだが

**デフォルトの名無しさん** · 2018/04/04(水) 00:46:27.40

>>522
「小さいな順」ってどっちだろうね？
単調増加か単調非減少か
私は単調増加だと思ったから答えは2個
普通のソートだと単調非減少だから単調増加？

どっちにしろアルゴリズムは大して変わらん

**デフォルトの名無しさん** · 2018/04/04(水) 00:51:30.79

>>523
義務教育でlogはやら無いぞ
何分でコーディング完了して動作確認までいったのよ

**デフォルトの名無しさん** · 2018/04/04(水) 00:52:29.89

logなんて使わん

**デフォルトの名無しさん** · 2018/04/04(水) 00:53:18.67

素因数分解を習えば十分

**デフォルトの名無しさん** · 2018/04/04(水) 00:53:53.74

>>526
何番のお台の話をしてるんだよ
ずれてるぞボケが

**デフォルトの名無しさん** · 2018/04/04(水) 00:56:57.83

ずれたとしたら俺のせいではない
>>519か>>525が悪い

**デフォルトの名無しさん** · 2018/04/04(水) 00:58:01.53

いや、お前が悪い。きっぱり

**デフォルトの名無しさん** · 2018/04/04(水) 00:59:08.89

んで、お前はその簡単な問題を
何分で問題解決しコーディング完了して動作確認までいったのよ

**デフォルトの名無しさん** · 2018/04/04(水) 01:00:53.49

>>519は>>459の問題であることは明らか

**デフォルトの名無しさん** · 2018/04/04(水) 01:02:49.08

log使ってんじゃん

普通に義務教育を出てれば一瞬でわかると思って
お前はその簡単な問題を
何分で問題解決しコーディング完了して動作確認までいったのよ
上の方のレスでどれがお前の回答よ

**デフォルトの名無しさん** · 2018/04/04(水) 01:04:22.37

>>531
簡単すぎて書く気にもならんレベル
logなんか使わん

**デフォルトの名無しさん** · 2018/04/04(水) 01:05:01.45

>>506にlogなんか出て来ないだろ？