عرض احتلال الخوارزمية الإقليدية الدائرة. عرض تقديمي حول موضوع "خوارزمية إقليدس". فكرة خوارزمية إقليدس

فصل: 6

أهداف الدرس:

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

المعدات: كمبيوتر وجهاز عرض وشاشة.

خلال الفصول

1. لحظة التنظيم (التحقق من استعداد الطلاب للدرس ، وضع علامة الغائب) (دقيقة واحدة)

2. عمل شفوي: (6 دقائق)

1. استبدل المنتج بدرجة:

د) أ * أ * أ * أ * أ

احسب: 2 3؛ 52 ؛ 3 3 ؛ 10 4.
أوجد قيمة التعبير: (3؟ 3؟ 5؟ 11): (3؟ 11). ما هو الاستنتاج الذي يمكن استخلاصه؟
أداء القسمة أعلى ال بإذا كانت أ = 170 ، ب = 35. اكتب المساواة ، ما يساوي أ.

اكتب هذه المساواة بشكل عام: سيكون a قابلاً للقسمة ، و b سيكون قاسمًا. دع حاصل القسمة يكون q والباقي r ، ثم: أ = بك + ص ، ويمكن أن يكون q عددًا طبيعيًا أو صفرًا. يمكن أن يكون ص أي رقم؟ [r عدد طبيعي ، و 0 < r < b .] ماذا يمكن أن يقال عن العددين أ وب إذا كان ص = 0؟ القسمة الصحيحة هي حالة خاصة من القسمة مع الباقي.

اكتشف واشرح ما إذا كان الرقم أ قابلاً للقسمة على الرقم ب بدون باقي إذا:

أ) أ = 2 3 * 3 * 5 * 7 ؛

ب) أ = 2 4 * 3 * 5 7 ؛

ب = 2 7 * 3 * 5 4

ج) أ = 2 * 3 4 * 5 * 13 ؛

ب = 2 * 3 3 * 5 * 11.

3. تحديث المعرفة الأساسية(10 دقائق)

1) الأسئلة:

ما هو رقم القاسم أ ?

ما هو العدد الأولي؟

ماذا يعني تحليل عدد في العوامل الأولية؟

صياغة علامات القسمة على 2 ، 3 ، 5 ، 9 ، 10 ؛

أعط مثالا على رقم مركب من رقم واحد ؛

هل صحيح أن العدد 77 هو عدد أولي؟

لماذا ، إذا كان من الممكن أن يتحلل أحد الأرقام إلى عاملين أوليين ، والآخر إلى 3 عوامل أولية ، فإن هذه الأرقام ليست متساوية؟

أي عدد ، أولي أم مركب ، هو حاصل ضرب عددين أوليين؟

ما هو القاسم المشترك الأكبر لرقمين أو أكثر؟

ما هي الأرقام التي تسمى coprime؟

كرر الطرق للعثور على GCD: هناك خوارزميات مختلفة لإيجاد GCD للأعداد الطبيعية.

1 الطريق:إذا تم إعطاء رقمين وكانا صغيرين نسبيًا ، فإن أفضل خوارزمية هي البحث بالقوة الغاشمة. ومع ذلك ، بالنسبة للأعداد الكبيرة ، ابحث عن gcd (a ؛ b) عن طريق سرد كافة قواسم الأرقام أو بهذه العملية شاقة وغير موثوقة.

من المفيد أن نتذكر أن gcd لأي عدد من الأرقام لا يتجاوز أصغرها.

2 طريقة:عن طريق تحليل الأرقام (الأكثر شيوعًا) (الملحق ، الشريحة 1)

2) احسب GCD للأرقام 24 و 16.

3) حلل الأرقام: 875 و 8000 وحساب GCD لهذه الأرقام.

(باستخدام الرقم 8000 كمثال ، كرر طريقة أبسط لتحليل الأرقام المنتهية بالأصفار: بما أن 10 = 2 * 5 ، ثم 8000 = 2 * 5 * 2 * 5 * 2 * 5 * 2 * 2 * 2 == 2 6 * 5 3)

