Question

برنامه ای که ب.م.م و ک.م.م دو عدد را چاپ کند

Answer 1

int bmm(int a,int b)
{
    if(b==0)
            return a;
    return (b,a%b);
}

int kmm(int a,int b)
{
    return (a*b)/bmm(a,b);
}

 

Answer 2

نفر قبلی جواب درستی داد اما صرفا برای توضیح بیشتر:

کد برنامه رو که این طوری هم میشه نوشت:

int gcd(int a, int b)
{
    if(b==0) return a;
    return gcd(b, a%b);
}

int lcm(int a, int b)
{
    return a*b/gcd(a, b);
}

 

این الگوریتم، در بین سایر الگوریتم های محاسبه ی ب م م از کمترین زمان ممکن استفاده میکنه و از مرتبه log n هستش یعنی اگر ورودی شما عدد n باشد، این الگوریتم به مقدار " log n در مبنای 2 " دستور را توسط cpu انجام میدهد.

روش کارش همون روش نردبانی هست که توی اول راهنمایی یاد گرفتیم.

لازم به ذکره که تابع gcd اگر b!=0 باشه به صورت خودکار دستور دوم را انجام میدهد. چون return در توابع مثل break در حلقه است.

نکته ی دیگه این که اگر ورودی های تابع ب.م.م به شکلی باشد که عدد اول کوچکتر از عدد دوم باشد، یعنی a<b :

gcd (a, b) = gcd (b, a%b) = gcd (b, a)

یعنی اگر a<b باشد، خود تابع به صورت اتوماتیک، جای آن دو را عوض میکند و نیازی نیست که مستقیما از دستور if استفاده کنیم.

Comments

mishe az( if, return) estefade nakard?!

---

سلام لطفاً فارسی تایپ کنید

---

میشه بیشتر توضیح بدید؟ (و اگر ممکنه فارسی تایپ کنید)
اگر منظورتون اینه که بازگشتی ننویسیم، جواب اینه که بله صد در صد میشه. یعنی واسه هر عدد یه وکتور درست کنیم که عوامل عدد رو توی خودش نگه میداره و با مقایسه ی اون دو تا وکتور و... به جواب برسیم. ولی زمان بیشتری مصرف میکنه.

---

حالا چرا log n ؟

---

یه قضیه ی نظریه اعداد هست به این صورت که اگر a>b باشد، a%b<a/2
(اثباتش آسونه کافیه دو تا نامعادله رو با هم جمع کنیم)
وقتی که تابع رو اجرا میکنیم، به ترتیب این عبارات برگردانده میشوند:
gcd b, a%b
این: (gcd a%b, b%(a%b
.
.
.
در خط دوم، ورودی مون، حداکثر نصف a هست(قضیه نظریه اعداد که گفتم).
در بدترین حالت و در مرحله ی آخر، مقدار gcd 1, 0 برگردانده میشود. با توجه به اون قضیه ی نظریه اعداد، موقعی به این حالت میرسیم که حداکثر 2 برابر log n در پایه ی 2 حرکت انجام داده باشیم و طبق تعریف تابع O، این الگوریتم از اردر log n است.

Answer 3

#include<iostream>

using namespace std;
int main(){
long int a,b,c,s,r,d;

cin>>a>>b;
s=a;
for(c=b;c>0;c=r){
r=s%c;
s=c;
}

d=(a*b)/s;
cout<<s<<" "<<d;	

return 0;
}

 

Answer 4

در پایتون :

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

a = int(input("Enter the first number: "))
b = int(input("Enter the second number: "))

print("GCD:", gcd(a, b))
print("LCM:", lcm(a, b))