מעבר לתוכן


תמונה

עזרה בשפת C


  • Please log in to reply
81 replies to this topic

#31 Danny boy

Danny boy

    ברונזה

  • רשומים+
  • 856 הודעות:

פורסם 01/09/2005 - 22:42

אלגנט, נראה לי שאתה מדבר רמה אחת גבוה מדי. אני אנסה את כוחי:

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

אפשר לממש בכמה צורות, הנה אחת: קחו את החלק הראשון ברשימה, לא משנה איזה. יש שלוש אפשרויות איך לשבץ אותו:
1. באוריינטציה (מאוזן/מאונך) הנוכחית;
2. באוריינטציה האחרת;
3. לא לשבץ בכלל.

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

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

אם אני לא ברור תגידו ואני אנסה להסביר. בהצלחה! :)

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

<{POST_SNAPBACK}>


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

נכון?

#32 מוש

מוש

    ברונזה

  • רשומים+
  • 759 הודעות:

פורסם 01/09/2005 - 23:08

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

נכון?

<{POST_SNAPBACK}>

לא לגמרי הבנתי את השאלה אז אני אנסה להסביר את מבנה הלולאות:

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

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

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

אולי צריך עוד הסבר על הבדיקה האם השמה כלשהי של חלק היא "טובה" או לא.

עוזר?

לא יודע מתי מועד ההגשה שלכם, אבל ביום ראשון אני באוני'.

"All these worlds are yours except Europa. Attempt no landings there."


#33 dumber

dumber

    משתמש טרי

  • רשומים
  • 16 הודעות:

פורסם 01/09/2005 - 23:28

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

<{POST_SNAPBACK}>


:אוףטופיק:
נשמע מעניין, אתה יכול להרחיב?

#34 number6

number6

    Things could be Different. But They're not

  • רשומים+
  • 8641 הודעות:

פורסם 01/09/2005 - 23:38

לא לגמרי הבנתי את השאלה אז אני אנסה להסביר את מבנה הלולאות:
עוזר?
לא יודע מתי מועד ההגשה שלכם, אבל ביום ראשון אני באוני'.

<{POST_SNAPBACK}>


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

זה אומר שצריך לבדוק כל חלק וחלק בכל מיקום אפשרי, מה שדי בלגן, לא..? :הממ:

The reception's gotten fuzzy
The delicate balance has shifted
Put on your gloves and your black pumps
Let's pretend the fog has lifted
Now you see me
Now you don't
Now you say you love me
Pretty soon you won't
If we get our full three score and ten
We won't pass this way again
So kiss me with your mouth open
Turn the tires toward the street
And stay sweet


#35 מוש

מוש

    ברונזה

  • רשומים+
  • 759 הודעות:

פורסם 01/09/2005 - 23:41

:אוףטופיק:
נשמע מעניין, אתה יכול להרחיב?

<{POST_SNAPBACK}>

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

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





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

"All these worlds are yours except Europa. Attempt no landings there."


#36 מוש

מוש

    ברונזה

  • רשומים+
  • 759 הודעות:

פורסם 01/09/2005 - 23:49

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

זה אומר שצריך לבדוק כל חלק וחלק בכל מיקום אפשרי, מה שדי בלגן, לא..? :הממ:

<{POST_SNAPBACK}>

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

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

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

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

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

"All these worlds are yours except Europa. Attempt no landings there."


#37 Peaches

Peaches

    קטנונית אך חביבה (ותודה למיפ)

  • גנרלים בדימוס
  • 14237 הודעות:

פורסם 01/09/2005 - 23:52

אתם יודעים מה? אני מסתכלת על השרשור הזה, וכל מה שיש לי לומר זה: :blink:
אבל זה מובן - אני הרי מדעי החברה (כן, חברה, ולא רוח!)

אז אולי כדאי שאיזה מנהל נחמד יעביר אותו למקום קצת יותר הולם עכשיו שספיידי מצא אנשים שיענו לו? הרי הקפה הוא לא ממש המקום בשביל שיחות כאלו... חלקנו רוצים להיות משועשעים
But home is where the heart is
So your real home’s in your chest

#38 number6

number6

    Things could be Different. But They're not

  • רשומים+
  • 8641 הודעות:

פורסם 01/09/2005 - 23:57

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

<{POST_SNAPBACK}>


bgu&me - Here we come !! :וי:

The reception's gotten fuzzy
The delicate balance has shifted
Put on your gloves and your black pumps
Let's pretend the fog has lifted
Now you see me
Now you don't
Now you say you love me
Pretty soon you won't
If we get our full three score and ten
We won't pass this way again
So kiss me with your mouth open
Turn the tires toward the street
And stay sweet


#39 mipmip

mipmip

    הבחורה עם הציפור

  • גנרלים בדימוס
  • 19316 הודעות:

פורסם 01/09/2005 - 23:57