4) هل يمكن أن يساوي GCD لثلاثة أعداد 15 إذا كان حاصل ضربهم يساوي 3000؟ [ لا، مثل

15 \ u003d 3 * 5 ، مما يعني أنه يجب تضمين الرقم 3 في توسيع كل من الأرقام الثلاثة. لكن 3000 = 2 3 * 3 * 5 3.]

5) ص تأكل المهمة"تم إحضار كتب مدرسية إلى الفصل: 24 في الرياضيات و 36 في التاريخ و 48 في الجغرافيا. ما هو أكبر عدد من المجموعات التي يمكن صنعها من هذه الكتب بحيث يحتوي كل منها على نفس العدد من الكتب في الرياضيات والتاريخ والجغرافيا؟ كم عدد الكتب في كل مجموعة؟ "

4. أعمال التحقق (الملحق ، الشريحة 2) (6 دقائق)

5. تعلم مادة جديدة (10 دقائق)

مدرس:الطريقة المدروسة للعثور على GCD (أ ، ب) بسيطة ومفهومة ومريحة ، ولكن لها عيبًا كبيرًا: إذا كانت الأرقام المعطاة كبيرة ، وحتى لا يمكن تحليلها بسهولة ، فإن مهمة العثور على GCD (أ ، ب) يصبح صعبًا جدًا. بالإضافة إلى ذلك ، قد يتضح أنه بعد أن عملنا بجد ، سنتأكد من أن GCD (أ ، ب) = 1 ويبدو أن كل العمل قد تم دون جدوى.

وجد إقليدس طريقة رائعة لإيجاد gcd (أ ، ب) دون أي معالجة مسبقة للأرقام. (الملحق ، الشريحتان 3 و 4)بعد ذلك ، أصبحت هذه الخوارزمية معروفة باسم خوارزمية إقليدس)

دعنا نتعرف على خوارزمية إقليدس. فليكن مطلوبًا للعثور على gcd (102 ؛ 84). قسّم رقمًا على آخر وابحث عن الباقي.

لنقم الآن بالعملية نفسها للعددين 84 و 18:

الخطوة التالية هي 18 و 12:

الآن - لـ 12 و 6:

0-بقايا. انتهت العملية.

لا يمكن أن تكون هذه العملية لانهائية ، لأن المخلفات تتناقص وتبقى الأعداد الصحيحة غير السالبة ، مجموعة منها ، كما هو معروف ، محدودة من الأسفل:

84 >18 > 12> 6 >0

إذا نظرت عن كثب إلى المساواة المكتوبة ، يمكنك إثبات أن GCD لجميع أزواج الأرقام متساوية مع بعضها البعض (قم بدعوة الطلاب للتفكير - لماذا؟) ،

أي gcd (102 ؛ 84) = gcd (84 ؛ 18) = gcd (18 ؛ 12) = gcd (12 ؛ 6) = 6. لكن الرقم 6 هو الباقي الأخير غير 0 .

في الواقع ، إذا كان c هو قاسم مشترك عشوائي للعددين a و b ، فإن r = a - bq يقبل القسمة على c ؛ والعكس صحيح ، إذا كانت c مقسومًا عشوائيًا مشتركًا لـ b و r ، فإن a يقبل القسمة على c. أي أن جميع القواسم المشتركة للأزواج (أ ؛ ب) و (ب ؛ ص) تتطابق ، ومن ثم تتطابق أيضًا القواسم المشتركة الأكبر بينهما.

تصبح ملاءمة خوارزمية إقليدس ملحوظة بشكل خاص إذا طبقنا شكل الترميز في شكل جدول:

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

وبالتالي ، فإن القاسم المشترك الأكبر لرقمين هو الأخير ، وليس 0 ، والباقي عند قسمة عدد أكبر على رقم أصغر ، أي إذا أ = ب*q + r ، ثم gcd (a ؛ b) = gcd (b ؛ r)

