ملخص وعرض الدرس الخوارزمية الإقليدية لإيجاد العقد. عرض تقديمي حول موضوع "خوارزمية إقليدس" الموضوع: خوارزمية إقليدس لإيجاد GCD

لاستخدام معاينة العروض التقديمية ، قم بإنشاء حساب Google (حساب) وقم بتسجيل الدخول: https://accounts.google.com

شرح الشرائح:

خوارزمية إقليدس إقليدس ، عالم رياضيات يوناني قديم. عمل في الإسكندرية في القرن الثالث. قبل الميلاد ه. وكان العمل الرئيسي "البدايات" (15 كتابا) ، يحتوي على أسس الرياضيات القديمة ، والهندسة الأولية ، ونظرية الأعداد ، والنظرية العامة للعلاقات ، وطريقة تحديد المساحات والأحجام ، والتي تضمنت عناصر نظرية الحدود. كان له تأثير كبير على تطوير الرياضيات. يعمل في علم الفلك والبصريات ونظرية الموسيقى. إقليدس (365-300 قبل الميلاد)

خوارزمية يوكليد (EUCLID'S ALGORITHM) هي خوارزمية لإيجاد القاسم المشترك الأكبر (gcd) لعددين صحيحين غير سالبين. إقليدس (365-300 قبل الميلاد) أطلق علماء الرياضيات اليونانيون القدماء على هذه الخوارزمية ἀνθυφαίρεσις أو ἀνταναίρεσις - "الطرح المتبادل".

الحساب GCD GCD = القاسم المشترك الأكبر لعددين طبيعيين هو أكبر رقم يمكن بواسطته القسمة على كلا الرقمين الأصليين بدون باقي. gcd (a، b) = gcd (a-b، b) = gcd (a، b-a) استبدل الرقم الأكبر من الرقمين بالفرق بين الأكبر والأصغر حتى يتساوى. هذا هو NOD. gcd (18، 45) = gcd (18، 45-18) = gcd (18، 27) = gcd (18، 9) = = gcd (9،9) = 9 مثال:

تشغيل الخطوة M N الحالة 1 الإدخال M 48 2 الإدخال N 18 3 M  N 48 18 ، نعم 4 M> N 48> 18 ، نعم 5 M: = M-N 30 6 M  N 30  18 ، نعم 7 M> N 30 > 18 ، نعم 8 م: = M-N 12 9 M  N 12 18 ، نعم 10 M> N 12> 18 ، لا 11 N: = N-M 6 12 M  N 12 6 ، نعم 13 M> N 12> 6 ، نعم 14 م: = M-N 6 15 M  N 6 6 ، لا 16 مخرج M

برنامج Evklid. فار م ، ن: عدد صحيح ؛ start writeln ("vved 2 chisla") ؛ readln (م ، ن) ؛ بينما تبدأ mn إذا كانت m> n ثم m: = m-n else n: = n-m ؛ نهاية؛ الكتابة ("nod ="، m) ؛ readln النهاية.

0. قم بتشغيل برنامج Evklid على الكمبيوتر. اختبره باستخدام M = 32 ، N = 24 ؛ م = 696 ، ن = 234. واحد . تحقق مما إذا كان رقمان معينان يمثلان جريمة حقوقية. ملحوظة. يُقال أن رقمين يمثلان جريمة مشتركة إذا كان القاسم المشترك الأكبر بينهما هو 1. 2. أوجد المضاعف المشترك الأصغر (LCM) للأرقام n و m إذا كان المضاعف المشترك الأصغر (n، m) = n * m / gcd (n، m). 3. تم إعطاء الأعداد الطبيعية م ون. أوجد الأعداد الطبيعية p و q التي ليس لها قواسم مشتركة مثل p / q = m / n. 4. أوجد GCD لثلاثة أرقام. ملحوظة. GCD (a، b، c) = GCD (gcd (a، b)، c) المهام

معاينة:

الموضوع: "خوارزمية إقليدس"

أهداف الدرس:

1. التعليمية:

1. تعلم كيفية استخدام خوارزمية إقليدس لإيجاد gcd لرقمين وثلاثة أرقام
2. توحيد المهارات في استخدام الهياكل الخوارزمية "التفريع" و "الدورة"
3. اكتساب الخبرة في الكتابة وبرامج التصحيح بلغة برمجة باسكال

1. التعليمية:

1. تشكيل الاستقلال والمسؤولية في دراسة المواد الجديدة

1. النامية:

1. تنمية الانتباه والتفكير التحليلي

خطة الدرس:

1. تنظيم الوقت
2. تحديث المعرفة
3. شرح الموضوع الجديد
4. الجزء العملي
5. تلخيص الدرس
6. الواجب المنزلي.

تنظيم الوقت

تحية طيبة. من غائب. رقم. موضوع الدرس. أسئلة عن الواجب المنزلي.

تحديث المعرفة.

أسئلة:

ما أنواع الهياكل الخوارزمية التي تعرفها؟

ما هو الهيكل الخطي؟ (Bl-sh)

ما هو الهيكل المتفرّع؟ (Bl-sh)

ما هو الهيكل الدوري؟ (Bl-sh)

ما أنواع الدورات التي تعرفها؟

كيف يتم تنفيذ حلقة مع عدد معروف من التكرارات في لغة برمجة باسكال؟

كيف يتم تنفيذ حلقة بها عدد غير معروف من التكرارات في لغة برمجة باسكال؟

شرح موضوع جديد (عرض)

حول إقليدس ؛

فكرة خوارزمية إقليدس

تعتمد فكرة هذه الخوارزمية على:

1. الخاصية التي إذا كانت M> N ، ثم GCD (M ، N) = GCD (M - N ، N).

بعبارة أخرى ، فإن gcd عددين طبيعيين يساوي gcd لاختلافهما الموجب (مقياس فرقهما) والعدد الأصغر.

دليل - إثبات: دع K يكون قاسم مشترك بين M و N (M> N). هذا يعني أن M \ u003d mK ، N \ u003d nK ، حيث m ، n أعداد طبيعية ، و m> n. ثم M - N \ u003d K (m - n) ، مما يعني أن K هو القاسم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم الفرق بينهما M - N ، بما في ذلك الأكبر القاسم المشترك.

2- الخاصية الواضحة الثانية:

GCD (م ، م) = م.

بالنسبة للعد "اليدوي" ، تبدو خوارزمية إقليدس كما يلي:

1) إذا كانت الأرقام متساوية ، فاخذ أيًا منها كإجابة ، وإلا استمر في الخوارزمية ؛

