高校時代の位相除算と位相減算のアルゴリズムについて

[[356850]]

プログラミングの本質はアルゴリズムから来ており、アルゴリズムの本質は数学から来ています。プログラミングとは、数学の問題をコーディングすることにすぎません。「----ルンセン」

小学校でよく聞く質問をしましょう。「2 つの整数の最大公約数を求めるにはどうすればいいですか?」

私はアルゴリズムに関する質問をかなりたくさん見てきましたが、そのうちのいくつかはデータ構造やアルゴリズムの概要ではなく、高校の数学から来ていることがわかりました。

高校数学の必修第３回では、「繰り上がり割り算の方法と引き算の方法」という非常に重要な知識ポイントがあります。

ユークリッドの互除法は、ユークリッドの互除法とも呼ばれ、2 つの正の整数の最大公約数を見つけるアルゴリズムです。これは紀元前 300 年にまで遡る最も古い既知のアルゴリズムです。

昔、「劉徽」という有名な数学者がいました。引き算の方法は、中国の数学者劉徽の著書『九章算術』に記録されています。

ローリング分割法

ユークリッドの互除法は最大公約数を見つけるアルゴリズムです。 2 つの数値が与えられれば、ペア (a、b) を形成できます。ユークリッドの互除法は、「2 つの整数の最大公約数は、小さい方の数値の最大公約数と、その 2 つの数値を割った余りに等しい」という原理に基づいています。

a と b の最大公約数を求めるには、a と b のうち小さい方の数を割ります。余りが残ります。余りが 0 の場合、小さい方が最大公約数です。

余りが 0 でない場合は、この余りを使用して大きい数を置き換え、最大公約数が見つかるまでこれを繰り返します。

たとえば、以下ではローリング除算法を使用して 100 と 24 の最大公約数を見つけます。最大公約数は 25 であることは明らかです。

 100 = 24 * 4 + 4
 24 = 4 * 6 + 0

明らかに、4 と 6 の間の小さい数 4 は、100 と 24 の最大公約数です。

次に、ローリング除算法を使用して、55 と 120 の最大公約数を見つけます。明らかに、最大公約数は 5 です。

 55 = 120 * 0 + 55
 120 = 55 * 2 + 10
 55 = 10 * 5 + 5

明らかに、10 と 5 の間の小さい数 5 は、55 と 120 の最大公約数です。

アルゴリズムのフローチャート（Baidu百科事典より）

したがって、2 つの数を m と n とします。2 つの数のどちらが最大であるかを判断する必要はありません。

2 つの数値 m と n の最大公約数を見つける手順は次のとおりです。

m を n で割ります。m%n=r (r>=0)。 r=0 の場合、min(m,n) となります。

r≠0の場合はnをrで割り、r=0になるまでこのサイクルを繰り返します。

次に、ローリング除算法を使用してコーディングします。

 gcd(a, b)を定義します。
    # bが0の場合はループを終了する
    一方、b:
        # ループ代入
        a、b = b、a%b
返す
印刷(gcd(100,25)) #25

ユークリッドの互除法は、本質的には、2 つの大きな数の公約数 gcd(a,b) を、小さい方の数と 2 つの数の余りの最大公約数 gcd(b,a%b) に変換し、b が 0 になるまで繰り返し、その後、最大公約数 gcd(gcd(a,b), 0) として a を返す再帰コードです。

したがって、次の式が得られます: gcd(a,b) = gcd(b,a%b) = gcd(gcd(a,b), 0)

 gcd(a, b)を定義します。
 b != 0 の場合は gcd(b, a % b)を返し、それ以外の場合はa を返す
     
印刷(gcd(55,120)) #5

以下はPythonコードをJavaコードに変換するものです

/**
 * @author ランセン
 * @日付2020/12/9 13:18
 */
パブリッククラスGcd{
公共 静的void main(String[] args) {
 gcd = gcd(91, 49);
        System.out.println(gcd ) ;
    } 
 
    プライベートスタティック  int gcd( int a, int b) {
        b != 0 の間
整数 温度= a % b;
            a = b;
            b =温度;
        }
を返します。
    }
 }

以下は、Python コードを JavaScript コードに変換するものです。

関数gcd(a, b){
    while(b != 0){
温度= a % b;
       a = b;
       b =温度;
    };
を返します。
 } 
      
コンソール.log((gcd(55,120))) #5

損失を減らす方法

昔、私の国にも最大公約数問題を求めるアルゴリズムがあり、それは引き算の手法でした。

『九章算術』には、互いに引き算して最大公約数を求める手順が書かれています。半分にできる場合は半分にし、半分にできない場合は分子と分母の数字を分母に置き換え、大きい数から小さい数を引き算し、互いに引き算して等しい数を求め、次に等しい数で引き算します。

減算法は、数の割り切れる性質から来ています。つまり、2 つの整数 a と b が両方とも c で割り切れる場合、a と b の差も C で割り切れます。

たとえば、98 と 63 の最大公約数を見つけます。

まず、98 と 63 を見てみましょう。63 は偶数ではないので、大きい数から小さい数を引くと、98-63=35、63-35=28、35-28=7、28-7=21、21-7=14、14-7=7 となります。

「このとき、減数と差は 7 に等しい」ので、98 と 63 の最大公約数は 7 です。

たとえば、260 と 104 の最大公約数を見つけます。

まず、260 と 104 という 2 つの数字を見てみましょう。どちらも偶数なので、2 ずつ簡略化して 130 と 52 になります。

簡略化後、130 と 52 も偶数になります。さらに 2 を加えて簡略化すると、65 と 26 になります。この時点では 65 は偶数ではないので、大きい数から小さい数を引きます。65-26=39、39-26=13、26-13=13。

このとき、減数と差は等しくなります。上の数から2を2つ取り除くと、得られる数は13です。したがって、260と104の最大公約数は2×2×13=52です。

したがって、削減方法は次の通りではありません。

両方の整数が偶数の場合は、両方の整数が偶数でなくなるまで 2 減算を使用し、手順 2 に進みます。両方の整数が偶数でない場合は、手順 2 に直接進みます。
大きい数から小さい数を引き、その差が小さい数とちょうど等しくなったら停止します。それ以外の場合は、より小さい数値と差に対してこのプロセスを繰り返します。
ステップ 1 で取り消された 2 の数とステップ 2 で得られた差の積は、元の 2 つの整数の最大公約数です。

次に、位相減算技術を使用してコーディングします。

 '' '
 @著者: ランセン
@WeChat: リュウ・ランセン
@WeChat 公式アカウント: Python の王
@CSDN: https://blog.csdn.net/weixin_44510615
 @Github: https://github.com/MaoliRUNsen
 @日付：2020/12/9
 '' '
 MaxCommDivisor(m, n)を定義します。
    # 両方の整数が偶数の場合は、2 つの簡略化を使用し、簡略化の回数を記録します。
インデックス= 1
    m % 2 == 0かつn % 2 == 0 の場合:
        ｍ = ｍ / 2
        ｎ = ｎ / 2
インデックス=インデックス* 2
    # 大きい数から小さい数を引くので、m と n の大きさを判断し、m が最大であることを確認する必要があります。
    m < nの場合:
        m, n = n, m
    # 大きい数から小さい数を引きます。差が小さい数とちょうど等しい場合は、停止します。それ以外の場合は、より小さい数値と差に対してこのプロセスを繰り返します。
    ただし、m - n != n の場合:
        差分 = m - n
        diff > nの場合:
            m = 差分
それ以外：
            メートル = メートル
            n = 差分
n *インデックスを返す  
 
印刷(MaxCommDivisor(24, 12)) #12