Реализации алгоритмов/Алгоритм Евклида: различия между версиями

Материал из Викиучебника — открытых книг для открытого мира
Содержимое удалено Содержимое добавлено
Новые реализации на разных диалектах BASIC
Строка 64: Строка 64:
DO WHILE B% > 0
DO WHILE B% > 0
A% = A% MOD B%
A% = A% MOD B%
'Для вычитания заменить предыдущую строку следующими:
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'DO WHILE A% >= B%
'DO WHILE A% >= B%
' A% = A% - B%
' A% = A% - B%
Строка 73: Строка 73:
END IF
END IF
B% = B% MOD A%
B% = B% MOD A%
'Для вычитания заменить предыдущую строку следующими:
'Для вычитания убрать предыдущую строку и раскомментировать следующие:
'DO WHILE B% >= A%
'DO WHILE B% >= A%
' B% = B% - A%
' B% = B% - A%
Строка 92: Строка 92:
Do While b > 0
Do While b > 0
a = a Mod b
a = a Mod b
'Для вычитания заменить предыдущую строку следующими:
убрать предыдущую строку и раскомментировать следующие
'Do While a >= b
'Do While a >= b
' a = a - b
' a = a - b
Строка 101: Строка 101:
End If
End If
b = b Mod a
b = b Mod a
'Для вычитания заменить предыдущую строку следующими:
убрать предыдущую строку и раскомментировать следующие
'Do While b >= a
'Do While b >= a
' b = b - a
' b = b - a
Строка 131: Строка 131:
Do While b > 0
Do While b > 0
a = a Mod b
a = a Mod b
'Для вычитания заменить предыдущую строку следующими:
убрать предыдущую строку и раскомментировать следующие
'Do While a >= b
'Do While a >= b
' a -= b
' a -= b
Строка 137: Строка 137:
If a = 0 Then Return b
If a = 0 Then Return b
b = b Mod a
b = b Mod a
'Для вычитания заменить предыдущую строку следующими:
убрать предыдущую строку и раскомментировать следующие
'Do While b >= a
'Do While b >= a
' b -= a
' b -= a

Версия от 22:48, 27 июля 2019

Реализации алгоритма Евклида для вычисления НОД — наибольшего общего делителя (англ. GCD — greatest common divisor) двух целых чисел на различных языках программирования.

Реализации

Assembler

ARM

Вычитание, цикл:

loop	CMP Ri, Rj		; проверка условий NE (i != j), GT (i > j) и LT (i < j);
	SUBGT Ri, Ri, Rj	; если GT, выполняется i = i-j;
	SUBLT Rj, Rj, Ri	; если LT, выполняется j = j-i;
	BNE loop		    ; если NE - переход на метку loop.

Z80

Вычитание, цикл:

GCD_DEHL:               ; CALL Inputs: HL,DE; Output: DE
        AND     A       ; сброс CF
LOOP:
        SBC     HL,DE   ; совмещение трёх в одном - одного сравнения и поочередно двух вычитаний.
        RET     Z       ; минимизация общего размера, поэтому в цикле.
        JR      NC,LOOP
        ADD     HL,DE   ; откат лишнего вычитания
        EX      DE,HL
        JR      GCD_DEHL

BASIC

Оригинальный BASIC

Цикл, вычитание (операция нахождения остатка MOD отсутствовала в этой версии языка):

10 INPUT "Two integer numbers", A, B
20 PRINT "GCD("; A; ", "; B,") = ";
30 LET A = ABS(A): LET B = ABS(B)
40 IF B = 0 THEN GOTO 90
50 IF A >= B THEN LET A = A - B: GOTO 50
60 IF A = 0 THEN LET A = B: GOTO 90
70 IF B >= A: LET B = B - A: GOTO 70
80 GOTO 40
90 PRINT A
100 END

GW-BASIC и совместимые диалекты

Цикл, деление с остатком либо вычитание (при указанных заменах в коде).

