תכנות - שיעור 23 18/December/2005    

קצת לוגיקה

דברנו על הטיפוס bool של Python המקבל ערכים של (שקר ואמת) False, True בלבד. אפשר להפעיל את פעולת השלילה not שהופכת אמת לשקר, ושקר לאמת, וכן פעולות של או (or) ושל וגם (and) על שני ערכים בוליאנים (לוגיים). הטבלאות הבאות מתארות את חוקי החישוב.

או:

וגם:

יעילות בבדיקת ראשוניות

כאשר מחפשים האם קיים מחלק למספר כך ש כדאי כמובן להתחיל לבדוק עבור

הכי פשוט לבדוק עד אבל זה עלול להיות תהליך איטי. קל לראות שאפשר לקצר ולבדוק עד

משפט: אם אז הוכחה: אם בדרך השלילה, אז אפשר להכפיל את שני אי-השויונים, ומקבלים: וזוהי סתירה לכך ש-

תרגילים

1. הריצו את התכנית, לבדיקת ראשוניות, שכתבתם לשעור הקודם (מבלי לשפרה!), ובדקו אותה עם המספר: רמז: זהו מספר ראשוני!
2. כתבו גירסא יעילה יותר של התכנית תוך ניצול הדיון שלמעלה. הריצו שוב עם אותו ראשוני גדול.
3. כתבו תכנית ובה פונקציה שמקבלת שני מספרים שלמים כפרמטרים isPythagoras(a,b) ומחזירה True אם הוא מספר רבועי, כלומר יש לו שורש רבועי שלם, ומחזירה False אחרת. התכנית תקרא לפונציה עבור כל זוגות המספרים שנתנים בשורת הפקודה, ותדפיס את "פסק הדין".

פתרון לתרגיל קודם

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