[ProjectEuler]1~10問目までの参考になったコードや考え方、関数などまとめ

以前プロジェクトオイラーを解いて、思考過程・コード・解答などをブログに載せていたが、ある時「答えとか書いて公開しないでね」と公式サイト上に乗っていることに気づいた。

なので記事を削除したが、解くきっかけになった考え方、当時の感想などをこの記事にまとめる。ほぼ自分の復習用。

言語はVisual Basicを使用。初心者、独学。

はじめに

シーザー暗号の問題を出してくれた後輩が、またプログラミングの問題を出してくれた。

数学の問題をプログラミングで解くサイト「Project Euler.net」。

Register」で”Username”と”Password”を入力し、簡単なユーザー登録を済ます。

これで問題が解けたかどうかをチェック(解答)できるようになる。

project euler解答

そして、何人が問題を解けたか、問題の難易度がわかる。

解けた問題に関しては、解答pdfとその問題に対するフォーラムがアンロックされる。(問題を解けた人が作成した、様々な言語で書かれたコードなどが読める。)

他の人が書いたコード読むの面白い。色々な解き方があると実感する。

Problem1 Multiples of 3 and 5

※「英語の勉強になるから」と、原文を読んで問題に挑戦した。そうしたらグーグル翻訳で”below”が”以下”と表示されたので、相当苦労してしまった。
次からは英語で何言っているのか考えた後に、日本語訳を見よう…。

日本語訳→Project Euler puwiki

・~or below(5 or below ⇒ 5以下)

・below~(below 5 ⇒ 5未満)

この英語表現できる? 「未満」「以下」「以上」はどういうの?

※すぐにわかった。以前同じような問題、fizz-buzz問題やったことあったので、その解き方の応用でいける。

※論理和の”Or”を使用する。

※自分だけ答えがわかればいいのなら、Console.WriteLineが便利。MsgBoxはコピペが使えない。

Problem2 Even Fibonacci numbers

※すでに使っている変数に新しく代入するという発想

※この問題から得たこと。

→なるべく問題は簡単に考える。一番簡単なところを実際に手を動かして作る。「フィボナッチ数列の法則性」とか難しく考えてしまうと解けない。1,1が2になって、1,2が3になるように素直に簡単に作ってみる。

→頭で考えない。紙を使って書き出してみる。頭の中で考えるとこんがらがるので、紙上で一つ一つ着実に考える。

Problem3 Largest prime factor

素因数分解か。やり方自体を忘れている。

素因数分解のやり方を分かりやすく解説!計算問題も付いてます

こちらのサイトを参考にして、やり方を思い出す。

基本操作としては、「元の自然数が1になるまで、素数で割ることを繰り返す」

数値が素数であるか判定する

プログラム作成には、こちらのサイトが参考になった。

プログラムを作成した際には

GoTo ステートメント

を使用したが、今思い返すとあまり良くない。とても読みづらいコードになってしまう。bool型を使用したほうがわかりやすい。

コード行にラベルを付けるには
ソースコード行の先頭に、識別子、コロンの順に配置

Problem4 Largest palindrome product

※problem3までやって学習したように、難しく考えちゃだめだ。簡単な、できることからやってみよう。

※変数の名前が適当だし、相当読みづらいと思う。これ、わかりやすく書かないと、後から見返したときに何やってるかわからないな。見やすく書くような方法とか調べないと。

コードの中にコメントを書いたり、変数の名前をわかりやすく書かないとなぁ。

変数の宣言する位置も全部一番最初にしてしまうと、超分かりづらい。

文字を取り出すLEFT関数、RIGHT関数、MID関数

Variant型 【 バリアント型 】

Variant型とは、Visual Basicなどに用意されているデータ型の一つで、どのような型のデータでも格納できる特殊な型。Variant型の変数は代入時に代入する値のデータ型がチェックされ、それに合うデータ型が自動的に選択される。“variant”は「異なる」「多様な」などの意味を持つ英単語。