هذا التسلسل من العمليات يسمى خوارزمية إقليدس. تسمح لك هذه الخوارزمية بالعثور على GCD للأرقام دون أخذها في الاعتبار (الملحق ، الشريحة 5)

6. تمارين (10 دقائق)

1. من المستحسن النظر في مثال. فليكن من الضروري العثور على GCD للأرقام 323 و 437. ليس من السهل القيام بذلك عن طريق الاختيار أو التحلل إلى عوامل أولية ، حيث لا يوجد أي من هذه الأرقام مضاعف 2 ، 3 ، 5 ، 7 ، 11. نحن استكمل كما يلي (

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

الأهداف:كرر الموضوعات التي سبق دراستها أكبر عامل قاسم مشترك وأقل مضاعف مشترك ، وأدخل خوارزمية إقليدس.

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

مهام التطوير - تطوير التفكير المنطقي والانتباه وذاكرة الكلام والقدرة على اكتشاف المعرفة الجديدة بشكل مستقل والفضول الرياضي والاهتمام المعرفي بالموضوع.

تتمثل مهام التعليم في تنمية ثقافة التفكير الرياضي والمساعدة المتبادلة والفحص الذاتي وتحليل أخطاء الفرد.

العمل على البطاقات

ابحث عن أرقام GCD أو LCM وفك تشفير العبارة:

300

D: GCD (33.88)

H: شهادة عدم ممانعة (9.40)

A: كرونة نرويجية (14.42)

E: GCD (48.18)

R: NOC (17.5)

ج: GCD (48.24)

K: GCD (72.12)

L: GCD (20.14)

E: GCD (30.18)

م: شهادة عدم ممانعة (25.12)

T: NOC (4،8،16)

H: شهادة عدم ممانعة (12.40)

ب: GCD (18.35)

أ: GCD (17.34)

الأول: gcd (102.68)

E: GCD (18،12)

في الجدول الأخير ، اكتب أزواج الأرقام المتبقية

الإجابات:

300

لكن

إل

جي

تي

في

إل

لكن

D: GCD (33.88) = 11

G: المضاعف المشترك الأصغر (9.40) = 360

أ: م م (14.42) = 42

ه: GCD (48،18) = 6

السابق: المضاعف المشترك الأصغر (17.5) = 85

ج: GCD (48 ، 24) = 24

ك: GCD (72.12) = 12

L: GCD (20 ، 14) = 2

ه: GCD (30 ، 18) = 6

م: المضاعف المشترك الأصغر (25 ، 12) = 300

T: المضاعف المشترك الأصغر (4،8،16) = 16

H: م م ع (12.40) = 120

ب: gcd (18،35) = 1

أ: GCD (17.34) = 17

و: GCD (102.68) = 34

ه: GCD (18 ، 12) = 6

تخمين كلمتين أكثر

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

يوجد في العمود الأول أزواج من الأرقام ، حيث لا يمكن قسمة أحدهما على الآخر تمامًا. هؤلاء. الباقي ليس 0.

كيف وجدت GCD و LCM لمثل هذه الأرقام. (عن طريق تحليل هذه الأعداد إلى عوامل أولية)

المضاعف المشترك الأصغر (12،40) = 2 3 * 3 * 5 = 120

استرجع قاعدة البحث عن GCD و LCM ، ابحث عن الصيغة LCM (أ ، ج) \ u003d (أ * ب) وتحقق منها: GCD (أ ، ب)

3 *3*11=264

المضاعف المشترك الأصغر (أ ، ب) \ u003d (أ * ب): GCD (أ ، ب)

264=(33*88):11=3*88=264

المضاعف المشترك الأصغر (20 ، 14) = 2 2 * 5 * 7 = 140

المضاعف المشترك الأصغر (أ ، ب) \ u003d (أ * ب): GCD (أ ، ب)

140=(20*14):2=10*14=140

GCD (12 ، 40) = 2 2 = 4

المضاعف المشترك الأصغر (أ ، ب) \ u003d (أ * ب): GCD (أ ، ب)

120=(12*40):4=3*4=120

استكشاف موضوع جديد:

GCD من أزواج الأرقام هو 6؟

6 = gcd (48.18) = gcd (30.18) = gcd (12.18)

ماذا لاحظت؟ كيف حصلت على 30؟ 48-18

كيف حصلت على 12؟ 30-18

عندما أ> ب \ u003d GCD (أ-ب ، ج)

هؤلاء. GCD (a ، c) عندما v> a = GCD (a ، c-a)

من يمكنه الاستمرار في هذه المساواة؟

6 = gcd (48.18) = gcd (30.18) = gcd (12.18) = gcd (12.6) = gcd (6.6) = 6

تستند خوارزمية إقليدس على هذه القاعدة.

خوارزمية إقليدس- فعال في إيجاد اثنين. تمت تسمية الخوارزمية على اسم من وصفها لأول مرة في الكتابين السابع والعاشر "".

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

أطلق علماء الرياضيات اليونانيون القدماء على هذه الخوارزمية اسم "الطرح المتبادل".

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

السؤال الأول هو ، هل هذه الأرقام متساوية؟ لا ، ليستا متساويتين ، لذلك نطرح الأصغر من الأكبر 48-18 = 30. 30 لا تساوي 18 ، مما يعني 30-18 = 12 ، 18-12 = 6 ، 12-6 = 6. أي أننا نقوم بهذه الإجراءات حتى تتساوى الأرقام. ومن ثم GCD (48،18) = 6

بمعرفة GCD للأرقام 48 و 18 ، ابحث عن NOC. المضاعف المشترك الأصغر (48 ، 18) = (48 * 18): 6 = 48 * 3 = 144

لنجد GCD (102 ؛ 68) باستخدام خوارزمية إقليدس.

لنجد إيماءة (357 ؛ 273)

هنا طرحنا العدد 84 3 مرات والعدد 21 ثلاث مرات.

كيف ، بدون إجراء عمليات طرح ، معرفة عدد عمليات الطرح في سلسلة واحدة ، وما الفرق الذي ستكون النتيجة؟ ما الحالات التي يجب النظر فيها؟ ( دلالة: تذكر الانقسام.)

يمكن صياغة القاعدة العامة على النحو التالي: إذا كان الرقم ألا يقبل القسمة على ب، ثم يتم استبداله بالباقي عند القسمة على ب(متى أ< بهذا الباقي أ) ؛ لو أمقسومة على ب، ثم استبدلها برقم ب. بالضبط نفس القاعدة ، مع التقليب أو ب، صالح أيضًا لـ ب. عدد أكبر يقسم إلى الأصغر ، ثم الأصغر إلى الباقي الأول ، ثم الباقي الأول إلى الباقي الثاني ، وهكذا ، حتى تحصل على 0. ثمالباقي الأخير لا يساوي 0 هو GCD .

ابحث عن GCD (357 ؛ 273).

357 273 273 84 84 21 GCD (357 ، 273) = 21

273 1 252 3 21 4

84 21 0

357=1*273+84 273=3*84+21 84=4*21

gcd (357.273) = gcd (273.84) = gcd (84.21) = 21

تصبح ملاءمة خوارزمية إقليدس ملحوظة بشكل خاص إذا طبقنا شكل الترميز في شكل جدول:

وبالتالي ، فإن القاسم المشترك الأكبر لرقمين هو الباقي غير الصفري الأخير عند قسمة العدد الأكبر على الأصغر.، بمعنى آخرإذا أ = ب *q + r ، ثم gcd (a ؛ b) = gcd (b ؛ r)

هذا التسلسل من العمليات يسمى خوارزمية إقليدس.

1) باستخدام خوارزمية إقليدس ، ابحث عن GCD للأرقام:

