c21coterie @ ウィキ

c21coterie @ ウィキ内検索 / 「プロジェクトオイラー問３０」で検索した結果

• プロジェクトオイラーを楽しむページIndex
  ...ー問２９ プロジェクトオイラー問３０ プロジェクトオイラー問３１ プロジェクトオイラー問３２ プロジェクトオイラー問３３ プロジェクトオイラー問３４ プロジェクトオイラー問３５ プロジェクトオイラー問３６ プロジェクトオイラー問３７ プロジェクトオイラー問３８ プロジェクトオイラー問３９ プロジェクトオイラー問４０ プロジェクトオイラー問４１ プロジェクトオイラー問４２ プロジェクトオイラー問４３ プロジェクトオイラー問４４この問題は完全にカンニングして解いた プロジェクトオイラー問４５ プロジェクトオイラー問４６ プロジェクトオイラー問４７ プロジェクトオイラー問４８ プロジェクトオイラー問４９ プロ...
• プロジェクトオイラー関係
  プロジェクトオイラー問い1～10 プロジェクトオイラー問い11～20 プロジェクトオイラー問い21～30 プロジェクトオイラー問い31～40 プロジェクトオイラー問い41～50 プロジェクトオイラー問い51～60 プロジェクトオイラー問い61～70 プロジェクトオイラー問い71～80 プロジェクトオイラー問い81～90 プロジェクトオイラー問い91～100 プロジェクトオイラー問い101～110 プロジェクトオイラー問い111～120 プロジェクトオイラー問い121～130 雑記・日記2へ戻る。 掲載を後回しにしている問い 66,69,80
• プロジェクトオイラー解説index
  プロジェクトオイラー解説ページ ここではプロジェクトオイラーの問題を気が向いた問題から解説をしていきます。 最良の解説とはいきませんが基本的に大体１分ルール満たせるレベルの解説はのせていくつもりです。 解説満足度は、自分なりにどれだけ納得できる解説を行えたかと記述ミスをどれだけチェックしたかと記述の進捗率の３点の総合的な％表示したものです。 プロジェクトオイラー解説問1 解説満足度70％ プロジェクトオイラー解説問2 解説満足度80% プロジェクトオイラー解説問3 解説満足度70% プロジェクトオイラー解説問4 解説満足度70％ プロジェクトオイラー解説問5 解説満足度75％ プロジェクトオイラー解説問6　解説満足度60％ プロジェクトオイラー解説問7　解説満足度70％ プロジェクトオイラー解説問8　解説満足度70％ ...
• プロジェクトオイラー問１２０
  Problem 120 「自乗で割った余り」 † (a-1)＾n+(a+1)＾n を a＾2 で割った余りを r と定義する. 例えば, a=7, n=3 の時, r=42 である 6＾3 + 8＾3 = 728 ≡ 42 mod 49. n が変われば r も変わるが, a=7 の時 r の最大値 rmax は 42 であることがわかる. 3 ≤ a ≤ 1000 において, Σ rmax を求めよ. 解法 ｎ乗を展開してa^2で割ると残るのはnが奇数なら末尾のan+1とan-1 偶数なら1+1だけです。 奇数の時だけ考えて an+1とan-1を足すと２anとなります ｎは奇数なのでｎが増加すると 2a,6a,10a,,,と増加します。 a^2-2を4で割った余りが1か３なら2anはa(a-1)を作れます。 そうでないなら2anはa(a-2)...
