โปรแกรม C หา GCD ด้วยฟังก์ชันไม่เรียกซ้ำ (Non-recursive)

โจทย์

หาตัวหารร่วมมาก (GCD) ของสองจำนวนโดยใช้ฟังก์ชันแบบไม่เรียกซ้ำ (non-recursive)

วิธีแก้

อัลกอริทึม

ขั้นตอน 1 - เริ่ม

ขั้นตอน 2 - อ่านจำนวนเต็ม a และ b

ขั้นตอน 3 - เรียกฟังก์ชัน G = GCD(a,b) ขั้นตอน 6

ขั้นตอน 4 - พิมพ์ค่า G

ขั้นตอน 5 - หยุด

ขั้นตอน 6 - ฟังก์ชัน GCD(a,b)

a. เริ่มต้น i=1, j, remainder
b. Remainder = i - (i/j*j)
c. ถ้า Remainder = 0 คืนค่า j มิฉะนั้นไปขั้นตอน 4
d. GCD(G,remainder) คืนค่าไปโปรแกรมหลัก

Flowchart

มีแผนภาพ flowchart สำหรับอัลกอริทึมหา GCD แบบ non-recursive

ตัวอย่าง

โปรแกรม C หา GCD ด้วยฟังก์ชัน non-recursive:

#include<stdio.h> #include<conio.h> #include<math.h> int gcdnonR(int i,int j){    int rem;    rem=i-(i/j*j);    if(rem==0)       return j;    else       gcdnonR(j,rem); } void main(){    int a,b;    printf("enter the two numbers:");    scanf("%d%d",&a,&b);    printf("GCD of %d",gcdnonR(a,b));    getch(); }

ผลลัพธ์

enter the two numbers:10 30 GCD of 10