אלגוריתם אמצע הריבוע
 |
ערך מחפש מקורות
| |
| ערך מחפש מקורות | |
אמצע הריבוע הוא אלגוריתם פרימיטיבי שמשמש ליצירת מספרים פסאודו אקראיים על בסיס מספר "זרע" ממנו מתחילה יצירת המספרים.
האלגוריתם נחשב לשיטה גרועה למדי, שכן בשלב כלשהו יתקבל שוב מספר שכבר נכלל ברשימה והיא תתחיל לחזור על עצמה. מכאן שהתפלגות המספרים ברשימה המתקבלת אינה אקראית ולכן לא מדובר בשיטה שמייצרת רשימה פסאודו אקראית של ממש[1]. עם זאת השיטה פשוטה, ומשמשת דוגמה טובה לשימוש במספר "זרע" ליצירת רשימה פסאודו אקראית. בנוסף, שימוש בזרעים ספציפיים מניב רשימה ארוכה לפני שמתקבל מספר שכבר היה, ואם אין צורך במספרים פסאודו אקראיים רבים השיטה טובה די הצורך.
האלגוריתם הוא להעלות את המספר הקודם בריבוע, ולבחור את הספרות האמצעיות של התוצאה בתור המספר הבא.
דוגמה לבחירת מספר פסאודו אקראי בעל 4 ספרות זרע 3237 3237 בריבוע זה 10,478,169 לכן השלב הבא הוא הספרות אמצעיות של 10,478,169, שהן 4781 4781 בריבוע זה 22,857,961 לכן השלב הבא הוא 8579 וחוזר חלילה.
כך הזרע קובע באופן דטרמיניסטי לחלוטין רשימה אינסופית של מספרים, מבלי שיהיה צורך לייצר את הרשימה מראש.
על מנת למנוע דעיכה של הריבועים למספר קטן מ-10,000,000, אם המספר הבא קטן מ-1,000 מוסיפים ספרה קבועה בסיום המספר הבא, למשל את הספרה האחרונה של המספר הקודם, על מנת למנוע דעיכה של הריבועים למספר קטן מ-10,000,000. דעיכה כזו פירושה שיתקבלו מספרים שאינם בני 4 ספרות, בניגוד לדרישה מהאלגוריתם.
לדוגמה 9384 בריבוע זה 88,059,456 הספרות האמצעיות הן 0594 מסיטים את המספר ספרה לשמאל, ומוסיפים 9, שהוא הספרה הראשונה של המספר הקודם כך שהמספר הבא הוא 9594
קיימות שיטות נוספות לפתרון סוגיה זו.
הערות שוליים[עריכת קוד מקור | עריכה]
- ^ Donald E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, 2nd edn. (Reading, Mass.: Addison-Wesley, 1981), ch. 3, section 3.1.