בתשובה לגדי אלכסנדרוביץ', 08/09/05 21:34
אלגוריתם אוקלידס - נוסח מקוצר 328482
אם אתה מחפש את הממג"ב של 1,000,000 ו-‏7, האלגוריתם המחסר יבלה זמן רב בניסיון להיפטר מה-‏7.

זו חידה נחמדה למצוא את צמדי המספרים הכי גרועים לאלגוריתם האוקלידי (רמז: בצמדים האלה, האלגוריתם המחלק מתנהג דומה מאוד לאלגוריתם המחסר). (עוד רמז: שפנים).
אלגוריתם אוקלידס - נוסח מקוצר 328494
פיבונאצ'י?
אלגוריתם אוקלידס - נוסח מקוצר 328495
כן. (למה?)
אלגוריתם אוקלידס - נוסח מקוצר 328502
נניח ש-x,y הם שני מספרי פיבונאצ'י רצופים, אז x=y+z כש-z הוא זה שלפני שניהם, ו-y>z כי y עצמו הוא סכום של שני מספרים טבעיים שאחד מהם הוא z. לכן x=y+z זו גם החלוקה עם שארית של x ב-y.

נחמד.
אלגוריתם אוקלידס - נוסח מקוצר 328527
בינתיים רק הסברת למה בהפעלת אוקלידס על פיבונצ'י, המנה בכל סיבוב היא תמיד 1 (והשארית היא מספר פיבונצ'י קודם). אינטואיטיבית זה נראה "הכי גרוע", אבל זה תרגיל מעניין וחינוכי לנסח בדיוק את הטענה שזה באמת "הכי גרוע", ואז להוכיח אותה בזהירות.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים