الگوریتم اقلیدس: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
برچسب تمیزکاری، برچسب: استفادهٔ زیاد از تگ یا الگوی سرخط |
|||
خط ۱:
{{تمیزکاری}}
'''الگوریتم اقلیدس'''، روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن [[بزرگترین مقسوم علیه مشترک]] دو عدد است که در ادامه، با مثالی آن را شرح می‌دهیم.{{سخ}}
مثال: برای محاسبهٔ <math>(846 , 204)</math> عدد بزرگتر یعنی 846 را بر 204 تقسیم می‌کنیم و سپس 204 را بر باقی ماندهٔ تقسیم مزبور تقسیم می‌کنیم و این عمل را تا جایی که [[باقی مانده]] صفر شود ادامه می‌دهیم، آخرین باقی‌مانده غیرصفر، بزرگترین [[مقسوم علیه]] مشترک دو عدد مزبور است. همچنین می‌توان این تقسیمات را در جدولی تنظیم نمود.
سطر ۱۳ ⟵ ۱۴:
'''اثبات:''' فرض می‌کنیم <math>(a,b) = d</math> و <math>(b,r) = d'</math>. پس
[[پرونده:Proof - Euclidean Algorithm.png|600px|وسط]]
''شبه کد الگوریتم اقلیدسی'':
{{سرخط}}procedure gcd(a,b:positive integers)
{{سرخط}}x:=a
{{سرخط}}y:=b
{{سرخط}}while y≠0
{{سرخط}}r:=x mod y
{{سرخط}}x:=y
{{سرخط}}y:=r
{{سرخط}}return x{gcd(a,b)is x}
== منابع ==
| |||