• プロジェクトオイラー問３０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2030 Problem 30 「各桁の5乗」 † 驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない. 1634 = 1^4 + 6^4 + 3^4 + 4^4 8208 = 8^4 + 2^4 + 0^4 + 8^4 9474 = 9^4 + 4^4 + 7^4 + 4^4 ただし, 1=14は含まないものとする. この数たちの和は 1634 + 8208 + 9474 = 19316 である. 各桁を5乗した数の和が元の数と一致するような数の総和を求めよ. 解法 9^5*7 1000000以下なので7桁以上は検討する必要がありません。 0～9までを含んだ数を重複なく反辞書順に６個...
• プロジェクトオイラー問６２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2062 Problem 62 「立方数置換」 † 立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である. 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. 解法 ３乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。 例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。 最初に5個Hitした辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• プロジェクトオイラー解説問8
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. データが多いので問題の詳細はリンク先を読んでください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 解法 おそらくファイル読み込みの演習だと思います。 文字列やファイル読み込みは言語によって雑多な違いがあり統一的な話はできません。 まず1000文字の数字列をテキストファイルに保存し、このファイルの中身を文字列型に読み込んでいきます。 まず1000文字の数字を文字列として一行ずつ読み込み、 読み込んだ行strとしてstrAll+=strのように読み込み1000文字の文字列とします。 ...
• prolog勉強プロジェクトオイラー321～330
  プロジェクトオイラーの問題を堀江伸一さんがProlog言語で解くページ。 Problem 321 「カウンタの交換」 † チェッカーの駒を入れ替えるパズルを題材にとった数学の問題。 問題の詳細はリンク先参照のこと。 http //odz.sakura.ne.jp/projecteuler/index.php?Problem%20321 解放　只今考え中。 30分ほど紙の上で色々試行錯誤した結果。 最小入れ替え回数はたぶん青のチェッカーの枚数をｎ枚として。 n^2+2nで最小入れ替え回数が与えられこれが三角数なので適当な自然数ｍをとって。 n^2+2n=m*(m+1)/2 を満たす自然数ｎ、ｍの組となる。 整理すると 7/4=2(n+1)^2-(m+1/2)^2 という2次曲線上の整数解の組を小さいものから求めよという問題となる。 パズルに見せかけて実態...
• プロジェクトオイラー問２６
  http //projecteuler.net/problem=26 Problem 26 「逆数の循環節 その1」 † 単位分数とは分子が1の分数である. 分母が2から10の単位分数を10進数で表記すると次のようになる. 1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1 0.1(6)は 0.166666... という数字であり, 1桁の循環節を持つ. 1/7 の循環節は6桁ある. d 1000 なる 1/d の中で小数部の循環節が最も長くなるような d を求めよ. 解法 オイラーのファイ関数によれば 1/pが循環するということはフェルマーの小定理によれば必ず...
• prolog勉強プロジェクトオイラー111～120
  プロジェクトオイラーという数学問題の掲載されたサイトの問題を堀江伸一さんがPrologで解くページ。 Prolog言語の特徴。 配列はない、ｓｔｄコンテナにあたるものはもちろんない。 何があるかっていうとリストしかない。 凄く不便。 しかも破壊的代入がない、そのため動的計画法と物凄く相性が悪い、破壊的代入を前提としたデータ構造とも相性が悪いというか現実的な計算量で実装できない物が多数。 基本ローカル変数しかないから変数が増える問題では関数（Prologでは厳密に述語といい関数とわけて考える）の引数が凄いことになる。 引数を減らすと、解集合を巨大なリストで得てそこから一番いい解を探すような富豪プログラムになる。 利点はバックトラックがあるくらい、このバックトラックという機能は論理的処理には向いており、このためマサチューセッツ工科大学でも論理枠でPrologの講義が一応行われて...
