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
• プロジェクトオイラー問１２０
  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)...
• プロジェクトオイラー解説index
  プロジェクトオイラー解説ページ ここではプロジェクトオイラーの問題を気が向いた問題から解説をしていきます。 最良の解説とはいきませんが基本的に大体１分ルール満たせるレベルの解説はのせていくつもりです。 解説満足度は、自分なりにどれだけ納得できる解説を行えたかと記述ミスをどれだけチェックしたかと記述の進捗率の３点の総合的な％表示したものです。 プロジェクトオイラー解説問1 解説満足度70％ プロジェクトオイラー解説問2 解説満足度80% プロジェクトオイラー解説問3 解説満足度70% プロジェクトオイラー解説問4 解説満足度70％ プロジェクトオイラー解説問5 解説満足度75％ プロジェクトオイラー解説問6　解説満足度60％ プロジェクトオイラー解説問7　解説満足度70％ プロジェクトオイラー解説問8　解説満足度70％ ...
• プロジェクトオイラー問６２
  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%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...
• プロジェクトオイラー解説問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 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を小さいほ...
• プロジェクトオイラー問１３０
  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勉強プロジェクトオイラー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が循環するということはフェルマーの小定理によれば必ず...
• プロジェクトオイラー問６９
  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%20124 http //projecteuler.net/problem=124 Problem 124 「順序付き根基」 † n の"根基"(radical)は, rad(n) に関する問題。 詳細はリンク先参照のこと。 解法 エラトステネスの篩もどきでテーブル化して計算しソートし１万個めを求めるだけです。 計算量ＢｉｇＯ（366401）+１０万個の要素のソート。 まあ普通です。 世の中Ｊ言語使いこなしてる人多いなと思います。 Ｊ言語だとこの問題１行、究極のショートコードですね。 #include stdio.h #include algorithm struct E{ int n,r...
• プロジェクトオイラー問１２５
  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 //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20121 Problem 121 「円盤ゲームの賞金額」 † 袋の中に赤い円盤 1 枚と青い円盤 1 枚が入っている. ある賭けゲームにおいて, プレイヤーは円盤を 1 枚ランダムに取り出しその色を記録する. 各ターンの終わりに円盤は袋に戻され, 追加の赤い円盤 1 枚が袋に足され, そして次の円盤がランダムに取り出される. プレイヤーはゲームをプレイするのに 1 ポンドを支払い, ゲーム終了時に青い円盤を赤い円盤より多く取り出していれば勝利する. ゲームが 4 ターンプレイされたとすると, プレイヤーが勝利する確率はちょうど 11/120 となる. したがって, 胴元が赤字の見込みになるまでにこのゲームで勝ちに対して割り当て...
• プロジェクトオイラー問１２３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20123 Problem 123 「素数の自乗で割った余り」 † pn を n 番目の素数とする. (p1 = 2, p2 = 3, ...) r を (pn - 1)n + (pn + 1)n を pn^2 で割った余りとする. 例えば, n = 3 のとき, p3 = 5 であり, 4^3 + 6^3 = 280 ≡ 5 mod 25. 余り r が 10^9 より大きくなる n の最小値は 7037 である. 余り r が 10^10 より大きくなる最初の n を求めよ. 解法 愚直に小さいほうから試す以外思いつきません。 何か賢い解法でもあるものでしょうか？ not_prime(N) - be...
• prolog勉強プロジェクトオイラー111～120
  プロジェクトオイラーという数学問題の掲載されたサイトの問題を堀江伸一さんがPrologで解くページ。 Prolog言語の特徴。 配列はない、ｓｔｄコンテナにあたるものはもちろんない。 何があるかっていうとリストしかない。 凄く不便。 しかも破壊的代入がない、そのため動的計画法と物凄く相性が悪い、破壊的代入を前提としたデータ構造とも相性が悪いというか現実的な計算量で実装できない物が多数。 基本ローカル変数しかないから変数が増える問題では関数（Prologでは厳密に述語といい関数とわけて考える）の引数が凄いことになる。 引数を減らすと、解集合を巨大なリストで得てそこから一番いい解を探すような富豪プログラムになる。 利点はバックトラックがあるくらい、このバックトラックという機能は論理的処理には向いており、このためマサチューセッツ工科大学でも論理枠でPrologの講義が一応行われて...
