blog2019-06-111000円分の切手の購入には、何通りの手法があるか?(伝え方が完全に悪かったのだけど、)インターンの大学生に1,000円分の切手を買ってきてとお願いしたら、1,000円切手1枚を渡された......。聞いたら、そもそも切手を買ったことなんて今までなかったそう。これが令和......。2019こんなツイートがバズっていた。「1000円分の切手を購入して」と頼まれたとき、一体何通りの買い方があるのだろう。10円くらいなら頑張れるけど1000円は相当の努力を要する。プログラマではないけど、なんとなく実装してみる。考え方としては、動的計画法?を使うと良さそうだ。切手が1円と2円のものしかなければ、5円を切手で買う場合、3円を切手買う通り数と4円を切手で買う通り数の合計が5円を切手で買う通り数になる。それぞれに2円切手と1円切手を追加する手法があるからだ。このあたりの数学的な話は、ちょうどAtCoderBeginnersContestのCで最近出たばかりだ。a[N]);}という適当なコードを書いたら、2018816696222833910656252468851793841738864262054617892302459180312970595153790345675412673676673112703307948339857624925883177447105511378331105500927787309118585058021154540560775964571577964892483432744215161103404706532767038310124338081271084872173277731084108619793301504通りと出た。doubleを使っているので多分これは精度が悪い。1.798...*10^308程度のdoubleの範囲を超えなかったのは幸い。安い金額に対しては同様のプログラムで厳密に求められる。332(10円の場合)通りの買い方があるらしい。10円でも332通り。激しい指数関数的な増加である。ここでpythonを使ってみよう!精度を高める手法があるらしい。いっても私はpythonなんて使ってないので、decimalなんて環境も知らなければ配列の使い方さえ知らなかった。検索しながら30分くらい格闘して以下のコードを作る。nums[i]+nums[i-int(stamps[j])]print(nums[1000])2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390とでた。ちなみにgetcontext().prec=1000というのが精度である。10進で1000桁には行かないので適当な設定。52bit(doubleの仮数部分の精度)は大体15〜16桁精度だ。getcontext().prec=15にしてみると2.01881669622321E+276とでた。C言語のdoubleでは2.0188166962228339E+276だったので、まあ誤差でそんなものだろう。2.01881669622321E+276←15桁精度2.018816696222854E+276←16桁精度2.0188166962228474069←1000桁精度python初めて30分みたいな人が書いたプログラムなので自信がない。1,2,3,5,10,20,30,50,62,82,92,100,120,140,205,280,310,500,1000円切手があった場合、1000円分の切手を買う方法は2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390通りなのかな。だれか、正しいか検証して欲しい。endendprint(nums[1000]);同じ結果2018816696222847406903248298783095971003454597950956950486814286870151769566638334351695889582461204439244633372769436724665312005396075530178629791204098410261766867285766690432361030106623128263952566362440060615017667935586334548238897367080748492851021980966669336418640390を得た。...2018-12-11そこには存在しない三角コーンおめでとう。アドベントカレンダーの2日目の記事とし...2017-01-06m進記数法とn進記数法の両方で0と1だけで表記される非負整数。人間と接することの難しさ・人の目を見て話すリハビリそこには存在しない三角コーン税金関係とその決定・納付日まとめ月別アーカイブはてなブログをはじめよう!D_PLIUSさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。