paiza開発日誌

IT/Webエンジニア向け総合求人・学習サービス「paiza」(https://paiza.jp ギノ株式会社)の開発者が開発の事、プログラミングネタ、ITエンジニアの転職などについて書いています。

プログラミング問題を作るエンジニアが、数学的な面白いアルゴリズムを紹介してみた

f:id:paiza:20170117123901j:plain
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つの数字を足したもの」の数列で、アルゴリズムを考える上でのいろんな要素が詰まっています。

フィボナッチ数列は、自然界の現象に数多く出現するとされています。例えば、ヒマワリの種のらせんはフィボナッチ数の法則に則っているとする話があります。が、実際は数が小さいうちは法則に則っていても、一定数を超えると種の並びに分岐などが起こったりして、必ずしもアルゴリズム通りではないそうですね。

f:id:paiza:20170117115746j:plain
Photo by Marcel Sigg

またフィボナッチ数列には、いわゆる「黄金比」と言われているものが隠れています。

黄金比とは
f:id:paiza:20170117121146p:plain
(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ラーニングこちら
アルゴリズム入門編1:FizzBuzzとフィボナッチ数を学ぶ-paiza動画ラーニング | ITプログラマー・エンジニア転職の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 に切り替わっているということ。

答えは地上波放送(首都圏)のチャンネル番号です。この話をすると歳がバレますね…。

■まとめ

というわけで数学的なアルゴリズムに触れてみました。

アルゴリズムはプログラミング考えるときに重要だし、いろんな法則があって楽しいので、少しでもアルゴリズムの勉強に興味を持ってもらえたら嬉しいです。(数学的な話が多くて嫌いになったって言われたらどうしよう……)

フィボナッチ数やハノイの塔、またもっと単純なFizzBuzzFizz Buzz - Wikipedia)などは、paizaラーニングアルゴリズム入門編でも学べます。

本日から2017年1月23日までの期間限定で、FizzBuzzやフィボナッチ数について学べる「アルゴリズム入門1無料で見放題になっています。来週2017年1月24日から30日までの一週間は、ハノイの塔について学べる「アルゴリズム入門2」の無料公開を予定しています。

無料公開の期間を過ぎると有料に戻ってしまいますので、ぜひこの機会にアルゴリズムを学んでみてください!
paiza.jp

アルゴリズムの学習レッスン動画が期間限定無料で見放題!プログラミング学習コース

f:id:paiza:20170117132313p:plain
paizaでは、未経験者でも動画を通してプログラミング等が学べる「paizaラーニング」を公開しております。

paizaラーニングでは、本日から2017年1月23日までの期間限定で「アルゴリズム入門1」を無料公開中

来週2017年1月24日から30日までの一週間は、「アルゴリズム入門2」の無料公開を予定しています。

paizaラーニングでは、paizaの人気美少女キャラクター霧島京子(cv:上間江望)が、かわいい声で優しく・楽しく・わかりやすくプログラミングを教えてくれます。「霧島京子による1本3分程度のレッスン動画」に加え、「ブラウザ上でコードを書いて実行できるオンライン実行環境」「複数の練習問題」で、初心者でも無理なくプログラミングを習得することができます。

paiza.jp




paizaではスキルのあるエンジニアがきちんと評価されるようにし、技術を追い続ける事が仕事につながるようにする事で、日本のITエンジニアの地位向上を図っていければと考えています。特にpaizaではWebサービス提供企業などでもとめられる、システム開発力や、テストケースを想定できるかの力(テストコードを書く力)などが問われる問題を出題しています。

テストの結果によりS,A,B,C,D,Eの6段階でランクが分かります。自分のプログラミングスキルを客観的に知りたいという方は是非チャレンジしてみてください。

http://paiza.jp


プログラミング入門講座|paizaラーニング

PHP入門編Ruby入門編Python入門編Java入門編JavaScript入門編C言語入門編C#入門編アルゴリズム入門編