分12今回は,この連載の第6回「ハサミを使うタイミング~どうやって端を見つけるの?─結城浩からの問題」の解説編です。挑戦していない方は,ぜひ先を読み進める前に挑戦してみてください。今回の問題では,「⁠コンパスとハサミを使って,長方形をチョキチョキと切る」というルールが与えられています。そのルールに注意しつつ,「⁠ハサミを使う回数をできるだけ少なくするような長方形を求めなさい」という問題ですね。このルールがいったい何を意味しているのかを見抜くことが,問題を解くうえで重要になってきます。今回のハサミ問題のキーワードは,2つあります。1つは「ユークリッドの互除法⁠」⁠。1つは「フィボナッチ数列」です。ユークリッドの互除法の代わりに「互いに素」や「最大公約数」がキーワードだと思ってもよいでしょう。コンパスとハサミの操作は「ユークリッドの互除法」になっている「ユークリッドの互除法」は,2つの正の整数が与えられた時,その最大公約数を求めるアルゴリズムです。アルゴリズムを学ぶほとんどの人が最初に学ぶアルゴリズムであるうえ,“⁠世界で最古のアルゴリズム⁠”といってよい歴史的なものです。ユークリッドの互除法は,以下のようなアルゴリズムです。ユークリッドの互除法(手続き)じつは,今回の問題の「コンパスとハサミを使った操作」は,ユークリッドの互除法そのものなのです。長方形の縦と横を「与えられた正の整数」だとし,問題文に与えられている操作を行っていくと,ハサミを使わずに終わった「最後の長方形」の短辺は,最大公約数になるのです。「⁠コンパスとハサミを使う」という図形的な操作で最大公約数が求められるというのは,おもしろいですね。コンパスとハサミの操作がユークリッドの互除法になっているかを,くわしく見ていきましょう。長方形Aの長辺をmとし,短辺をnとします。短辺nを半径にして,コンパスで四分の一円を描けるだけ描き,最後に長方形Bが残ったとします。n⁠)⁠」に相当します。n)の長方形を得る操作になります。これを,長辺がちょうど短辺の倍数になるまで繰り返すのですが,これはまさにユークリッドの互除法にほかなりません。今回の問題でいう「ハサミの回数」は,「⁠余りを求める回数(割り算の回数⁠)⁠」に相当します。ここまでは,アルゴリズムを学んだことのあるプログラマならばよく理解できるはずです。ここまでの理解だけで,今回のハサミ問題を解くのは難しいでしょう。いうのは,適当な長方形を作って試しても,なかなか40回という数にまで至らず,意外と少ない回数で操作が終了してしまうのです。言い換えればこれは,ユークリッドの互除法は「非常に効率のよいアルゴリズム」ということでもあります。ハサミの回数が少ないということは,割り算の回数が少なくてすむということになるからです。「ハサミ40回」の逆から考えるのがポイントじつは,今回の問題を解くためには,ユークリッドの互除法を使う必要はまったくありません(!⁠)⁠。今回の問題を解くときには,最初から「ハサミ40回」に挑戦するのではなく,少ない回数から考えるのがポイントです。逆に考えるということです。短辺が1のとき,どんな長方形でもハサミ0回で終了します。短辺が2のとき,長辺が3の長方形のときハサミ1回で終了します。ハサミ1回の最小長方形(a)は,2×3です。短辺が3のとき,コンパスを1回だけ使って,残りの長方形がさっきの(a)になるようにすれば,ハサミ2回の最小長方形(b)が作れます。長辺を3+2=5にすればいいということです。ハサミ2回の最小長方形(b)は,3×5です。操作を繰り返していけばいいと予想できます。それは言い換えると「長辺が次の短辺になり,長辺と短辺の和が次の長辺になるような長方形を作る」という操作の繰り返しです。言葉で説明するとわかりにくいですが,これは次の図のような「らせん」を描くことに相当します。長方形が作り出すらせんじつは,このような操作は「フィボナッチ数列」を作り出していることにほかなりません。これが今回の問題の2つ目のキーワードです。フィボナッチ数列を作り出せば正解が見えるフィボナッチ数列というのは,以下の漸化式で定義された数列です。3,4,5,...)具体的には,フィボナッチ数列は,以下の数列になります。フィボナッチ数列の計算(手続き)ハサミ1回の最小長方形は2×3。F[4])に相当します。ハサミ2回の最小長方形は3×5。F[5])に相当します。今回の問題を解くためには「フィボナッチ数列を作り出していけばいい」ということになります。以下,ハサミn回を使う長方形を列挙してみます。ハサミ1回2×3ハサミ2回3×5ハサミ3回5×8ハサミ4回8×13ハサミ5回13×21ハサミ6回21×34ハサミ7回34×55ハサミ8回55×89...ハサミ39回165580141×267914296ハサミ40回267914296×433494437よって,正解は以下になります。267914296x433494437この解答が最小面積になることは,数学的にも証明できます。ガール」シリーズ作者。プログラミング言語入門書,IT技術書,数学入門書などの著書多数。2019」を開催しました。DAY1・DAY2の様子を注目セッションとともにお伝えします。LINEのエンジニア3名がイベントに先駆けて見どころを紹介します。コードの安全性・安定性を高める開発サイクル~テスト管理の効率を上げ,脆弱性診断を自動で行う~本連載では,連載「業務を改善する情報共有の仕掛け」を受けつつ,安全性・安定性を加えた開発サイクルについて考えていきます。若者世代から圧倒的な人気を誇るライブ配信&動画投稿コミュニティアプリ「MixChannel」(ミクチャ)の裏側(レコメンドシステムやサーバサイド開発など)について解説していきます。その他の連載CSS3アニメーションでつくるインターフェイス表現CSS3によるアニメーション表現を紹介していきます。その中でも,幅広い読者に応用してもらえるだろうインターフェイスを主なお題とします。MySQL道普請便り本連載では,MySQLを使ったアプリ開発・運用に関するノウハウをご紹介していきます。RecipeUbuntuの強力なデスクトップ機能を活用するための,いろいろなレシピをお届けします。JavaScriptセキュリティの基礎知識JavaScriptに関するセキュリティ上の問題はどこで発生し,どうすれば防ぐことができるのか?について解説していきます。〜システムをきちんと運用するための基礎知識システムは「作って終わり」ではなく,運用の中でさまざまな問題が発生します。問題の発生に備えて事前にどのような対応をしておくべきなのか,問題発生時に何をしなければならないのか,ポイントを解説していきます。きたみりゅうじの聞かせて珍プレーソフトウェア開発の現場で体験したトホホな失敗,思わずうなる珍プレーをきたみりゅうじ氏が四コママンガで紹介。Linuxのメンテナンスの傍ら,Linuxやオープンソースソフトと日々を過ごす著者が,その魅力とつきあい方を,エッセイ風味でお届けします。PRESS特別編集部員,さわやか笑顔のスーパーハカーはまちちゃんとネット大好き14歳わかばちゃんが,毎号,読者の皆さんから寄せられたおたよりを紹介します。皆さんの日頃の悩みにも答えちゃいますよ。]メールでのお知らせメールで次の案内をお送りしております。メールの配信を希望する方は,利用したい項目をチェックしてメールアドレスを入力し,[登録]ボタンをクリックしてください。UPDATES[ほぼ週間に1回]新刊メールマガジン[ほぼ週間に1回]電脳会議の各号案内[ほぼ1ヵ月半に1回]※変更する場合や停止する場合は,登録情報変更ページをご覧ください。※登録いただいたメールアドレスには,そのお知らせ以外,配信いたしません。Ltd.ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。