2基本情報技術者試験 対策 最大公約数 ユークリッド互除法 ソート

2基本情報技術者試験 対策 勉強中 40代中年ががんばる 最大公約数 ユークリッド互除法 ソート

最大公約数の求め方

最大公約数とは
2つ以上の整数に共通な約数のうちで最も大きな約数のことです。まあなんか難しい感じですが、素因数分解した時に出てくる数字で互いに共通した大きな数と考えれば良いのでしょうかね。
小学生か中学生のときに習った記憶は小さい数でひたすら割っていった気がしますが時間がかかりました。

ユークリッド互除法による計算方法は
二つの自然数AとBがあり、AがBよりも大きいとして
AをBで割った時の余りCを求めます。
次に
Bを余りCで割ります。
このように割り切れるまで続けるとその時の割ったCが最大公約数になります。
余りではなく割る数になります。

例えば
45、54の最大公約数を求めると
54/45は余りが9です。
今度は45/9で計算します。商は5で余りがゼロになり、割り切れました。この時の割った9が最大公約数になります。商が最大公約数になるのではありませんので誤解しないようにしましょうかね。
一応試し算をしましょう。
45の約数は1、3、5、9、15、45
54の約数は1、2、3、6、9、18、27、54
で共通する公約数は1、3、9ですね。
最も大きな数は9ですから、9が最大公約数です。
他の例です

ソートの種類、クイックソート、シェルソート、バブルソート、ヒープソート

プログラムでソートはよく学習しますが使ったことは一度もない。実践でソートすることは私はありませんでした。人生もソートしたい気分です。

バブルソート

隣り合う数字を比較し入れ替え続けます。これが一番わかりやすいソートです。泡のようにとなりで比較して弾けるイメージです。
n^2

クイックソート

(クイックにソートしたいので基準値を決める)
基準値を決めて大きければ右へ小ければ左に移す。

ヒープソート

再帰呼び出しを使わずに二分木ヒープを用いて比較する

シェルソート

ある一定間隔おきに数字を取り出した部分列から間隔を縮めて間隔が1になるまで繰り返す

こちらの記事もどうぞ