בתשובה ל., 08/09/05 20:47
אלגוריתם אוקלידס - נוסח מקוצר 328472
מה שמעניין הוא אם האלגוריתם הזה יעיל באותה מידה כמו האלגוריתם המקורי. למישהו יש דוגמה שעליה האלגוריתם הזה "ייתקע" להרבה זמן?
אלגוריתם אוקלידס - נוסח מקוצר 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 (והשארית היא מספר פיבונצ'י קודם). אינטואיטיבית זה נראה "הכי גרוע", אבל זה תרגיל מעניין וחינוכי לנסח בדיוק את הטענה שזה באמת "הכי גרוע", ואז להוכיח אותה בזהירות.
אלגוריתם אוקלידס - נוסח מקוצר 328483
מה זה כבר מקדם פולינומי ביני ובינך...

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

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