• プロジェクトオイラー問６９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2069 Problem 69 「トーティエント関数の最大値」 † オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は, n と互いに素な n 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6. n互いに素な数φ(n)n/φ(n) 2112 31,221.5 41,322 51,2,3,441.25 61,523 71,2,3,4,5,661.1666... 81,3,5,742 91,2,4,5,7,861.5 101,3,7,942.5 n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる. n ≤ 1,0...
• プロジェクトオイラー問７２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2072 Problem 72 「分数の数え上げ」 † nとdを正の整数として, 分数 n/d を考えよう. n d かつ HCF(n,d)=1 のとき, 真既約分数と呼ぶ. d ≤ 8について真既約分数を大きさ順に並べると, 以下を得る 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 この集合は21個の要素をもつことが分かる. d ≤ 1,000,000について, 真既約分数の集合は何個の要素を持つか? 解法 オイラーのファイ関数をエラトステネスの...
• プロジェクトオイラー問３
  Problem 3 「最大の素因数」 † 13195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 1ずつ増やしながらためし割りしていけば素数のときだけ割ることができます。 コードではたとえばｐで割れたらdiv述語でｐで割れるだけ割ってから次に進みます。 数字Nの素因数はN=p1^a1*p2^a^*,,,*pn^anですが、ｐiで割り切れば、piはｎから完全に消えます。 それ以外の素因数は消えません。 なので小さいほうから試しても素数以外で割ることがないということになります。 Prologは導出木と等価ですが、その分杓子定規な記述になります。 実際今回のコードを教科書的に記述してみましたがコードが膨らんでいますね。 Prologでは細部でコードを短くするのではなく、賢い導出木と...
• プロジェクトオイラー問２７
  Problem 27 「二次式素数」 † オイラーは以下の二次式を考案している n＾2 + n + 41. この式は, n を0から39までの連続する整数としたときに40個の素数を生成する. しかし, n = 40 のとき 40＾2 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる. また, n = 41 のときは 41＾2 + 41 + 41 であり明らかに41で割り切れる. 計算機を用いて, 二次式 n＾2 - 79n + 1601 という式が発見できた. これは n = 0 から 79 の連続する整数で80個の素数を生成する. 係数の積は, -79 × 1601 で -126479である. さて, |a| 1000, |b| 1000 として以下の二次式を考える (ここで |a| は絶対値) 例えば |11| = ...
• プロジェクトオイラー問１２９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20129 Problem 129 「レピュニットの非整除性」 † 1のみからなる数をレピュニットという. R(k) を長さ k のレピュニットとする. 例えば, R(6) = 111111 となる. GCD(n, 10) = 1 なる正の整数 n が与えられたとき, R(k) が n で割り切られるような k が常に存在することが示せる. A(n) をそのような k の最小のものとする. 例えば, A(7) = 6, A(41) = 5 となる. A(n) の値が10を超える最小の n は17である. A(n) の値が100万を超える最小の n を求めよ 解法 111、、、111を９倍すると999、、、999...
• プロジェクトオイラー問１３０
  Problem 130 「素数桁レピュニットと同じ性質を持つ合成数」 † 1からのみなる数をレピュニットと呼ぶ. R(k)で長さkのレピュニットを表す. 例えばR(6) = 111111である. GCD(n, 10) = 1 となる正整数 n について, 必ず正整数 k が存在し n が R(k) を割り切ることが証明できる. A(n) でそのような最小の k を表す. 例 A(7) = 6. A(41) = 5. 5より大きい素数 p について, A(p) が p - 1 を割り切ることが知られている. p = 41 のときには, A(41) = 5 であり, 40は5で割り切れる. 非常に少ないのだが, 合成数においても上が成立する場合がある. 最初の5つの例は 91, 259, 451, 481, 703 である. GCD(n, 10) = 1 か...