• プロジェクトオイラー問１２６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20126 Problem 126 「直方体層」 † 3 x 2 x 1 の直方体の表面全てを覆いつくすのに必要最小限の立方体の数は 22 個である. p_126.gif さらにこの立体に表面を覆いつくすように2層目を追加すると, 46 個の立方体が必要である. 3層目は 78 個, 4層目は 118 個の立方体が表面を覆いつくすのに必要である. ところで 5 x 1 x 1 の直方体への1層目も 22 個の立方体が必要である. 同様に 5 x 3 x 1, 7 x 2 x 1, 11 x 1 x 1 の直方体への1層目も全て 46 個の立方体である. 何層目かが n 個の立方体からなる直方体の数を, C(n) と定義す...
• プロジェクトオイラー問７２
  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 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...
• プロジェクトオイラー問２７
  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%2015 Problem 15 「格子経路」 † 2×2 のマス目の左上からスタートした場合, 引き返しなしで右下にいくルートは 6 つある. では, 20×20 のマス目ではいくつのルートがあるか. 問題の詳細はリンク先を参照のこと。 解法 20回下に２０回右に行く移動を並べ替えたものの全てですから。 40！/(20！)^2でおわりです。 fact(0,1) -!. fact(N,Result) - N1 is N-1, fact(N1,Re), Result is Re*N. main15 - fact(40,All), fact(20,Div), Ans is All/(Div^2), write(Ans).
• prolog勉強プロジェクトオイラー121～130
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ どうでもいい雑記。 今日宮沢賢治のやまなし　という作品を読んだ。 自然描写力が圧倒的、作画が一流のアニメを見た後のような読後感があった。 コードはページの下のほうに掲載。 コードを見てもらう前に競技プログラムの世界の話を少し書いておきます。 競技プログラムとは数学の問題のようにプログラムの問題が出題されそれを解くことを競う競技で国際的な大会も常時開催されていたりします。 ふつうはN月M日の１６時に出題され１８時までに回答を出題したかたのみ採点のように制限時間付となりますが、過去問題や問題集だけを扱ったサイトもあります。 プロジェクトオイラーは問題集サイトになります。 ここで問題を解くプログラムの話をします。 プログラムの世界では書いたプログラムをコードと呼びます。 競技プログラムの...
• プロジェクトオイラー問１９
  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%20115 Problem 115 「ブロックの組み合わせ方の数え上げ その2」 † 注意 これは Problem 114 をより難しくした問題である. 長さ n ユニットからなる 1 列上に, 最低 m ユニットの長さを持つ赤ブロックが置かれている. ただしどの赤ブロック同士も, 少なくとも 1 ユニットの黒い正方形が間にある(赤ブロックは長さが異なってもよい). 敷き詰め計数関数 F(m, n) は 1 列に敷き詰める方法が何通りかを表すとする. 例えば, F(3, 29) = 673135 であり, F(3, 30) = 1089155 である. m = 3 の時, n = 30 がこの敷き詰め計数関数が初...
• プロジェクトオイラー問１８
  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%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%2011 Problem 11 「格子内の最大の積」 † 20×20 の格子のうち連続した４数の積が最大になる部分を探す問題。 詳しくはリンク先を参照のこと。 解法 この問題は配列のない言語ではちょっとした難問です。 擬似的な配列としてリストのリストとしてnth0を２回適用してアクセスするのが一番楽です。 処理に失敗した部分はなかったことになるPrologの特性を利用して全部の地点で縦横斜めを検証し全ての4マス掛け算のリストを得その中で最大のものを答えとします。 もしも問題が10万行*１０万列になった場合でも動く処理を書くとしたら、４行単位で一行ずつずらしながら処理してその４行で計算できる最大値と今まで見つかった最大...
