רוטר - אתגר מתמטי (קומבינטוריקה) + תיכנותי לפורום

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

"אתגר מתמטי (קומבינטוריקה) + תיכנותי לפורום"

גירסת הדפסה

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

אשכול מספר 14636

Net_Boy

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

21:21 10.03.08

אתגר מתמטי (קומבינטוריקה) + תיכנותי לפורום

עוגן האשכול הוסר בתאריך 22.03.08 בשעה 23:15 על-ידי Net_Boy, (סגן מנהל)

הרבה זמן לא היה אתגר והחלטתי להעלות אחד.
אני הכנתי את האתגר והוא לא לקוח מאף מקום ,אז אני אשמח לקבל כל סוג של משוב בסוף האתגר (לטובה או לרעה).
הזוכה יקבל WINNER + נקודות למחפשים (לא יודע עדיין כמה , שחן יחזור הוא יחליט)
החידה לא כל כך קלה אבל היא בהחלט מאתגרת ושווה להשקיע זמן ולנסות לפתור אותה (אגב, הייתה חידה די דומה בעבר . זו קצת משודרגת)
היא מורכבת מחלק מתמטי וחלק תיכנותי.
פשוט תנסו לעשות מה שאתם מצליחים. זה לא נורא אם לא פתרתם את הכל.
את החלק התיכנותי ניתן להגיש בכל שפת תיכנות שהיא (מבחינתי עדיף C\C++ אבל כל דבר יתקבל בברכה).
החלק התיכנותי :
נתונה מטריצה בגודל mxn בעלת ערכים 0 או 1. כאשר 0 מסמן נתיב חסום ו1 מסמן נתיב שניתן לעבור בו.
צריך לכתוב פונקציה שמקבלת 2 זוגות קורדינטות שמייצגות תאים במטריצה ולמצוא את כל המסלולים האפשריים בין 2 הזוגות האפשריים כאשר הכיוונים הם : <מעלה,מטה,שמאלה,ימינה> .
עכשיו הפונקציה צריכה להחזיר את כל המסלולים האלו (כלומר מבחינה טכנית זה מערך שמכיל מערכים שמכילים זוגות של מספרים) ואין להשתמש בשום פונקציות עזר.
אין להפוך לגרפים , זו שאלה של מטריצות נטו.
החלק המתמטי :
נתונה מטריצה nxn . יש למצוא נוסחא הנותנת את מספר המסלולים האפשריים בין 2 הנקודות באלכסון הראשי , כאשר ניתן ללכת רק בכיוונים: <מעלה,מטה,שמאלה,ימינה> .
לדוגמא: עבור מטריצה בגודל 2x2 ישנם שתי מסלולים.

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

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
אחלה יוזמה :) אם יהיה לי זמן מתישהו אשתדל להשתתף. בהצלחה לכולם!	idan192	10.03.08 22:49	1
יאללה עידן אני בונה עליך :)	Net_Boy	10.03.08 23:01	2
הלוואי שהיה לי זמן(-: אולי אם יהיה אשב על זה	men123	11.03.08 12:07	3
את השאלה הראשונה נתת כבר פעם :\	DLN	11.03.08 18:13	4
נכון ולא נכון	Net_Boy	11.03.08 18:56	5
צריך לחשוב על פחות פרמטרים	DLN	11.03.08 19:12	6
בחלק המתמטי..	sHuMpI	11.03.08 19:21	7
כל מסלול אפשרי...	Net_Boy	11.03.08 19:24	8
אממ אם הייתם משקיעים קצת בלהסביר חלק מהמושגים שכתבת שם הייתי משתתף:}	akoka	14.03.08 20:20	9
החלק המתמטי זה משהו אפשרי מבחינתנו	mega-killer	14.03.08 22:29	10
כל תיכנות זו מתמטיקה. צריכה להיות לך רק רמת חשיבה תכנותית	idan192	15.03.08 12:50	11
מספיקה רמה של מתמטיקה 5 יחידות	Net_Boy	15.03.08 17:56	12
למה לא לממש עם גרף אגב ?	dingrins	16.03.08 14:22	13
כי זה אתגר של מטריצות :)	Net_Boy	16.03.08 21:03	14
what ever :P	dingrins	16.03.08 23:45	15
הממ טוב, ביקשתי שאני אתן קצת PUSH לחברה :)	IcqBoy	17.03.08 00:31	16
טוב בגלל חוסר הענות מוחלט , האתגר יורד	Net_Boy	22.03.08 23:15	17
באסה דווקא רציתי ללכת על זה :\	Ngel	22.03.08 23:32	18
יאללה אז תעלה את הקוד , אני אמתין בנתיים :)	Net_Boy	23.03.08 00:03	19
יש את מה שכתבתי שלא ממש עובד אבל הרעיון נכון חח	DLN	23.03.08 16:14	20
אני בסוף שבוע מפרסם את הפיתרון אם מישהו יעלה לפני יזכה בוינר	Net_Boy	24.03.08 23:25	21
בקשר לאתגר המתמטי.	IcqBoy	07.04.08 00:33	22
באשר למתכנתים -	IcqBoy	07.04.08 00:34	23

idan192

22:49 10.03.08

1. אחלה יוזמה :) אם יהיה לי זמן מתישהו אשתדל להשתתף. בהצלחה לכולם!
בתגובה להודעה מספר 0

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

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

Net_Boy

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