2) استبدل الرقم الأكبر بالفرق بين الرقمين الأكبر والأصغر ؛

3) العودة إلى تنفيذ الفقرة 1.

رسم تخطيطي لخوارزمية إقليدس

برنامج في شبيبة باسكال

برنامج Evklid.

فار م ، ن: عدد صحيح ؛

يبدأ

writeln ("vved 2 number") ؛

readln (م ، ن) ؛

بينما mn تفعل

يبدأ

إذا م> ن

ثم م: = م ن

آخر ن: = ن م ؛

نهاية؛

اكتب ("nod ="، m) ؛

readln

نهاية.

الجزء العملي

أسئلة ومهام:

1. قم بتشغيل برنامج Evklid على جهاز الكمبيوتر الخاص بك. اختبره على M = 32 ، N = 24 ؛ م = 696 ، ن = 234.
2. تحقق مما إذا كان رقمان معينان يمثلان جريمة حقوقية. ملحوظة. يُقال أن رقمين يمثلان جريمة مشتركة إذا كان القاسم المشترك الأكبر بينهما هو 1.

تلخيص الدرس

اليوم في الدرس تعرفنا على خوارزمية إقليدس ، والتي تسمح لنا بالعثور على GCD من عددين صحيحين غير سالبين ، كتبنا برنامجًا بلغة برمجة باسكال يطبق هذه الخوارزمية. في المنزل ، ستتلقى مهمة تقوم فيها بتطبيق هذه الخوارزمية للعثور على GCD المكون من ثلاثة أرقام والمضاعف المشترك الأصغر لرقمين.

الواجب المنزلي.

1. اكتب برنامجًا لإيجاد القاسم المشترك الأكبر لثلاثة أعداد باستخدام الصيغة التالية:

gcd (أ ، ب ، ج) = gcd (gcd (أ ، ب) ، ج)

2. اكتب برنامجًا لإيجاد المضاعف المشترك الأصغر (LCM) لرقمين باستخدام الصيغة:

A  B \ u003d GCD (A ، B)  LCM (A ، B)

شريحة 1

الشريحة 2

الشريحة 3

الشريحة 4

الشريحة 5

الشريحة 6

شريحة 7

الشريحة 2

خوارزمية إقليدس هي خوارزمية لإيجاد القاسم المشترك الأكبر (gcd) لعددين صحيحين غير سالبين. إقليدس (365-300 قبل الميلاد) أطلق علماء الرياضيات اليونانيون القدماء على هذه الخوارزمية ἀνθυφαίρεσις أو ἀνταναίρεσις - "الطرح المتبادل".

الشريحة 3

حساب GCD

