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%2062 Problem 62 「立方数置換」 † 立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である. 立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ. 解法 ３乗の数字を小さいほうから試していき、数字を辞書順で並べ替えたものを基準に集計していきます。 例えば345002なら002345が一つ見つかったとそれぞれ集計していきます。 最初に5個Hitした辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• プロジェクトオイラー問５
  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%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%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%2057 Problem 57 「平方根の近似分数」 † 2の平方根は無限に続く連分数で表すことができる. √ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213... 最初の4回の繰り返しを展開すると以下が得られる. 1 + 1/2 = 3/2 = 1.5 1 + 1/(2 + 1/2) = 7/5 = 1.4 1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666... 1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379... 次の3つの項は99/70, 239/169, 577/408である. ...
• プロジェクトオイラー問５０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2050 Problem 50 「連続する素数の和」 † 素数41は6つの連続する素数の和として表せる 41 = 2 + 3 + 5 + 7 + 11 + 13. 100未満の素数を連続する素数の和で表したときにこれが最長になる. 同様に, 連続する素数の和で1000未満の素数を表したときに最長になるのは953で21項を持つ. 100万未満の素数を連続する素数の和で表したときに最長になるのはどの素数か? 解法 B Aとして A番目の素数までの集計値-B番目の素数までの集計値の差分が AからBまでの連続した素数の和です。 それだけの問題です。 素数は篩で選り分けて集計して。 後は差分のなかで素...
• プロジェクトオイラー問５５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2055 Problem 55 「Lychrel数」 † 47とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる. 全ての数が素早く回文数になるわけではない. 349を考えよう, 349 + 943 = 1292, 1292 + 2921 = 4213 4213 + 3124 = 7337 349は, 3回の操作を経て回文数になる. まだ証明はされていないが, 196のようないくつかの数字は回文数にならないと考えられている. 反転したものを足すという操作を経ても回文数にならないものをLychrel数と呼ぶ. 先のような数の理論的な性質により, またこの問題の目的のために, Lychrel数...
• プロジェクトオイラー問５９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2059 Problem 59 「XOR暗号解読」 † (訳者注 文字コードの説明は適当です) 各文字はそれぞれ一意のコードに割り当てられている. よく使われる標準としてASCII (American Standard Code for Information Interchange) がある. ASCIIでは, 大文字A = 65, アスタリスク (*) = 42, 小文字k = 107というふうに割り当てられている. モダンな暗号化の方法として, テキストファイルの各バイトをASCIIに変換し, 秘密鍵から計算された値とXORを取るという手法がある. XOR関数の良い点は, 暗号化に用いたのと同じ暗号化鍵でXORを取ると平文を復号...
• プロジェクトオイラー解説問8
  Problem 8 「数字列中の最大の積」 † 以下の1000桁の数字から5つの連続する数字を取り出して その積を計算する. そのような積の中で最大のものの値はいくらか. データが多いので問題の詳細はリンク先を読んでください。 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%208 解法 おそらくファイル読み込みの演習だと思います。 文字列やファイル読み込みは言語によって雑多な違いがあり統一的な話はできません。 まず1000文字の数字列をテキストファイルに保存し、このファイルの中身を文字列型に読み込んでいきます。 まず1000文字の数字を文字列として一行ずつ読み込み、 読み込んだ行strとしてstrAll+=strのように読み込み1000文字の文字列とします。 ...
