اشکال کوچک در برنامه بزرگترین مقسوم علیه مشترک

[davood59]

سلام دوستان؛
این الگوریتم رو بدلیل اینکه خودم نوشته و از جای دیگه ای ایده نگرفتم میخوام در رفع اشکالش کمک کنید.
خطوط این برنامه رو نیز جهت رفع شبهات براتون توضیح دادم !
اشکالاتم رو هم در آخر بیان کردم.


#include <stdio.h>
#include <conio.h>
#include <iostream.h>
int main()
{
clrscr();
int a,b,bmaghsom;
cin>>a;
cin>>b;
این خط برای اینه که ابتدا عدد بزرگتر رو بدست بیاره، بعدش اگه چنانچه در تقسیم عدد بزرگتر بر کوچکتر نتیجه صفر شد ، پس همون عدد کوچکتر ب . م . م نیز هست.//
int min=b;
int max=a;
int d,d2;
if (min>max)
{
min=a;
max=b;
}
if (max%min==0)
{
bmaghsom=min;
cout<<bmaghsom;
} else
در این قسمت عدد بزرگتر رو تقسیم بر 2 کردم تا حلقه از نصف عدد بزرگتر بالا نزنه، طبیعیه که نباید هم بیشتر باشه//
for (int i=max/2;i>1;i--)
{
//cout<<i;
d=max%i;
d2=min%i;
if (d==0 & d2==0)
{
cout<<i;
}
}
//cout<<"no there is any bmaghsom";

getch();
// chera return 1 baese chape 2 mishe
}



حالا سوال من اینه؟
اولا اگه شرایط فوق برقرار نباشه میخوام پیغام وجود ندارد هیچگونه ب.م.م چاپ بشه!
ثانیاً بعنوان مثال اگه شما اعداد 54 و 12 رو بزنید ، عدد اول که همون ب.م.م هست رو نشون میده و مقسوم بعدی رو هم نشون میده که من نمیخوام اینجوری باشه.
دوستان اگه کمک کنند ممنون میشم.

[clover]

اولا اگه شرایط فوق برقرار نباشه میخوام پیغام وجود ندارد هیچگونه ب.م.م چاپ بشه!
این اتفاق هیچ وقت رخ نمیده، چون عدد 1 مقسوم علیه مشترک همه اعداد هست.

ثانیاً بعنوان مثال اگه شما اعداد 54 و 12 رو بزنید ، عدد اول که همون ب.م.م هست رو نشون میده و مقسوم بعدی رو هم نشون میده که من نمیخوام اینجوری باشه.
به محض اینکه ب.م.م پیدا شد از حلقه خارج شوید:

if (d == 0 & d2 == 0)
{
cout << i;
break;
}
این هم یک نمونه هست که با الگوریتم اقلیدس نوشتم، شاید براتون جالب باشه:

#include <iostream.h>
#include <conio.h>
int main()
{
int a, b, temp;
cin >> a;
cin >> b;
while (b)
{
temp = a;
a = b;
b = temp % b;
}
cout << a;
getch();
return 0;
}

[davood59]

دوست عزیزم خیلی ممنونم.
الگوریتمی که فرستادید خیلی جالب و زیباست! میشه طرز کارش رو توضیح بدید؟
ضمناً الگوریتمی که خودم نوشتم چه جوریه؟
ضمنا یک سوال دیگه؟ ببینید اگه ما 24 و 12 رو وارد کنیم برنامه دوبار عدد 12 رو بعنوان ب م م وارد می کنه که یکبار در اینجاست:



if (max%min==0)
{
bmaghsom=min;
cout<<bmaghsom;
}



و یکبار دیگه هم بعد از اینکه وارد برنامه اصلی شد، چاپ میکنه!
چیکارش کنم که بعد از همین مرحله برنامه رو تموم کنه؟

[clover]

الگوریتمی که فرستادید خیلی جالب و زیباست! میشه طرز کارش رو توضیح بدید؟
توی دوره ی راهنمایی یادتون هست چطور ب.م.م را محاسبه می کردیم ؟ یه جدول می کشیدیم و عدد بزرگتر سمت چپ میذاشتیم و عدد کوچکتر را سمت راست، بعد باقیمانده ی تقسیم عدد بزرگتر بر عدد کوچکتر را به دست می آوردیم، اگر صفر می شد، عدد کوچکتر همان مقسوم علیه مشترک بود وگرنه باقیمانده را سمت راست می گذاشتیم و دوباره تقسیم را انجام می دادیم تا به صفر برسیم.