• prolog勉強プロジェクトオイラー121～130
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ どうでもいい雑記。 今日宮沢賢治のやまなし　という作品を読んだ。 自然描写力が圧倒的、作画が一流のアニメを見た後のような読後感があった。 コードはページの下のほうに掲載。 コードを見てもらう前に競技プログラムの世界の話を少し書いておきます。 競技プログラムとは数学の問題のようにプログラムの問題が出題されそれを解くことを競う競技で国際的な大会も常時開催されていたりします。 ふつうはN月M日の１６時に出題され１８時までに回答を出題したかたのみ採点のように制限時間付となりますが、過去問題や問題集だけを扱ったサイトもあります。 プロジェクトオイラーは問題集サイトになります。 ここで問題を解くプログラムの話をします。 プログラムの世界では書いたプログラムをコードと呼びます。 競技プログラムの...
• プロジェクトオイラー問３３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2033 Problem 33 「桁消去分数」 † 49/98は面白い分数である.「分子と分母からそれぞれ9を取り除くと, 49/98 = 4/8 となり, 簡単な形にすることができる」と経験の浅い数学者が誤って思い込んでしまうかもしれないからである. (方法は正しくないが，49/98の場合にはたまたま正しい約分になってしまう．) 我々は 30/50 = 3/5 のようなタイプは自明な例だとする. このような分数のうち, 1より小さく分子・分母がともに2桁の数になるような自明でないものは, 4個ある. その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ. 解法 ルールが恣意的だということはその...
• プロジェクトオイラー問３６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2036 Problem 36 「二種類の基数による回文数」 † 585 = 10010010012 (2進) は10進でも2進でも回文数である. 100万未満で10進でも2進でも回文数になるような数の総和を求めよ. (注 先頭に0を含めて回文にすることは許されない.) 解法 １０進数の回文数だけをpermとtoNumで作って、それが２ビットでも回文数であるか調べるだけです。 計算量は999*2+99*2+9*2回。 perm([_]). perm([X,X]). perm([X,_,X]). perm([X,Y,Y,X]). perm([X,Y,_,Y,X]). perm([X,Y,Z,Z,Y,X]). ...
• プロジェクトオイラー問３７
  Problem 37 「切り詰め可能素数」 † 3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3). 右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ. 注 2, 3, 5, 7を切り詰め可能な素数とは考えない. 解法 切り詰め可能な素数は最後は必ず、2,3,5,7となります。 逆に考えると右を削るの逆操作を考えると、右に付け足すと考えても目的の数は手に入ります。 そして幸運なことに一桁目を素数から初めて永遠に右に付け足すことはできません。 ２桁以上が手に入ったら左を全て削れるか試して合格した数を答えとします。 ね、簡単でしょ？...
• プロジェクトオイラー問３１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2031 Problem 31 「硬貨の和」 † イギリスでは硬貨はポンド£とペンスpがあり，一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p). 以下の方法で£2を作ることが可能である． 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p これらの硬貨を使って£2を作る方法は何通りあるか? 解法 初めてこの問題にPrologで挑戦した時は破壊的代入も配列もstd mapもないPrologでどうやって動的計画法をするか悩みました。 基本がわかれば考え方は簡単。...
• プロジェクトオイラー問３４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2034 Problem 34 「桁の階乗」 † 145は面白い数である. 1! + 4! + 5! = 1 + 24 + 120 = 145となる. 各桁の数の階乗の和が自分自身と一致するような数の和を求めよ. 注 1! = 1 と 2! = 2 は総和に含めてはならない. 解法 7桁までの長さで一桁ずつ昇順で保持した重複のない数字のリストを作ります。 リストの要素をPermとします。 Permを各桁とみて階乗の和Numを計算します。 Numを各桁のリストに戻してソートしList1とします。 List1とPermが同じならその数Numは条件を満たす数です。 条件を満たす数は重複する数があるのでsor...
• プロジェクトオイラー問３５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2035 Problem 35 「巡回素数」 † 197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである. 100未満には巡回素数が13個ある 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および97である. 100万未満の巡回素数はいくつあるか? 解法 一桁はスペシャルケースとして扱う。 ２桁以降は数字に0,２,4,6,8は入らない。 5も当然入らない。 巡回素数に使える数は1,3,7,9だけとなる。 4＾6+4^5+4^3+4^2個の数字を検討するだけ、これなら木構造とか凝ったことをしても対して早くならな...
• プロジェクトオイラー問３８
  Problem 38 「パンデジタル倍数」 † 192 に 1, 2, 3 を掛けてみよう. 192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 積を連結することで1から9の パンデジタル数 192384576 が得られる. 192384576 を 192 と (1,2,3) の連結積と呼ぶ. 同じようにして, 9 を 1,2,3,4,5 と掛け連結することでパンデジタル数 918273645 が得られる. これは 9 と (1,2,3,4,5) との連結積である. 整数と (1,2,...,n) (n 1) との連結積として得られる9桁のパンデジタル数の中で最大のものはいくつか? 解法 まずは1を書けるのですから求める先頭数字は9であることを期待します。 xを何らかの一文字の数字とすると...