GCD = القاسم المشترك الأكبر لرقمين طبيعيين هو أكبر رقم يمكن بواسطته القسمة على كلا الرقمين الأصليين بدون باقي. GCD (أ ، ب) = GCD (أ ب ، ب) = GCD (أ ، ب أ) استبدل الرقم الأكبر من الرقمين بالفرق بين الأعداد الأكبر والأصغر حتى تتساوى. هذا هو NOD. GCD (18 ، 45) = GCD (18 ، 45-18) = GCD (18 ، 27) = GCD (18 ، 9) = = GCD (9،9) = 9 مثال:

الشريحة 4

الشريحة 5

برنامج Evklid. فار م ، ن: عدد صحيح ؛ ابدأ الكتابة ("رقمان vved") ؛ readln (م ، ن) ؛ بينما تبدأ mn إذا كانت m> n ثم m: = m-n else n: = n-m ؛ نهاية؛ الكتابة ("nod ="، m) ؛ readln النهاية.

الشريحة 6

0. قم بتشغيل برنامج Evklid على الكمبيوتر. اختبره باستخدام M = 32 ، N = 24 ؛ م = 696 ، ن = 234. 1. تحقق مما إذا كان رقمان معينان يمثلان جريمة مشتركة. ملحوظة. يُطلق على رقمين اسم coprime إذا كان القاسم المشترك الأكبر بينهما هو 1. 2. ابحث عن المضاعف المشترك الأصغر (LCM) للأرقام n و m إذا كان المضاعف المشترك الأصغر (n، m) = n * m / gcd (n، m). 3. تم إعطاء الأعداد الطبيعية m و n. أوجد الأعداد الطبيعية p و q بدون قواسم مشتركة مثل p / q = m / n. 4. أوجد GCD لثلاثة أرقام. ملحوظة. gcd (a، b، c) = gcd (gcd (a، b)، c) المهام

شريحة 7

إقليدس ، عالم الرياضيات اليوناني القديم. عمل في الإسكندرية في القرن الثالث. قبل الميلاد ه. وكان العمل الرئيسي "البدايات" (15 كتابا) ، يحتوي على أسس الرياضيات القديمة ، والهندسة الأولية ، ونظرية الأعداد ، والنظرية العامة للعلاقات ، وطريقة تحديد المساحات والأحجام ، والتي تضمنت عناصر نظرية الحدود. كان له تأثير كبير على تطوير الرياضيات. يعمل في علم الفلك والبصريات ونظرية الموسيقى.

اعرض كل الشرائح

بيان المشكلة ضع في اعتبارك المشكلة التالية: مطلوب كتابة برنامج لتحديد القاسم المشترك الأكبر (GCD) لرقمين طبيعيين. لنتذكر الرياضيات. القاسم المشترك الأكبر لعددين طبيعيين هو أكبر عدد طبيعي يقبل القسمة عليه بالتساوي. على سبيل المثال ، الأرقام 12 و 18 لها قواسم مشتركة: 2 ، 3 ، 6. القاسم المشترك الأكبر هو الرقم 6. هذا مكتوب على النحو التالي: gcd (12،18) = 6. قم بالإشارة إلى البيانات الأولية كـ M و N بيان المشكلة كما يلي: معطى: M، N البحث: GCD (M، N).

N ، ثم GCD (M ، N) = GCD (M - N ، N). بمعنى آخر ، فإن gcd عددين طبيعيين يساوي gcd للاختلاف الموجب بينهما والعدد الأصغر. "title =" (! LANG: فكرة الخوارزمية تستند فكرة هذه الخوارزمية إلى خاصية أنه إذا كانت M> N ، ثم gcd (M ، N) = gcd (M - N ، N) وبعبارة أخرى ، فإن gcd عددين طبيعيين يساوي gcd لاختلافهما الموجب والعدد الأصغر." class="link_thumb"> 4 !}فكرة الخوارزمية تعتمد فكرة هذه الخوارزمية على الخاصية التي إذا كانت M> N ، فإن GCD (M ، N) = GCD (M - N ، N). بعبارة أخرى ، فإن gcd عددين طبيعيين يساوي gcd للاختلاف الموجب بينهما والعدد الأصغر. N ، ثم GCD (M ، N) = GCD (M - N ، N). بمعنى آخر ، gcd عددين طبيعيين يساوي gcd للاختلاف الموجب بينهما والعدد الأصغر. "> N ، ثم gcd (M ، N) = gcd (M - N ، N). وبعبارة أخرى ، فإن gcd من عددين طبيعيين يساوي gcd لاختلافهما الموجب والعدد الأصغر. "> N ، ثم GCD (M ، N) = GCD (M - N ، N). بمعنى آخر ، فإن gcd عددين طبيعيين يساوي gcd للاختلاف الموجب بينهما والعدد الأصغر. "title =" (! LANG: فكرة الخوارزمية تستند فكرة هذه الخوارزمية إلى خاصية أنه إذا كانت M> N ، ثم gcd (M ، N) = gcd (M - N ، N) وبعبارة أخرى ، فإن gcd عددين طبيعيين يساوي gcd لاختلافهما الموجب والعدد الأصغر."> title="فكرة الخوارزمية تعتمد فكرة هذه الخوارزمية على الخاصية التي إذا كانت M> N ، فإن GCD (M ، N) = GCD (M - N ، N). بعبارة أخرى ، فإن gcd عددين طبيعيين يساوي gcd للاختلاف الموجب بينهما والعدد الأصغر."> !}

