ソフトウェア工学的には羽生善治の「5二銀」は最善手ではない!?　東工大入試問題をプログラムで解く（2/4 ページ）

公開 2020年11月04日 10時02分

更新 2021年03月17日 15時43分

著者

山浦恒央　東海大学大学院組込み技術研究科非常勤講師（工学博士）

[TechFactory]

印刷する連載新着通知を受け取る

問題1の解答＆解説

　入試会場でこの問題を見た受験生は、こう考えるでしょう。「5の2乗の25のように、2乗した数は、ガウス数は[√25]＝5なので割り切れる。他の数はどうか。雰囲気をつかむため、少しだけ試してみよう」。

　上記のように、√25から√35まで、ガウス数が5となり、25、30、35がガウス数で割り切れます。ここで、大きな数、例えばガウス数が89になると、√7921から√8099まで調べねばならず、「大きな数字がたくさんあって、超面倒だぁ」と憂鬱になります。

　この問題を作った東工大の先生の意図は、「1, 2, ... 99, 100の2乗を全てチェックするのは大変だ。そこで、何らかの法則を自分で見つけて解いてほしい」でしょうね。

　「何らかの法則」とは、羽生五段の5二銀のような「妙手」です。入試問題ですので、「妙手」が存在することは保証されていますが、妙手を探すにはいろいろ考えねばなりません。

　入試では、「10000もの数をチェックするのは超級大変でしょう？」ですが、プログラミングでは、最も壁の厚い正面からぶつかって全数をチェックする戦法は、とても単純で簡単で、誰でも思いつきます。全数チェックは、ソフトウェアでのアルゴリズムの基本です。

　プログラミングで解くには、1から10000まで全数で平方根のガウス数を計算して、割り切れる個数をカウントアップすればいいのです。具体的には以下の手順となります。

「変数」に1、「割り切れた個数」に0を代入する。
「変数」の「平方根」を計算する。
「平方根」の小数点以下を切り捨て、「ガウス数」を求める。
「ガウス数」が「変数」の約数なら（割り算の余りがゼロなら）、「割り切れた個数」に1を加算する。
「変数」に1を加える。
「変数」が10000以内なら、「2.」へ戻る。10000を越えたら、「割り切れた個数」を出力して終了する。

　巻末の「参考ソースコード1」にプログラムを掲載しました。平方根を求める関数（sqrtf）や割り算の余りを求める関数（%）で、整数と実数の型のキャスティングをせねばならず、泥臭いコーディングになって、お恥ずかしい限りです。コメント行やprintfで分かりやすくコーディングしていますが、実質的なステップ数は15行。所要時間は10分ほどです。プログラミングに慣れた人は、もっと短時間で短くスタイリッシュに書けるでしょう。

　東工大の入試問題の答えは、以下のように、298個です。

次ページへ「桶狭間の戦い」症候群～問題2

印刷する

組み込みエンジニアの現場力養成ドリル

このコラムでは、組み込みエンジニアが日々の開発で実際に遭遇する「小さなトラブルを」取り上げ、演習形式で解説します。

連載新着通知を受け取る

この連載の記事をもっと見る

この記事の著者

山浦恒央　東海大学大学院組込み技術研究科非常勤講師（工学博士）

1977年、日立ソフトウェアエンジニアリングに入社、2006年より、東海大学情報理工学部ソフトウェア開発工学科助教授、2007年より、同大学大学院組込み技術研究科准教授、2016年より非常勤講師。主な著書・訳書は、「Advances in Computers」（Academic Press社、共著）、「ピープルウエア第2版」「ソフトウェアテスト技法」「実践的プログラムテスト入門」「デスマーチ第2版」「ソフトウエア開発プロフェッショナル」（以上、日経BP社、共訳）、「ソフトウエア開発 55の真実と10のウソ」「初めて学ぶソフトウエアメトリクス」（以上、日経BP社、翻訳）。