קודם כל, קוראים לי אוהד, חובב מתמטיקה ומחשבים.
בד"כ אני אכתוב על שאלה מתמטית – אלגוריתמית ופתרונה.
את רוב השאלות שלי אני לוקח מהאתר http://projecteuler.net/index.php?section=problems&sort=id&method=ascending
(פרוייקט אוילר, אתר לחובבי מתמטיקה ברמה גבוהה מאוד)
היום נתחיל במשהו קליל:
שאלה 1:
מצא את סכום המספרים שמתחלקים ב 3 או 5 הקטנים מ 1000.
טוב...
אין פה הרבה אפשרויות לפתור, אז במקום להתברבר על הסבר אומר במילים פשוטות: צריכים לעבור על כל המספרים מ1 עד 999, לבדוק מה מתחלק ב3 או ב5 (והמחשב מחסר כבר את מה שמשותף כחלק מהגדרת "או" המסומן כך "||"), כל פעם שמס' יענה על ההגדרה הזאת נוסיף אותו למשתנה (שם עם גודל ומידע, כלומר, נניח איציק- מכיל את הערך "נכון", או 15).
int sum = 0;
for (int num = 1; num < 1000; ++num)
if (num % 3 == 0 || num % 5 == 0)
sum += num;
Console.WriteLine(sum);
אני רואה שהתחחמנו קצת... אז בואו נדלג לשאלה קצת יותר קשה:
שאלה 7:
מצא את המספר הראשוני ה 10,001.
דבר ראשון, מספר ראשוני = מספר שלא מתחלק באף מספר זולתו ו-1.
מכיוון שמספרים ראשוניים משחקים משחק חשוב בשאלות Project Eulerאז חשוב להתחיל בשאלה פשוטה כזאת....
כמו שאתם יכולים להבין, אנחנו צריכים לרוץ על הרבה מספרים, לזהות אילו מבין המספרים הוא ראשוני וכאשר הגענו למספר הראשוני ה 10001 – להדפיס אותו ולסיים את התוכנית:
int primeCntr = 0;
for (int potentialPrime = 2; ; potentialPrime++)
{
bool isPrime = true;
for (int primeChecker = 2; primeChecker < potentialPrime; ++primeChecker)
if (potentialPrime % primeChecker == 0)
{
isPrime = false;
break;
}
if (isPrime)
{
++primeCntr;
if (primeCntr == 10001)
{
Console.WriteLine(potentialPrime);
break;
}
}
}
הסבר קצר לפאקצות ולטיפשים, סליחה, טיפשות, שלא הבינו את קטע הקוד:
בהתחלה מגדירים משתנה שגדל מ2 ומעלה, אח"כ מגדירים עוד משתנה כזה ומתחילים בהרבה וריאציות של חילוק, כל פעם שוריאציה כזאת היא בעלת שארית- כלומר, המספר ראשוני אז מספר הראשוניים עולה, ככה עד 10000, איך בדיוק זה יודע שזה במיקום הזה? תתאמצו קצת מהקוד!
*הערה: הרצת התוכנית הזו היא סיוט – ההרצה לוקחת כחצי דקה בגלל שלא עשינו פה שום שיפורים.
בהמשך נראה איך ניתן ליעל אלגוריתמים מסוג זה ואיך ניתן לפתור את החידה הזו (על המחשב שלי) בשתי אלפיות בלבד!
לסיום, בואו נפתור את חידה 9. פה אני כן רוצה שננסה לייעל קצת את התוכנית.
התרגיל: מצא את המכפלה של השלשה הפיתגוראית היחידה {a,b,c} שמקיימת a + b + c = 1000.
שלשה פיתגוראית: a*a + b*b = c*c (כאשר a,b,c טבעיים, וc הגדול בשלשה)
מכיוון שיש לנו את המשוואה שלמעלה להגיע מ a ו b ל c – נצטרך לעבור רק על a ו b ולעשות עליהם תנאים לבדוק האם סכום השלשה שווה ל 1000.
לפי מה שהבנו קודם:
פה ניתן לייעל אפילו עוד כי יודעים שהגורמים של 1000-a מוכלים בגורמים של 500-a ו 1000. אבל עזבו את זה. זה לא חיוני כי גם ככה הגענו למשהו יעיל מספיק.
התנאי היחיד שלנו הוא ש b הוא טבעי. (ובהכרחc טבעי)
אז מה שאנחנו צריכים לעשות הוא לרוץ על 1 < a < 293 (אפשר להגיע למספר הזה) ולמצוא מתי b הוא שלם ואז נחשב את a*b*c עבור אותו ה a.
קוד (C#):
for (int a = 1; a < 293; ++a)
{
double b = 1000f * (500 - a) / (1000 - a);
if (b == (int)b)
{
Console.WriteLine(a * b * Math.Sqrt(a * a + b * b));
break;
}
}
אין תגובות:
הוסף רשומת תגובה