حالا این دقیقا همون روش هست، و در ضمن حلقه ی while طوری نوشته شده که در مرتبه ی اول اجرا اگر عدد کوچکتر ابتدا وارد بشه جای دو عدد را عوض می کنه و بعد هم مدام عدد کوچکتر را در a و باقیمانده را در b می ریزه تا جایی که b صفر بشه .


ضمناً الگوریتمی که خودم نوشتم چه جوریه؟
برای اعداد بزرگ امتحان کنید و ببینید چه اتفاقی می افته، مثلا برای دو عدد 1000001 و 2 اگر اشتباه نکنم حلقه ی for شما تقریبا 500000 بار تکرار میشه ولی با روش اقلیدس حلقه while فقط 2 بار تکرار میشه، پس راه بهینه ای نیست.


ضمنا یک سوال دیگه؟ ببینید اگه ما 24 و 12 رو وارد کنیم برنامه دوبار عدد 12 رو بعنوان ب م م وارد می کنه که یکبار در اینجاست:
یکبار دیگه هم بعد از اینکه وارد برنامه اصلی شد، چاپ میکنه!
چیکارش کنم که بعد از همین مرحله برنامه رو تموم کنه؟
همین الان هم فقط یک بار چاپ و تموم می کنه، به خاطر else

[Salar Ashgi]

برای محاسبه ب.م.م دو عدد از روش تابع بازگشتی نیز میتوانید استفاده کنید :



int GCD(int a,int b){
if(b==0)
return a;
if(b==1)
return 1;
else
return GCD(b,a%b);
}
* توضیح : همانطور که از بحث نظریه اعداد در ریاضیات گسسته میدانیم :




a = bq+r //Division Algorithm
(a,b) = (b,r)//result of above algorithm
r=a%b
موفق باشید .

[qanewaisi]

برای محاسبه ب.م.م دو عدد از روش تابع بازگشتی نیز میتوانید از این کد استفاده کنید :



int GCD(int a,int b){
if(a>b)
return GCD(a-b,b);
if(a<b)
return GCD(a,b-a);
return a;
}

[davood59]

با تشکر از همه شما، آقا سالار با توجه به اینکه من تازه C رو شروع کردم میشه برنامه تون رو به طور کامل بذارید! منظورم شیوه کاربرد تابع توی برنامه است؟
من اینجوری گذاشتم ولی اشکال گرفت! راستش خیلی به syntax های C آشنا نیستم و بیشتر الگوریتم خوندم.




#include <stdio.h>
#include <conio.h>
#include <iostream.h>
int GCD(int a,int b){
if(b==0)
return a;
if(b==1)
return 1;
else
return GCD(b,a%b);
}
int main()
{
cin>>a;
cin>>b;
GCD(a,b);
}


مرسی
ضمناً یه توضیح دو خطی هم در مورد منطق برنامه بده.

و اما clover عزیز در خصوص این گفته شما یعنی:

در ضمن حلقه ی while طوری نوشته شده که در مرتبه ی اول اجرا اگر عدد کوچکتر ابتدا وارد بشه جای دو عدد را عوض می کنه
من trace کردم و خیلی ملموس نبود.
ببینید مثلا طرف ابتدا 25 و بعدش 60 رو وارد می کنه. عدد 25 در a و عدد 60 در b قرار میگیره!
در مرحله بعد عدد 25 در temp ، و عدد 60 در a.
در مرحله نهایی مقدار b برابرباقیمانده تقسیم 25 بر 60 میشه! آیا این درسته؟

[qwerty11]

در تکمیل صحبت های salar_cpp_cs (http://www.barnamenevis.org/forum/member.php?u=70109) منم یه تابع برای ب.م.م دو تا عدد میگم که در واقع همین تابعیه که ایشون گفتن فقط یه ذره جمع و جور تر :


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

[Salar Ashgi]

آقا سالار با توجه به اینکه من تازه C رو شروع کردم میشه برنامه تون رو به طور کامل بذارید! منظورم شیوه کاربرد تابع توی برنامه است؟
من اینجوری گذاشتم ولی اشکال گرفت!


دستور cout یا همون printf رو فراموش کرده بودین :



#include <stdio.h>
#include <conio.h>
#include <iostream.h>
int GCD(int a,int b){
if(b==0)
return a;
if(b==1)
return 1;
else
return GCD(b,a%b);
}
int main()
{
cin>>a;
cin>>b;
cout<<GCD(a,b)<<endl;
}


منطق برنامه هم خیلی ساده بر اساس منطق برنامه های بازگشتی هستش ، اگه با مفاهیم مبحث

بازگشت و توابع بازگشتی آشنایی داشته باشید ، براحتی میتوانید کد را درک کنید !