Algorytm Euklidesa pozwala wyznaczyć największy wspólny dzielnik dwóch dodatnich liczb całkowitych. Jest to jeden z najstarszych znanych algorytmów numerycznych. Euklides zamieścił go ok. 300 roku p.n.e. w „Elementach” – jednym z najsłynniejszych dzieł naukowych ludzkości.
PHP
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
<?php function algorytm($a,$b) // funkcja pobiera dwie liczby dodatnie { while ($b != 0) { // dopóki b jest różne od zera $modulo = $a % $b; // oblicza resztę z dzielenia a przez b $a = $b; // a zastępujemy b $b = $modulo; // b zastępujemy resztą
modulo } return $a; // jeżeli b = 0 zwraca wynik a } echo algorytm(100,15); // podstawiamy dowolne wartości a,b /* wspólny dzielnik = 5 */ ?> |
JAVA
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
public class Algorytm { int algorytm(int a, int b) { while (b != 0) { int modulo = a%b; a = b; b = modulo; } return a; } public static void main(String args[]) { Algorytm Euklides = new Algorytm(); System.out.println(Euklides.algorytm(100,15)); } } |
DELPHI / PASCAL
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
program Euklides; {$APPTYPE CONSOLE} uses SysUtils; var a,b,modulo:integer; begin a:=100; b:=15; while (b <> 0) do begin modulo:= a mod b; a:= b; b:= modulo; end; Writeln(a); Readln; end. |
Więcej informacji na pl.wikipedia.org/wiki/Algorytm_Euklidesa