Photo by sarah_poo
こんにちは。谷口です。
paizaでは多数のプログラミングスキルチェック問題を公開しています。
問題はS・A・B・C・Dと5つのランクにわかれているので、プログラミング初心者の方でもDランクから無理なく挑戦していただくことができます。
ただ、プログラミングの勉強を始めたばかりの方から「簡単な問題は解けるけど、なかなかランクをアップさせることができない」「少し難しい問題になると、途端に解き方がわからなくなってしまう…」とご相談を受けることもあります。
そこで、paizaラーニングでは「アルゴリズム入門編」という動画講座を公開しています。
プログラミング問題を題材に、単純な解き方だけでなく、コードの改善の仕方やアルゴリズムの考え方などをあわせて解説していますので、「アルゴリズムについて学びたい」「プログラミング問題に挑戦してみたい」といった方の参考になると思います。
今回はその「アルゴリズム入門編」から、フィボナッチ数を表示するプログラムの作り方についてご紹介します。
※今回はJavaで解いていますが、解き方やアルゴリズムに関してはどの言語でも通じます。
※この記事で解説している解き方は、paizaのスキルチェック問題で言うとC〜Bランク程度です。
フィボナッチ数とは
フィボナッチ数とは、イタリアの数学者レオナルド・フィボナッチ氏にちなんで名づけられた数で
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…
というように、一定の規則にしたがってだんだん大きくなっていく数列です。
規則については数列を見ていただければわかると思いますが、最初は0、次は1、それから前の2つの0と1を足して1、また前の2つを足して2、また前の2つを足して3、5、8…というように、前の2つの数を足しています。これを繰り返すことで、だんだん大きな数値が並ぶ数列が続いていきます。
今回は、これを算出するコードを考えてみます。
フィボナッチ数をシンプルに考えてみる
たとえば「5」を指定すると、5番のフィボナッチ数が出力される…というふうに、指定した位置のフィボナッチ数を出力するプログラムを作ってみます。
最初はとりあえず、シンプルで愚直な解き方でやってみましょう。
まず、プログラムを作成する準備をしておきます。
public class Main { public static void main(String[] args) throws Exception { int number= 0; System.out.println(number + ":" + fibonacci(number)); } // 指定番のフィボナッチ数を求める public static long fibonacci(int num) { return num; } }
number変数で、求めたいフィボナッチ数の位置を指定しています。とりあえず0を代入しておきます。
printlnメソッドでは、number変数と一緒に fibonacci というメソッドの戻り値を出力するようにします。fibonacciメソッドは、指定番のフィボナッチ数を求めるメソッドです。いったん引き数をそのまま返すようにしておきます。このプログラムを実行すると、当然ですが 0：0 と表示されます。
次に、fibonacciメソッドの中身を作っていきます。
フィボナッチ数は0番から始まるようになっていますから、0番のフィボナッチ数の場合は0をそのまま返せばいいですね。
public class Main { public static void main(String[] args) throws Exception { int number = 0; System.out.println(number + ":" + fibonacci(number)); } // 指定番のフィボナッチ数を求める public static long fibonacci(int num) { if(num == 0) { return 0; } return num; } }
続いて、1番のフィボナッチ数を戻すようにします。1番のフィボナッチ数の場合も、1をそのまま返せばいいですね。
public class Main { public static void main(String[] args) throws Exception { int number = 0; System.out.println(number + ":" + fibonacci(number)); } // 指定番のフィボナッチ数を求める public static long fibonacci(int num) { if(num == 0) { return 0; } if(num == 1) { return 1; } return num; } }
2番目以降のフィボナッチ数を求めるには、その位置までループを使って計算していきます。
public class Main { public static void main(String[] args) throws Exception { int number = 0; System.out.println(number + ":" + fibonacci(number)); } // 指定番のフィボナッチ数を求める public static long fibonacci(int num) { if(num == 0) { return 0; } if(num == 1) { return 1; } long fibo = 0; long fibo_0 = 0; long fibo_1 = 1; for (int i = 1; i < num; i++){ fibo = fibo_0 + fibo_1; fibo_0 = fibo_1; fibo_1 = fibo; } return fibo; } }
まず、フィボナッチ数を求める変数として、long型でfibo変数を用意しています。それから、fibo_0 = 0、fibo_1 = 1とします。これが最初の2つのフィボナッチ数になります。
次に、for文を使って1からnumまで順番にループを回していきます。 このときfibo変数には、fibo_0とfibo_1を足してあげます。
それから新しいfibo_0として、fibo_1を代入します。fibo_1には、計算したfibo変数の値を代入します。この2つの変数の値を次の繰り返し処理で使っていきます。
ループを抜けたら、戻り値としてfibo変数を返します。
このまま順番に試していくのは大変ですから、ループ処理で結果を出力してみましょう。
0番から50番までフィボナッチ数を出力するように、for文を追加してあげます。number変数は、iに変更します。
public class Main { public static void main(String[] args) throws Exception { int number = 50; for (int i = 0; i <= number; i++) { System.out.println(i + ":" + fibonacci(i)); } } // 指定番のフィボナッチ数を求める public static long fibonacci(int num) { if(num == 0) { return 0; } if(num == 1) { return 1; } long fibo = 0; long fibo_0 = 0; long fibo_1 = 1; for (int i = 1; i < num; i++){ fibo = fibo_0 + fibo_1; fibo_0 = fibo_1; fibo_1 = fibo; } return fibo; } }
これで実行すると、0から50までのフィボナッチ数が表示されます。
というわけで、一応フィボナッチ数を計算できるコードができましたが、このままではあまり効率がよくないですね。
毎回0番から順にフィボナッチ数を計算しているので、たとえば5番のフィボナッチ数を求めるためには、0から5番までのフィボナッチ数を計算し、6番のフィボナッチ数を求めるためには、また0から6番までのフィボナッチ数を計算する…というように、同じ計算を何度もくり返してしまっています。
配列を使って解いてみる
では次に、途中の計算結果を配列に格納するようにしましょう。
先ほどは指定した位置のフィボナッチ数を求めるプログラムを作りましたが、今回は最初から順番にフィボナッチ数を計算していきます。
まずnumber変数を用意して、フィボナッチ数を求める範囲を指定します。とりあえず、50まで計算してみましょう。
それから、0から50までの数値を順番に作るプログラムを作成しておきます。
public class Main { public static void main(String[] args) throws Exception { int number = 50; for (int i = 0; i <= number; i++){ System.out.println(i); } } }
次にフィボナッチ数を格納しておく配列を用意し、0番のfibo配列には0、1番の配列には1を、初期値として代入しておきます。
public class Main { public static void main(String[] args) throws Exception { int number = 50; long fibo[] = new long[number + 1]; fibo[0] = 0; fibo[1] = 1; for (int i = 0; i <= number; i++){ System.out.println(i); } } }
では、2番以降のフィボナッチ数を計算してみましょう。
ループの中でif文を使って、i変数が2以上だったらi番のfibo配列にひとつ前のfibo配列を足し、2つ前のfibo配列の値を代入して、このfibo配列の値を出力します。
public class Main { public static void main(String[] args) throws Exception { int number = 50; long fibo[] = new long[number + 1]; fibo[0] = 0; fibo[1] = 1; for (int i = 0; i <= number; i++){ if(i >= 2) { fibo[i] = fibo[i - 1] + fibo[i - 2]; } System.out.println(i + ":" + fibo[i]); } } }
このプログラムを実行すると、0から50までのフィボナッチ数が出力されます。
このプログラムでは配列を使っているので、二重ループによる余分な処理がありません。N番目のフィボナッチ数を求める場合には、最初のプログラムと計算量に差はありませんが、0番目～50番目のフィボナッチ数を出力するという場合なら、最初よりも計算量が少なくなって、高速に実行できます。
まとめ
というわけで、愚直にループを使う方法と、もう一歩進んで配列を使う方法でフィボナッチ数を出してみました。
フィボナッチ数はこれ以外にも、再帰を使ったやり方でも計算することができます。また、「ビネの公式」という、そもそもフィボナッチ数を求めるための公式もあり、それをコードに組み込んで算出することもできます。
再帰やビネの公式を使った解き方は、paizaラーニングの「アルゴリズム入門編」で解説しています。
「なんだ、公式があるならそれを使えばいいじゃないか」と思うかもしれませんが、プログラミングはひとつの解き方さえできればそれでOKというものではありません。むしろ、さまざまな解き方やアルゴリズムを知って、実際に解いてみることで理解が深まります。（↓ビネの公式ってこういうのなので、使いこなすには数学的な前提知識も必要になりますし…）
また、まずは「愚直でシンプルな解き方」が理解できていないと、そこから発展させて「ではもっと効率よいコードにするにはどうしたらよいか？」を考えることもできなかったりしますので、ひとつの問題に対しても、ぜひいろいろな解き方で挑戦してみてください。
「アルゴリズム入門編」ではもっと簡単な「FizzBuzz」や、もう少し難しい「ハノイの塔」や「巡回セールスマン問題」の解き方なども解説しています。
「プログラミングの勉強を始めたばかりで全然わからなかった」という方はFizzBuzzから、また「簡単すぎる、もっと難しい問題がいい」という方はハノイの塔や巡回セールスマン問題の動画レッスンに挑戦していただくと、無理なく楽しくアルゴリズムを学べるかと思います。
paizaラーニングのアルゴリズム入門編はこちら
FizzBuzzやフィボナッチ数、ハノイの塔といったプログラミング問題は、就職・転職の技術面接などでもよく出題されます。
「もっといろいろなプログラミング問題を解いてみたい」という方は、スキルチェック問題に挑戦してみてください。
詳しくはこちら
「paizaラーニング」では、未経験者でもブラウザさえあれば、今すぐプログラミングの基礎が動画で学べるレッスンを多数公開しております。
詳しくはこちら
そしてpaizaでは、Webサービス開発企業などで求められるコーディング力や、テストケースを想定する力などが問われるプログラミングスキルチェック問題も提供しています。
スキルチェックに挑戦した人は、その結果によってS・A・B・C・D・Eの6段階のランクを取得できます。必要なスキルランクを取得すれば、書類選考なしで企業の求人に応募することも可能です。「自分のプログラミングスキルを客観的に知りたい」「スキルを使って転職したい」という方は、ぜひチャレンジしてみてください。
詳しくはこちら
