プログラミングのお題スレ Part10
レス数が950を超えています。1000を超えると書き込みができなくなります。
なるほど、最小って条件は止めるか
条件を変えるわ
解がN通りある時、それぞれの解の本数をa_i(1≦i≦N)とする
この時、任意のi,j(1≦i,j≦N)に対しa_j-a_i≧0を満たすa_iを出力してくれれば良いよ
>>845 隣接しない
隣接したらあみだくじとして成立しないしね >>841 J
2 echo 2&#;._2 stdin'' 多分最小を別の表現にしたつもりなんだろうけど
日本語がめちゃくちゃ
無理しなくて良いよ >>853-854
ここ数日、数学の知識全くないくせに噛みついてる無知はお前だろ
>>851は一般的な最小元の定義だろうが 「任意のi,j(1≦i,j≦N)に対しa_j-a_i≧0を満たすa_iを出力」
意味がわかりません >>856
「任意の i, j」というのがおかしい、i を先に決定した上での「任意の j 」でいい >>859 >>861
一般ピープルが習得するとよい（大げさにいえば世界観が変わるような）数学の分野を教えていただければ嬉しいです 群論・環論
ごめん聞いたことあるような言葉を羅列してみただけ お題
マイナンバーが一部欠けてしまった
?部分を補完して可能性のあるマイナンバーをすべて列挙せよ
[example 1]
99999999999?
=>
999999999996
[example 2]
??9999999999
=>
069999999999
179999999999
289999999999
399999999999
509999999999
619999999999
729999999999
839999999999
949999999999 >>869 Ruby 全探索
A = (1..11).map{|i| i + 1 - i / 7 * 6}
%w[
99999999999? ??9999999999
].each{|s|
puts '', s, '=>'
10.**(s.count(??)).times{|i|
d = "%012d".%(i).chars
m = s.gsub(??){d.pop}.reverse.chars.map(&:to_i)
x = A.zip(m[1, 11]).map{|a, b| a * b}.sum % 11
puts m.reverse.join if (x == 1 ? 0 : -x % 11) == m[0]
}
}
#=>
99999999999?
=>
999999999996
??9999999999
=>
509999999999
619999999999
729999999999
839999999999
949999999999
069999999999
179999999999
289999999999
399999999999 マイナンバーのチェックディジットを分かり易く解説しているページはないものかと探したらあったのでURL書いとく。
https://qiita.com/kmz_kappa/items/af18ac7b6b8bfe9041b0 >>858 マジだわ、算数できない奴に噛み付いて自分がダメージ受けた
やはり数学で無理に語るべきではないな、専攻の情報の範囲だけにしとこ…… >>869 Squeak/Pharo Smalltalk
| check |
check := [:digitsStr |
| digits checkDigit calcDigit |
digits := digitsStr asArray collect: #digitValue.
checkDigit := digits last.
calcDigit := ((digits * #(6 5 4 3 2 7 6 5 4 3 2 0)) sum \\ 11
in: [:x | x < 2 ifTrue: [0] ifFalse: [11 - x]]).
checkDigit = calcDigit
].
#('99999999999?' '??9999999999') collect: [:incmpNum |
| indices candNums |
indices := incmpNum asArray collectWithIndex: [:chr :idx | chr == $? ifTrue: [idx] ifFalse: [0]].
indices := indices reject: #isZero.
candNums := OrderedCollection new.
($0 to: $9) asDigitsToPower: indices size do: [:digs |
| candNum |
candNum := incmpNum copy.
indices with: digs do: [:idx :dig | candNum at: idx put: dig].
(check value: candNum) ifTrue: [candNums add: candNum]
].
incmpNum -> candNums asStringWithCr
] >>865
回転すし問題が気になります＞＜
教えてください！！ >>875
0296 デフォルトの名無しさん 2017/06/26 21:09:32
前にあったやつ。??
回転寿司にやってきた私は、コンベア上の寿司をすべて食べて帰ることにしている。??
コンベアは毎秒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" > ? お題
0〜N-1の数字を1つずつ使ったN進数表記でN桁の数のうち、最も多くの素因数を持つ数を求めよ
N=2
→10
N=5
→34210 (10進数で2430=2*3^5*5, 素因数は7個)
N=10
→??? 全てを探索
しかない気がする
N=14くらいが限度か まーた数学の問題か。
まーたマウント取りたいセンセの荒らしか。
うんざり アルゴリズムと数学は切り離せないものだし数学が役立つ場面はもちろん多いんだけど、数学だけで完結しちゃう問題では、プログラミングのお題としては面白味がないよね。
むしろこのスレに的には悪問と言ってもよいと個人的には思う。
素直なプログラミングでは複雑になってしまうところを数学を使うことでスマートに解けるとか、逆に数学を使うことで全く別のアプローチの解法があるとかだと、面白いと思う。
必ずしも速い、安い、上手いが正義じゃなくて、そんな解き方もあるのねとか、それどうなってんの？と不思議に思えるような解法とかも見てみたいし、そんな解法が見られるお題が面白いと思う。 追加すると、言語によって異なる記述能力や得手不得手を活かして上手く解いたとか簡潔に書けたとか、逆にわざわざそんな敢えて難しいやり方をするかとか、そういうのも面白いなと思います。 数学で完結してんのかこれ
コンピュータ使わない解法思いつかんが 素因数の個数って何だっけ
互いに素な約数の個数なら、N=5の時33220(=2310=2*3*5*7*11)の方が多いし、素因数分解で出てくる素数の個数ならN=5の時31143(=2048=2^11)の方が多いし
私が文を読めていないだけ？ ただ列挙して調べなきゃいけないとすると面白くもなんともない。
いい解を作ろうとすれば、できるかどうかはともかく
数学ひねり回すのだけがメインの仕事になるみたいな。 J ブルートフォース
q =: >./&(+/&|:&(0&<)&q:&(#. (i.@! A. i.)))"0
iPhone の J インタプリタでは N=8 までが限界だった
q 2 3 4 5 6 7 8
1 2 6 7 13 10 16 素因数の個数だと2^11は2の1個だけなんだけどなあ
例だと11個と数えたいようだけど >>888
数学ひねり回してどうにかなる気はしない >>891
問題の着目点に応じて相異なる素因数の数になるか重解を許すか解釈すればいいんじゃないの
そうしないと高校数学に良くある(このスレにも出てるな)
「n! の素因数2の個数を求めよ」の答えが恒等的に1になってしまう。
知らんけど。 いや重解は変換ミス
それに重複を許さない個数でも問題は成立するな、
良く考えると。 >>897
解と根は本来、別の用語だよ
今はごっちゃに使われてるけど >>898
例を出さなかったらそれぞれの解釈が見れて面白かったかも
>>899
それで言い訳になってると思ってんの？ >>889 Thanks、理解した
全探索しか思いつかなかったorz >>816 J
200$(#~ 2&=@#@q:)2+i.1000 このスレを見ると
世の中のソフトが重くなる理由がよく分かる >>903
それ1000までの間に半素数が200個存在するってあらかじめ分かってなきゃ使えなくない あらかじめ調べておけばいい
どうせなら半素数自体もしらべてテーブルにしておけば コンパイラが究極に進化するとそうなる
今でも純関数&定数指定にすれば 究極に進化して、ある数を素因数分解しろとか離散対数求めろと言われたら、
何桁でもテーブルにあって即答ってか？
暗号死ぬわ。 >>816 J
>>817のやり方で
/:~~.,*/~p:i.20 トップバストとアンダーバストがmm単位で与えられるので
JIS L 4006におけるカップ体型区分を出力せよ
なお、与えられた体系が当該規格の数値と一致しない場合は
最も差の少ない体型区分を選べ
-*- input -*-
880 815
999 799
755 480
-*- output -*-
AA
E
H ミス
>>915 Ruby
#!ruby -na
puts ['AA',*?A..?I][(eval($F*?-)/25.0-3).round.clamp(0,9)] このスレは、素数表を使う問題が多い
一方、プログラミング・コンテストでは、自作ライブラリも持ち込めるから、
素数表・ZDD を持ち込んで、解けるような問題は少ない
数学的な解法がなくて、全探索して見つけるものが多い じゃあここで出てる問題をまず最初にNP完全かどうかを判定すればいい
競技プログラミングに適している問題かどうかを証明してから、改めてプログラミングにあたる プログラミング・コンテストの良問は、
持ち込みの自作ライブラリでは解けないもので、
素直に全探索すると、計算回数が1億回以上になって、2秒以内に解けないもの
ここで、パズル的に考えて、数学的な法則を使うことで、
枝切り・ショートカットして、計算回数が1千万回以下になるもの >>915 J
f=:{&(25#'AA'';;/'ABCDEFGHI')@<.@-&62.5&(-/) >>925
分かりにくいのは毎度の事だが今回はあんまり短くもならないんだな。 JアプリみつけたのでJで遊んでる初学者だけど
参考にするコード見つけにくい(少ない検索し難い読みにくい)から
>>925の人の存在は有り難い
見所はインデックスを25で割らずテーブルを25倍にしてるとこか お題：文字列の配列をカンマ区切りで表示せよ
複数の方法を用いること
ruby
https://ideone.com/cKprYN 配列を、って言ってるのに%wでスペース区切りの文字列から作るの？
てかrubyの%wって何のためにあるの？
splitあるのに組み込みので提供するほどのもの？
他言語者からしたらsplitは分かってもらえると思うが%wは分からんと思うぞ？
やっぱ書くだけの書き捨て言語なんかな。 >>928 common lisp
(let ((a '("java" "ruby" "rust")))
(format t "~{~A~^, ~}~%" a)
(princ (reduce (lambda ($0 $1) (concatenate 'string $0 ", " $1)) a))
)
; java, ruby, rust
; java, ruby, rust >>929
＞てかrubyの%wって何のためにあるの？
まさに今回のような場合に配列リテラルを作るためのものだろ
各要素が所与なのになんでわざわざ繋いだ文字列リテラル書いてsplitしようとするの？ >>928 ruby
puts a[0...-1].inject(''){|r,s| r << s << ',' } + a.last
puts a.inject(''){|r,s| r << s << ',' }.chop
puts a.map{|s| [s, ','] }.join.chop
b = a.join
a[0...-1].inject(0){|r,s| r += s.length + 1; b = b.insert(r-1, ','); r }
puts b >>929
Perl だと
@week = qw(Sun Mon Tue Wed Thu Fri Sat) >>931
今回のような？？
今回の問題文、「文字列の配列をカンマ区切りで表示せよ」ってなってんだが…
スペース区切りの文字列から始めてどうする。
それじゃ%wで配列にするまでもなく正規表現でスペースをカンマに置換すればいいじゃん。 >>928
Kotlin
https://paiza.io/projects/ZW2Hjc9tfnlrMwqvblaKlw
文字列は1行づつ入力から読んで MutableList に add して終わったら Array に変換して文字列の配列にしている。 >>928 javascript
var langs = ['javascript', 'python', 'go']
console.log(langs.join()) //ES5
console.log(langs.reduce((acc, elm) => `${acc},${elm}`)) //ES2015
langs |> ary => ary.join() |> console.log //ESNext
console.log((langs + ',').slice(0, -1)) //ES5 一番かんたんなの忘れてた
console.log(langs.toString())
console.log(langs + '')
console.log(`${langs}`) console.log(String(langs))
langs |> String |> console.log //ESNext >>928 Squeak Smalltalk
| arr |
arr := #(java rust ruby).
arr asCommaString. "=> 'java, rust, ruby' "
arr asCommaStringAnd. "=> 'java, rust and ruby' "
String streamContents: [:ss |
arr do: [:each | ss << each] separatedBy: [ss << ', ']
]. "=> 'java, rust, ruby' " >>928
join一発でできるようなことをわざわざ問題にするなよ... 誰かにコードを教えてもらう為に「お題」と言ってるだけじゃね？ 数学センセが嫉妬かみっともない
開口の広いお題が繁盛すんのは当たり前 蛇足で無粋でしょうけど寸評をもってお礼に代えさせて下さい
寸評：
>>930 素早くreduce拾って下さったのと、コードのリズム感が目に優しくてすこ
formatたる謎の戦法も興味深い
>>932 chop戦略を出して下さって感謝。bを使ったほうはフフッときた
>>935 Kotlinのコードいつも楽しく拝見してます
「先頭別で、二個目からカンマくっつけ戦法」出してくれて感謝
>>936 joinでカンマついちゃうのが他言語から見たら興味深い
>>939 いつも楽しく拝見してます、相変わらずギョッとさせられる
じつは当初、andつきのほうをお題にしようかとも迷いましたが
不要な複雑さを持ち込んでしまうと危惧して止めたんですがさすがのSmalltalk
総評：
joinでの解決一個だけで回答されるのが一番つまらないので
それを暗に防ぐために複数の方法っていう指定をした
二番目三番目の方法となると、見てて楽しい、言語ごとの工夫が見えてくる
おまえらありがとう そういや昨日本屋に行ったら「C言語による標準アルゴリズム事典」が売られてて、うわー懐かしいまだ売ってたのかこれ
と思ってよく見たら今年出たばかりの第2版だった。
［改訂新版］C言語による標準アルゴリズム事典 Software Technology
http://amzn.asia/bjcCLfp
この本はある意味お題になりそうな問題の宝庫ではないかと思う。 >>949
おう！
pascal 版を見たことがある、と思ってたんですが、気のせいだったのかな？ レス数が950を超えています。1000を超えると書き込みができなくなります。
