プログラミングのお題スレ Part9 [無断転載禁止]©2ch.net
レス数が900を超えています。1000を超えると表示できなくなるよ。
作ってみたけど、オッセ―。
なんか数学的にやらないとダメぽ。
>>810
検索したら出てきた。
ただのHYPODだった。 あ〜ん。足し算10兆回かかるとかむりげーじゃ。
どうしようかこれ。 >>807
https://ideone.com/5Tu6fx
C++。ギブアップ。遅すぎだ。
デバッグ不完全だからそこを忘れないで。
多分1日かけても終わらないと思う。 >>807
特に大きな工夫もなく普通に3重ループで出来ましたよ
151個かな ぶ。おれは・・・いったい・・・。
だめだなぁ。才能ないなぁ。 >>801のように積へ変換した場合、どれ位の精度・桁数が必要なのか簡単にわからないな。
>>801でやると、誤差ありの巨大な数同士の掛け算になって、その結果誤差が拡大する。
和のままやると、適当に2ベキをかければ、各項の整数部分だけ計算すればよさそうだけど。
>>801は桁を十分にとったとしても、2進10桁以上の部分も計算途中で無視はできないか。 グア。題意勘違いしてた。
直方体の対角線はいらんのか。うおー。
ばかばかー。 >>807
https://ideone.com/Uipgvw
C++。書き直したら、>>816のパクリ見たくなった。
そしてそれでも遅いとかあかんなー。
うーん。なんでなんだろう・・・。 >>820
普通に、求めたい精度＋α の精度を保てば十分かと
演算回数はlog(n)のオーダーなので
普通にlog(2)を求める時には使える手法 物体は表面だけでなく無数の内面を有するという考えは絶対に存在する
一方で全てを表面でしかとらえない人の存在も否定できない log2は>>801でもできそうだ。
積の先頭ほど精度が必要で、無視できる上限・下限を積の位置で可変にするか、
最初の積の計算で必要な精度をすべてに適用するかでいけそう。 >>817
これパクってstd::bitset<10001>でやったら動かないかな
nextSetBitだけ作れば動きそう >>807
これでいいかな？
Kotlin で書いた。しかしpaiza.ioの制限なのか、何故か import kotlin.math.* がエラーだったので java.lang.Math の関数を使っている。
https://paiza.io/projects/ImbYdf3NSWgW-zj8Ke6cDw >>833 ruby
i,j=0,-1;p i while(i+=j+=1)<10000 >>833 Brainf**k ワンライナー(笑)
https://ideone.com/TyMeco
遅すぎて8bitまでしか計算できなかった ideone.comはたいして最適化しないBrainf**k処理系だからな >>833
1+2+3+... だよね? じゃあこうだ。
perl -e '$i=0;$n=1;while(($i+=$n)<=10000){print"$i\n";++$n}' >>833
while じゃなくて for にするとこう。
perl -e 'for($i=0,$n=1;($i+=$n)<=10000;++$n){print"$i\n"}' >833 R
cat(cumsum(0:140)) >>801は精度管理の手間を考えたら、そのまま級数計算するのと大差ないと諦めたが。
こうすれば割り算の小数計算がほぼでないからいいのでは? 既に実装済?
an = 1/n、r = 2として、Σ an/r^n を定数C倍したやつの整数部分の取り出し。
C*anを再びanとおく。
Σ an/r^n
= a2/r^2 + a4/r^4 +・・・+ aN(2)/r^N(2) (添え字は2の倍数を動く)
+ a3/r^3 + a9/r^9 + a15/r^15 + ・・・+ aN(3)/r^N(3)
+ ap/r^p + ・・・+ aq/r^q + ・・・ (pは素数、qはp未満の数で割り切れないpの倍数)
= 1/N(2)r^N(2) * ( N(2)*a2*r^(N(2)-2) + ・・・ + N(2)*aN(2) ) + ・・
この分子部分は、各項、整数でそのまま計算しても>>801でも速くなるはず。 秒数ではCPU依存するから正確に比較できない。
掛ける2だけのループを10^10回するだけでも19秒では終わらない。
無料のideone codepadなどの実行可能時間以内にできる範囲とか、
ベースとなる簡単なコード、関数の何倍時間がかかるかなどだと比較できるけど。 くだらん話かも知れんけど
竹内関数のメモ化
https://ideone.com/sVhke1
これはC++によるものだけど、C++や他の言語でもっと高速に書く方法はあるか？ あ、ちなみにideoneの結果は間違っている
多分スタックオーバーフローしている
100, 50, 0の場合は答えは100 >>849
constexprにすれば実行時はほぼ計算無しにできると思う。
コンパイル時間半端ないけど。 ところで、いくらメモ化してても5回しか呼ばれないってことがあるのか？って気はする。 https://ideone.com/Y9WhRz
竹内関数constexprにしてみた。
ウチの環境だとこの辺のパラメータが限界っぽいかな。
100,50,0だとメモリ使い切るらしい。 あら、コンパイルエラーになっちゃった。
VCだと通ったんだけど。もちろんステップ数とか設定はいじってるが。 お題
6つの辺の長さが 与えられた4面体の体積を求める お題
8つの辺の長さが与えられた超5面体の体積を求める お題
与えられた自然数を高々四個の四角数(平方数)の和で表せ >>856 Ruby
https://ideone.com/qbHExm
ただし四面体ABC-Dに対して入力の順序は
AB BC CA CD DA BD とする >>857
8つだと多胞体が一意に定まらないと思うんだが >>853
64bit環境でやったらスラッシング起きて＼(^o^)／ >>862
１０でも足りないと思うんだけどひょっとして超五面体って五胞体のつもりで言ってる？ >>861
ウチはi6700メモリ8Gだな。20秒くらいボケーっとしてたらコンパイル完了する。
実実行より全然早い。 >>866
んー32bitでコンパイルしてみるかな
64bitはマジ卍ヤバい >>866
悪い
VCで /constexpr:steps 1000000を付けてコンパイルしたら4秒ほどでコンパイルが終わった
多分/MPも付けてるからだと思う
実行結果は25になった
gcc 7.2.0 64bitだとどんどんメモリを食って行って最後にスラッシングが起きる
馬鹿正直な実装をしているからかも知れないね
VCの方がいろいろとメモリを食わないように工夫されてるのかも
Clangでも/constexpr:steps は -fconstexpr-steps という形でサポートされてるようだから
多分行けると思う
メモリ64G積んでるし >>868
いいマシーンだな。
まぁ、ウチはあれくらいで資源尽きちゃうけど、メモリ64Gもあったらもっと行けるな。
気が向いたらどうぞ。 以下のURLのように、同じ色の点同士をつなぐゲームがある。
https://play.google.com/store/apps/details?id=com.bigduckgames.flow
N×Mの2次元配列が与えられる。配列の各要素は半角英字('a'-'z')または'*'である。
半角英字は色付きの点を表し、'*'は空のマスを表す。
'*'以外の文字は、配列中に必ず2個ずつ存在する。
このパズルの解を一つ出力せよ。
・'-'は左右のマスをつなぐ
・'|'は上下のマスをつなぐ
・'.'はマスをつながない
解がない場合は"No solution"と出力せよ。
[input]
***rg
**bg*
r****
ob*yo
****y
[output]
*-*-*-r.g
|.......|
*.*-b.g-*
|.|......
r.*.*-*-*
..|.|...|
o.b.*.y.o
|...|.|..
*-*-*.*-y >>841
やってはないけど、そもそもこれ間違ってるのと、同じような発想でやるとしても
全ての素数での分類ではなく、3分割くらいのほうが効率がいいのと、
Σ (2の倍数) + Σ (3の倍数かつ2の倍数でない) + Σ (2と3で割り切れない)
分割する事もなく、N項の和だとしたらNの階乗か分数をなくせる最小公倍数かけてもいい。それだと掛け算もしくは割り算がいくつも出てくるが。 >>871
等幅フォントで表示しているエディタにコピペしてようやっと何を言わんとしているか分かった。
それってマスとマスの間に - または | を入れて繋ぐってことでいいんだよね? で、つながない所がピリオドだと。
(まあ等幅フォントのASCIIでやるならそれしか方法ないとは思うけど)。 しかしピリオドは
**
**
の時に
*.*
...
*.*
のようになって中央のピリオドが本来なら不要なものになるわけだが、それはスペースでなくても良いのかな？
まあただの幅合わせだからどうでもいいものではあるが。 >>801 の方法で出来ると書いてるけど
結局誰もやってないのか
個人的には(高速には)出来ないと思っている >>871
課題じゃなくて
単にソルバーの作成依頼でしょ 無理に線引かないでrだのgだので埋めた方がわかりやすいと思うがな
すべてのマスを埋めなければならないルールが抜け落ちてるみたいだから
実は別物のゲームで交差があるとかなったらそうはいかないが ブレゼンハム的なやつって、始点と傾き(と区間や境界等で決まる明示されない終点)が
与えられた際に、終点座標を求めてから始点に向かうのってアリなんだろうか？ ここでやるには問題がでかすぎ
100分割してほしい 訂正
ただし解は1つでありかつ線が通らないマスは無いことを前提とする
ではなく
解が存在すればすべての解は全てのマスを通ることを前提とする お題
22の分割(たとえば3+3+5+8)のうち
分割したそれぞれの数の逆数の和が1になるものを求める 早速間違えましたすみません
3 +5 +6 +8
でした >>883 ruby
f=->n,k{n==1?[[k]]:(1..k/n).flat_map{|i|f[n-1,k-i].map{|j|[i,*j].sort}}.uniq}
(1..22).each{|i|f[i,22].each{|a|p a if a.map{|e|1r/e}.sum==1}}
#=>[2, 4, 8, 8]
[2, 5, 5, 10]
[3, 3, 4, 12] C++で書いたけど、オセー。
デバッグ大変だ。
うーん。困ったなぁ。 https://ideone.com/3ZWKv1
C++。こんなコード書いてみたけど、無理ゲー。
ちょっと厳しいなぁ。最近解けてないなぁ。
ちなみにデバッグ不完全なのであしからず。 こういう数学的な問題を解くにはやっぱりプログラミング以前に数学を勉強した方がいいのでしょうか？ >>888
数学は大事だよー。
俺数学出来ないから、解けない問題がそれなりにある。
算数では限界だ〜〜。
まぁ、数学とプログラミングって習得時はオーバーラップするところが少ないから融合するまでちょっと大変かな。
でも数学は強力なツールです。 一般論でいえば必要だろうけど>>883なんて全部列挙したところで計算量はたかが知れてるし
目下必要なのは論理学的思考能力なのでは >>883 Java
https://ideone.com/WiMkNl
22くらいなら大丈夫だけど桁が増えると(´・ω・`) お題
52をいくつかの自然数に分解して
それらの最小公倍数を最大化せよ 分解って、積じゃなくて和で良いんだよね？
数学の知識を使うと一瞬だけど 数学の知識が無いなら素直にコンピューターの力を借りなさい そもそも数学で簡単にとけない問題を力わざでとくための計算機だろ >>894
よくわからんが52の場合は
180180 [3, 4, 5, 7, 9, 11, 13]
ということらしいぞ C++17発行されたから開発環境がさっさと対応してGCDくらい使えるようになりたい。 >>768の問題で0<=b<10,0<c<10という制限がついた時
移動を何回か繰り返すと必ず元に戻るんだけど
その回数はbには無関係にc,10-c,10の最小公倍数で
okかな？ 一回の移動ではd=1ね。
ま、その制限を付けなくともd,c,10-c,10の最小公倍数になるんだろうけど >>901-902
10-c,10の最小公倍数じゃね？ 数学云々言ってる奴って、何故かその成果見せないよな。
俺でも出来そうなFUD、いやマウントかな。 ていうか、計算機はどちらかというと算数だよな。
数学は公式とか証明とか、そういう手順みたいなものを考えるわけで、プログラミングに近い。
コンピュータは作られたプログラムに従って計算結果を出すだけ。
もちろんプログラムそのものをコンピュータに作らせることも可能だけどね。これは次元が違う話だよね。 プログラムには算数と三角関数とかがあればいい
あとN進法 では簡単なお題を
bを底とする値vを、2〜36進数に変換し表示してください。
なお、bは2〜36の整数、vは0以上の整数とし、不正な入力はないものとしてよい。
また、底と値の区切り文字は入出力ともに特に問わない。
[入力例]
16 deadbabe
[出力例]
2#11011110101011011011101010111110
3#100122100210210001200
4#3132223123222332
5#30122344134421
6#1414413520330
7#161402600604
8#33653335276
9#10570723050
10#3735927486
11#1647919685
(略)
27#9h9ll1i
28#7l225hi
29#6842o9l
30#53m7kg6
31#46f9hir
32#3farelu
33#2tf7mor
34#2e7m366
35#214kbpb
36#1ps9w3i レス数が900を超えています。1000を超えると表示できなくなるよ。