→文字列を桁数指定で置換できますか?

ちなみにVBなら.NETでも
Mid(BeforeStr, 3, 1) = “2”
の記述が可能です。これはBeforeStr自体を書き換えます。

これは非常に役に立った。

Mid(変数, 3, 1) = “2”

”変数”の”左3文字目”から”1文字”を”2″に書き換える。

→【VB】Mid/MidB関数

Left()関数、right()関数と似たような結果をえる場合が特に参考になった。

→VB.NETのデータ型変換関数による変換

Problem5 Smallest multiple

※難しい…。最小公倍数を求めればいいんだけど。

とりあえず例題の「1~10で2520」をどうやって求められるか、法則性などを見つけるため、紙に書き出して考えてみる。

… 紙に書き出してみたら、法則性を発見。プログラムを作成する前に、紙と電卓で問題が解けた。

※これで終了なのもの味気ないので、プログラムも作ってみる。

これプログラム作るほうが大変だぞ。いまいち理解しづらい・慣れない配列を使わないと…。

・宣言しただけだと、値は0。いくら掛け合わせても0のまま。気をつける。当たり前なんだけど、意識してなかった。

・ミスったとき、上手く動かなかったときは、具体的にどう動くかを変数に実際の数を代入して頭の中で少し追ってみる。ぼーっと「問題はなにか?」なんて考えず、より具体的に手や頭を動かす。

・上手くいかなかったときでも、答えが「1」とか「0」になるのならば、ある程度原因が絞れる。初期値が0だったり、値がリセットされていなかったり、上手く掛け合わされてなかったり。ミス・エラーのパターンを覚えることを意識をすると良いかも。

・配列難しい。添字に変数が入ると混乱する。慣れ…かなぁ。

Dim ステートメント (Visual Basic)

Problem6 Sum square difference

前回、problem5のほうが圧倒的に大変だった。前回が出来たら、今回のもできる。基本的な配列を使用する問題だと思う。(あくまで俺の思いついた/行った解法ならばの話。考え方・解き方は無数にある)

特に詰まることなく出来た。

Problem7 10001st prime

※うん。これproblem5のやつ少し手直しすればできる。配列を使う必要もない。答えが10001だから、配列(0)の気配を感じたが、そんなこともなかった。微妙なひっかけを食らった気分。

※このあたりから条件分岐にbool型を使用。

【Python入門】ブール型(Boolean)の用途と使い方を学ぼう!

Problem8 Largest product in a series

string型で宣言した後、Asc関数でinteger配列に格納

Asc関数は文字コード(ASCIIコード)で返す

→この辺の考え方は以前のシーザー暗号を解いたときのが参考になった。

13個の連続した数字の掛け算を算出し、既に算出した値よりも大きい場合は答えを入れ替える。

Problem9 Special Pythagorean triplet

繰り返し処理を3つ。多階層の繰り返し、入れ子/ネスト。

for文 – 入れ子(ネスト)多階層の繰り返し処理

外側のループのカウンタ「i」が1つ増加する間に内側のループのカウンタ「j」がひと回り(0〜9)します。

まだ強く意識すべき段階までは成長できていないが、「答えさえ出ればいいや」という考え方をちょっとずつ整えていったほうがいい。

ソースコードの見やすさ、処理の簡単さ、変数名のわかりやすさ等を気をつけていきたい。

ただ、まだそんな高度なレベルじゃあないので、基本的には解けりゃあいいの気持ちで。

Problem10 Summation of primes

以前作成した素数判定のプログラムを使ったが、めちゃくちゃおそい。2000000回の繰り返し処理はきちぃ。

こちらのサイトが参考になった→素数判定いろいろ – シンプルな判定と、素数の分布

超絶早くなる。解けた。

シェアする

  • このエントリーをはてなブックマークに追加

フォローする