Project Euler Problem11~15(Python)
自分なりの解答と考え方を載せていきます。
少し雑なのでコメントしてくれれば詳しく載せます。
ミスやアドバイスもコメントお願いします!!
Problem 11 「格子内の最大の積」
縦 横 斜め右 斜め左の4パターンを計算して、その中で一番でかいやつを答えにした。注意した点は斜めの書き方と範囲ですね。配列の考え方は下図に貼ります(ipadアプリを使ってみました)
問題の格子をどのようにして配列に入れるかが最初一番わからなかったです(笑)
Answer: 70600674
Problem 12 「高度整除三角数」
三角数は下図のように1,2,3と加算される数です。なぜ三角数というかは形を見てもらえば理解できると思います。余談ですが四角数、五角数などもあります。
Answer: 76576500
Problem 13 「大きな数の足し算」
私がpythonが不慣れというのもあり、最後の結果をきれいに出す方法がわからず強引に答えを出してます。ただすべてを足し、その合計を出して上十桁をコピーするだけです。(笑)
Answer: 5537376230
Problem 14 「最長のコラッツ数列」
初期値から1に至るまでの最長の数列ですね。設定を見る限り初期値が奇数であることが予想できます。というのも奇数の場合初期値より大きくなる可能性があるからです。(問題文の13→40にあるように)
それを踏まえて1に至るまで網羅的に計算していきます。
Answer: 837799
Problem 15 「格子経路」
これはまず前提として格子経路のルートの数を求める方法を知っていると有利な気がします。詳しいことは調べると出るのですが結論から言うとCombinationを使います。
40C20を求めると答えになります。この先使うことが有るかもしれないのでCombinationの関数を作っておきました。(Pythonのライブラリでもしかしたらあるかもしれないから作る必要ないかも笑)
Answer: 137846528820
Project Euler Problem1~10(Python)
自分なりの解答と考え方を載せていきます。
少し雑なのでコメントしてくれれば詳しく載せます。
ミスやアドバイスもコメントお願いします!!
Problem1「3と5の倍数」
1<n<1000で3,5の倍数を足して、3,5の共通公倍数である15の倍数を引く。
答え 233168
Problem 2 「偶数のフィボナッチ数」
フィボナッチ数の問題です。自然を表す数列いわれたり、整数の数列なのに一般項に無理数があったり色々不思議な数列です。
まずは項の値が400万以下のフィボナッチ数列を出し、そのうえで2で割れる値を足していきます。
答え 4613732
Problem 3 「最大の素因数」
① 力任せに2から割っていく。
今回は計算量が少なく結果がすぐ出るが、forの末端など工夫するところは大有り。
ちなみにこのコードでは素因数が1つしかなくその素因数が3乗以上の時結果が誤って出る。。
答え 6857
Problem 4 「最大の回文積」
① forで3桁×3桁をして結果を文字列に入れそれを反転しても同じだったら良い
答え 906609
Problem 5 「最小の倍数」
① まずは1から20までの中の素数を出す。その次にその素数の累乗数を出す。
あとはそれらを全部かける。
関数Primecounterで2から√n+1の数までを割り、割り切れなかった場合素数としてTrueを返しています。n-1まで割るのではなく√n+1までにすることで計算量を減らしています。
Answer: 232792560
Problem 6 「二乗和の差」
これは単純にforで二乗和と和を計算して、計算するだけですね。
Answer: 25164150
Problem 7 「10001番目の素数」
problem5で作った素数カウンターを使い、10001番目の素数がきた時にforを終わらします。
Answer: 104743
Problem 8 「数字列中の最大の積」
まず数字を読み込みそれをいったん文字列にして一つずつ配列に入れていきます。
あとは配列を一個ずつづらして13個の連続する積の最大値を求めます。
正直問題の解き方より、数字の読み込み作業に戸惑いました(笑)
Answer: 23514624000
Problem 9 「特別なピタゴラス数」
二重forをつかいa,bに数値を代入していく、a,bを決めればcは1000-a-bと定義できるのであとはピタゴラ数になる組み合わせになるまで待つだけですね。
Answer: 31875000
Problem 10 「素数の和」
これもProblem5の関数を使いforで200万まで回していきます。
ただ時間がかかるので、これからも素数を使うと考えると素数の配列を作っていた方がよさそうですね(; ; )
Answer: 142913828922