רוטר - חידה נחמדה ששמעתי (ופתרתי), לא חושב שיהיה לכם אתגר :)

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"חידה נחמדה ששמעתי (ופתרתי), לא חושב שיהיה לכם אתגר :)"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #15563	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 15563

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק, 36 נקודות

23:18 18.11.09

חידה נחמדה ששמעתי (ופתרתי), לא חושב שיהיה לכם אתגר :)

2 רובוטים מוצנחים על קו אינסופי, בנקודות שונות על הקו.
בהגעה לאדמה, המצנח נמצא לידם, ותכנה מסויימת מורצת אצל 2 הרובוטים בו זמנית, ועם בדיוק אותו סט של פקודות.
המטרה - לגרום לרובוטים להיפגש לבסוף.
הפקודות העומדות לרשותכם:
1. לך צעד שמאלה
2. לך צעד ימינה
3. אם ליד מצנח, לך לשורה מספר...
4. לך לשורה מספר...
יש לכתוב את התכנית בצורה BASIC, עם שורות, למשל:
1. לך שמאלה
2. לך שמאלה
3. אם ליד מצנח, לך לשורה 4.
4. לך לשורה 1
וכו' וכו'.

בהצלחה

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
מה המטרה אבל? לשאוף למינימום סיבוכיות זמן\מקום?	DLN	18.11.09 23:58	1
לא, רק לפתור חחח, אבל בוא נראה מי יפתור בהכי פחות שורות	Ice Cold	19.11.09 00:10	2
אממ רגע	ronen333	19.11.09 00:16	3
אז ככה:	Ice Cold	19.11.09 09:46	4
אממ	ronen333	19.11.09 14:21	6
כן...	Deuce	19.11.09 14:23	7
חידה נחמדה, אני מכיר ופתרתי, לכן לא אגלה.	Deuce	19.11.09 14:15	5
אני זוכר דיברנו על זה גם בתלת מימד :)	Net_Boy	20.11.09 15:57	18
חחח כן, בטעות פתרתי לך את זה בתלת מימד בזמנו.	Deuce	20.11.09 16:38	19
לא הבנתי את פקודה מספר 3,	שמשון פישטונה	19.11.09 14:28	8
לפקודה מספר ... אני מניח	Oleaf	19.11.09 14:32	9
יעני JUMP	ronen333	19.11.09 15:04	11
שורת פקודה מספר...	Ice Cold	20.11.09 00:24	15
התוכנה צריכה להיות סופית נכון?	Oleaf	19.11.09 14:33	10
כעקרון אם כל פקודה\שורה	DOWNTOWN	19.11.09 15:05	12
אה טוב גם בלי זה אפשר, הצלחתי בלי ההנחה	DOWNTOWN	19.11.09 16:06	14
זה הפתרון אם מישהו מעוניין	DOWNTOWN	21.11.09 22:59	29
כל הכבוד :)	Ice Cold	21.11.09 23:05	30
YEP.	Deuce	21.11.09 23:27	31
פאק איזה אדיר.. לא חשבתי על זה P=	ronen333	23.11.09 21:34	35
לי זה נשמע כמו Beam Search, למרות שאפשר להשתמש	ldan192	19.11.09 15:19	13
Beam Search ?! זה יותר אלגוריתם יוריסטי לא?	Deuce	20.11.09 04:03	16
משתמשים המון, אבל כנראה שלא בחידות שאין בהן יש	ldan192	20.11.09 23:03	21
לא כזה קל לממש.	Deuce	20.11.09 23:29	22
האמת היא שזה דבר שבקלות אפשר לממש ע''י מכונת טיורינג	ldan192	21.11.09 11:39	23
לא רואה איך אפשר לממש את זה בקלות גם בעזרת מ''ט.	Deuce	21.11.09 15:39	24
הרי יש להם בהכרח זכרון, נכון?	ldan192	21.11.09 18:17	25
זה נהיה ויכוח פלצני אבל אתה טועה.	Deuce	21.11.09 21:24	26
מה נסגר איתך עידן? זו חידה... לא מצב מציאותי בחיים	ronen333	21.11.09 21:27	27
אין שום פלצנות. אחרי הכל, תסכים איתי שכל אלגוריתם	ldan192	22.11.09 00:12	32
מבקשים ממך לכתוב	שמשון פישטונה	23.11.09 13:11	34
ברשותך יניב מספר חידודים.	Deuce	20.11.09 04:11	17
פתרון?	ronen333	20.11.09 18:01	20
ואני חשבתי שזה יהיה לכם קל... :/	Ice Cold	21.11.09 22:18	28
טעית P=	ronen333	22.11.09 09:32	33