אתם יודעים מה? אני מסתכלת על השרשור הזה, וכל מה שיש לי לומר זה:  :blink:
אבל זה מובן - אני הרי מדעי החברה (כן, חברה, ולא רוח!)

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

<{POST_SNAPBACK}>


party pooper...
בלילות שישי, במוצאי שבת
אוהבים הרבה, מדברים מעט
מנגנים דואט ובבת אחת,
הצלילים עולים והלב נרעד
נישאים הם סחור וסחור
הוא גיטרה היא כינור.



רגע, אז עכשיו אני צריכה לשנות את היוזר לmipBA ?

#40 Lilush

Lilush

    :מתלהב:

  • רשומים+
  • 12178 הודעות:

פורסם 01/09/2005 - 23:59

אתם יודעים מה? אני מסתכלת על השרשור הזה, וכל מה שיש לי לומר זה:  :blink:
אבל זה מובן - אני הרי מדעי החברה (כן, חברה, ולא רוח!)

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

<{POST_SNAPBACK}>


איזה רעה!!! (כן, עם דגש על ה - ע') :o

לא ראיתי שיצאת חוצץ נגד שיעורי הקרטל/מונופול/יוסטמן/שיעור 10/שיעור 5/תורת המחירים/מבוא למיקרו/קקטוסית/מרקו כשהשירשור של ריקו הפך לדיון ראוי לגדי חזק את דוד וטשטיין או אפילו מרק גרדשטיין (אגב, נראה לי שאני יודעת מה תנאי קבלה לראש מחלקת כלכלה באב"ג - שטיין בסוף שם משפחה ארוך)... :P :lol:

אומרים שבלי רעש אין שקט...


#41 Peaches

Peaches

    קטנונית אך חביבה (ותודה למיפ)

  • גנרלים בדימוס
  • 14237 הודעות:

פורסם 02/09/2005 - 00:04

bgu&me - Here we come !!  :וי:

<{POST_SNAPBACK}>

:lol:

party pooper...

<{POST_SNAPBACK}>


:no:

איזה רעה!!! (כן, עם דגש על ה - ע')  :o

לא ראיתי שיצאת חוצץ נגד שיעורי הקרטל/מונופול/יוסטמן/שיעור 10/שיעור 5/תורת המחירים/מבוא למיקרו/קקטוסית/מרקו כשהשירשור של ריקו הפך לדיון ראוי לגדי חזק את דוד וטשטיין או אפילו מרק גרדשטיין (אגב, נראה לי שאני יודעת מה תנאי קבלה לראש מחלקת כלכלה באב"ג - שטיין בסוף שם משפחה ארוך)...  :P  :lol:

<{POST_SNAPBACK}>

תשמעי, השרשור הזה בתחילתו היה רלוונטי ביותר לקפה. אני פשוט ויתרתי עליו בעמוד 5 בערך...

אבל לו הייתי רואה, וזה היה נמשך יותר מ-4/5 תגובות, ייתכן והייתי מעירה להם משהו בסגנון: "Get a forum already"...
But home is where the heart is
So your real home’s in your chest

#42 Lilush

Lilush

    :מתלהב:

  • רשומים+
  • 12178 הודעות:

פורסם 02/09/2005 - 00:13

תשמעי, השרשור הזה בתחילתו היה רלוונטי ביותר לקפה. אני פשוט ויתרתי עליו בעמוד 5 בערך...

אבל לו הייתי רואה, וזה היה נמשך יותר מ-4/5 תגובות, ייתכן והייתי מעירה להם משהו בסגנון: "Get a forum already"...

<{POST_SNAPBACK}>


:o

לקחת אותי ברצינות מדי, אני צחקתי מותק... :lol:

אומרים שבלי רעש אין שקט...


#43 Peaches

Peaches

    קטנונית אך חביבה (ותודה למיפ)

  • גנרלים בדימוס
  • 14237 הודעות:

פורסם 02/09/2005 - 00:25

:o

לקחת אותי ברצינות מדי, אני צחקתי מותק...  :lol:

<{POST_SNAPBACK}>

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

Oh, well
But home is where the heart is
So your real home’s in your chest

#44 Lilush

Lilush

    :מתלהב:

  • רשומים+
  • 12178 הודעות:

פורסם 02/09/2005 - 00:26

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

Oh, well

<{POST_SNAPBACK}>


:lol:


דווקא זה היה מצחיק! :וי:

אומרים שבלי רעש אין שקט...


#45 קריימר

קריימר

    סתמנכ"ל הפורום בדימוס

  • גנרלים בדימוס
  • 23743 הודעות:

פורסם 02/09/2005 - 00:29

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

<{POST_SNAPBACK}>

אז תחשוב מה זה לקרוא הודעות שלו בפורום של המחלקה שלנו :lol:
תמונה מצורפת
"I'm out there Jerry and loving every minute of it."

קינמונים להמונים

:מסמיק:
קריימר, אתה מספר 1!!!!





0 משתמשים קוראים נושא זה

0 משתמשים, 0 אורחים, 0 משתמשים אנונימיים