ווטסאפ - לינוקס, BSD, קוד פתוח ותוכנה חופשית בעברית. Whatsup - Linux, BSD, open source and free software in Hebrew

 
 
  כניסת חברים · רישום · שכחתי סיסמה  
tux the penguin
תגובה לנושא
צפיה בנושא הבא Printable version התחבר כדי לבדוק הודעות פרטיות צפיה בנושא הקודם
אורח · ·
 

הודעה פורסם: 06/03/2018 - 20:00
נושא ההודעה: שוב פעם מתוסכל אש. שוב פעם haskell. מספרים ראשוניים.

הקוד הזה מוצא מספרים ראשוניים מ-2 ועד... עד מתי שאתם לוחצים Ctrl c או מלכתחילה מבקשים כמות מסויימת של מספרים.
בכל אופן זה לא חשוב.
מה שכן חשוב הוא שאני לא מבין למען השם מה קורה פה.
הרקורסיות האלו דופקות לי את המוח ואני מתוסכל אפילו יותר מזה שאני בתול, כרגע.

קוד:
primes = 2 : [x | x <- [3,5..], isprime x]
isprime x = all (\p -> x `mod` p > 0) (factorsToTry x)
  where
    factorsToTry x = takeWhile (\p -> p*p <= x) primes
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 06/03/2018 - 21:56
נושא ההודעה:

טוב אני חושב שכן הבנתי.
בשורה הראשונה נוצרת רשימה שמתחילה עם המספר הראשוני 2 וממשיכה עם רשימה שבנויה בעזרת המספרים האי זוגיים (עוקבים) שמתחילים ב-3,5 (וכן הלאה) אבל רק כאשר כל המספרים האיזוגיים *האלו*, נבדקים שהם ראשוניים, ע"י הפונקציה isPrime.
ועל כן כרגע בתוך primes יש לנו "רשימה" שיש בה רק את הספרה 2.
ל- isPrime אנו שולחים את הסיפרה 3 בתור התחלה.
הפונקציה all מקבל פונקציה ורשימה.
הפונקציה (ש-all מקבלת) שואלת שאלה על כל איבר מהרשימה ומחזירה bool (כן או לא).
אם כל האיברים ברשימה החזירו כן, התשובה של all תהיה כן.
וכמובן הפוך, אם כולם החזירו תשובה שלילית, תשובת all תהיה לא.
הסוגריים הראשונים ש-all מקבלת היא הפונקציה.
הפונקציה הזו מקבל מהרשימה (הסוגריים השניים ש-all מקבלת) את כל האיברים שלה.
עכשיו אנו מחלקים את x בכל האיברים האלו של הרשימה (פעם פעם) ושואלים האם השארית גדולה מ-0.
אם באחד החילוקים האלו מתקבלת שארית 0 יוצא ש-x אינו מספר ראשוני כי הוא התחלק יפה ובאופן מושלם באחד מהאיברים שברשימה הזו (ואחד מהאיברים שברשימה הזו אינו 1 או x עצמו כמובן Smile).
אם בכל החלוקות (את x באיברי הרשימה) השארית גדולה מ-0, סימן שיש לנו בינגו כלומר מספר ראשוני, כלומר all החזירה true כלומר אנו חוזרים אחורה לשורה הראשונה ומוסיפים את האיבר שבדקנו לספרה 2 שברשימה הראשונית.

אבל רגע רגע, תשאלו אותי:
מה נסגר עם האיבר השני לפונקציה all?
הרי הוא שולח לפונקציה נוספת שמתוארת בשורה הרביעית של הקוד.
זה הקטע שבו התחרפנתי אבל נדמה לי שהבנתי.
זה קצת טריקי אז היו דרוכים. זה גם מאוד מרטיט (בתקווה שאני בכלל צודק במה שאכתוב כמובן Very Happy).
האיבר השני ל- all הוא (כפי שכבר אמרנו למעלה) רשימה שנוצרת ע"י הפונקציה factorsToTry.
factorsToTry גם מקבלת את x שלנו.
takeWhile היא פונקציה שמקבלת שני איברים (אין לי מילה אחרת בנמצא כרגע).
הראשון הוא פונקציה ששואלת שאלה והשני הוא (ניחשתם נכון) רשימה.
כשמה כן היא: takeWhile יוצרת רשימה כל עוד התנאי של הפונקציה שהיא מקבלת מחזיר true.
היא לוקחת את איברי הרשימה ועל כל אחד שואלת את השאלה.
אם נכון, האיבר הזה מתווסף לרשימה חדשה שנוצרת.
כשמגיעים לתשובה שלילית, הפונקציה נעצרת ונשארנו עם הרשימה שקיבלנו עד עכשיו.
וכן, אם למשל כבר האיבר הראשון לא מקיים את התנאי (חוזר false), חוזרת רשימה ריקה.