• 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...
• 雑記・日記2
  ここはこのサイトの管理人こと堀江伸一さんの個人的な雑記、日記　勉強記録を雑多に集めたページです。 当サイトの小学生レベルの創作物に関する言い訳 勉強記録一覧 リンク　→会津大学オンラインジャッジコード記録 会津大学オンラインジャッジの解答コードでこちらへ来た方はリンク先へどうぞ、私のコードが掲載されています。 一応少数の問題でコード実行速度一位を取ったコードもあるのですこしは参考になるかもしれません(ご近所さんのある方はＡＯＪでコード実行速度一位とるなんて馬鹿でもできる笑いもの　ぷぷぷ　とか言ってました。世間的なＡＯＪの評価ってそんなものかもしれません)。 会津大学オンラインジャッジ復習 ここより以下は本当に個人的な雑記ですので気にしないでください。 もしも結婚できたら子供に言ってみたいこと ネットで好みのイラスト収集 新ギレン...
• プロジェクトオイラー問１３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2013 Problem 13 「大数の和」 † 以下の50桁の数字100個の和の上位10桁を求めよ. 詳細はリンク先を参照のこと。 解法 与えられたデータをテキストファイルにリスト形式で保存しそれを読み込んで集計し目視で上位１０桁を抽出します。 それだけです。 この種の言語では読み込んだテキストファイルを組み合わせてコードとして成立させるというテクがあるそうです。 sum([],0) -!. sum([X|Xs],Result) -sum(Xs,Re),Result is Re+X. myread(FN) - open(FN,read,IS), read_term(IS,A,[]), sum(A,An...
• プロジェクトオイラー問１１２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20112 Problem 112 「はずみ数」 † 左から右までどの桁もその左の桁を下回らない数を増加数と呼ぶ. 例えば, 134468. 同様に, どの桁もその右の桁を下回らない数を減少数と呼ぶ. 例えば, 66420. 増加数でも減少数でもない正の整数をはずみ数と呼ぶことにする. 例えば, 155349. 100以下にはずみ数が無いのは明らかだが, 1000未満では半数を少し上回る525個がはずみ数である. 実際, はずみ数の割合が50%に達する最少の数は538である. 驚くべきことに, はずみ数はますます一般的になり, 21780でははずみ数の割合は90%に達する. はずみ数の割合がちょうど...
• プロジェクトオイラー問１４
  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万以上になってもよい...
• プロジェクトオイラー問１７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2017 Problem 17 「数字の文字数」 † 1 から 5 までの数字を英単語で書けば one, two, three, four, five であり, 全部で 3 + 3 + 5 + 4 + 4 = 19 の文字が使われている. では 1 から 1000 (one thousand) までの数字をすべて英単語で書けば, 全部で何文字になるか. 注 空白文字やハイフンを数えないこと. 例えば, 342 (three hundred and forty-two) は 23 文字, 115 (one hundred and fifteen) は20文字と数える. なお, "and" を使用するのは英...
• オイラープロジェクト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 プロジェクトオイラーというサイトで数学の問題をプログラムで解こうという練習問題を扱ったサイトです。 自分で考え出した...
• プロジェクトオイラー問１０４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20104 Problem 104 「両端がパンデジタルなフィボナッチ数」 † フィボナッチ数列は再帰的な関係によって定義される Fn = Fn−1 + Fn−2 F541 (113桁)は, 下9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. そして, F2749 (575桁)は, 頭から9桁に1から9までの数字をすべて含む初めてのフィボナッチ数である. Fkが, 頭から9桁と下9桁のどちらも1から9までの数字をすべて含む初めてのフィボナッチ数とするとき, kを求めよ. 解法 足し算を繰り返すとある桁以下は上位９桁に影響を与えなくなってきます。 上位１７桁くらいとっておけばまず安全に上位９桁を正...
• プロジェクトオイラー問１０２
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20102 Problem 102 「三角形の包含」 † ２次元平面に三角形の座標が与えられるので、原点を含む三角形の数をこたえる問題。 詳細はリンク先参照のこと。 解法 ２次元の外積の値で判断します。 それだけ。 三角形のデータファイルはテキストエディタでＰｒｏｌｏｇのリスト形式に変換してから読み込んだ。 check(T1,T2,T3) -T1= 0,T2= 0,T3= 0,!. check(T1,T2,T3) -0= T1,0= T2,0= T3,!. isIns(Rows,1) - member([X1,Y1,X2,Y2,X3,Y3],Rows), T1 is X1*Y2-X2*Y1, T2 is X2*...
• プロジェクトオイラー問１０８
  http //odz.sakura.ne.jp/projecteuler/index.php?Problem%20108 Problem 108 「ディオファントス逆数 その1」 † 次の等式で x, y, n は正の整数である. 1/x + 1/y = 1/n n = 4 では 3 つの異なる解がある. 1/5 + 1/20 = 1/4 1/6 + 1/12 = 1/4 1/8 + 1/8 = 1/4 解の数が 1000 を超える最小の n を求めよ. 注 この問題は Problem 110 の易しいケースである. こちらを先に解く事を強く勧める. 解法 素朴な解法でもなんとかなる範囲の問題です。 1/x+1/y=1/n (x+y)/xy=1/n nx+ny=xy (x-n)(y-n)=n^2 よりｘ...
• プロジェクトオイラー問１０５
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20105 Problem 105 「特殊和集合 検査」 † 大きさ n の集合 A の要素の和を S(A) で表す. 空でなく共通要素を持たないいかなる 2 つの部分集合 B と C に対しても以下の性質が真であれば, A を特殊和集合と呼ぼう. i. S(B)≠S(C); つまり, 部分集合の和が等しくてはならない. ii. B が C より多くの要素を含んでいればこのとき S(B) S(C) となる. たとえば, {81, 88, 75, 42, 87, 84, 86, 65} は, 65 + 87 + 88 = 75 + 81 + 84 であるため特殊和集合ではないが, {157, 150, 164, 119, 79...
• プロジェクトオイラー問１１６
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20116 Problem 116 「赤タイル, 緑タイル, あるいは青タイル」 † 5 個の黒い正方形のタイルの列を, 赤(長さ 2), 緑(長さ 3), 青(長さ 4)から選んで, この色のついた長方形のタイルでいくつか置き換える. もし赤のタイルを選んだ場合は, ちょうど 7 通りの方法がある. 図略 もし緑のタイルを選んだ場合は, 3 通りである. 図略 もし青のタイルを選んだ場合は, 2 通りである. 図略 複数の色を混ぜられない場合は, 5 ユニットの長さの 1 列に並んだ黒いタイルを置き換える方法は 7 + 3 + 2 = 12 通りある. 50 ユニットの長さの 1 列に並んだ黒い...
• プロジェクトオイラー問１１３
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20113 Problem 113 「非はずみ数」 † ある数の桁を左から右へと順に見たとき, 任意の桁の数が自身の左にある桁の数以上であるとき, その数を増加数 (increasing number) と呼ぶ; 例えば134468は増加数である. 同様に, 任意の桁の数が自身の右にある桁の数以上であるとき, その数を減少数 (decreasing number) と呼ぶ; 例えば66420がそうである. 増加数でも減少数でもない数を "はずみ"数 ("bouncy" number) と呼ぶ; 155349がそうである. nが大きくなるにつれ, n以下のはずみ数の割合は大きくなる. ...
• プロジェクトオイラー問１１０
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20110 Problem 110 「ディオファントス逆数 その2」 † 次の等式で x, y, n は正の整数である. 1/x + 1/y = 1/n n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である. 解の数が 4,000,000 を超える最小の n を求めよ. 注 この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる. 解法 問108では私は約数から答えを探しました。 今回は約数から元の数を生成する方法で解きます。 n=２＾３*３＾２はn1=２＾２*３＾３...
• プロジェクトオイラー問１１７
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20117 Problem 117 「赤タイル, 緑タイル, そして青タイル」 † 黒い正方形のタイルと, 2 ユニットの長さの赤のタイル, 3 ユニットの長さの緑のタイル, 4 ユニットの長さの青のタイルから選んで組み合わせて, 5 ユニットの長さの 1 列をタイルで敷く方法はちょうど 15 通りある. 図略 長さ 50 ユニットの 1 列をタイルで敷く方法は何通りあるか. 注 この問題は Problem 116 に関連する 詳細はリンク先参照のこと。 解法 黒いブロックも１ブロックを置くものだと考えると単純な漸化式になります。 前４つの項から決まるフィナボッチ数列と考えればよいだけです。 ね、簡単でしょ。 ...
• プロジェクトオイラー問１１９
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20119 Problem 119 「数字和のべき乗」 † 512 という数は興味深い数である. というのも, 各桁の和を何乗かしたものに等しくなっているからである 5 + 1 + 2 = 8, 8＾3 = 512 である. この特性を持つ他の数は例えば 614656 = 28＾4 である. この数列の第 n 項を an と定義し, また 2 桁以上であるとしよう. a2 = 512, a10 = 614656 となる. a30 を求めよ. 解法 各桁の和はまあ大きく見積もっても200くらいです。 その1＾ｎから200＾ｎまでの乗数を小さいほうから求めます。 ｍ＾ｎの各桁の和でm^nをあまりなく割り続け...
• プロジェクトオイラー問１１４
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20114 Problem 114 「ブロックの組み合わせ方の数え上げ その1」 † 直列な５０マスを特定の規則のもと赤ブロックで埋めるとき何通りの埋め方があるか計算する問題。 詳細はリンク先参照のこと。 解法 手前から埋めていく動的計画法で片が付きます。 計算量は48回。 search(52,[_,_,Sum],_,_) -!,write([ans,Sum]). search(Len,[X1,X2,X3],Sum,Add) - !, Add1 is Add+X1, Sum1 is Sum+Add, Len1 is Len+1, write([Len1,Sum1,Add1]),nl, search(Len1,[X2,X...
• プロジェクトオイラー問１１８
  http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem+118 Problem 118 「パンデジタル素数集合」 † 1 から 9 の全ての数字を使い, 自由につなげることで 10 進数の数字を作り, 複数の集合を作ることができる. 集合 {2,5,47,89,631} は面白いことに全ての要素が素数である. 1 から 9 の数字をちょうど 1 個ずつ含み, 素数の要素しか含まない集合はいくつあるか? 解法 全ての分割組み合わせを重複なく昇順の集合として生成します。 一つの要素は [[1,2,3],[4,5,6],[7,8,9]]の３つで一つ組といった具合です。 [[4,5,6],[1,2,3],[7,8,9]]とかは同じ組み合わせとみなして生成しません。 後はそれぞれn個の中...
• プロジェクトオイラー問１００
  Problem 100 「組み合わせの確率」 † 箱の中に15個の青い円盤と6個の赤い円盤からなる21個の色のついた円盤が入っていて, 無作為に2つ取り出すとき, 青い円盤2つを取り出す確率P(BB)は P(BB) = (15/21) × (14/20) = 1/2 であることがわかる. 無作為に2つ取り出すとき, 青い円盤2つを取り出す確率がちょうど1/2となるような次の組み合わせは, 箱が85個の青い円盤と35個の赤い円盤からなるときである. 箱の中の円盤の合計が1012 = 1,000,000,000,000を超えるような最初の組み合わせを考える. 箱の中の青い円盤の数を求めよ. 解法 なんとなく直感的に、行列演算で次に大きな数が出てくるのでは？ と考えて。 [[a,b],[c,d]][3,1]+[e,f]=[15,6] [[a,b],[c...
• 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...
• @wiki全体から「プロジェクトオイラー問１２０」で調べる

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