10 INPUT "Two integer numbers", A%, B%
20 PRINT "GCD("; A%; ", "; B%; ") = ";
30 A% = ABS(A%): B% = ABS(B%)
40 WHILE B% > 0
50 A% = A% MOD B% 'Для вычитания заменить на WHILE A% >= B%: A% = A% - B%: WEND
60 IF A% = 0 THEN A% = B%: GOTO 90
70 B% = B% MOD A% 'Для вычитания заменить на WHILE B% >= A%: B% = B% - A%: WEND
80 WEND
90 PRINT A%

QuickBasic версий < 4.0, Turbo Basic

Цикл, деление с остатком либо вычитание (при указанных заменах в коде).

DEF FNGCD%(A%, B%)
	A% = ABS(A%)
	B% = ABS(B%)
	DO WHILE B% > 0
		A% = A% MOD B%
		'Для вычитания убрать предыдущую строку и раскомментировать следующие:
        'DO WHILE A% >= B%
		'	A% = A% - B%
		'LOOP
		IF A% = 0 THEN
			FNGCD% = B%
			EXIT DEF
		END IF
		B% = B% MOD A%
		'Для вычитания убрать предыдущую строку и раскомментировать следующие:
        'DO WHILE B% >= A%
		'	B% = B% - A%
		'LOOP 
	LOOP
	FNGCD% = A%
END DEF

PowerBASIC, QBASIC, QuickBasic версий ≥ 4.0, Visual Basic

В следующих примерах используется тип Integer (стандартное целое); вместо него можно применять также тип Long (длинное целое).

Цикл, деление с остатком либо вычитание (при указанных заменах в коде):

Function GCD(a As Integer, b As Integer) As Integer
	a = Abs(a)
	b = Abs(b)
	Do While b > 0
		a = a Mod b
		убрать предыдущую строку и раскомментировать следующие
		'Do While a >= b
		'	a = a - b
		'Loop
		If a = 0 Then
			GCD = b
			Exit Function
		End If
		b = b Mod a
		убрать предыдущую строку и раскомментировать следующие
        'Do While b >= a
		'	b = b - a
		'Loop
	Loop
	GCD = a
End Function

Рекурсия, деление с остатком:

Function GCD(a As Integer, b As Integer) As Integer
    If b = 0 Then
        GCD = Abs(a)
    Else
        GCD = GCD(b, a Mod b)
    End If
End Function

VB.NET

В следующих примерах используется тип Integer (стандартное целое); вместо него можно применять любые другие целочисленные типы платформы .NET.

Цикл, деление с остатком либо вычитание (при указанных заменах в коде):

Shared Function GCD(ByVal a As Integer, ByVal b As Integer) As Integer
	a = Math.Abs(a)
	b = Math.Abs(b)
	Do While b > 0
		a = a Mod b
		убрать предыдущую строку и раскомментировать следующие
		'Do While a >= b
		'	a -= b
		'Loop
		If a = 0 Then Return b
		b = b Mod a
		убрать предыдущую строку и раскомментировать следующие
        'Do While b >= a
		'	b -= a
		'Loop
	Loop
	Return a
End Function

Рекурсия, деление с остатком:

Function GCD (a As Integer, b As Integer) As Integer
	If b = 0 Then Return Math.Abs(a)
	Return GCD(b, a Mod b)
End Function

C/C++

C: Тип IntType должен быть задан как:

typedef int IntType; /* Вместо int можно подставить любой другой целочисленный тип */

C++: Любую из нижеприведённых функций (включая abs) следует предварить строкой:

template < typename IntType >

Для корректной обработки отрицательных чисел все последующие примеры на C/C++ используют функцию вычисления модуля числа:

IntType abs (IntType value) {
    return (value < 0) ? -value : value;
}

Деление с остатком, цикл:

IntType gcd (IntType a, IntType b) {
    IntType c;
    while (b) {
        c = a % b;
        a = b;
        b = c;
    }
    return abs(a);
}

Более короткое решение:

IntType gcd (IntType a, IntType b) {
    while (b)
        b ^= a ^= b ^= a %= b;
    return abs(a);
}

Деление с остатком, рекурсия:

