תכנות - שיעור 34 2/April/2006    

הצבת מלכות על לוח שחמט

אנו רוצים להציב 8 מלכות על לוח שחמט כך שלא "תאיימנה" אחת על רעותה. הנה פתרון עבור 5 מלכות על לוח של lteq1.png

כלומר מלכות במשבצות:

a1 b4 c2 d5 e3
אנו נעדיף את הסימון הבא:
lteq2.png
כלומר את המשבצות כזוגות של טור ושורה:
lteq3.png
ובפייתון נתאר את קבוצת המשבצות הללו בצורה חסכונית כרשימת השורות:
[0, 3, 1, 4, 2]
שימו לב: אין צורך לציין את הטור כי הוא נובע מהמקום ברשימה.

נמשיך לדון בבעייה מאוחר יותר. תחילה נקל על עצמנו.

הצבת צריחים

ניתן להציב 3 צריחים על לוח של lteq4.png כך שלא יהיה ביניהם איום ב-6 הצורות הבאות:

lteq5.png

למעשה מדובר ב-6 האפשרויות לסדר בסדרה את lteq6.png

תמורות (permutations) ועצרת (factorial)

נגדיר את פעולת עצרת (factorial) באופן הבא:
lteq7.png
לדוגמא:
lteq8.png

קל לראות כי מספר התמורות שהן האפשרויות בהן ניתן לסדר lteq9.png אברים שונים הוא lteq10.png

תרגילים

פתרונות לקודמים

צפו או הורידו פתרון לתרגיל 2 של שעור קודם.

חדשים

  1. סימו (מי שלא סיים) את תרגיל 3, ונסו שוב את תרגיל 5 של שעור קודם.
  2. הורידו והריצו את תכנית הדוגמא מהשעור הקודם. שנו אותה כך שלכל אדם (Person) יצויין ויודפס גם צבע העיניים (eye_color).
  3. כתבו פונקציה (כמו שכתבנו על הלוח בשיעור) שמקבלת רשימת מספרים lteq11.png שמתארים סדרת משבצות על לוח שחמט, בסימון שלנו את המשבצות:
    lteq12.png
    ומחזירה מחרוזת של שמות שחמט של המשבצות.
    לדוגמא (כמו למעלה): אם הפונציה תקבל lteq13.png אז היא תחזיר את המחרוזת:
    "a1 b4 c2 d5 e3"
חזרה לעמוד האם