• プロジェクトオイラー問３２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2032 Problem 32 「パンデジタル積」 † すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう 例えば5桁の数 15234 は1から5のパンデジタルである. 7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる. 掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ. HINT いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ. 解法 a*b=cとすると a =...
• プロジェクトオイラー問３９
  Problem 39 「整数の直角三角形」 † 辺の長さが {a,b,c} と整数の3つ組である直角三角形を考え, その周囲の長さを p とする. p = 120のときには3つの解が存在する {20,48,52}, {24,45,51}, {30,40,50} p ≤ 1000 のとき解の数が最大になる p はいくつか? 解法 周長1000以下の原始ピタゴラス数とその定数倍のリストを得て出現回数をカウントするだけです。 gcd(0, B, B). gcd(A, B, G) - A 0, R is B mod A, gcd(R, A, G). calc_ok(M,N) - ((M-N) mod 2)= =1, gcd(M,N,G), G= =1 . calc(M,N,Result) - Result is M^2+N^2+2*M*N+M^2-N...
• prolog勉強プロジェクトオイラー1～10
  プロジェクトオイラーの問題を堀江伸一こと私がＰｒｏｌｏｇで解くページ。 プロジェクトオイラーの問題は問題番号が小さいものほど簡単で問題番号が大きいものは非常に難しくなります。 この辺は最初なので中学生プログラマでも挑戦できるレベルの問題が並ぶ。 Problem 1 「3と5の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 1000未満の３か５の倍数になっている自然数の合計を答えよ 解法 数式で解くのが正しいけれどサイトの趣旨、数学の問題をプログラムで特に合わせて末尾再帰で記述。 mod_n(N,N) - member(R,[3,5]), N mod R= =0, !. mod_n(_,0) -!. search(1000,Ans) -!,write...
• オイラープロジェクト321～330
  問い324 以下の問題があります。 3x3xn の塔を 2x1x1 のブロックで埋める場合の数を f(n) とする。 ブロックは好きな方向に回転することができる；しかし、塔自身を回転・反転等させたものは区別して数える。 たとえば（q=100000007 として）： f(2) = 229, f(4) = 117805, f(10) mod q = 96149360, f(10^3) mod q = 24806056, f(10^6) mod q = 30808124. f(10^10000) mod 100000007 を求めよ。 問題の原文サイトはこちら。 http //projecteuler.net/problem=324 プロジェクトオイラーというサイトで数学の問題をプログラムで解こうという練習問題を扱ったサイトです。 自分で考え出した...
• 雑記・日記2
  ここはこのサイトの管理人こと堀江伸一さんの個人的な雑記、日記　勉強記録を雑多に集めたページです。 当サイトの小学生レベルの創作物に関する言い訳 勉強記録一覧 リンク　→会津大学オンラインジャッジコード記録 会津大学オンラインジャッジの解答コードでこちらへ来た方はリンク先へどうぞ、私のコードが掲載されています。 一応少数の問題でコード実行速度一位を取ったコードもあるのですこしは参考になるかもしれません(ご近所さんのある方はＡＯＪでコード実行速度一位とるなんて馬鹿でもできる笑いもの　ぷぷぷ　とか言ってました。世間的なＡＯＪの評価ってそんなものかもしれません)。 会津大学オンラインジャッジ復習 ここより以下は本当に個人的な雑記ですので気にしないでください。 もしも結婚できたら子供に言ってみたいこと ネットで好みのイラスト収集 新ギレン...
• prolog勉強プロジェクトオイラー21～30
  プロジェクトオイラーの問題をPrologで解くページ。 創価学会の皆さまから小学校の算数までしかできないと言われている堀江伸一さんがこのページのコードを書いているようです。 Problem 21 「階乗の数字和」 † http //projecteuler.net/problem=21 10000以下の友愛数の和を求めよという問題。 そのまま定義通り計算するだけです。 複数の関数で一つの関数を表現するＰｒｏlogて独特。 yakusuu_sum(1,_,1,Sum,Sum) -!. yakusuu_sum(N,M,1,Sum,Sum1) -N M*M,!,Sum1 is Sum*(N+1). yakusuu_sum(N,M,Multi,Sum,Result) - 0= =N mod M,!, N1 is N//M, Multi1 is Multi*M+1, ya...