IntType gcd (IntType a, IntType b) {
   return (b == 0) ? abs(a) : gcd(b, a % b);
}

Вычитание, цикл:

IntType gcd (IntType a, IntType b) {
    a = abs(a);
    b = abs(b);
    while (a != b) {
        if (a > b)
            a -= b;
        else
            b -= a;
    }
    return a;
}

C#, Java[1]

Вместо long можно использовать и другие целочисленные типы — byte, int и т. д.

Деление с остатком, цикл:

static long GCD (long a, long b)
{
    while (b != 0)
        b = a % (a = b);
    return a < 0 ? -a : a;
}

Деление с остатком, рекурсия:

static long GCD (long a, long b)
{
    return b == 0 ? (a < 0 ? -a : a) : GCD(b, a % b);
}

Erlang

Деление с остатком, рекурсия:

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, (A rem B)).

F#

Деление с остатком, рекурсия:

let rec gcd a b =
    match b with
    |0 -> a
    |b -> gcd b (a % b)

Forth (диалект RetroForth)

Деление с остатком, рекурсия:

: GCD ( n1 n2 -- n ) tuck mod 0; GCD ;

Go

Тип IntType определён как:

type IntType = int // Вместо int можно подставить любой другой целочисленный тип

Для корректной обработки отрицательных чисел все последующие примеры на Go используют функцию вычисления модуля числа:

func IntAbs(value IntType) IntType {
	if value < 0 {
		return -value
	}
	return value
}

Деление с остатком, цикл:

func GCD(a, b IntType) IntType {
	for b != 0 {
		a %= b
		if a == 0 {
			return IntAbs(b)
		}
		b %= a
	}
	return IntAbs(a)
}

Вычитание, цикл:

func GCD(a, b IntType) IntType {
	a = IntAbs(a)
	b = IntAbs(b)
	for b != 0 {
		for a >= b {
			a -= b
		}
		if a == 0 {
			return b
		}
		for b >= a {
			b -= a
		}
	}
	return a
}

Haskell

Деление с остатком, рекурсия:

gcd :: Integral a => a -> a -> a
gcd 0 0 = error "НОД от 0 и 0 не определён."
gcd x y = gcd' (abs x) (abs y)
    where gcd' x 0 = x
          gcd' x y = gcd' y (x `rem` y)

Pascal

Тип IntType определён как:

type IntType = Integer; { Вместо Integer можно подставить любой другой целочисленный тип }

Деление с остатком, цикл:

function GCD (a, b: IntType): IntType;
begin
    while a * b <> 0 do
       if a > b then
           a := a mod b
       else
           b := b mod a;
    GCD := Abs(a + b)
end;

Более быстрый алгоритм:

function GCD (a, b: IntType): IntType;
var c: IntType;
begin
    while b > 0 do
    begin
        c := a mod b;
        a := b;
        b := c
    end;
    GCD := Abs(a)
end;

Деление с остатком, рекурсия:

function GCD (a, b: IntType): IntType;
begin
   if b = 0 then
       GCD := Abs(a)
   else
       GCD := GCD(b, a mod b)
end;

Perl

Деление с остатком, рекурсия:

sub gcd {
    return  $_[0] != 0  ?  gcd ( ( $_[1] % $_[0] ), $_[0] )  :  $_[1];
}

PHP

Деление с остатком, цикл:

function gcd ($a, $b) {
    while ($a <> 0 && $b <> 0) {
        if ($a > $b)
            $a = $a % $b;
        else
            $b = $b % $a;
    }
    return abs($a + $b);
}
echo gcd(5, 3);

Prolog

Деление с остатком, рекурсия:

?GCD(a, b, x)

GCD(0, b, b) <-
GCD(a, 0, a) <-
GCD(a, b, x) <- a >= b, m is a mod b, GCD(m, b, x)
GCD(a, b, x) <- a < b, m is b mod a, GCD(a, m, x)

w:SWI-Prolog

Деление с остатком, рекурсия:

gcd(0, B, B).
gcd(A, 0, A).

