Photo by Alex Graves
秋山です。
paizaでは主にプログラミングスキルチェック問題の作成を担当しているので、アルゴリズムについて調べることもよくあります。
というわけで今回はみんな大好き？な、数学的なアルゴリズムについて書いてみたいと思います。
プログラミングの勉強を始めたばかりの人から「アルゴリズムってどうやって考える＆勉強するといいんですか？」と聞かれることもあるので、参考になればと思います。
■数列のアルゴリズム(フィボナッチ数、黄金比)
数字が 1,2,3,4,5,6....100 というように、最初の1から順に1ずつ増えていくというのも、ある意味アルゴリズムにのっとった数列であると言えます。
もう少し複雑な数列になると、paizaラーニングのアルゴリズム入門編でも出てくる「フィボナッチ数列」という数列があります。数学が苦手な人でも聞いたことある言葉ではないでしょうか…。（フィボナッチ数 - Wikipedia）
フィボナッチ数列とは、 1, 1, 2, 3, 5, 8, 13, 21,.... と続く、要は「前の2つの数字を足したもの」の数列で、アルゴリズムを考える上でのいろんな要素が詰まっています。
フィボナッチ数列は、自然界の現象に数多く出現するとされています。例えば、ヒマワリの種のらせんはフィボナッチ数の法則に従っているとする話があります。が、実際は数が小さいうちは法則通りでも、一定数を超えると種の並びに分岐などが起こったりして、必ずしもアルゴリズム通りではないそうですね。
Photo by Marcel Sigg
またフィボナッチ数列には、いわゆる「黄金比」と言われているものが隠れています。
黄金比とは
（1:1.6180……）になる比のことです。
これがフィボナッチ数列とどう関係あるかというと、例えば 1, 1, 2, 3, 5, 8, 13, 21,.... の8番目の 21 を 7番目の 13 で割ると、 1.61538461538 という、黄金比の近似値を求めることができます。もっと数列を進めれば、隣同時の比も、どんどん黄金比に近づいてきます。フィボナッチ数列で隣り合う数の比は、黄金比に収束するんですね。
黄金比は、古い建造物や絵画などにも現れていると言われていますが、偶然なのかこじつけなのかはよくわかりません。
ちなみに、MacBookPro13・15インチは解像度の比率が1.6です。テレビ放送や映像作品では、16:9が主流となっていて、1.77ぐらいの比率です。古いアナログ放送などは、4:3で1.33ぐらいの比率です。どの比率が見やすいかは個人差かもしれませんが、なんとなーく近い範囲なのが興味深いです。(これこそこじつけかもしれませんが……)
↓フィボナッチ数列を使ったプログラミングが学べるpaizaラーニングはこちら
アルゴリズム入門編: FizzBuzzとフィボナッチ数を学ぶのチャプター一覧 | プログラミング学習サービス【paizaラーニング】
■リュカのキャノンボール問題(平方ピラミッド問題)
フランスの数学者、エドゥアール・リュカが考案した「砲丸を並べて底面が正方形のピラミッドを作っていった時に、ピラミッドに使われた砲丸の総数が平方数になるピラミッドの段数を答えよ」という問題です。
（ちなみにリュカは先に紹介したフィボナッチ数列を研究したり、ハノイの塔のアルゴリズムを考案したりした人です。ハノイの塔についてはpaizaラーニングのアルゴリズム入門編でも説明しています。）
一見、砲丸を無限に積めるとなると、平方数も無限に出てきそうな気がしますよね。
でも、実際に平方数になるのは1段と24段の時だけなんです。これを証明するのはものすごく難しいので、力技で解いてみたのがこちら↓
少なくとも、1000段目までの間で、1段目と24段目以外に平方数は出てきませんでした。
無限に試しても平方数になるのは1段目と24段目だけ、という数学的証明について日本語で読める概要はこちら↓が参考になるかと思います。
平方ピラミッド問題と楕円曲線の整数点 石井夕紀子
■Googleの入社試験で出た？という噂がある数列問題(※真偽は不明です)
1, 11, 21, 1211, 111221, ...
10,9,60,90,70,66, ...
という数列において、「それぞれ次に来る数字は何か答えよ」という問題です。
これはちょっと意地悪な問題です。数列を読み上げるとわかりますね。
1 11 ← 1つの1(手前の数字を読み上げる) 21 ← 2つの1 1211 ← 1つの2 と 1つの1 111221 ← 1つの1 と 1つの2 と 2つの1
ということは、次の数は
3つの1 と 2つの2 と 1つの1 → 312211
となりますね。
次の数列も読み上げるとわかります。(英語で）
10 → ten 9 → nine 60 → sixty 90 → ninety 70 → seventy 66 → sixty-six
文字数に注目すると、1ずつ増えているのがわかります。
ということは、次の数は
ninety-six → 96
となります。
10 tenのところがoneやsix、同様に9 nineのところがfourやfiveでない理由は、その文字数中で最大の数……という意味らしいです。
もし本当に出題されていたとしたら、こういった点について具体的に説明できるかどうかを面接で見ていたんですかね。
※余談ですが、昔、数学の授業で 1, 3, 4, 6, 8, 10, 12 は何の数列？という問題を出されたことがあります。ヒントはこの数字は2011年廃止されて 1, 2, 4, 6, 8, 5, 7 に切り替わっているということ。
答えは地上波放送(首都圏)のチャンネル番号です。この話をすると歳がバレますね…。
■まとめ
というわけで数学的なアルゴリズムに触れてみました。
アルゴリズムはプログラミングを考えるときに重要ですし、いろんな法則があって楽しいので、少しでもアルゴリズムの勉強に興味を持ってもらえたらうれしいです。（数学的な話が多くて嫌いになったって言われたらどうしよう……）
フィボナッチ数やハノイの塔、またもっと単純なFizzBuzz（Fizz Buzz - Wikipedia）などは、paizaラーニングのアルゴリズム入門編でも学べます。ぜひごらんください！
paizaラーニングでは、paizaの人気美少女キャラクター霧島京子（cv:上間江望）が、かわいい声で優しく・楽しく・わかりやすくプログラミングを教えてくれます。
「霧島京子による1本3分程度のレッスン動画」に加え、「ブラウザ上でコードを書いて実行できるオンライン実行環境」「複数の練習問題」で、初心者でも無理なくプログラミングを習得することができます。
paizaではスキルのあるエンジニアがきちんと評価されるようにし、技術を追い続ける事が仕事につながるようにする事で、日本のITエンジニアの地位向上を図っていければと考えています。特にpaizaではWebサービス提供企業などでもとめられる、システム開発力や、テストケースを想定できるかの力(テストコードを書く力)などが問われる問題を出題しています。
テストの結果によりS,A,B,C,D,Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。
