กำหนดจำนวนเต็มสองจำนวน Num1 และ Num2 เป็นอินพุต จำนวนเต็มสามารถแสดงเป็นเศษส่วน Num1/Num2 . เป้าหมายคือลดเศษส่วนนี้ให้อยู่ในรูปแบบต่ำสุด
การใช้ GCD เพื่อค้นหาตัวส่วนสูงสุด
-
เราจะคำนวณตัวหารร่วมมากของตัวเลขทั้งสอง
-
หารตัวเลขทั้งสองด้วย gcd นั้น
-
ตั้งค่าตัวแปรทั้งสองเป็นผลหารหลังการหาร
-
เศษส่วนต่ำสุดจะเป็น Num1/Num2
ตัวอย่าง
ป้อนข้อมูล − Num1=22 Num2=10
ผลผลิต − Num1 =11 Num2 =5
เศษส่วนต่ำสุด :11/5
คำอธิบาย − GCD ของ 22 และ 10 คือ 2
22/2=11 และ 10/2=5
เศษส่วนต่ำสุดคือ 11/5
ป้อนข้อมูล − Num1=36 Num2=40
ผลผลิต − Num1 =9 Num2 =10
เศษส่วนต่ำสุด :9/10
คำอธิบาย − GCD ของ 36 และ 40 คือ 4
40/4=10 และ 36/4=9
เศษส่วนต่ำสุดคือ 9/10
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในแนวทางนี้ ก่อนอื่นเราจะคำนวณ GCD ของตัวเลขอินพุตโดยใช้วิธีการแบบเรียกซ้ำ หารตัวเลขทั้งสองด้วย GCD และรับผลหาร ผลหารเหล่านี้จะเป็นส่วนหนึ่งของเศษส่วนต่ำสุด
-
รับตัวแปรอินพุต Num1 และ Num2
-
ฟังก์ชัน findGCD(int a, int b) รับ num1 และ num2 และคืนค่า gcd ของทั้งสองอย่าง
-
ถ้า b เป็น 0 ให้ return a else ส่งคืน findGCD(b,a%b)
-
ฟังก์ชัน lowFraction(int num1, int num2) รับทั้งตัวเลขเป็นอินพุตและพิมพ์เศษส่วนต่ำสุด
-
หาค่าตัวแปรสำหรับ gcd
-
ตั้งค่า num1=num1/denom และ num2=num2/denom.
-
พิมพ์ num1 และ num2.
-
พิมพ์เศษส่วนต่ำสุดเป็น num1/num2
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int findGCD(int a, int b) {
if (b == 0)
return a;
return findGCD(b, a % b);
}
void lowestFraction(int num1, int num2){
int denom;
denom = findGCD(num1,num2);
num1/=denom;
num2/=denom;
cout<< "Num1 = " << num1<<endl;
cout<< "Num2 = " << num2<<endl;
cout<< "Lowest Fraction : "<<num1<<"/"<<num2;
}
int main(){
int Num1 = 14;
int Num2 = 8;
lowestFraction(Num1,Num2);
return 0;
} ผลลัพธ์
หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
Num1 = 7 Num2 = 4 Lowest Fraction : 7/4
