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 //projecteuler.net/problem=25 Problem 25 「1000桁のフィボナッチ数」 † フィボナッチ数列は以下の漸化式で定義される Fn = Fn-1 + Fn-2, ただし F1 = 1, F2 = 1. 最初の12項は以下である. F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 F10 = 55 F11 = 89 F12 = 144 12番目の項, F12が3桁になる最初の項である. 1000桁になる最初の項の番号を答えよ. 解法 フィナボッチ数列の近似式と対数計算から求めます。 式から求めるのは少しめんどくさいですね。 fina(N,Result) - Result is ...
• プロジェクトオイラー問６２
  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した辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• プロジェクトオイラー問２６
  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が循環するということはフェルマーの小定理によれば必ず...
• プロジェクトオイラー解説問8
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. データが多いので問題の詳細はリンク先を読んでください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 解法 おそらくファイル読み込みの演習だと思います。 文字列やファイル読み込みは言語によって雑多な違いがあり統一的な話はできません。 まず1000文字の数字列をテキストファイルに保存し、このファイルの中身を文字列型に読み込んでいきます。 まず1000文字の数字を文字列として一行ずつ読み込み、 読み込んだ行strとしてstrAll+=strのように読み込み1000文字の文字列とします。 ...
• プロジェクトオイラー問２７
  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| = ...
• 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 //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...
• prolog勉強プロジェクトオイラー111～120
  プロジェクトオイラーという数学問題の掲載されたサイトの問題を堀江伸一さんがPrologで解くページ。 Prolog言語の特徴。 配列はない、ｓｔｄコンテナにあたるものはもちろんない。 何があるかっていうとリストしかない。 凄く不便。 しかも破壊的代入がない、そのため動的計画法と物凄く相性が悪い、破壊的代入を前提としたデータ構造とも相性が悪いというか現実的な計算量で実装できない物が多数。 基本ローカル変数しかないから変数が増える問題では関数（Prologでは厳密に述語といい関数とわけて考える）の引数が凄いことになる。 引数を減らすと、解集合を巨大なリストで得てそこから一番いい解を探すような富豪プログラムになる。 利点はバックトラックがあるくらい、このバックトラックという機能は論理的処理には向いており、このためマサチューセッツ工科大学でも論理枠でPrologの講義が一応行われて...
• プロジェクトオイラー問７２
  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について, 真既約分数の集合は何個の要素を持つか? 解法 オイラーのファイ関数をエラトステネスの...
• プロジェクトオイラー問２
  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%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...
