Euclidean algorithm

[share]

...Euclidean algorithm เรื่องใคร่รู้
ขอเพื่อนโปรด เล่าสู่ พ้นสงสัย
เขาว่ากัน มันแค่ ขั้นเด็กไง
จริงหรือไร เหมาะเรียน เขียนโปรแกรม

[share]

What Euclid called "common measure" is termed nowadays a common factor or a common divisor.

Euclid VII.2 then offers an algorithm for finding the greatest common divisor (gcd) of two integers.

http://www.cut-the-knot.org/blue/Euclid.shtml

[ohmohm]

Python นะครับ

PHP Code:

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


[share]

ขอบคุณ โปรแกรม ที่ให้
โปรดได้ แบ่งปัน อีกหนา
วานเพื่อน ขยายความ แจงมา
ภาษา บ้านบ้าน วานนะเธอ

[ohmohm]

คิดหนักเลยครับ ภาษาบ้านๆ

[share]

เขึยนเล่าแบบลำดับความคิด
หรือ flowchart น่าจะช่วยให้เข้าใจได้ง่าย

เขียนเป็น programming language ไม่ว่า Python PHP C
ผู้ไม่เคยเรียน ก็จะดูไม่เข้าใจครับ

ขอบคุณล่วงหน้าครับ

[share]

...สื่อสาร (สอบ)ทานง่าย ฉายประโยชน์
บ่โกรธ ผู้มัก ซักถาม
เข้าใจ ไขแจ้ง กระจ่างความ
ไป่ปล่อย รอยหนาม คาใจ

Euclidean algorithm can be used to find the greatest common divisor of a = 1071 and b = 462.

To begin, multiples of 462 are subtracted from 1071 until the remainder is less than 462.
Two such multiples can be subtracted (q0 = 2), leaving a remainder of 147:
1071 = 2 × 462 + 147.

Then multiples of 147 are subtracted from 462 until the remainder is less than 147.
Three multiples can be subtracted (q1 = 3), leaving a remainder of 21:
462 = 3 × 147 + 21.

Then multiples of 21 are subtracted from 147 until the remainder is less than 21.
Seven multiples can be subtracted (q2 = 7), leaving no remainder:
147 = 7 × 21 + 0.

Since the last remainder is zero,
the algorithm ends with 21 as the greatest common divisor of 1071 and 462.

[share]

คห.เดิม ได้จาก
https://en.wikipedia.org/wiki/Euclidean_algorithm

ดู Description
Procedure

Worked example
ครับ