DLN
חבר מתאריך 20.4.07
15884 הודעות, דרג אמינות חבר זה

23:58 18.11.09

1. מה המטרה אבל? לשאוף למינימום סיבוכיות זמן\מקום?
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק, 36 נקודות

00:10 19.11.09

2. לא, רק לפתור חחח, אבל בוא נראה מי יפתור בהכי פחות שורות
בתגובה להודעה מספר 1

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

00:16 19.11.09

3. אממ רגע
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 19.11.09 בשעה 00:19 בברכה, ronen333

1)אתה שולט ב2 הרובוטים?
2)אתה יודע באיזה צד הרובוט? XD ח...
3)הם בדיוק אותם רובוטים? זזים באותה מהירות?

זה נקודות שאתה צריך להדגיש.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק, 36 נקודות

09:46 19.11.09

4. אז ככה:
בתגובה להודעה מספר 3

בדיוקקק אותם רובוטים, זזים באותה מהירות, והם לא זזים לשום מקום אם לא תגיד להם. הקוד שתכתוב ירוץ ב-2 הרובוטים בו זמנית, ככה שהצד לא משנה. תגיד שמאלה - שניהם יזוזו שמאלה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

14:21 19.11.09

6. אממ
בתגובה להודעה מספר 4

קו אינסופי ישר? כי אם כן אין לי מושג X=

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

14:23 19.11.09

7. כן...
בתגובה להודעה מספר 6

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

14:15 19.11.09

5. חידה נחמדה, אני מכיר ופתרתי, לכן לא אגלה.
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Net_Boy

חבר מתאריך 1.4.02
17151 הודעות, 1 פידבק, 2 נקודות

15:57 20.11.09

18. אני זוכר דיברנו על זה גם בתלת מימד :)
בתגובה להודעה מספר 5

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

16:38 20.11.09

19. חחח כן, בטעות פתרתי לך את זה בתלת מימד בזמנו.
בתגובה להודעה מספר 18

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

שמשון פישטונה

דרג אמינות חבר זה

14:28 19.11.09

8. לא הבנתי את פקודה מספר 3,
בתגובה להודעה מספר 0

מה זאת אומרת לך לשורה מספר...?

מדברים על קוו אחד או על מספר קווים?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Oleaf
חבר מתאריך 15.11.09
651 הודעות

14:32 19.11.09

9. לפקודה מספר ... אני מניח
בתגובה להודעה מספר 8

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

15:04 19.11.09

11. יעני JUMP
בתגובה להודעה מספר 8

קפיצה לא מותנת לשורה.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק, 36 נקודות

00:24 20.11.09

15. שורת פקודה מספר...
בתגובה להודעה מספר 8

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Oleaf
חבר מתאריך 15.11.09
651 הודעות

14:33 19.11.09

10. התוכנה צריכה להיות סופית נכון?
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DOWNTOWN
חבר מתאריך 28.5.02
5388 הודעות, דרג אמינות חבר זה

15:05 19.11.09

12. כעקרון אם כל פקודה\שורה
בתגובה להודעה מספר 0

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

s22holyshits33

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DOWNTOWN
חבר מתאריך 28.5.02
5388 הודעות, דרג אמינות חבר זה

16:06 19.11.09

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

DOWNTOWN
חבר מתאריך 28.5.02
5388 הודעות, דרג אמינות חבר זה

22:59 21.11.09

29. זה הפתרון אם מישהו מעוניין
בתגובה להודעה מספר 14

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

