【VB.Net】最大公約数を求めるプログラムを考えてみる

どうも!リョクちゃです。

しばらく投稿が途絶えており、久々の投稿になります。

⇒ オンライン学習と趣味に費やしていました……。

そんなことはさておき、今回は最大公約数を求めるプログラムについて考え、

最終的にはプログラムによって2つの値の最大公約数を求める

といった内容を紹介していきます。

ちなみに前回はこちらでした。

ある数字の桁を抽出し、各桁の和を求めるアルゴリズムを考え、VB.Netで関数化してみました。関数化第1弾ということでプログラムコンテストでも取り扱われる計算問題を例に紹介をしていきます。



準備編

VisualStudio2019を使って、Windowsフォームアプリケーションを作成していきます。

最初の手順については、下記記事をご参照ください。

VisualStudioを使ってWindowsアプリケーションを開発していく流れを紹介します。 以前に、簡単にざっくりと教える機会があった...
スポンサーリンク




フォームの作成

以下のようなフォームを作成します。

①~⑦のコントロールについては以下の表のとおりです。

Noコントロール名前
1LabellbxValue_1
2LabellbxValue_2
3TextBoxtbxValue_1
4TextBoxtbxValue_2
5ButtonbtnMath
6LabellbxAnswer
7LabellbxGcd

各コントロールのフォントは、メイリオの16ptを設定しています。

実行環境

筆者の実行環境は、

  • VisualStudio2019
  • Windows 10 64bit
  • .Net Framework 4.5.1

になります。

※ Windows7 8 8.1でも動作はできますが、画面デザインの表示が変わるかもしれません。

アプリケーションの目的

「計算する」ボタンを押すことで、値1と値2に入力された数字(自然数)の最大公約数を

算出し、結果を最大公約数に表示するプログラムの作成を目的とします。

プログラム編

最大公約数とは?

最大公約数とは、WikiPediaで調べてみると

最大公約数(さいだいこうやくすう、greatest common divisor)とは、少なくとも一つが0ではない複数の整数公約数のうち最大の数を指す[1]

出典: フリー百科事典『ウィキペディア(Wikipedia)』

要するに複数の値を割ることができる共通の値の中でも値が最も大きいモノを指します。

例えば、12と16の最大公約数は4になります。

12と16では、約数(割ることのできる整数)はそれぞれ

12 → 1, 2, 3, 4, 6, 12

16 → 1, 2, 4, 8, 16

となり、12と16で共通している約数は、それぞれ1,2,4になります。

1,2,4は公約数(2つ以上の整数、この場合12と16の共通の約数)と呼ばれます。

最大公約数とは、これらの中で最も大きな値である4が最大の公約数になります。

このようにして2つの自然数から最大公約数を見つけていきます。

最大公約数を求める手順

  1. 2つの自然数の約数を算出する。
  2. 1で求まった約数から共通の約数を算出する。
  3. 2で見つかった共通の約数から最大の値を見つける。
  4. 3で見つかった最大の値が最大公約数になる。

1~4の手順を行えば、最大公約数を算出することができます。

では実際に1つずつ手順をプログラム化していきたいと思います。

最大公約数を算出するプログラムの作成

各手順について1つずつプログラム化する説明をしていきます。

2つの自然数から約数を算出

与えられた2つの自然数からそれぞれ約数を抽出していきます。

ちなみに約数は、ターゲットとなる自然数を割ることができる数が約数でした。

今回は、リスト型を使ってターゲットとなる自然数の約数を算出していきます。

割ることのできる数の範囲は、ターゲットとなる自然数以下が範囲になります。

ターゲットとなる自然数が最大の約数になりますので、それ以下としています。

したがって、1~ターゲットとなる自然数の範囲で割ることができるかできないかを

条件式で判断し、割り切れる場合はリスト型の変数へ代入をする。

これをターゲットとなる自然数の回数分、

繰り返し処理を行っていくプログラムを書けば、約数を算出することができそうです。

実際にコードを書いていくと、

このようになります。

今回は約数を算出する自然数が複数あるので、これを関数化します。

これで最大公約数を求める手順1をプログラム化することができました。

求まった約数から共通の約数を算出する

1で求まった2つの自然数の約数から共通の約数を見つけていきます。

それぞれの約数はリスト型変数で宣言をしているので、

リスト型で提供されている以下のメソッドを使用して、

リスト型変数にある共通の要素(値)をまとめていきます

リスト型変数1.FindAll(Address Of リスト型変数2.Contains)

FindAllメソッドはリスト型変数1と2の中で要素(値)を抽出する条件にあった時に

Trueで返すメソッドに基づいて、リスト型変数を作成し、

戻り値として返すメソッドになっています。

今回それぞれのリスト型変数で共通の要素を抽出したいので、

『抽出する条件にあった時にTrueで返すメソッド』には

リスト型変数.Containsメソッドを使用します。

実際にコードで書くと以下のようになります。

共通の約数から最大の値を見つける

最大の値を見つけるには、以下のメソッドを使用します。

リスト型変数.Max

Maxメソッドは、リスト型変数の要素のうち

最大の要素を返してくれる、便利なメソッドです。

ここで返された値が与えられた2つの自然数の最大公約数となります。

最後に求まった値を表示してあげれば、

2つの自然数の最大公約数を算出するプログラムの完成です。

お疲れ様です。



実行編

プログラム起動時

値1への値を入力

値2への値を入力

値1と値2の最大公約数を算出(結果表示)

別の値での算出

別解編

一方で当然過程を知らなくても最大公約数を算出するプログラムを作成することは可能です。

最大公約数の言葉の意味を知っていれば、できてしまいます。

最大公約数 → 割り切れる共通の約数の中で最大となる値

これに+α ひらめきがあれば先ほどの手順なんて不要でしょう。

実際に、こういった場合の手順を無視したパターンのコードを書くと、

以下のようになります。

最大公約数は2つの自然数同士が割り切れるまで計算していきます。

割り切れたら、最大公約数を求めることができます。

この時、割り切れた時の商が最大公約数ではなく、割り切れた時の分母となる値が

最大公約数となります。

これでも2つの自然数の最大公約数を算出することができます。

最後に

いきなり公式などに基づいて計算をして答えがわかっても、途中の過程がわからなければ

プログラム化をすることは難しいと思います。

このようにして過程を抽出していくことで、どのようにして答えが求められているのかが

見えてきます。

結果、プログラム化することが簡単になります。

癖として、計算過程を考え書いていく習慣をつけることで

様々な視点で答えを見つけられる力が養われていき、

難題に直面した場合でも冷静に物事を見ることができるのではないでしょうか。

答えは1つだとしても、答えに行き付く過程は1つとは限りません

公式をアプリケーション化するのは学習にもなるし、公式も覚えられるようになるので

結構便利なのではないかなと考えています。

まとめ

最大公約数を算出する手順(アルゴリズム)について考え、

プログラム化していく方法について紹介しました。

最大公約数以外にも最小公倍数や階乗など計算による答えを

プログラムによって求めたい場合にも応用はできるかと思います。

こうした計算法をプログラム化する上では、

まず、『答えがどのようにして求められているか計算過程を抽出』して

考えてみるのが良いです。

参考にしていただけたら嬉しいです。

最後までご覧いただきありがとうございます。

・参考になりそうなオススメVB.Net書籍

VisualBasic2019パーフェクトマスター (Perfect Master)

現場ですぐに使える! Visual Basic 2019 逆引き大全 500の極意

かんたん Visual Basic [改訂2版] (プログラミングの教科書)

作って覚えるVisual Basic 2019 デスクトップアプリ入門

スポンサーリンク