תרגיל ב-++C

[gofida]

תרגיל ב-++C

בעיה מוכרת אבל לא מצאתי לה פתרון ב-C++. התוכנית שלי קורסת כל הזמן. מצורף המקור. תיאור הבעיה: פרש ממוקם על משבצת כלשהי, שתסומן בערך 0 במערך דו מימדי. כעת יש לסמן בכל שאר המשבצות את מספר הצעדים המינימלי שדרוש כדי להגיע ממשבצת 0 אליהן. האלגוריתם שלי: תנאי עצירה לרקורסיה - האם סומנו כל המשבצות אם המשבצת הנוכחית עוד לא סומנה ( הלוח אותחל לערכי -1 ) סמן אותה במספר הצעדים שנעשו עד כה, והגדל את מספר המשבצות שסומנו ב-1. כעת בדוק את כל הנקודות אליהן הפרש יכול להגיע מהמשבצת הנוכחית. יש למישהו רעיון איפה טעיתי? בתודה מראש.

 

[gofida]

תיקונים

אוקיי התקדמות!! מכל נקודה הרקורסיה מתפצלת וכאן הבעיה - הפרש מתחיל להסתובב במעגלים אינסופיים. אם למישהו יש פתרון לזה.. ב-C++ או בפסקל או אפילו בביסיק... זה היה תרגיל בקורס באוניברסיטה הפתוחה לפני כמעט 3 שנים אם מישהו למד אז ופתאום נזכר בפתרון.

 

[DNile]

הפתרון צריך להתנהל במקביל..

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

 

[GPhoenixX]

אבל איך 8 ?

פרש זה לא זה שזז רק במאונך ומאוזן ? סתם מתעניין בשאלה ...

 

[DNile]

לא, זה צריח.

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

 

[coredumb]

בהנחה שאין כלים אחרים על הלוח ../images/Emo13.gif