gcd(A, B, X) :-  A >= B, M is A mod B, gcd(M, B, X).
gcd(A, B, X) :-  A < B, M is B mod A, gcd(A, M, X).

Python

Деление с остатком, цикл:

def gcd (a, b):
    while b:
        a, b = b, a % b
    return abs(a)

Деление с остатком, рекурсия:

def gcd (a, b):
    return abs(a) if b == 0 else gcd(b, a % b)

Ruby

Деление с остатком, цикл:

def gcd (a, b)
    a, b = b, a % b until b.zero?
    a.abs
end

Деление с остатком, рекурсия:

def gcd (a, b)
    return a.abs if b.zero?
    gcd(b, a % b)
end

Вычитание, цикл:

def gcd (a, b)
    a = a.abs
    b = b.abs
    if a > b
        a -= b
    else
        b -= a
    end while a != b
    a
end

Rust

Деление с остатком, цикл:

extern crate num;

use self::num::FromPrimitive;
use std::ops::Rem;


pub fn gcd <IntType> (mut a: IntType, mut b: IntType) -> IntType
where IntType: Copy + FromPrimitive + PartialEq + Rem<Output = IntType> {
    let zero = FromPrimitive::from_u32(0u32).unwrap(); // Обобщённая константа 0
    let mut c: IntType;
    while b != zero {
        c = a % b;
        a = b;
        b = c;
    }
    a
}

Вычитание, цикл:

use std::ops::SubAssign;


pub fn gcd <T: Copy + PartialOrd + SubAssign> (mut a: T, mut b: T) -> T {
    while a != b {
        if a > b {
            a -= b;
        } else {
            b -= a;
        }
    }
    a
}

Scheme

Вычитание, рекурсия:

(define gcd (lambda (a b)
  (if (> a b) (gcd (- a b) b)
     (if (< a b) (gcd a (- b a))
        a))))

Shell

Деление с остатком, рекурсия:

gcd () {
    n = 1 a = $1 b = $2
    if [[ $a -ne 0 ]]
    then
        gcd $(( $b % $a )) $a
        let "n = $?"
    else
        let "n = $b"
    fi
    return $n
}

gcd $1 $2
echo "Greatest common divisor is $?"

Глагол

Деление с остатком, цикл:

ЗАДАЧА НОД (a, b: ЦЕЛ): ЦЕЛ;
УКАЗ
    ПОКА (a # 0) И (b # 0) ВЫП
        ЕСЛИ a < b ТО
            b := b ОСТАТОК a
        ИНАЧЕ
            a := a ОСТАТОК b
        КОН
    КОН;
    ВОЗВРАТ МОДУЛЬ(a + b)
КОН НОД;

Программируемые микрокалькуляторы «Электроника»

Использование: <первое число> В↑ <второе число> В/О С/П (НОД на индикаторе).

МК-61 / 52 / 152 / 161 / 163 / 1152

Деление с остатком, цикл. Корректно обрабатываются любые целые числа (включая 0 и отрицательные). В вычислениях участвуют только регистры стека.

00. Fx≠0   01. 13     02. ↔      03. В↑     04. FВx    05. ÷      06. FВx    07. ↔      08. K[x]   09. ×
10. −      11. Fx=0   12. 02     13. +      14. K|x|   15. С/П

Б3-34, МК-54 / 56 / 61 / 52 / 152 / 161 / 163 / 1152

Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.

00. −      01. Fx≠0   02. 12     03. Fx<0   04. 09     05. FВx    06. ↔      07. /−/    08. −      09. FВx
10. БП     11. 00     12. FВx    13. С/П

Б3-21, МК-46 / 64, МС-1103

Вычитание, цикл. Корректно обрабатываются любые целые неотрицательные числа. В вычислениях участвуют только регистры стека X и Y.

00. Px≠0   01. ↔      02. −      03. Px≥0   04. F1     05. ↔
10. −      11. /−/    12. ↔      13. Px=0   14. Peⁱˣ   15. ↔
20. С/П

См. также

Ссылки

  1. Для соответствия правилам оформления кода Java метод следует переименовать в gcd и перенести { в конец предыдущей строки