ペル方程式の問題です。って言ってますけど、わからないので、情報を調べていてこの方程式がペル方程式という物だということを知ったんですけどね。解く方法はわかったんですが、残念なことに、どうしてこうすれば答が出るのか理解できてません。そういうの多いんですけど、ちょっと悔しいね。もとのペル方程式は、 x^2 - Dy^2 = ±1の形をしています。これの最小解を求めるには、二次体(Q√D)がなんたらかんたらで、結局は連分数√Dの連分数展開の結果を使ってごにょごにょであるとのこと。詳しくはペル方程式でググってください。やりかただけ書くと、まずは√Dの連分数展開を求めます。平方根の連分数展開は、小数点以下が必ずループするので、こんな形になります。{a0: a1, a2, ... an, ,a1, ...}で、この、n-1番目までの結果を分数にしたものの分子と分母がそれぞれxとyの最小解になっているんだそうな。連分数展開は前の問題で作ったのがあるけど、ちょっと改変が必要。あと、結果は場合によっては、x^2...
魔方陣系の問題です。条件を見つけるためにちょっと試していたら、その場で答が出ちゃったという初めての経験をしました。ですけど、勉強のために、コードは書いてみました。魔方陣のセオリー通り、穴は図のA(外周)とB(内周)の様に2種類に分けられます。一列に並んだ数の合計を同じにするということは、 A1 + B1 + B2 A2 + B2 + B3 A3 + B3 + B4 A4 + B4 + B5 A5 + B5 + B1この5つが同じになるということです。これをXとすると全部の合計は、5X ということになります。次に、上の式から全部の合計は、 ...
18の問題と同じで、データが大きくなった問題。18を解いたときにもそれなりに考えて作ったんだけれども、電車に乗っているとにきいい方法を思いついたので、実装してみた。ライン数で10分の1くらいになったんじゃないかな？基本的な考えかたは18を解いたときと同じ。この問題は、最大の数だけわかればいいので、上からたどっていって、合計が大きくなるものを見付ければいい。たとえば下のような場面では、 o A B o o o X o oXの値に影響するのはA、Bの2つのみ。 それぞれAとBまでのルートの和が大きくなる方からXに来るのが大きいルート。例題の場合1: 32: 7 43: 2 4 64: 8 5 9 32列目は、それぞれ上が3なので、10と7。3列目。 10 7 /\...
eについて、ある段階まで連分数展開したものを分数表記したときの分子の数字の問題。これは、問題57で使った公式ですぐに解ける。問題57ではは√2だったけど、こんどはe。この方式は、連分数展開したときの 数列aを求める必要がある。64の答えを使ってもいいのだけれど、eの連分数は、 {2:1,2,1,1,4,1,1,6,1,1,8,1,....} になることが分っているので、これをつかう。a0 = 2 、このあとa1 = 1, a2 = 2, a3 = 1,a4 = 1, a5 = 4, a6 = 1,a7 = 1 a8 = 6, a9 = 1,のように規則的に並んでいる。これを、a[n] についての場合で分けるとこうなる。n=0 のときは2nを3で割った余りが2のときは ((n+1)/3)*2それ以外は1これで実装した。
...
平方根の正則連分数展開のループの繰り返し数の問題です。問題文にある通りに連分数展開をしていく処理を作りました。連分数にする手順は、以下の通りです。初めの数を以下の形にします。 √X + M-------- N最初は、M=0、N=1になります。これを帯分数にします。 √X + M'a + --------- Nになります。真分数の部分を連分数にするために逆数にします。 1a + ----------- N --------- √X...
XのN乗を考えたとき、Xの桁数nがNと同じになるような、ものはいくつあるかという問題。最初、なんのことかよくわからなかった。1の場合は、 1^1 =1、1^2=1、1^3=1 .... となって1^1だけ。2の場合は、 2^1 =1、 2^2=4 、 2^3=8 ... となってこれも2^1だけ。おやー。 で、昼休みが終り。次の日、あっと思って、基数を動かして書いてみた。1^1=1、2^1=1、3^1=3、.... 9^1=9、10^1=10 ... となって、1から9。1^2=2、2^2=4、3^2=9、4^2=16、5^2=25、.... 9^2=81、10^2=100 ... となって、4から9。考えてみれば、Xが10のとき、10^nは、かならずn+1桁になってしまうので、Xは1桁の数でしかありえない。この先を手で計算してもできそうだったけど、プログラムにしてみた。...
同じ数字でできている5組の3乗数をみつける問題。これも全数アタックHashを使って分類する方法を採った。3乗数を作って、含まれている数をリストにしてソートしたものをキーにして、Hashに入れる。Hashに入れたときに、5つたまったらそれが答え。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
...
四桁の3～8角数を任意の順に並べて輪を作る問題。全くいい方法を思いつかなかったので全数アタック。・ 4桁のX角数を全部リストアップしておく。・ 3～8の数の順列を全部リストアップしておく。・ 順列すべてについて、あてはまるものがあるかどうかを探す。・ 途中でみつかっても中断せず、すべて探すだいぶ長くなってしまった。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor...
どの2つを取ってつないでも素数になる5つの素数の組をさがす問題解くのにすごく手間どった。なにしろ計算が終らない。ロジックに問題があるのだとばかり思っていたら、そうではなくて、素数判定の考慮漏れだったという情無い落ち。といっても、解くのに15分以上かかってしまっているので、情無いのには変りない。全数アタック以外の方法を思いつかないし、出た答えを見ても、うまい枝刈りの方法も思いつかないので、現状ではこれがほぼベスト。8けた以上の数の素数判定が早くなれば、かなり減りそうだけれど、1分にはほど遠い感じ。方法はこんな感じ。素数の列を作る。2と5は題意から除外する。3 7 9 11 13 17 ......1こずつ取ってきて、組をつくる。そのときこういうことをする。a 自分だけの組b もともとあった組c もともとあった組すべてに自分を加えた組できたものを、要素の数の多い順に並べる。初めは(3)。...
勢いに乗って、予選の問題Cを解いた。今やらないと、しばらくできないような気がしたので。この問題、当日は時間が無くて手をつけられなくて、終了後に全数アタックで実装してSmallだけ解いた。でも、そのやりかただと例題の最後のやつ1つも解けないわけで、全面みなおし。かかった時間は、70msec弱。 上々かな。何個か手で解いてみて、数字を並べて眺めていて思った。もとの数から直接解答の数を作れないかな。これでほぼできたに等しい。虫食い算を解くようなもの。下の桁から繰り上がりとかを考えなから条件を詰めていって埋めていく。情報が少ないので、aとbを決定することはできないけれど、1のビットの合計を求めるのに支障はない。考えかた- Nのある桁が1だったときと0だったときのaとbの対応する桁がどうなるべきか、下の位からの繰り上がりの有無を加味して考える。表にしてみる繰り上がり N:0...
Clojure Programmingを予約してあったんだけど、発売日また延期されちゃって、どうやら年内には手に入りそうもない。そもそも、最初に買ったプログラミングClojureはいい本なのだけれども、対応バージョンが古いのと、もうちょっと真髄みないなものに触れたいと思って、すでに発売中のThe Joy of Clojureと比べて、表紙の絵と新しさでClojure Programmingを選択していたわけだけれども、もう待てません。予約をキャンセルして、The Joy of Clojureを買っちゃいました。届きました。うーん。やっぱりこの表紙は怪しい。まだ、本文は1ページも読んでない。LOLを返したら読みはじめます。評価が高い本なので、期待してます。Clojure Programmingは、来年になって、評価がよかったら買います。1.3のことが...
Code Jam Japan予選のB問題。 ふと思い出したときにちょこっと考えていたりしたんだけど、やりかた思いついたので、やってみた。 解けた。もうちょっと効率を上げたりできそうだけど、500msちょっとで解けたんだからまあこれでいいでしょう。予選当日に考えた方式は以下の通り。結果としてこの方式で解いた。戦略- 今日何を飲むかではなくて、このコーヒーはいつ飲むのかを考える。- 満足度の高いコーヒーから飲む日を決めていく。- 飲む日はどうやって決めるのか？たとえば - 期間が5日 - 満足度(S)10 賞味期限(T)が3日のコーヒーAが2杯(C) -...
先週の週末、娘が図書館で本を借りたいというので、ついていきました。家から数分のところにある南部図書館という小さな出張所なので、品揃えは貧弱です。これまでも、買い物帰りにぶらっと寄ったことはあったのですが、雑誌を読むくらいのことしかしてなかったのですが、一回りしてみることにしました。コンピューター関連書籍の棚を見てみると、お約束のWordやExelの本に混って、「Let Over Lambda」が置いてあるじゃありませんか。 ちょっとびっくり。借りちゃいました。今、仕事の行き帰りに読んでいいて、1/3くらいまで来ました。情報によれば、後半に山場があるそうなので、まだ、感想を言うのは早いのでしょうが、「マクロはこう使え」っていう本ですね。僕にはやっぱりマクロは難しいし、今一つピンとこない。よくある手法などを定型で効率よく扱えるようにできるのはとても便利です。そして、ライブラリとしてくくり出すよりも、はるかに自由度が高いのはよくわかります。新しい考えかたなんかむうまく実現できるし、さらに、DSLという概念を頭に入れてとりかかると方向性を見失わずに済む。でも、ちょっと、Common...