23:01 10.03.08

2. יאללה עידן אני בונה עליך :)
בתגובה להודעה מספר 1

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

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

men123
חבר מתאריך 3.10.05
6269 הודעות

12:07 11.03.08

3. הלוואי שהיה לי זמן(-: אולי אם יהיה אשב על זה
בתגובה להודעה מספר 0

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

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

DLN
חבר מתאריך 20.4.07
15884 הודעות

18:13 11.03.08

4. את השאלה הראשונה נתת כבר פעם :\
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 11.03.08 בשעה 18:13 בברכה, DLN

כאילו אז נתת מקרה ספציפי
ועידן פתר את זה ממש אלגנטית עם באקטראקינג
גם פה אפשר לעשות את זה ממש פשוט עם באקטראקינג
אני מציע שתשנה את החידה ככה שהפתרון הכי יעיל ינצח, ולאו דווקא הכי אלגנטי
בבאקטראקינג זה יוצא O(2^2n) לכל קואורדינטת התחלה שלא נמצאת על גבולות המערך וo(2^n) גם למצב הכי נוח שזה בפינות :|
את המתמ' אני לא יודע חח
אני אשב על זה מחר ואם אני אצליח ת'מתמ' אני אעלה את שני הפתרונות :|

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

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

Net_Boy

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

18:56 11.03.08

5. נכון ולא נכון
בתגובה להודעה מספר 4

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

בהצלחה

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

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

DLN
חבר מתאריך 20.4.07
15884 הודעות

19:12 11.03.08

6. צריך לחשוב על פחות פרמטרים
בתגובה להודעה מספר 5

אז היית צריך לעשות השוואות לבדוק מה המסלול הקצר, הפעם כל פעם שאתה מגיע לסוף המסלול אתה פשוט מדפיס אותו :|
בקיצור, אני אשב על זה עוד מעט וזהו :}

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

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

sHuMpI

19:21 11.03.08

7. בחלק המתמטי..
בתגובה להודעה מספר 0

נגיד במטריצה 4 על 4, כל מסלול באורך 6 הכוונה?

או גם לקחת מסלולים ארוכים?

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

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

Net_Boy

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

19:24 11.03.08

8. כל מסלול אפשרי...
בתגובה להודעה מספר 7

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

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

akoka

20:20 14.03.08

9. אממ אם הייתם משקיעים קצת בלהסביר חלק מהמושגים שכתבת שם הייתי משתתף:}
בתגובה להודעה מספר 0

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

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

mega-killer
חבר מתאריך 1.8.02
859 הודעות

22:29 14.03.08

10. החלק המתמטי זה משהו אפשרי מבחינתנו
בתגובה להודעה מספר 0

או שצריך תואר שני?
או שהחלק התיכנותי מרמז על הנוסחא המתמטית?

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

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

idan192

12:50 15.03.08

11. כל תיכנות זו מתמטיקה. צריכה להיות לך רק רמת חשיבה תכנותית
בתגובה להודעה מספר 10

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

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

Net_Boy

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

17:56 15.03.08

12. מספיקה רמה של מתמטיקה 5 יחידות
בתגובה להודעה מספר 10

אתה צריך לדעת מה זה רקורסיה בצורה המתמטית ולאו דווקא בצורה התיכנותית

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

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

dingrins

14:22 16.03.08

13. למה לא לממש עם גרף אגב ?
בתגובה להודעה מספר 0

נשמע לי יותר הגינוי ..
1\0 = אם יש קשת או אין קשת ..

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

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

Net_Boy

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

21:03 16.03.08

14. כי זה אתגר של מטריצות :)
בתגובה להודעה מספר 13

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

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

dingrins

23:45 16.03.08

15. what ever :P
בתגובה להודעה מספר 14

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

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

IcqBoy

00:31 17.03.08

16. הממ טוב, ביקשתי שאני אתן קצת PUSH לחברה :)
בתגובה להודעה מספר 0

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

למה זה? זה לא כזה טריוויאלי. מומלץ קודם להכיר את בעיית סידור n תפוזים זהים ב-k תאים שונים ואז לנסות ולהבין מה הולך פה.

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

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

Net_Boy

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

23:15 22.03.08

17. טוב בגלל חוסר הענות מוחלט , האתגר יורד
בתגובה להודעה מספר 0

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

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

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

Ngel

23:32 22.03.08

18. באסה דווקא רציתי ללכת על זה :\
בתגובה להודעה מספר 17

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

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

Net_Boy

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

00:03 23.03.08

19. יאללה אז תעלה את הקוד , אני אמתין בנתיים :)
בתגובה להודעה מספר 18

ותקבל וינר ובלאגנים

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

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

DLN
חבר מתאריך 20.4.07
15884 הודעות

16:14 23.03.08

20. יש את מה שכתבתי שלא ממש עובד אבל הרעיון נכון חח
בתגובה להודעה מספר 19

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

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

Net_Boy

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

23:25 24.03.08

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

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

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

IcqBoy

00:33 07.04.08

22. בקשר לאתגר המתמטי.
בתגובה להודעה מספר 0

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

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

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

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

IcqBoy

00:34 07.04.08

23. באשר למתכנתים -
בתגובה להודעה מספר 0

אני מתפלא עליכם שאף אחד לא העלה קוד.
בסה"כ חידה סבירה למתכנתים.
ציפיתי מכם ליותר.

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

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