أ) 703 ، 481 ؛ ب) 2112 و 1680 ؛ ب) 5075 و 1450

GCD (703 ، 481) = 37

GCD (2112 ، 1680) = 48

GCD (5075 ، 1450) =

تحقق من النتائج على جهاز الكمبيوتر.

مهمة الأطفال على الكمبيوتر هي العثور على GCD و LCM لثلاثة أرقام باستخدام البرنامج للعثور على GCD و LCM.

gcd (150 ، ____) = ____

GCD (450،315،135) = ____

GCD (135 ، ____) = ____

GCD (2160،1350،1080) = ____

GCD (1080 ، ____) = ____

GCD (5300،3180،2120) = ____

GCD (2120 ، ____) = ____

(للعثور على GCD لثلاثة أرقام أو أكثر ، ابحث أولاً عن GCD لأي اثنين منهم ، ثم GCD للمقسوم عليه الذي تم العثور عليه والرقم المحدد الثالث.

والثالث رقم معين.

7. التحقق من النتائج على جهاز الكمبيوتر. حل المشكلات بشكل مستقل.

1) تم تحضير نفس الهدايا لطلاب الفصل. جميع الهدايا تضمنت 120 قطعة شوكولاتة و 280 قطعة حلوى و 320 حبة بندق. كم عدد الطلاب في الصف الأول إذا كان معروفاً أن هناك أكثر من 30؟

