FreeStyleWiki

プロジェクト・オイラー(096-100)

[プロジェクト・オイラー]

プロジェクト・オイラー(096-100)

  Problem 96

Probem 「数独」

 "数独"(日本語で数字を配置するという意味)とは人気があるパズルの名前である.
 起源は不明だが, その評判はラテン語で"Squares"と呼ばれる同様な, そしてはるかに難しいパズルを考案した
 レオンハルト・オイラーの貢献によるものに違いない.
 しかしながら, "数独"パズルの目的は
 それぞれの行, 列が3×3の枠を含む9×9の格子の空白(もしくは0)をそれぞれ1から9の数字で置き換えることである.
 下に, 一般的なパズルの開始状態とその解答の例がある.うまく作られている"数独"パズルは,
 選択肢を消去するために"仮定とテスト"方式を用いる必要があるかもしれないが,
 ただ一つの解を持ち, 論理によって解くことができる(これについては様々な意見がある).探索の複雑さがパズルの難易度を決定する;
 上に挙げた例は, 単純で直接的な推論によって解く事ができるため, 簡単であると考えられる.6kバイトのテキストファイルsudoku.txt(右クリックで,"名前をつけてリンク先を保存")
 にはただ一つの解を持つ, 様々な難易度の50の"数独"パズルが含まれている(上の例題はこのファイルにおける最初のパズルである).50すべてのパズルを解き, それぞれの解答の左上隅にある3桁の数の合計を求めよ;
 例えば483は上の解答例の左上隅の3桁の数である.

Answer

+ 解答

  Problem 97

Probem 「大きな非メルセンヌ素数」

 100万桁を超える初めての素数は1999年に発見された. これはメルセンヌ素数であり, 2^6972593-1 である. 実際, 2,098,960桁ある.
 それ以降も, より多くの桁になるメルセンヌ素数 (2p-1の形の数) が他にも発見されている.
 しかし, 2004年に, 非常に大きな非メルセンヌ素数が発見された. これは2,357,207桁の数であり, 28433×2^7830457+1である.この素数の末尾10桁を答えよ.

Answer

+ 解答

  Problem 98

Probem 「アナグラム平方数」

 CARE という単語の各文字をそれぞれ 1, 2, 9, 6 に置き換えることによって, 平方数 1296 = 36^2 ができる.
 注目すべきことに, 同じ数字の置換をつかうことにより, アナグラムの RACE も平方数 9216 = 96^2 をつくる. 
 CARE (と RACE) を平方アナグラム単語対と呼ぼう. 先頭のゼロは許されず, 異なる文字が同じ数字をもつこともないとする.
 約 2,000 個の一般的な英単語を含む 16K のテキストファイルwords.txt (右クリックして "名前をつけてリンク先を保存") を用いて,
 平方アナグラム単語対をすべて求めよ (回文となる単語はそれ自身のアナグラムとはみなさない).
 そのような対のメンバーから作られる最大の平方数は何か?
 注: 作られるアナグラムは, すべて与えられたテキストファイルに含まれている.

words.txt(8)

Answer

+ 解答

  Problem 99

Probem 「最大のべき乗」

 指数の形で表される2つの数, 例えば 2^11 と 3^7, の大小を調べることは難しくはない. 
 電卓を使えば, 2^11 = 2048 < 3^7 = 2187 であることが確かめられる.
 しかし, 632382^518061 > 519432^525806 を確認することは非常に難しい (両者ともに300万桁以上になる).
 各行に1組が書かれている1000個の組を含んだ22Kのテキストファイル base_exp.txt から, 最大の数が書かれている行の番号を求めよ.
 注: ファイル中の最初の二行は上の例である.

p099_base_exp.txt(9)

Answer

+ 解答

  Problem 100

Probem 「組み合わせの確率」

 箱の中に15個の青い円盤と6個の赤い円盤からなる21個の色のついた円盤が入っていて, 
 無作為に2つ取り出すとき, 青い円盤2つを取り出す確率P(BB)はであることがわかる.
 無作為に2つ取り出すとき, 青い円盤2つを取り出す確率がちょうど1/2となるような次の組み合わせは, 
 箱が85個の青い円盤と35個の赤い円盤からなるときである.
 箱の中の円盤の合計が1012 = 1,000,000,000,000を超えるような最初の組み合わせを考える. 
 箱の中の青い円盤の数を求めよ.

Answer

+ 解答