שלום לכם,

הפעם לפניכם חידת תִכנות:

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

המשימה שלכם: לכתוב את התוכנה הנ"ל כך שהרובוטים יפגשו לבסוף.

הפקודות העומדות לרשותכם:
1. לך צעד שמאלה.
2. לך צעד ימינה.
3. תנאי: אם יש מתחת מצנח.
(הבהרה למי שאינם בקיאים בתכנות: אם "אם יש מתחת מצנח" הוא פסוק שכאשר הוא אמת יש לעשות פקודה כלשהי).
4. עבור לפקודה מספר N (עבור כל N טבעי)

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

אילוסטרציה: Shutterstock

בהצלחה!

סקובידו



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

9 תגובות

  • אלעד

    מהו הפתרון?

    אשמח למענה

  • אסנת

    פתרון הבעיה

    שני הרובוטים יקודמו בקצב מואט בכיוון זהה, הראשון שפוגש מצנח מאיץ את הקצב
    השני לא יכול לפגוש מצנח היות והוא נע בכיוון מנוגד לו ולכן ממשיך בקצב האיטי:
    1. לך שמאלה
    2 לך ימינה
    3. לך שמאלה
    4. אם יש למטה מצנח עבור לפקודה 3
    5. עבור לפקודה 1

  • רמי

    חידת הרחבה : הרובוטים לא יודעים מצפונם

    חידה דומה לחידה הקיימת למעט שני הסעיפים הבאים:
    א) הרובוטים מוצנחים ולא יודעים אם פניהם צפונה או דרומה.
    ב) מצטרפת לאוסף הפקודות פקודה נוספת (פקודה חמישית):
    5. הכפל את שורת הפקודה הבאה

    הסבר הפקודה : הפקודה גורמת לפקודה שאחריה להיות משוכפלת ולהיות מוכנסת מייד לאחר השורה המשוכפלת (לפני השורה שאחרי המשוכפלת).

    דוגמה:
    למשל שורת הפקודות הבאה :
    1) לך צעד שמאלה
    2) הכפל את שורת הפקודה הבאה
    3) עבור לפקודה מספר 1
    4) לך צעד ימינה

    לאחר איטרציה (חזרור) אחת, רשימת הפקודות תהיה :
    1) לך צעד שמאלה
    2) הכפל את שורת הפקודה הבאה
    3) עבור לפקודה מספר 1
    4) עבור לפקודה מספר 1
    5) לך צעד ימינה

    המשימה שלכם: לכתוב את התוכנה הנ"ל כך שהרובוטים יפגשו לבסוף.

    הערות:
    - לא חייבים להשתמש בכל הפקודות
    - לרובוטים אין מגבלת זיכרון

  • עדי

    עוד פתרון

    רעיון דומה-

    1)לך צעד ימינה
    2)אם יש מתחת מצנח עבור לפקודה מספר 4
    3)עבור לפקודה מספר 1
    4)לך צעד ימינה
    5)לך צעד ימינה
    6)עבור לפקודה מספר 4

    ברגע שהרובוט רואה שחברו היה שם: הוא מתחיל "לרוץ" בגלל שהאחר ממשיך "ללכת", הרובוט ישיג אותו בסוף.
    כמובן שזה תקף רק אם ההנחה של רמי תקפה

  • עדי

    תיקון

    צריך להשהות איך שהוא כי אחרת הרובוטים ילכו באותו הקצב
    או
    שהרובוטים יהיו איטיים במיוחד ושפקודה 2 תגרום להם להשתהות וכך יוכל הרובוט להשיג את חברו

  • רמי

    שאלה

    ברצוני לאשש את ההנחה הבאה:
    הרובוטים נוחתים עם פניהם לאותו צד של הקו.
    כלומר אם הקו נמתח ממזרח למערב, אז הרובוטים ינחתו כששניהם פניהם לכיוון צפון או שניהם פניהם לכיוון דרום.

    האם ההנחה נכונה?
    או אולי הכוונה לכתוב קוד גם למקרה בו הם עשויים לנחות כשפניהם לכיוונים הפוכים : אחד צפון ואחד דרום (ואז ימין ושמאל שונים לכל אחד מהם)

  • מומחה מצוות מכון דוידסוןפזיה

  • רמי

    פתרון

    התוכנה:

    1) לך צעד ימינה (*)
    2) אם יש מתחת מצנח עבור לפקודה מספר 7
    3) לך צעד ימינה
    4) אם יש מתחת מצנח עבור לפקודה מספר 7
    5) לך צעד שמאלה
    6) עבור לפקודה מספר 1
    7) לך צעד ימינה
    8) עבור לפקודה מספר 7

    (*) בהנחה שהמצנח קטן מגודל צעד. אחרת ניתן להגדיל את מספר הצעדים ימינה עד השאלה לגבי המצנח (כי גודלו סופי).

  • איתן

    לא מובן

    הרובוט הולך כל הזמן ימינה, בין אם יש מצנח מתחת ובין אם לא, אם שניהם כל הזמן ימינה- כיצד יפגשו?