1. ללכת שמאלה
2. ללכת ימינה
3. ללכת שמאלה
4. אם ליד מצנח עבור לשורה 6
5. עבור לשורה 1
6. ללכת שמאלה
7. עבור לשורה 6
כעקרון, השמאלי יותר יילך שמאלה לעד, אבל בקצב איטי(שמאלה,ימינה,שמאלה)
והימני יילך בקצב האיטי עד שהוא יגיע למצנח השמאלי ואז הוא ילך די מהר יחסית, ויעקוף אותו בסופו של דבר(קו אינסופי)

s22holyshits33

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק, 36 נקודות

23:05 21.11.09

30. כל הכבוד :)
בתגובה להודעה מספר 29

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

23:27 21.11.09

31. YEP.
בתגובה להודעה מספר 29

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

21:34 23.11.09

35. פאק איזה אדיר.. לא חשבתי על זה P=
בתגובה להודעה מספר 29

כל הכבוד

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

15:19 19.11.09

13. לי זה נשמע כמו Beam Search, למרות שאפשר להשתמש
בתגובה להודעה מספר 0

גם ב-Random Restart או ב-iDSF.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

04:03 20.11.09

16. Beam Search ?! זה יותר אלגוריתם יוריסטי לא?
בתגובה להודעה מספר 13

משתמשים בזה בכלל?
בכל מקרה תפתרו כבר חח

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

23:03 20.11.09

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

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

23:29 20.11.09

22. לא כזה קל לממש.
בתגובה להודעה מספר 21

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

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

11:39 21.11.09

23. האמת היא שזה דבר שבקלות אפשר לממש ע''י מכונת טיורינג
בתגובה להודעה מספר 22

וכמעט כל דבר שקל לממש ע"י מכונת טיורינג יהיה קל לממש בתוכנה.

בהינתן סט הפקודות האלה, זה לא אמור לקחת יותר מ-8 שורות קוד.

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

15:39 21.11.09

24. לא רואה איך אפשר לממש את זה בקלות גם בעזרת מ''ט.
בתגובה להודעה מספר 23

מודלים וחישוביות זה התחום שלי, תזהר
אתה כן יכול להגיד במ"ט בהתחלה לשים תו מצד ימין ומצד שמאל, לחזור להתחלה. לך ימינה, עבור למצב Q1. חזור למצב q1 עד שנתקלת בתו ריק ואז תרשום שם תו חדש. לך שמאלה למצב Q2. המשך שמאלה עד שנתקלת בתו ריק, שים תו חדש וחזור ל-Q1.

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

18:17 21.11.09

25. הרי יש להם בהכרח זכרון, נכון?
בתגובה להודעה מספר 24

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

21:24 21.11.09

26. זה נהיה ויכוח פלצני אבל אתה טועה.
בתגובה להודעה מספר 25

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

21:27 21.11.09

27. מה נסגר איתך עידן? זו חידה... לא מצב מציאותי בחיים
בתגובה להודעה מספר 25

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

מה נסגר איתך אחי?

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ldan192
חבר מתאריך 14.9.08
95119 הודעות

00:12 22.11.09

32. אין שום פלצנות. אחרי הכל, תסכים איתי שכל אלגוריתם
בתגובה להודעה מספר 27

ערכתי לאחרונה בתאריך 22.11.09 בשעה 00:16 בברכה, ldan192

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

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

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

בברכה,
עידן

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

שמשון פישטונה

דרג אמינות חבר זה

13:11 23.11.09

34. מבקשים ממך לכתוב
בתגובה להודעה מספר 32

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

04:11 20.11.09

17. ברשותך יניב מספר חידודים.
בתגובה להודעה מספר 0

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

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

18:01 20.11.09

20. פתרון?
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 20.11.09 בשעה 18:06 בברכה, ronen333

מסתבר שלא...

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Ice Cold

חבר מתאריך 3.8.02
28041 הודעות, 19 פידבק, 36 נקודות

22:18 21.11.09

28. ואני חשבתי שזה יהיה לכם קל... :/
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

09:32 22.11.09

33. טעית P=
בתגובה להודעה מספר 28

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד