c21coterie @ ウィキ

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

• プロジェクトオイラー解説index
  ...足度50％ プロジェクトオイラー解説問38　解説満足度85％ プロジェクトオイラー解説問110　解説満足度50％ プロジェクトオイラー解説問134　解説満足度90％ プロジェクトオイラー解説問142　解説満足度75％ プロジェクトオイラー解説問161　解説満足度15％ プロジェクトオイラー解説問162　解説満足度65％ プロジェクトオイラー解説問164　解説満足度60％ プロジェクトオイラー解説問191　解説満足度70％ プロジェクトオイラー解説問194　解説満足度70％ プロジェクトオイラー解説問199　解説満足度65％ プロジェクトオイラー解説問201　解説満足度80％ 解説記述者 堀江伸一 記述ミスや解説のミスなどを発見された方は sinapusu2002@yaho...
• プロジェクトオイラー関係
  プロジェクトオイラー問い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
• プロジェクトオイラー解説問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 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)...
• プロジェクトオイラー解説問38
  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を何らかの一文字の数字とすると 9x...
• プロジェクトオイラーを楽しむページIndex
  プロジェクトオイラーの問題を個人的に楽しむページ。 210番以上は私の学力では手が届かない世界なのでそれ以下の問題をもう一度楽しもうと思ってこのページを作成しました。 プロジェクトオイラーの問題は何度か挑戦するともっと賢い解法があると気づくという記述をネットで見かけるので私も何か気づけるかもしれません。 最初からもう一度個人的に楽しんでみます。 閲覧数ほぼ0のサイトなのでマイペースになります。 プロジェクトオイラー問１ プロジェクトオイラー問２ プロジェクトオイラー問３ プロジェクトオイラー問４ プロジェクトオイラー問５ プロジェクトオイラー問６ プロジェクトオイラー問７ プロジェクトオイラー問８ プロジェクトオイラー問９ プロジェクトオイラー問１０ プロジェクトオイラー問１１ ...
• プロジェクトオイラー解説問3
  Problem 3 「最大の素因数」 † 13195 の素因数は 5, 7, 13, 29 である. 600851475143 の素因数のうち最大のものを求めよ. 解法 ｂ=600851475143とします。 2,3,4,5,,,, と小さい数から1ずつ増加させこの数をaとしましてaでｂを割り切れるか試します。 割り切れるなら割り切れる限りその数でbを割り、割った数を再度ｂとしまたaを１ずつ増加させて割り切れるかためしこれを繰り返します。 これにより素数による割り切りだけが残ります。 もしa^2 bとなったら最後に割り切った数とbのうち大きなほうが答えとなります。 なぜここで答えを出してよいかというと。 bがaより大きな数cで割り切れたとします。 するとb/c=d　ｄは自然数と定義できます。 b=cdで bはｄでも割り切れることが判明し...
• プロジェクトオイラー問６２
  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した辞書順があればそれが答えです。 集計で新しい辞書順が出て...
• プロジェクトオイラー解説問134
  Problem 134 「素数ペアの結合」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20134 問題 連続する素数 p1 = 19, p2 = 23 について考える. 1219 は末尾の桁が p1 からなり p2 で割り切られる最小の数であることが確かめられる. 実際, p1 = 3, p2 = 5 を除けば, 全ての p2 p1 なる連続する素数のペアについて, 末尾の桁が p1 からなり p2 で割り切られる数 n が存在する. S を n の最小のものであるとする. 5 ≤ p1 ≤ 1000000 を満たす連続する素数のペア全てに対し ∑ S を求めよ. 解説 この問題は具体的に考えると解けます。 p1=19とp2=23の場合で考えま...
• プロジェクトオイラー解説問1
  Problem 1 「3と5の倍数」 † 10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる. 同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ. 解法 この問題で解説が必要ということは、プログラム言語の基本構文であるループとif。 もしくは再帰処理などの記述がよくわからない。 という読者だと考えられます。 その辺を解説してみます。 解法1 ループに頼らない数学的解法 高校数学の知識によればこの問題はプログラムを書くまでもなく一行でもとまります。 ３の倍数は (3,6,9,,,,999) 5の倍数は (5,10,15,,,995) まであります。 3の倍数は (3*1,3*2,,,3*333)と記述しなおせます。 ...