• プロジェクトオイラー問５８
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2058 Problem 58 「螺旋素数」 † らせん状に数字を生成した時対角線上の数字の素数の割合をこたえる問題。 詳細はリンク先を参照のこと 解法 書くだけ問題。 ほとんどの計算時間が素数判定に費やされているので、そこを多少改善できますが。 それくらいです。 not_prime(P) -P 2,!. not_prime(P) - between(2,P,Div), (Div^2 P- !,fail;true), P mod Div= =0, !. is_prime(P) -!,not(not_prime(P)). search(Hit,Bad,N,Size,0) - Size 3, Hit1 is Hit*10...
• プロジェクトオイラー問５６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2056 Problem 56 「もっとべき乗の数字和」 † Googol (10＾100)は非常に大きな数である 1の後に0が100個続く. 100＾100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である. a, b 100 について自然数 ab を考える. 桁の和の最大値を答えよ. 解法 書くだけ問題でなんか面白くないです。 賢い方法あるのでしょうか？ keta_sum(0,0) -!. keta_sum(N,Result) - N1 is N//10, X is N mod 10, keta_sum(N1,Re), Result is Re+X. sear...
• プロジェクトオイラー問５１
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2051 Problem 51 「素数の桁置換」 † *3の第1桁を置き換えることで, 13, 23, 43, 53, 73, 83という6つの素数が得られる. 56**3の第3桁と第4桁を同じ数で置き換えることを考えよう. この5桁の数は7つの素数をもつ最初の例である 56003, 56113, 56333, 56443, 56663, 56773, 56993. よって, この族の最初の数である56003は, このような性質を持つ最小の素数である. 桁を同じ数で置き換えることで8つの素数が得られる最小の素数を求めよ. (注 連続した桁でなくても良い) 解法 変更するのが1,2,4,5つの桁数だと。 一気に変更した時各桁の和を...
• プロジェクトオイラー問５４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2054 Problem 54 「ポーカーハンド」 † ポーカーの勝敗を判定する問題。 詳細はリンク先を参照のこと。 解法 世界中で何回ポーカーの役判定のコードが書かれたのだろうかと思いをはせる問題です。 両者ともに素朴に役を判定して役に対応したスコアと役で使ったカードの数字を返し、 Aのほうがスコアが大きいなら勝利、同じならカードを比べてAの勝利か判定するだけ。 １を14として取り扱うと話が綺麗になります。 判定には巧みな手法があるそうなのでそれを調べるのもいいかもしれませんね。 ファイルは一行ごと１０枚のカードを現すリストと変換しています。 max(A,B,A) -A B,!. max(_,B,B) -!. ...
• 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について, 真既約分数の集合は何個の要素を持つか? 解法 オイラーのファイ関数をエラトステネスの...
• プロジェクトオイラー問１２９
  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 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勉強プロジェクトオイラー121～130
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ どうでもいい雑記。 今日宮沢賢治のやまなし　という作品を読んだ。 自然描写力が圧倒的、作画が一流のアニメを見た後のような読後感があった。 コードはページの下のほうに掲載。 コードを見てもらう前に競技プログラムの世界の話を少し書いておきます。 競技プログラムとは数学の問題のようにプログラムの問題が出題されそれを解くことを競う競技で国際的な大会も常時開催されていたりします。 ふつうはN月M日の１６時に出題され１８時までに回答を出題したかたのみ採点のように制限時間付となりますが、過去問題や問題集だけを扱ったサイトもあります。 プロジェクトオイラーは問題集サイトになります。 ここで問題を解くプログラムの話をします。 プログラムの世界では書いたプログラムをコードと呼びます。 競技プログラムの...
• 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 プロジェクトオイラーというサイトで数学の問題をプログラムで解こうという練習問題を扱ったサイトです。 自分で考え出した...
• プロジェクトオイラー問１３０
  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%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...
• オイラープロジェクトカンニング履歴
  会津大学オンラインジャッジの問題とおなじくカンニングして解いたオイラープロジェクトの問題のリスト。 数学の問題集を扱ったサイトなので調べものして数学の知識を身につけながら解くのが正道な気がするが、一応出来るだけ自力で解きたいところ。 なのでカンニングして解いた問題のリストを掲載。 問い12 問題を解く方法がよくわからず掲示板で質問。 コードまで書いてもらうもコードの読解や原理がよくわからず考え中。 問い25 フィナボッチ数が１０００桁になるのは数列の何個目か？ 単純に1000ケタを超えるまでフィナボッチ数列を計算して解こうと挑戦。 ほとんどコードを書いたことがないＬｉｓｐで解こうと考え、初心者レベルのコードを記述してみて実行時エラー。 掲示板でloop中の（が一つ多いでのでsetqのあたりが余分に関数と解釈されてると指摘を受けそれを修正してアセプト。 修...
