Difference between revisions of "Greatest common divisor/fi"
From Free Pascal wiki
Jump to navigationJump to searchm (Fixed syntax highlighting; deleted category included in page template) |
|||
(2 intermediate revisions by 2 users not shown) | |||
Line 1: | Line 1: | ||
− | {{ | + | {{Greatest common divisor}} |
+ | |||
= Suurin yhteinen tekijä = | = Suurin yhteinen tekijä = | ||
Line 10: | Line 11: | ||
== Funktio GreatestCommonDivisor == | == Funktio GreatestCommonDivisor == | ||
− | <syntaxhighlight> | + | <syntaxhighlight lang=pascal> |
function GreatestCommonDivisor(a, b: Int64): Int64; | function GreatestCommonDivisor(a, b: Int64): Int64; | ||
Line 27: | Line 28: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | == | + | Tai toinen vaihtoehtoinen tapa |
+ | |||
+ | <syntaxhighlight lang=pascal> | ||
+ | function GreatestCommonDivisor_EuclidsSubtractionMethod(a, b: Int64): Int64; | ||
+ | //only works with positive integers | ||
+ | begin | ||
+ | if (a < 0) then a := -a; | ||
+ | if (b < 0) then b := -b; | ||
+ | if (a = 0) then Exit(b); | ||
+ | if (b = 0) then Exit(a); | ||
+ | while not (a = b) do | ||
+ | begin | ||
+ | if (a > b) then | ||
+ | a := a - b | ||
+ | else | ||
+ | b := b - a; | ||
+ | end; | ||
+ | Result := a; | ||
+ | end; | ||
+ | |||
+ | </syntaxhighlight> | ||
+ | |||
+ | == Katso myös == | ||
* [http://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal Recursive example] | * [http://rosettacode.org/wiki/Greatest_common_divisor#Pascal_.2F_Delphi_.2F_Free_Pascal Recursive example] | ||
− | * [[Least common multiple]] | + | * [[Least common multiple/fi|Pienin yhteinen jaettava]] (Least common multiple) |
* [[Mod]] | * [[Mod]] | ||
− | |||
− |
Latest revision as of 13:12, 16 February 2020
│
English (en) │
suomi (fi) │
français (fr) │
polski (pl) │
русский (ru) │
Suurin yhteinen tekijä
Suurin yhteinen tekijä on suurin kokonaisluku, jolla voidaan jakaa annetut kaksi kokonaislukua. Jos annetut kokonaisluvut ovat 121 ja 143 niin niiden suurin yhteinen tekijä on 11.
On olemassa monia menetelmiä laskea tämä. Esimerkiksi jakoon perustuva Eukleideen algoritmia käyttävä versio voidaan ohjelmoida näin:
Funktio GreatestCommonDivisor
function GreatestCommonDivisor(a, b: Int64): Int64;
var
temp: Int64;
begin
while b <> 0 do
begin
temp := b;
b := a mod b;
a := temp
end;
result := a
end;
Tai toinen vaihtoehtoinen tapa
function GreatestCommonDivisor_EuclidsSubtractionMethod(a, b: Int64): Int64;
//only works with positive integers
begin
if (a < 0) then a := -a;
if (b < 0) then b := -b;
if (a = 0) then Exit(b);
if (b = 0) then Exit(a);
while not (a = b) do
begin
if (a > b) then
a := a - b
else
b := b - a;
end;
Result := a;
end;
Katso myös
- Recursive example
- Pienin yhteinen jaettava (Least common multiple)
- Mod