• プロジェクトオイラー問２９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2029 Problem 29 「個別のべき乗」 † a^bで 2 =a,b =100を考えるとき重複を排除すると何通りの数が作れるか？ 解法 とりあえずプルートゥーズな方法で実装してみました。 全部求めて重複削除、それだけです。 calc(C) - between(2,100,A), between(2,100,B), C is A^B. main29 - findall(PowAB,calc(PowAB),PowABs), list_to_set(PowABs,PowABs1), length(PowABs1,Ans), write(Ans).
• prolog勉強プロジェクトオイラー121～130
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ どうでもいい雑記。 今日宮沢賢治のやまなし　という作品を読んだ。 自然描写力が圧倒的、作画が一流のアニメを見た後のような読後感があった。 コードはページの下のほうに掲載。 コードを見てもらう前に競技プログラムの世界の話を少し書いておきます。 競技プログラムとは数学の問題のようにプログラムの問題が出題されそれを解くことを競う競技で国際的な大会も常時開催されていたりします。 ふつうはN月M日の１６時に出題され１８時までに回答を出題したかたのみ採点のように制限時間付となりますが、過去問題や問題集だけを扱ったサイトもあります。 プロジェクトオイラーは問題集サイトになります。 ここで問題を解くプログラムの話をします。 プログラムの世界では書いたプログラムをコードと呼びます。 競技プログラムの...
• プロジェクトオイラー問２８
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2028 Problem 28 「螺旋状に並んだ数の対角線」 † 1から初めて右方向に進み時計回りに数字を増やしていき, 5×5の螺旋が以下のように生成される 2122232425 2078910 1961211 1854312 1716151413 両対角線上の数字の合計は101であることが確かめられる. 1001×1001の螺旋を同じ方法で生成したとき, 対角線上の数字の和はいくつか? 解法 ４つ角単位で計算します。 最初の１はスペシャルケース。 そのあとは右下角を基準に、左下角＝右下+枠のサイズ-1、左上角＝右下+(枠のサイズ-1)*2　右上角=右下+(枠のサイズ-1)*3 となります。 右下角の...
• 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...
• プロジェクトオイラー問２０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2020 Problem 20 「階乗の数字和」 † n × (n - 1) × ... × 3 × 2 × 1 を n! と表す. 例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる. この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である. では, 100! の各桁の数字の和を求めよ. 解法 そのまま階乗を計算して、各桁の和をketaSumで取り出す。 何も工夫してません。 fact(0,1) -!. fact(N,Result) - N1 is N-1, fact(N1,Re), Result is Re*N....
• プロジェクトオイラー問２１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2021 Problem 21 「友愛数」 † d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. ) もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという. 例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である. また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である. それでは10000未満の友愛数の和を求めよ. 解法 原理主義的に約数の集合を得てそれ...
• プロジェクトオイラー問２２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2022 Problem 22 「名前のスコア」 † 5000個以上の名前が書かれている46Kのテキストファイルを用いる. まずアルファベット順にソートせよ. のち, 各名前についてアルファベットに値を割り振り, リスト中の出現順の数と掛け合わせることで, 名前のスコアを計算する. たとえば, リストがアルファベット順にソートされているとすると, COLINはリストの938番目にある. またCOLINは 3 + 15 + 12 + 9 + 14 = 53 という値を持つ. よってCOLINは 938 × 53 = 49714 というスコアを持つ. ファイル中の全名前のスコアの合計を求めよ. （詳細はリンク先を参照のこと） ...
• プロジェクトオイラー問２３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2023 Problem 23 「非過剰数和」 † 完全数とは, その数の真の約数の和がそれ自身と一致する数のことである. たとえば, 28の真の約数の和は, 1 + 2 + 4 + 7 + 14 = 28 であるので, 28は完全数である. 真の約数の和がその数よりも少ないものを不足数といい, 真の約数の和がその数よりも大きいものを過剰数と呼ぶ. 12は, 1 + 2 + 3 + 4 + 6 = 16 となるので, 最小の過剰数である. よって2つの過剰数の和で書ける最少の数は24である. 数学的な解析により, 28123より大きい任意の整数は2つの過剰数の和で書けることが知られている. 2つの過剰数の和で表せない最大の数がこの上...
• プロジェクトオイラー問２４
  問24 Problem 24 「辞書式順列」 † 順列とはモノの順番付きの並びのことである. たとえば, 3124は数 1, 2, 3, 4 の一つの順列である. すべての順列を数の大小でまたは辞書式に並べたものを辞書順と呼ぶ. 0と1と2の順列を辞書順に並べると 012 021 102 120 201 210 になる. 0,1,2,3,4,5,6,7,8,9からなる順列を辞書式に並べたときの100万番目はいくつか? 解法 計算しやすいように0123456789　を０番目の数として計算します。 最初の一桁目は 0から始まる数が9！通り 1から始まる数が2*9！通り 2から始まる数が3*9！通り 3だと１００万を超えるので一桁目は２． 残りも同様の方法で決まる。 fact(0,1) -!. fact(N,Result) -N1 is N-...
• オイラープロジェクト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 プロジェクトオイラーというサイトで数学の問題をプログラムで解こうという練習問題を扱ったサイトです。 自分で考え出した...
• プロジェクトオイラー問１３０
  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 か...