טוב, ומה התנאי הזה שמופעל על הרשימה הזו?
התנאי שכל איבר מהרשימה הזו, כשאני מכפיל אותו בעצמו (p*p), האם הוא קטן או שווה ל-x שלנו.
למה זה חשוב? טוב ששאלתם.
זה כי (לא יודע להוכיח את זה אבל ניראה שזה נכון) אין צורך לבדוק עוד מספרים אם הגענו למספר שהמכפלה שלו בעצמו, גדולה מ-x שלנו.
תבדקו את זה:
נניח ש- x שלנו הוא 121.
אנחנו לא צריכים לבדוק את כל המספרים מ-2 ועד 121 אם הם מחלקים את 121.
מספיק שנבדוק את כל המספרים עד ל-11.
11 כפול 11 זה 121 ואין עוד מחלקים ל-121 (מלבד 1 ו-121 עצמו).
ככה זה (כניראה) לכל מספר ראשוני.
קחו לכם כל דוגמא אחרת ובדקו Smile.

טוב אז בואו נחזור לענייננו.
אספנו לנו עכשיו רשימה שהיא בעצמה מגיעה מתוך רשימת ה- primes שלנו שהיא בשורה הראשונה של הקוד.
זה החלק המרטיט.
ה- primes כל הזמן נבנית עוד ועוד (ע"י מספרים איזוגיים עוקבים עד אינסוף) וכל הזמן משתמשים בה מחדש (כולל המספרים החדשים שנוספו לה) בתוך הפונקציה factorsToTry.

אז עכשיו לדוגמא הממשית.
המספר הראשון שלנו ברשימה של ה- primes הוא 2.
והתחלנו לייצר רשימה של מספרים איזוגיים עוקבים שמתחילה ב- 3.
וכל מספר כזה, אנו שולחים אותו ל- isPrime.
isPrime משתמש בפונקציה all שהיא בתורה משתמשת בפונקציית תנאי שהסברנו מקודם ורשימה נוספת שנוצרת בעזרת עוד פונקציה factorsToTry.
אז עכשיו אנו עם 3 שמועבר ל-factorsToTry ושם ה-p הוא כל פעם איבר אחר מהרשימה primes.
להזכירכם, כרגע primes היא רק עם איבר אחד (הסיפרה 2).
לכן התנאי שואל אותנו האם 2*2 קטן או שווה ל-x שלנו (שהוא 3).
התשובה שלילית!
לכן מה שחוזר ל- factorsToTry הוא רשימה ריקה.
ואז אנו חוזרים אחורה ל- isPrime ושם הסוגריים השניים נהפכים לרשימה ריקה.
ועכשיו all נבדקת עם תנאי (הסוגריים הראשונים ב- all) ועם רשימה ריקה.
במצב הזה התשובה היא תמיד true (בגלל שלא משנה מה התנאי, הפונקציה all מחזירה true *תמיד* אם הרשימה שמועברת אליה, ריקה.
כלומר isPrime מקבלת תשובה true שחוזרת לשורה הראשונה בקוד.
ובגלל שקיבלנו שם true (ולהזכירכם כל זה לגבי הסיפרה 3), הסיפרה 3 מצטרפת אחר כבוד אל רשימת ה- primes שלנו שעכשיו היא הפכה להיות [2,3].

ועכשיו כל התהליך הזה ממשיך לספרה 5 ברשימה וגם היא נשלחת אל isPrime.
ואז בתוך isPrime אנו קודם צריכים לייצר שם את הרשימה באיבר השני לפונקציה all (כלומר ללכת אל הפונקציה factorsToTry).
אז אנו הולכים לשם (להזכירכם x=5 עכשיו) ועכשיו ה- primes שלנו היא (הרשימה) כבר [2,3] ושוב אנו בודקים:
האם 2*2 קטן או שווה ל-5? כן!
לכן אנו מכניסים אותו לרשימה ש- takeWhile יוצרת לנו.
ואז אנו עוברים לספרה 3 (האיבר השני ב- primes) ושואלים:
האם 3*3 קטן או שווה ל-5? לא!
לכן הוא לא נכנס לרשימתנו הקטנה ו- takeWhile חוזרת עם הרשימה [2] אל isPrime (אל האיבר השני ש- isPrime מקבלת שהוא בעצם הרשימה שנוצרה לנו לפני רגע שכוללת את הסיפרה 2 בלבד).
שם אנו נשאלים האם ה- x שלנו (5), כשאני מחלק אותו ב-2 (שזהו ה- p) נותן שארית גדולה מ-0?
התשובה כן!
כלומר isPrime מחזירה true לשורה הראשונה בקוד ואכן גם 5 הינו ראשוני וגם הוא מצטרף אל ה- primes שלנו כך שעכשיו primes נראית כך [2,3,5]

וכן הלאה וכן הלאה עד קץ הימין Smile.
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 06/03/2018 - 22:04
נושא ההודעה:

רק מתקן משהו:
"אספנו לנו עכשיו רשימה שהיא בעצמה מגיעה מתוך רשימת ה- primes שלנו שהיא בשורה הראשונה של הקוד.
זה החלק המרטיט.
ה- primes כל הזמן נבנית עוד ועוד (ע"י מספרים איזוגיים עוקבים עד אינסוף) וכל הזמן משתמשים בה מחדש (כולל המספרים החדשים שנוספו לה) בתוך הפונקציה factorsToTry. "

זה לא מדוייק.
ה- primes אכן גדלה כל הזמן, אבל לא בכל האיזוגיים שנוצרים שם, אלא רק האי זוגיים שהם *גם* isPrime (כלומר ראשוניים).
כל פעם שמצאנו איזוגי שהוא גם ראשוני, הוא מתווסף ל- primes ואז בהמשך כשנגיע עוד פעם לפונקציה factorsToTry שבה משתמשים ב- primes, ה- primes תהיה מעודכנת ותכלול גם את המספר הראשוני החדש שמצאנו.
וכן הלאה עד אינסוף לכאורה.
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 06/03/2018 - 22:06
נושא ההודעה:

עזוב אותך ממחשבים ורקורסיות, לך תאבד את הבתולים, זה הדבר הכי חשוב
בתנאי כמובן שאתה מעל גיל 14.
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 06/03/2018 - 22:50
נושא ההודעה:

Anonymous :
עזוב אותך ממחשבים ורקורסיות, לך תאבד את הבתולים, זה הדבר הכי חשוב
בתנאי כמובן שאתה מעל גיל 14.


אני בן מעל 30 לא עלינו.
ואני לא באמת בתול, אלא בתול מחדש (כלומר הרבה זמן כבר לא...). Surprised
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 07/03/2018 - 12:12
נושא ההודעה:

Anonymous :
עזוב אותך ממחשבים ורקורסיות, לך תאבד את הבתולים, זה הדבר הכי חשוב
בתנאי כמובן שאתה מעל גיל 14.

גיל 14?! מה נסגר?!
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 07/03/2018 - 12:43
נושא ההודעה:

Anonymous :
Anonymous :
עזוב אותך ממחשבים ורקורסיות, לך תאבד את הבתולים, זה הדבר הכי חשוב
בתנאי כמובן שאתה מעל גיל 14.

גיל 14?! מה נסגר?!

אכן מוזר.
גם אני חשבתי שזה מבוגר מדי.
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
אורח · ·
 

הודעה פורסם: 07/03/2018 - 20:17
נושא ההודעה:

Anonymous :
Anonymous :
עזוב אותך ממחשבים ורקורסיות, לך תאבד את הבתולים, זה הדבר הכי חשוב
בתנאי כמובן שאתה מעל גיל 14.

גיל 14?! מה נסגר?!

בזמנו קיבלתי מתנה יפה מחברה שלי ליום הולדת 14, ומאז ברוך השם כבר 28 שנה העסק כמעט לא מפסיק לעבוד, חוץ מכמובן טירונות ושנה קשה עם מעט יציאות בשריון...
 
   
תגובה  עם ציטוט חזרה למעלה
חזרה לתוכן הדיון
הצגת הודעות מלפני:     
מעבר אל:  
כל הזמנים הם GMT + 2 שעות
תגובה לנושא
צפיה בנושא הבא Printable version התחבר כדי לבדוק הודעות פרטיות צפיה בנושא הקודם
PNphpBB2 © 2003-2004 

תוכן הדיון

  1. אורח
  2. אורח
  3. אורח
  4. אורח
  5. אורח
  6. אורח
  7. אורח
  8. אורח