ن). هذا يعني أن M = mK ، N = pK ، حيث m ، n أعداد طبيعية ، و m> n. ثم M - N = K (m - n) ، مما يعني أن K هو القاسم المشترك لـ M - N. وبالتالي ، فإن جميع القواسم المشتركة لـ M و N هي قواسم "title =" (! LANG: Proof Let K هو قاسم مشترك من M و N (M> N) وهذا يعني أن M = mK ، N = pK ، حيث m ، n هي أعداد طبيعية ، و m> n. ثم M - N = K (m - n) ، من حيث يتبع أن K مقسوم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم" class="link_thumb"> 5 !}دليل على أن K يكون قاسمًا مشتركًا لكل من M و. N (M> N). هذا يعني أن M = mK ، N = pK ، حيث m ، n أعداد طبيعية ، و m> n. ثم M - N = K (m - n) ، ومن هنا يتبع ذلك أن K هو القاسم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم اختلافهما M - N ، بما في ذلك الأكبر القاسم المشترك. ومن ثم: GCD (M ، N) = GCD (M - N ، N). الخاصية الواضحة الثانية: GCD (M ، M) = M. ن). هذا يعني أن M = mK ، N = pK ، حيث m ، n أعداد طبيعية ، و m> n. ثم M - N \ u003d K (m - n) ، ومن هنا يتبع ذلك أن K هو القاسم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم "\ u003e N). وهذا يعني أن M \ u003d mK ، N \ u003d pK ، حيث m ، n هي أعداد طبيعية ، و m> n. ثم M - N = K (m - n) ، ومن هنا يتبع ذلك أن K هو مقسوم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم الاختلاف بينهما M-N ، بما في ذلك القاسم المشترك الأكبر. ومن ثم: GCD (M ، N) = GCD (M - N ، N). الخاصية الواضحة الثانية: GCD (M ، M) = M. "> N). هذا يعني أن M = mK ، N = pK ، حيث m ، n أعداد طبيعية ، و m> n. ثم M - N = K (m - n) ، مما يعني أن K هو القاسم المشترك لـ M - N. وبالتالي ، فإن جميع القواسم المشتركة لـ M و N هي قواسم "title =" (! LANG: Proof Let K هو قاسم مشترك من M و N (M> N) وهذا يعني أن M = mK ، N = pK ، حيث m ، n هي أعداد طبيعية ، و m> n. ثم M - N = K (m - n) ، من حيث يتبع أن K مقسوم على الرقم M - N. ومن ثم ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم"> title="دليل على أن K يكون قاسمًا مشتركًا لكل من M و. N (M> N). هذا يعني أن M = mK ، N = pK ، حيث m ، n أعداد طبيعية ، و m> n. ثم M - N \ u003d K (m - n) ، مما يعني أن K هو مقسوم على الرقم M - N. وبالتالي ، فإن جميع القواسم المشتركة للأرقام M و N هي قواسم"> !}

برنامج في برنامج باسكال Evklid ؛ فار م ، ن: عدد صحيح ؛ ابدأ الكتابة ("أدخل M و N") ؛ readln (M ، N) ؛ بينما تبدأ MN إذا كانت M> N ثم M: = M-N else N: = N-M end ؛ كتابة ("HOD =" ، M) النهاية. N ثم M: = M-N else N: = N-M end ؛ اكتب ("HOD ="، M) end. "> N ثم M: = M-N else N: = N-M end ؛ اكتب (" HOD = "M) end."> N ثم M: = M-N else N: = N-M نهاية؛ اكتب ("HOD ="، M) end. "title =" (! LANG: Pascal program Program Evklid؛ var M، N: صحيح؛ start writeln ("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}
N ثم M: = M-N else N: = N-M end ؛ اكتب ("HOD ="، M) end. "title =" (! LANG: Pascal program Program Evklid؛ var M، N: صحيح؛ start writeln ("Введите M и N"); readln(M,N); while MN do begin if M>N then M:=M-N else N:=N-M end; write("HOD=",M) end."> !}