• プロジェクトオイラー問６
  Problem 6 「二乗和の差」 † 最初の10個の自然数について, その二乗の和は, 1^2 + 2^2 + ... + 10^2 = 385 最初の10個の自然数について, その和の二乗は, (1 + 2 + ... + 10)^2 = 3025 これらの数の差は 3025 - 385 = 2640 となる. 同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ. 解法 数学の公式を使えば一行で答えが出ますが。 せっかくプログラム言語があるのだし逐次的に求めてみましょう。 再帰で足す数Nを1ずつ足す数を増加させながら２乗の和と普通の和を足して、最後に普通の和を２乗してその差分をとれば答えです。 calc(Stop,Stop,Sum1,Sum2,Ans) -!, Ans is Sum1*Sum1-Sum2. calc(N,Sto...
• プロジェクトオイラー問２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%202 Problem 2 「偶数のフィボナッチ数」 † フィボナッチ数列の項は前の2つの項の和である. 最初の2項を 1, 2 とすれば, 最初の10項は以下の通りである. 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... 数列の項の値が400万以下の, 偶数値の項の総和を求めよ. 解法 漸化式を使った解法。 再帰で自然に記述できます。 賢い解法はこちらを参照のこと。 http //bach.istc.kobe-u.ac.jp/lect/ProLang/org/euler-002.html isAdd(N,0) -N mod 2= =1,!. isAdd(N,N) -!. ...
• プロジェクトオイラー問９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%209 Problem 9 「特別なピタゴラス数」 † ピタゴラス数(ピタゴラスの定理を満たす自然数)とは a b c で以下の式を満たす数の組である. a^2 + b^2 = c^2 例えば, 3^2 + 4^2 = 9 + 16 = 25 = 5^2 である. a + b + c = 1000 となるピタゴラスの三つ組が一つだけ存在する. これらの積 abc を計算しなさい. 解法 原始ピタゴラス数を求める公式はWikiにある通りです。 原始ピタゴラス数の三辺 a+b+cが1000の約数になればそれを1000/(a+b+c)倍した三角形が答えです。 C++ならｍとｎの２重ループとすると...
• プロジェクトオイラー問１
  Problem 1 「3と5の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%201 10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる. 同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ. 解法 条件を満たす数のリストを得てそれを集計する方法。 okNum(N) -N mod 3= =0,!. okNum(N) -N mod 5= =0,!. numListCreate(N) - between(1,999,N), okNum(N). sum([],0) -!. sum([X|Xs],Result) -sum(Xs,Re),Resul...
• prolog勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• オイラープロジェクトカンニング履歴
  会津大学オンラインジャッジの問題とおなじくカンニングして解いたオイラープロジェクトの問題のリスト。 数学の問題集を扱ったサイトなので調べものして数学の知識を身につけながら解くのが正道な気がするが、一応出来るだけ自力で解きたいところ。 なのでカンニングして解いた問題のリストを掲載。 問い12 問題を解く方法がよくわからず掲示板で質問。 コードまで書いてもらうもコードの読解や原理がよくわからず考え中。 問い25 フィナボッチ数が１０００桁になるのは数列の何個目か？ 単純に1000ケタを超えるまでフィナボッチ数列を計算して解こうと挑戦。 ほとんどコードを書いたことがないＬｉｓｐで解こうと考え、初心者レベルのコードを記述してみて実行時エラー。 掲示板でloop中の（が一つ多いでのでsetqのあたりが余分に関数と解釈されてると指摘を受けそれを修正してアセプト。 修...
• プロジェクトオイラー問４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%204 Problem 4 「最大の回文積」 † 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数の最大値を求めよ. 解法 まずは数字を一桁ごとのリストに変える述語toList。 リストが左右対称であるかをしらべる述語palindromeを書きます palindrome(List,[],List) -!. palindrome(List,[X|Rest],RevList) - palindrome(List,Rest,[X|RevList]). toList(0,[]) -!. toL...
• プロジェクトオイラー問７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%207 Problem 7 「10001番目の素数」 † 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10001 番目の素数を求めよ. 基本はsqrt(N)まで試し割って割り切れる数が見つかればその数は素数でない。 でなければ素数と判定します。 本当や１以下の取り扱いや２や素の倍数の判定が必要ですが、問題の性質から奇数だけを考えてコードをくみます。 not_prime(N) - between(1,N,N1), Div is N1*2+1, (Div*Div N- !,fail;true), N mod Div= =0, !. is_prime(N...
• プロジェクトオイラー問い51～60
  問い51 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2051 　*3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる. 　56**3の第3桁と第4桁を同じ数で置き換ることを考えよう. この5桁の数は7つの素数をもつ最初の例である 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である 　56003は, このような性質を持つ最小の素数である.　 　桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注 連続した桁でなくても良い) 解法 100万までの素数をvectorに格納し、各素数それぞれについて*文字にチェンジした全パタ...
• プロジェクトオイラー問８
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. 詳細はリンク先を参照してください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 まず１０００桁の数字を文字列リストとしてわたし、文字列リストを48引いて数字に戻します。 あとは文字列リストの先頭５桁の掛け算を試しながら大きいほうをTempAnsとして残して、先頭を一つずつ短くしながらsearchして、サイズ4になったら計算終了で値を返します。 max(A,B,A) -A B,!. max(_,B,B) -!. search([_,_,_,_],Ans,Ans) -!. search([A,B,C...
• プロジェクトオイラー問５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%205 Problem 5 「最小の倍数」 † 2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である. では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか. 解法 機械的に考えるならlcm(1,2,3,,,,20)ですのでそのまま実装します。 手計算で考えると 1,2,3、、、で割れる数と考えていくと。 1で最初その数は１． 2でその数は２． 3でそのかずは３． 4でその数は２＾２で割れるのだから、２が二つ、３が一つ素因数として必要、だから4*3＝12. 5でその数は2＾２　３　5で割れないとダメだから2＾2*3*5....
• プロジェクトオイラー問１９
  http //projecteuler.net/problem=19 Problem 19 「日曜日の数え上げ」 † 次の情報が与えられている. 1900年1月1日は月曜日である. 9月, 4月, 6月, 11月は30日まであり, 2月を除く他の月は31日まである. 2月は28日まであるが, うるう年のときは29日である. うるう年は西暦が4で割り切れる年に起こる. しかし, 西暦が400で割り切れず100で割り切れる年はうるう年でない. 20世紀（1901年1月1日から2000年12月31日）中に月の初めが日曜日になるのは何回あるか? 解法 問題のほうで日数計算に必要なデータが提示されているので、出題の意図を読んでそれをつかって計算するのが正しいと思いますが。 ツェラーの公式で手抜きしました。 zellers(Y,M,D,Result) - (M 3 ...
• プロジェクトオイラー問４４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2044 Problem 44 「五角数」 † 五角数は Pn = n(3n-1)/2 で生成される. 最初の10項は 1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ... である. P4 + P7 = 22 + 70 = 92 = P8 である. しかし差 70 - 22 = 48 は五角数ではない. 五角数のペア Pj と Pk について, 差と和が五角数になるものを考える. 差を D = |Pk - Pj| と書く. 差 D の最小値を求めよ. 解法 http //d.hatena.ne.jp/inamori/20100214/p2 三平方の定理と結びつける解...
• プロジェクトオイラー問１０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2010 Problem 10 「素数の和」 † 10以下の素数の和は 2 + 3 + 5 + 7 = 17 である. 200万以下の全ての素数の和を求めよ. 解法 小さい数から試します、N=2は既知として与え、３以上の数Nが素数ならそれを足す処理とします。 素数判定はsqrt(N)までのためし割りでは速度が出ません。 それまで得られた1500以下の数の素数リストで試し割ることで少しだけ速度をあげます。 素数リストを作るときappendを使っています。 appendは効率が悪いという話がありますが、1500以下の素数リスト程度の長さなら気にするほどではないでしょう。 not_prime(N,Primes) - mem...
• プロジェクトオイラー問１６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2016 Problem 16 「累乗の各桁の和」 † 2＾15 = 32768 であり, これの各桁の和は 3 + 2 + 7 + 6 + 8 = 26 となる. 同様にして, 2＾1000 の各桁の和を求めよ. 解法 ２＾1000を計算して各桁の和をとるだけです。 何か賢い方法はあるのでしょうか？ calc(0,0) -!. calc(X,Result) - Add is X mod 10, X1 is X//10, calc(X1,Re), Result is Re+Add. main16 - X is 2^1000, calc(X,Ans), write(Ans).
• プロジェクトオイラー問５３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2053 Problem 53 「組み合わせ選択」 † 12345から3つ選ぶ選び方は10通りである. 123, 124, 125, 134, 135, 145, 234, 235, 245, 345. 組み合わせでは, 以下の記法を用いてこのことを表す 5C3 = 10. 一般に, r ≤ n について nCr = n!/(r!(n-r)!) である. ここで, n! = n×(n−1)×...×3×2×1, 0! = 1 と階乗を定義する. n = 23 になるまで, これらの値が100万を超えることはない 23C10 = 1144066. 1 ≤ n ≤ 100 について, 100万を超える nCr は...
• プロジェクトオイラー問９９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2099 Problem 99 「最大のべき乗」 † 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 電卓を使えば, 2^11 = 2048 3^7 = 2187 であることが確かめられる. しかし, 632382^518061 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる). 各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ. 注 ファイル中の最初の二行は上の例である. 解法 Ｌｏｇを使っても十分答えが出るよう...
• プロジェクトオイラー問１１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2011 Problem 11 「格子内の最大の積」 † 20×20 の格子のうち連続した４数の積が最大になる部分を探す問題。 詳しくはリンク先を参照のこと。 解法 この問題は配列のない言語ではちょっとした難問です。 擬似的な配列としてリストのリストとしてnth0を２回適用してアクセスするのが一番楽です。 処理に失敗した部分はなかったことになるPrologの特性を利用して全部の地点で縦横斜めを検証し全ての4マス掛け算のリストを得その中で最大のものを答えとします。 もしも問題が10万行*１０万列になった場合でも動く処理を書くとしたら、４行単位で一行ずつずらしながら処理してその４行で計算できる最大値と今まで見つかった最大...
• プロジェクトオイラー問５２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2052 Problem 52 「置換倍数」 † 125874を2倍すると251748となる. これは元の数125874と順番は違うが同じ数を含む. 2x, 3x, 4x, 5x, 6x が x と同じ数を含むような最小の正整数 x を求めよ. 解法 有名問題。 1/7＝0.142857 答えは142857 ２番目に小さな数は何だろうか？
• プロジェクトオイラー問８６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2086 Problem 86 「直方体のルート」 † 下に示す直方体は寸法が6×5×3である. この直方体の1つの頂点Sにクモがいる. また反対の頂点Fにはハエがいる. SからFまでの壁に沿って直線移動する最短ルートは図に示す通りで, この長さは10である. 図略 この最短ルートの候補は3本あるが, 最短のものがいつも整数長さとは限らない. さて, M×M×M以下の寸法の直方体について, 最短ルートが整数である直方体の数を考える. M=100のとき, 条件を満たす直方体は2060個ある. このM=100は個数が2000を超える最小のMである. なお, M=99のときは1975個である. 100万個を超える最小...
• @wiki全体から「プロジェクトオイラー問３０」で調べる

更新順にページ一覧表示 | 作成順にページ一覧表示 | ページ名順にページ一覧表示 | wiki内検索