إجابه:________________________

2) هناك ثلاثة قطارات ركاب في المحطة: في الأول - 418 مقعدًا في مقصورة السيارات ، وفي الثانية - 494 وفي الثالث - 456 - كم عدد سيارات المقصورة في كل قطار إذا كان هناك نفس عدد المقاعد في كل سيارة وعددها الإجمالي أكثر من 20؟ إجابه _________________________

3) صُنعت الباقات من 156 شاي و 234 وردة بيضاء و 390 وردة حمراء ، وفي كل باقات الورد من كل نوع كانت متساوية وكان عدد هذه الباقات أكثر من 50. كم عدد الباقات التي صنعت من هذه الورود وكم عددها الورود من كل نوع كانت في باقة واحدة؟ إجابه_________________

ملخص الدرس. بأي طريقة لإيجاد GCD و LCM التقينا في الدرس. خوارزمية إقليدس. ما هو الاسم الآخر لهذه الطريقة؟ (طريقة الطرح). كيف تم تحسين هذه الطريقة؟ مع القسمة ، يتم قسمة العدد الأكبر على العدد الأصغر ، ثم الرقم الأصغر على الباقي الأول ، ثم الباقي الأول على الباقي الثاني ، وهكذا ، حتى تحصل على 0. والباقي غير الصفري الأخير هو 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) المهام

معاينة:

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

أهداف الدرس:

التعليمية:

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

التعليمية:

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

النامية:

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

خطة الدرس:

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

تنظيم الوقت

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

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

أسئلة:

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

ما هو الهيكل الخطي؟ (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

نهاية.

الجزء العملي

أسئلة ومهام:

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

تلخيص الدرس

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

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

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

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

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

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

بيان المشكلة ضع في اعتبارك المشكلة التالية: مطلوب كتابة برنامج لتحديد القاسم المشترك الأكبر (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."> !}

شريحة 1

الشريحة 2

الشريحة 3

الشريحة 4

تشغيل الخطوة 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: = 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: = M-N 6 15 M N 6 6 لا 16 الخلاصة M

الشريحة 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. تحقق مما إذا كان رقمان معينان يمثلان جريمة مشتركة. ملحوظة. يُطلق على عددين أوليين نسبيًا إذا كان القاسم المشترك الأكبر بينهما هو 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 كتابا) ، يحتوي على أسس الرياضيات القديمة ، والهندسة الأولية ، ونظرية الأعداد ، والنظرية العامة للعلاقات ، وطريقة تحديد المساحات والأحجام ، والتي تضمنت عناصر نظرية الحدود. كان له تأثير كبير على تطوير الرياضيات. يعمل في علم الفلك والبصريات ونظرية الموسيقى.

عرض احتلال الخوارزمية الإقليدية الدائرة. عرض تقديمي حول موضوع "خوارزمية إقليدس". فكرة خوارزمية إقليدس

شرح الشرائح:

معاينة:

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

تنظيم الوقت

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