• prolog勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• プロジェクトオイラー問い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%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...
• プロジェクトオイラー問１９
  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 ...
• プロジェクトオイラー問４０
  Problem 40 「チャンパーノウン定数」 † 正の整数を順に連結して得られる以下の10進の無理数を考える 0.123456789101112131415161718192021... 小数第12位は1である. dnで小数第n位の数を表す. d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000 を求めよ. 解法 一桁は９個めまで ２桁は１８０+9個めまで ３桁は２７００+１８０+9個めまで続き以下同様です。 例えば3000なら２８８９個めの４桁の中に答えがあり、 ４桁は4つ数字が延々ならぶので(111-1)/4+1000の数字の中に目的のポイントがあり。 そのポイントの数字の中の(p-1) mod 4桁目が答えとなります。 calcP(P,[S|_],Keta,ReNum,Re...
• プロジェクトオイラー問１２
  Problem 12 「高度整除三角数」 † 三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... となる. 最初の7項について, その約数を列挙すると, 以下のとおり. 1 1 3 1,3 6 1,2,3,6 10 1,2,5,10 15 1,3,5,15 21 1,3,7,21 28 1,2,4,7,14,28 これから, 7番目の三角数である28は, 6個以上の約数をもつ最初の三角数であることが分かる. では, 500個以上の約数をもつ最初の三角数はいくつか. 解法 三角数はD=n(n+1)/2で、約数の個数はDを小さいほ...
• プロジェクトオイラー問２５
  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%2018 Problem 18 「最大経路の和 その1」 † 以下の三角形の頂点から下まで移動するとき, その数値の和の最大値は23になる. 3 7 4 2 4 6 8 5 9 3 この例では 3 + 7 + 4 + 9 = 23. 以下の三角形を頂点から下まで移動するとき, その最大の和を求めよ. 詳細はリンク先参照のこと。 解法 一段ずつの動的計画法で片が付きます。 max(A,B,A) -A B,!. max(_,B,B) -!. calcCol([D],[X,Y],AddDX,[AddDY]) - !, write([X,Y,D]), AddDY is D+Y, Ad...
• プロジェクトオイラー問２９
  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).
• プロジェクトオイラー問４６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2046 Problem 46 「もうひとつのゴールドバッハの予想」 † Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した. 9 = 7 + 2×12 15 = 7 + 2×22 21 = 3 + 2×32 25 = 7 + 2×32 27 = 19 + 2×22 33 = 31 + 2×12 後に, この予想は誤りであることが分かった. 平方数の2倍と素数の和で表せない最小の奇合成数はいくつか? 解法 小さい数から試していきます。 i=2から初めてiを1ずつ増加させます。 iが平方数ならiとi以下の素数個々との和全部をstd setに入れます。 ...
• プロジェクトオイラー問７５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2075 Problem 75 「1通りの整数直角三角形」 † ある長さの鉄線を折り曲げたときに1通りの直角三角形を作る最短の長さは12 cmである. 他にも沢山の例が挙げられる. 12 cm (3,4,5) 24 cm (6,8,10) 30 cm (5,12,13) 36 cm (9,12,15) 40 cm (8,15,17) 48 cm (12,16,20) それとは対照的に, ある長さの鉄線 (例えば20cm) は整数長さで折ることができない. また2つ以上の折り曲げ方があるものもある. 2つ以上ある例としては, 120cmの長さの鉄線を用いた場合で, 3通りの折り曲げ方がある. 120 ...
• プロジェクトオイラー問７４
  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...
• @wiki全体から「プロジェクトオイラー問５」で調べる

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