• 雑記・日記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%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...
• プロジェクトオイラー問７４
  http //projecteuler.net/problem=74 Problem 74 「桁の階乗による連鎖」 † 145は各桁の階乗の和が145と自分自身に一致することで有名である. 1! + 4! + 5! = 1 + 24 + 120 = 145 169の性質はあまり知られていない. これは169に戻る数の中で最長の列を成す. このように他の数を経て自分自身に戻るループは3つしか存在しない. 169 → 363601 → 1454 → 169 871 → 45361 → 871 872 → 45362 → 872 どのような数からスタートしてもループに入ることが示せる. 例を見てみよう. 69 → 363600 → 1454 → 169 → 363601 (→ 1454) 78 → 45360 → 871 → 4536...
• オイラープロジェクトカンニング履歴
  会津大学オンラインジャッジの問題とおなじくカンニングして解いたオイラープロジェクトの問題のリスト。 数学の問題集を扱ったサイトなので調べものして数学の知識を身につけながら解くのが正道な気がするが、一応出来るだけ自力で解きたいところ。 なのでカンニングして解いた問題のリストを掲載。 問い12 問題を解く方法がよくわからず掲示板で質問。 コードまで書いてもらうもコードの読解や原理がよくわからず考え中。 問い25 フィナボッチ数が１０００桁になるのは数列の何個目か？ 単純に1000ケタを超えるまでフィナボッチ数列を計算して解こうと挑戦。 ほとんどコードを書いたことがないＬｉｓｐで解こうと考え、初心者レベルのコードを記述してみて実行時エラー。 掲示板でloop中の（が一つ多いでのでsetqのあたりが余分に関数と解釈されてると指摘を受けそれを修正してアセプト。 修...
• prolog勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• プロジェクトオイラー問４
  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...
• プロジェクトオイラー問３
  Problem 3 「最大の素因数」 † 13195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 1ずつ増やしながらためし割りしていけば素数のときだけ割ることができます。 コードではたとえばｐで割れたらdiv述語でｐで割れるだけ割ってから次に進みます。 数字Nの素因数はN=p1^a1*p2^a^*,,,*pn^anですが、ｐiで割り切れば、piはｎから完全に消えます。 それ以外の素因数は消えません。 なので小さいほうから試しても素数以外で割ることがないということになります。 Prologは導出木と等価ですが、その分杓子定規な記述になります。 実際今回のコードを教科書的に記述してみましたがコードが膨らんでいますね。 Prologでは細部でコードを短くするのではなく、賢い導出木と...
• プロジェクトオイラー問８
  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...
• プロジェクトオイラー問い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に格納し、各素数それぞれについて*文字にチェンジした全パタ...
• プロジェクトオイラー問５
  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 //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2014 Problem 14 「最長のコラッツ数列」 † 正の整数に以下の式で繰り返し生成する数列を定義する. n → n/2 (n が偶数) n → 3n + 1 (n が奇数) 13からはじめるとこの数列は以下のようになる. 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1 13から1まで10個の項になる. この数列はどのような数字からはじめても最終的には 1 になると考えられているが, まだそのことは証明されていない(コラッツ問題) さて, 100万未満の数字の中でどの数字からはじめれば最長の数列を生成するか. 注意 数列の途中で100万以上になってもよい...
• プロジェクトオイラー問１２５
  Problem 125 「回文数の和」 † 回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ 6^2+7^2+8^2+9^2+10^2+11^2+12^2 1000 未満で連続する平方数の和で表せる回文数はちょうど 11 あり, その合計は 4164 である. 正の整数の平方のみをこの問題では扱うため, 1=0^2+1^2 は含めないことに注意せよ. 回文数でありかつ連続する平方数の和で表せる, 10^8 未満のすべての数の合計を求めよ. 解法 とりあえず地道に計算しても求まります。 たぶんこの問題双曲線上の整数解を求めるもっと高度な解法がありそうです。 is_palindromic(N) - N 0, number_codes(N,Codes), reverse(Codes,Codes). search2(Sum,...
• プロジェクトオイラー問１９
  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 から, 最大の数が書かれている行の番号を求めよ. 注 ファイル中の最初の二行は上の例である. 解法 Ｌｏｇを使っても十分答えが出るよう...
• プロジェクトオイラー問３７
  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でどうやって動的計画法をするか悩みました。 基本がわかれば考え方は簡単。...
• @wiki全体から「プロジェクトオイラー問２５」で調べる

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