ENGLISH「拓く。」クイズ 解答 情報科学科
ヒントに従って、 11,188,907 を 2,798,251 で割ってみましょう。 すると、商が 3、あまりが 2,794,154 と計算できます。
11,188,907 ÷ 2,798,251 = 3 … 2,794,154
次に 2,798,251 を 2,794,154 で割ってみます。以下のように 商が 1、あまりが 4,097 と計算されます。
2,798,251 ÷ 2,794,154 = 1 … 4,097
さらに 2,798,251 を 4,907 で割ると、商は 682 であまりが 0 となり、割り切れました。
2,794,154 ÷ 4,097 = 682 … 0
このとき 4,097 が 11,188,907 と 2,798,251 の最大公約数と なります。小学生でもできる割り算３回で解答を得ることがで きました。
このように２個の整数の最大公約数を効率よく求める計算の手順 （アルゴリズムと呼ばれます）は「ユークリッドの互除法」と呼 ばれています。
この手順で最大公約数が求められる理屈を簡単に説明しておきま しょう。整数 a を 整数 b で割るとき、商を q、あまりを r と しておきます。
a ÷ b = q … r
このとき、「a と b の最大公約数」は「b と r の最大公約数」と等しいことが証明できます。
この事実を用いると、本問では
「11,188,907 と 2,798,251 の最大公約数」
は
「 2,798,251 と 2,794,154 の最大公約数」
と等しく、さらに
「 2,794,154 と 4,097 の最大公約数」
とも等しいことになるのです。
2,794,154 は 4,097 で割り切れるため、結局 4,097 が最大公約数
となるのです。
|
前のページ 「拓く。」クイズ 解答 生命科学科 |
コンテンツのトップ |
次のページ 「拓く。」クイズ 解答 人間システム工学科 |