Project Euler 240 {1,...,i}からn個をとった上位t個の和がsになる出方の個数をf(i,n,t,s)とする. f(12,20,10,70)の値を求めたい.まず{1}からn個とったうち上位t個の和がtになる出方は1通り, 和がそれ以外になるのは0通り.{1,...,i}からn個をとった上位t個の…

Project Euler 151 A1の紙がa1枚, A2の紙がa2枚, ..., A5の紙がa5枚あるときから始めて, 封筒に紙が1枚だけ入っている回数の期待値を として漸化式を立てて, を求める. 例えば紙の枚数がの日にA3の紙を手にとったら, 次の日の紙の枚数はになる. Project Eule…

包除原理の例題みたいな問題。先頭から続く0は無視することだけ注意すればよい。n桁の16進数xの個数は15*16^n個 f(prop) = 条件propを満たすn桁の16進数の個数 とするとf(0を含む & 1を含む & Aを含む) = 15*16^n - f(0を含まない | 1を含まない | Aを含まな…

MathWorldに載っているけれど確かめてみた http://ideone.com/WayQn結果だけ 正四面体 // Hamiltonian Path: 6本 // Cycle: 6本 // Tetrahedral graph */正六面体 // Hamiltonian Path: 18本 // Cycle: 12本 // Cubical graph */正八面体 // Hamiltonian Pat…

3つの八百屋から値段の異なるリンゴをいくつか仕入れた。 これを5つの袋に決められた個数ずつ振り分ける。 袋ごとの平均単価が同じくらいになるように振り分ける方法を見つけたい。元ネタはここ要するに画像の5x3の表を埋めつつ目的関数を最小化したい ただ…

Yahoo知恵袋で携帯のメールアドレスとして可能な種類はいくつ？ という質問があったので, 考えてみるWikipedia:メールアドレス メールアドレスは、次の構文を持つ。 ローカル部@ドメイン（例：foo@example.com） ドメインはdocomo.co.jp, ezweb.ne.jp, softb…

137は,問題の式を変形して, xについてまとめて,判別式を見る. 結局,フェルマー・ペル方程式 を解けばいい.114は少し不思議. $cnt=0 def f(m,n,last) if n == 0 $cnt+=1 elsif last == 0 f(n-1,0) m.upto(n){|k| f(n-k,k) } else f(m,n-1,0) end endとして泥…

"いくつかの"正整数kにたいして, 4^t,2^t,kが正整数で4^t = 2^t +kを満たすtが存在する.P(m)をk たとえば, 4^1 = 2^1 + 2 4^log2(3) = 9 = 3 + 6 = 2^log2(3) + 6 (2^a = c <=> log2(c) = a)より, P(5) = #{(k,t)=(2,1)}/#{(2,1)} = 1/1 P(6) = #{(k,t)=(2,1…

点O(0,0), P(x1,y1), Q(x2,y2) でつくられる三角形OPQのうち, 直角三角形の数を求める.ただし, x1,y1,x2,y2は整数で, 0 (x,y)を2桁の51進数と考えると, (x,y) = {(0,0),(0,1),...,(50,50)} -> { 0, 1, 2,...,2600 }のようにして整数と一対一対応がつけられる…

整数n に対して,1/x + 1/y = 1/nを満たす整数x,yの組を考える.1/2 + 1/3 = 1/3 + 1/2 のように, x,yを入れ替えたものも1つと数えるとすると,例えばn=4では, 1/x + 1/y = 1/4 = 1/5 + 1/20 = 1/6 + 1/12 = 1/8 + 1/8の3通りの組み合わせがある.で, [x,y]の組…

40 x 40のマスを左から右端まで行くときの最小コストを求める, 最短経路を求める問題の一種. ただし, マスは左から右か上下にしか移動できない.答えの確認はまだなので, 考えた手順のメモだけ.右から左に進めればよいから,縦の列ごとに最短経路を求めて行け…

巨大な素数 28433 * 2^7830457 + 1 の下10桁を求める問題.つまり, (28433 * 2^7830457 + 1) % 10^10 が知りたい.Wikipediaのべき剰余 を写経. # ruby 1.6.8 def modpow(b,e,m) result = 1 while(e > 0) result = (result * b) % m if((e & 1) == 1) e >>= 1 …

Euler 4 3桁の2数の積で上から読んでも下から読んでも同じ数を求める.回文の判断は(equal? n (reverse n)), あとは2重ループを再帰で書き直しただけ. (define (palindrome? string) ((lambda (l) (equal? l (reverse l))) (string->list string))) (define (…

帰省中はErlangを触れないのでScheme (Gauche)で解いてみる.1-100までの二乗和と和の二乗との差を求める. 再びAccumulatorに働いてもらう. (define (acc c v l) (if (null? l) v (c (car l) (acc c v (cdr l))))) (define (sum-of-sq l) (acc (lambda (x y) …

Euler Projectという数学やらプログラミングの問題サイトがあったので, Erlangの練習も兼ねて始めてみる. 1. 1000未満の自然数で, 3か5の倍数の数字を全て足した数を答える. ちょうどよいのでAccumulatorを使ってみた. -module(euler1). -export([acc/3, ran…

アドレスを連想して隠されたページを見付けだすゲーム.スタートは 1.html から.始めはとても簡単だけれど, 後半になるにつれて発想だけでなく知識・検索力を求められる問題が増えるので, 各ページの問題とメモを残す. 1 two iii ruof ffiivvee 666666 uranus…