• プロジェクトオイラー解説問2
  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 私の解説よりずっと高度な解説をしています。 初等的解法 フィナボッチ数列を眺めると 1 1 2 3 5 8 13 21 34 55 89 144 奇 奇 偶 奇 奇 偶 奇 奇 偶 奇 奇 偶 と奇奇偶とループしていることがわかります。 これはフ...
• プロジェクトオイラー解説問6
  Problem 6 「二乗和の差」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%206 最初の10個の自然数について, その二乗の和は, 1^2 + 2^2 + ... + 10^2 = 385 最初の10個の自然数について, その和の二乗は, (1 + 2 + ... + 10)^2 = 3025 これらの数の差は 3025 - 385 = 2640 となる. 同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ. 高校数学の公式によれば 1^2 + 2^2 + ... + n^2=n*(n+1)(2n+1)/6 1+2+,,,+n=n*(n+1)/2 です。 (1+2+,,,+n)^2=(n*(n+1)/2)^...
• プロジェクトオイラー解説問9
  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 を計算しなさい. 解法 ピタゴラス数の3つ組は原始ピタゴラス数という概念によって計算されます。 m,nは自然数で互いに素,m-nが奇数でm nである時 a^2+b^2=c^2として。 a=m^2-n^2 b=2mn c=m^2+n^2 という関係式であらわされます。 実はa^2+b^2=c^2をみたす整数組(a,b,c)は k(m^2-n^2)+k(2mn)=k(m^2+n^2...
• プロジェクトオイラー解説問5
  Problem 5 「最小の倍数」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%205 2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である. では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか. 解法 この問題は手計算で解けます。 1～10の場合を分析してみましょう。 答えをaと考えます。 aの素因数をp1,p2,p3,,pnとします。 a=p1^a1*p2^a2*,,pn^an です。 1～10で割れるということは１～10それぞれの数の素因数で割ってもaが整数であるということです。 aの素因数を()で書いてみます。 aはどんな条件を満たしてる数か1～10...
• 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次曲線上の整数解の組を小さいものから求めよという問題となる。 パズルに見せかけて実態...
• プロジェクトオイラー解説問4
  Problem 4 「最大の回文積」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%204 左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である. では, 3桁の数の積で表される回文数の最大値を求めよ. 解法 組み合わせ数が少ないので全部検討しても十分間に合います。 a=100～999=900個 b=100～999=900個 としても 全部で81万個の数字の検討にしかなりません。 最近のパソコンでは処理回数が5億回で1秒かそれ以下ですので、81万回の検討程度なら瞬きする間に終わります。 c=a*b とします。 100*100=10000 =c =999*999=9...
• プロジェクトオイラー解説問7
  Problem 7 「10001番目の素数」 † 素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり, 6番目の素数は 13 である. 10001 番目の素数を求めよ. 解法 http //ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9 Wikiにあるエラトステネスの篩を使います。 エラトステネスの篩とは素数リストを得るための効率的な方法です。 素数の判定は非常に奥が深く難しい理論がたくさんありますが。 一般向けではこの篩と試し割がわかれば大体大丈夫です。 言語によっては素数判定メソッドが使えるものもありますのでそれを使うのも手です。 篩の具体的な実装については http...
• prolog勉強プロジェクトオイラー111～120
  プロジェクトオイラーという数学問題の掲載されたサイトの問題を堀江伸一さんがPrologで解くページ。 Prolog言語の特徴。 配列はない、ｓｔｄコンテナにあたるものはもちろんない。 何があるかっていうとリストしかない。 凄く不便。 しかも破壊的代入がない、そのため動的計画法と物凄く相性が悪い、破壊的代入を前提としたデータ構造とも相性が悪いというか現実的な計算量で実装できない物が多数。 基本ローカル変数しかないから変数が増える問題では関数（Prologでは厳密に述語といい関数とわけて考える）の引数が凄いことになる。 引数を減らすと、解集合を巨大なリストで得てそこから一番いい解を探すような富豪プログラムになる。 利点はバックトラックがあるくらい、このバックトラックという機能は論理的処理には向いており、このためマサチューセッツ工科大学でも論理枠でPrologの講義が一応行われて...
• プロジェクトオイラー解説問201
  Problem 201 「唯一の和を持つ部分集合」 † 変更履歴 (*2013/12/10　らすかるさんというかたから計算方法に記述ミスがあると指摘を受け修正、まだ解説サイトを始めたばかりで不慣れなためにこういうミスは減らさねばとよい自戒となる、１２月１１日図の修正完了) (*2013/12/13 図の説明のＢｉｔが１桁ずれていること一部の解説がわかりにくいことをaerile_reさんという方からご指摘を受ける　2013/12/13修正完了) 問題 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20201 数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる....
• プロジェクトオイラー解説問110
  Problem 110 「ディオファントス逆数 その2」 † 次の等式で x, y, n は正の整数である. 1/x + 1/y = 1/n n = 1260 では 113 の異なる解があり, この n が解の個数が 100 を超える最小の値である. 解の数が 4,000,000 を超える最小の n を求めよ. 注 この問題は Problem 108 を非常に難しくしたケースである. 総当り法で解ける範囲を超えているので, 賢い解き方が求められる. 解説 まずは素朴に式変形をしてみる。 1/x+1/y=1/n (x+y)/(xy)=1/n nx+ny=xy (x-n)(y-n)=n^2 なのでｘ-ｎとｙ-ｎはn^2の約数であればよいと分かります。 n^2の約数はその素因数を n=p1^a1*p2^a2*,,,pm^amとします...
• プロジェクトオイラー解説問194
  ただいま解説や画像や問題文の写し準備中 このページの解説完了度100％ 只今中身がきちんとしているかチェック中。 Problem 194 「着色配置」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20194 ユニットA とユニットB からなるグラフについて考える. ユニット同士を垂直方向の辺に沿ってくっつけてグラフにする. 下図はグラフの一例である. (a,b,c)タイプの配置とは, 以下を満たすグラフのことである a 個のユニットAと b 個のユニットBからなる各頂点は色づけされていて, 最大で c 色まで使われておりどの隣接する2頂点も同じ色にはならない。 上のグラフは(2,2,6)タイプの配置の例である. 正確に...
• プロジェクトオイラー解説問199
  Problem 199 「反復円充填」 † 問題 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20199 3つの半径の等しい円が, 1つのもっと大きい円の中にあり, 各円は他の円とお互い接している. ただし中の円はお互いが重ならない. 4つのすき間があり, これを繰り返し接する円で埋めていく. 各ステップで, 全てのすき間にそれぞれ最大の円を置いていき, 結果として次のステップにはさらにすき間が増えていく. 3ステップ後には上の図のようになる. 108のすき間ができ, 円で埋められていない面積の比率は10進8桁に四捨五入して 0.06790342 となる. 10ステップ後に円で埋まっていない面積の比率はいくらか？ 10進数8桁に四捨五入し, x.xxxxxxxx とい...
• プロジェクトオイラー解説問162
  只今解説準備中 Problem 162 「16進数」 † 問題 16進法では, 数は以下の16個の数字によって表される 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F 16進数の AF は, 10進法での 10x16 + 15 = 175 と等しい. 3桁の16進数 10A, 1A0, A10, A01 には, 0, 1, A の全てが現れている. 10進数で書くときと同様に, 先頭の0は書かないことにする. 0, 1, A がそれぞれ少なくとも1回は現れるような16桁までの16進数はいくつ存在するか? 16進数で答えよ. (A,B,C,D,E,F は大文字とし, 先頭や末尾の16進数であることを表す記号や先頭の0は許されない. つまり, 1A3F ならOK. 1a3f, 0x1a3f, $1A3F, #1A3F, 000000...
• プロジェクトオイラー解説問161
  Problem 161 「トリオミノ」 † 問題 トリオミノとは3つの正方形を辺で繋げたものである. 以下は2つの基本形. すべての方向を可能性に入れると, 以下の6つがある. n x m が3で割り切れるならば, どのn x m の格子もトリオミノによって埋めることができる. 反転, 回転によって得られる埋めかたを別の埋め方とすると, 2 x 9 の格子では41通りの埋め方がある. 9*12の格子では何通りの埋め方があるか。 解法 只今解説準備中。 左下から右上へ図のような順番で隙間なくみっちり敷き詰めていき動的計画法で解きます。 詰めていくときピースのおかれた状態を管理するための記法が必要となります。 マス目に１～108まで図のように番号を割り振ります。 これを１２８ビット整数型で管理しこれを主キーとしこの主キ...
• 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...
• プロジェクトオイラー解説問164
  Problem 164 「どの連続した3桁の和も与えられた数を超えない数」 † 問題 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20164 どの連続した3桁の和も9以下のような(9以下は9を含む)20桁の数(先頭の0は認めない)はいくつあるか? 解法 この問題は３桁から初めて１桁ずつ伸ばしていく動的計画法で解きます。 最初３桁で条件を満たす組み合わせをすべて元ます。 それに一桁ずつ足して４桁、５桁、、、の場合の組み合わせ数を計算し数字列と組み合わせ数のデータを２０桁まで伸ばします。 伸ばすとき簡単な理由から末尾３桁で分類しながら組み合わせ数を計算すればよいのですが、それについて今から説明します。 最初頭３桁の数を考えます。 memo[10][10...
• プロジェクトオイラー解説問142
  修正履歴 2014/1/6　数式の記述ミスや記述のあいまいさを訂正。大体の記述はあってるはずなのでここで仮完成とする。 Problem 142 「完全平方数コレクション」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20142 x + y, x - y, x + z, x - z, y + z, y - zが全て平方数となる整数の組 x y z 0で, 最小の x + y + z を求めよ. 解法 この問題は深さ制限探索で解きます。 まず式を定義しなおします。 x+y=S1 x-y=S2 y+z=S3 y-z=S4 x+z=S5 x-z=S6 と定義します。（S1～S6は当然平方数） 探索を行うに当たってできるだけ早めに、(ｘ,ｙ,ｚ)の組が式...
• prolog勉強プロジェクトオイラー121～130
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ どうでもいい雑記。 今日宮沢賢治のやまなし　という作品を読んだ。 自然描写力が圧倒的、作画が一流のアニメを見た後のような読後感があった。 コードはページの下のほうに掲載。 コードを見てもらう前に競技プログラムの世界の話を少し書いておきます。 競技プログラムとは数学の問題のようにプログラムの問題が出題されそれを解くことを競う競技で国際的な大会も常時開催されていたりします。 ふつうはN月M日の１６時に出題され１８時までに回答を出題したかたのみ採点のように制限時間付となりますが、過去問題や問題集だけを扱ったサイトもあります。 プロジェクトオイラーは問題集サイトになります。 ここで問題を解くプログラムの話をします。 プログラムの世界では書いたプログラムをコードと呼びます。 競技プログラムの...
• プロジェクトオイラー解説問191
  Problem 191 「賞を貰える文字列」 † 問題 http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20191 ある学校では出席率が高く遅刻率が低い生徒に褒賞金を出している. 3日連続で休む, または, 2回以上遅刻した生徒は褒賞金を得る権利を失う. n日間の各生徒の出席状況を3進の文字列で表す. 文字はL (late, 遅刻), O (on time, 出席), A (absent, 欠席) である. 4日間の場合, 81通りの3進の文字列が考えられる. そのうち賞を貰えるのは以下の43個の文字列である. OOOO OOOA OOOL OOAO OOAA OOAL OOLO OOLA OAOO OAOA OAOL OAAO OAAL OALO OALA OLOO OLOA OL...
• オイラープロジェクト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
  ここはこのサイトの管理人こと堀江伸一さんの個人的な雑記、日記　勉強記録を雑多に集めたページです。 当サイトの小学生レベルの創作物に関する言い訳 勉強記録一覧 リンク　→会津大学オンラインジャッジコード記録 会津大学オンラインジャッジの解答コードでこちらへ来た方はリンク先へどうぞ、私のコードが掲載されています。 一応少数の問題でコード実行速度一位を取ったコードもあるのですこしは参考になるかもしれません(ご近所さんのある方はＡＯＪでコード実行速度一位とるなんて馬鹿でもできる笑いもの　ぷぷぷ　とか言ってました。世間的なＡＯＪの評価ってそんなものかもしれません)。 会津大学オンラインジャッジ復習 ここより以下は本当に個人的な雑記ですので気にしないでください。 もしも結婚できたら子供に言ってみたいこと ネットで好みのイラスト収集 新ギレン...
• プロジェクトオイラー問２６
  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...
• 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...
• プロジェクトオイラー問７２
  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勉強プロジェクトオイラー71～80
  プロジェクトオイラーの問題を堀江伸一さんがPrologで解くページ。 と書きましたが、下記リンク先サイトの方が私のコードよりずっと賢いのでそちらを参考にした方がよいです。 http //d.hatena.ne.jp/nineties/20110119 プロジェクトオイラーについては私のサイトよりこの人のサイトの方がずっと賢いです。 問い75はブロコット木を使えば早くなるとか、76や77は分割数と見るより、1～99までのコインを組み合わせたり素数を組み合わせる動的計画法とみるなど。 読めば目からうろこな発想でかかれています。 物事や問題をシンプルな話に変換できる能力、リンク先の人は私から見れば尊敬に値します。 プロジェクトオイラーの問題は問題番号が大きいほど難しくなるのですが、頭の悪い私でも問題番号100以下の簡単な問題なら解けます。 しかし同じ簡単な問題を解く...
• オイラープロジェクトカンニング履歴
  会津大学オンラインジャッジの問題とおなじくカンニングして解いたオイラープロジェクトの問題のリスト。 数学の問題集を扱ったサイトなので調べものして数学の知識を身につけながら解くのが正道な気がするが、一応出来るだけ自力で解きたいところ。 なのでカンニングして解いた問題のリストを掲載。 問い12 問題を解く方法がよくわからず掲示板で質問。 コードまで書いてもらうもコードの読解や原理がよくわからず考え中。 問い25 フィナボッチ数が１０００桁になるのは数列の何個目か？ 単純に1000ケタを超えるまでフィナボッチ数列を計算して解こうと挑戦。 ほとんどコードを書いたことがないＬｉｓｐで解こうと考え、初心者レベルのコードを記述してみて実行時エラー。 掲示板でloop中の（が一つ多いでのでsetqのあたりが余分に関数と解釈されてると指摘を受けそれを修正してアセプト。 修...
• プロジェクトオイラー問１３０
  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 か...
• プロジェクトオイラー問６
  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...
• prolog勉強プロジェクトオイラー201～210
  プロジェクトオイラーの問題を堀江伸一子と私がProlog言語で解くページ。 最近スランプ気味。 Problem 201 「唯一の和を持つ部分集合」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%20201 数の集合Aについて, sum(A)でAの要素の和を表す. 集合B = {1,3,6,8,10,11}を考えよう. Bの3要素の部分集合は20個あり, それぞれ和は以下になる. sum({1,3,6}) = 10, sum({1,3,8}) = 12, sum({1,3,10}) = 14, sum({1,3,11}) = 15, sum({1,6,8}) = 15, sum({1,6,10}) = 17, sum({1,6,11}) = 18, sum({...
• プロジェクトオイラー問８
  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に格納し、各素数それぞれについて*文字にチェンジした全パタ...
• prolog勉強プロジェクトオイラー11～20
  小学校の算数までしかできないと巷で評判の堀江伸一さんが、プロジェクトオイラーの問題にprolog言語で挑戦してみました。 ローカルな言語が集まるプロジェクトオイラーですが流石にprologで解いてるのは私だけかな、チェックはしてないけど。 Problem 11 「格子内の最大の積」 † http //odz.sakura.ne.jp/projecteuler/index.php?cmd=read page=Problem%2011 20*20の格子に数字が入ってるものが与えられる。 上下左右斜めの連続する4つの数字の積の最大値を求めよ。 解法 こういう問題はＰｒｏlogのありがたさが少しだけわかる。 失敗したらとりあえずエラー処理もいらずにバックトラックしてくれるというのはとても便利。 dyxs(1,0). dyxs(0,1). dyxs(1,1). ...
• プロジェクトオイラー問２
  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...
• プロジェクトオイラー問１１
  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%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...
• @wiki全体から「プロジェクトオイラー解説問38」で調べる

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