| כותב |
|
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 October 2007 בשעה 20:39 | | IP רשוּם
|
|
|
|
יש לכם מטבעות של 100,10,5,1,וחצי שקל. (כמות בלתי מוגבלת מכל מטבע)
כתבו תוכנית בעלת פונקציה אחת או יותר שמקבלת סכום כסף ובודקת אם אפשר להגיע אליו בעזרת בדיוק 10 מטבעות מהמטבעות הנ"ל. (התוכנית מחזירה אמת אם הדבר אפשרי ושקר אם לא). רמז: פונקציה רקורסיבית מפשטת את הפיתרון.
דוגמאות: נרכיב 9 מ8 מטבעות של שקל ו2 מטבעות של חצי שקל.
נרכיב 124 מ2 מטבעות 5,מ2 מטבעות 1,מ4 מטבעות חצי שקל, ממטבע 10 שקל וממטבע 100 שקל.
זה התרגיל, אפשר עזרה בתרגיל למה הסתבכתי לגמרי!
אפילו רק לתת לי רמזים.. והתחלה..
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 29 October 2007 בשעה 20:53 | | IP רשוּם
|
|
|
|
פונקציה רקורסיבית שמקבלת מספר צעד, סכום רצוי וסכום עד כה
יש מערך גלובאלי של מטבעות
אם זה צעד לפני 10 עבור כל מטבע (ייעול: שגדול או שווה למטבע האחרון
שהשתמשנו בו) אם לא עוברים את הסכום הרצוי עושים קריאה רקורסיבית עם
הסכום החדש והצעד הבא (קריאה רקורסיבית: אם היא מחזירה אמת מחזירים אמת
ויוצאים, אחרת ממשיכים)
אם אנחנו בצעד העשירי ובסכום הרצוי אז מחזירים אמת.
בסוף אם לא החזרנו אמת מחזירים שקר.
עוד ייעול קטן: יש לנו את המטבע הכי קטן ואת מטבע הכי גדול: אפשר לבדוק בכל
קריאה אם הכמות הכי קטנה גדולה מההפרש בין הסכום הרצוי לקיים אז לא נצליח
ולוותר מראש. כנ"ל לגבי מספר הצעדים שנותרו כפול המטבע הכי גדול, אם זה לא
מספיק כדי להגיע להפרש הרצוי אז אפשר לוותר.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 October 2007 בשעה 22:45 | | IP רשוּם
|
|
|
|
אבל איך אני יודע באיזה מטבע להשתמש את ?
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 October 2007 בשעה 22:47 | | IP רשוּם
|
|
|
|
את = אה
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 29 October 2007 בשעה 23:04 | | IP רשוּם
|
|
|
|
אתה מנסה את כולם, עבור כל אחד שאתה מחליט שיכול להיות שמתאים (קטן או שווה
למטבע האחרון ושאר הייעולים) אתה יוצר קריאה רקורסיבית.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 October 2007 בשעה 23:46 | | IP רשוּם
|
|
|
|
עדיין לא הבנתי אפשר תוכנית בC++
אוףף איזה מייאש זה!
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 October 2007 בשעה 00:26 | | IP רשוּם
|
|
|
|
לא, אי אפשר!
אתה יודע שברקורסיה יש לפעמים כמה קריאות רקורסיביות, נכון ?
במקרה הזה יש קריאה רקורסיבית עבור כל סוג מטבע!
והתנאי עצירה הוא שעברנו את הסכום הרצוי או שהגענו ל-10 מטבעות בשימוש.
וכל פעם שעושים קריאה רקורסיבית, עושים אותו בתוך תנאי של if ואם היא מחזירה
אמת אז אוטומטית מחזירים אמת (סימן שכמה קריאות אח"כ הגענו למסקנה שכן
אפשר להגיע לסכון הנקוב).
לילה טוב.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
לוק
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 October 2007 בשעה 01:48 | | IP רשוּם
|
|
|
|
תחשוב על זה ככה:
בעבור כל מטבע או שהוא מוכל בתת קבוצה שמקיימת את הסכום, או שלא.
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 October 2007 בשעה 11:47 | | IP רשוּם
|
|
|
|
תודה שלא הבאת לי :]]] סוף סוף הבנתי את הסוגי תרגילים האלה
אבללל אני לא בטוח אם זאת הדרך הכי יעיליה
הנה הקוד :
קוד:
bool isPossible(float sum, float sumSoFar, int step)
{
if (step < 10)
{
for (int i = 0; i < sizeof(arr) / sizeof(float); ++i)
if (isPossible(sum,sumSoFar+arr[i],step+1))
return true;
}
if (sum == sumSoFar && step == 10)
return true;
return false;
}
|
|
|
כי זה מנסה מלא מלא אפשרויות, זה הכי יעיל ?
|
| חזרה לתחילת העמוד |
|
| |
אורח
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 October 2007 בשעה 11:51 | | IP רשוּם
|
|
|
|
ה arr זה:
קוד:
float arr[] = { 0.5, 1, 5, 10, 100 };
|
|
|
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 30 October 2007 בשעה 13:34 | | IP רשוּם
|
|
|
|
אגב, כדי לבדוק עצמך אתה יכול בשור השלפני ה-return true להדפיס את המטבע הנוכחי.
וזה לא הכי יעיל, תסתכל על הייעולים שרשמתי בהודעה הראשונה שלי.
ועוד ייעול שחשבתי עליו זה שאם מספר המטבעות מתחלק במספר הצעד (מתחילים לספור מ-
1) וגם החלוקה שלהם כפול הסכום עד כה שווה לסכום הדרוש אז אפשר להחזיר אמת.
ואגב, כדי לוותר על חס וחלילה חוסר דיוק במספרים הייתי משתמש במספר אגורות במקום
במספר שקלים ואז אפשר להשתמש במספרים שלמים.
והייעולים שוב:
א. לפני שעושים את הלולאה וכו' לבדוק אם בגלל אפשר במספר הצעדים שנותר להגיע לסכום
הרצוי - מחשבים את ההפרש בין הסכום הרצוי לקיים והוא צריך להיות בין מספר הצעדים
שנותרו כפול המטבע הכי קטן למספר הצעדים שנותרו כפול המטבע הכי גדול.
ב. מכיוון שהסדר של המטבעות בסכום לא משנה, יש להניח שאם הגענו לנסות מטבע גדול
מהכי קטן זה בגלל שניסינו קודם יותר קטן וזה לא הצליח, לכן בכל נסיון עם אינדקס מסויים
אפשר להעביר עוד פרמטר שזה המטבע האחרון שהשתמשנו בו (שבהתחלה בקריאה
הראשונית זה 0) ואז בקריאה הרקורסיבית ננסה רק החל מהמטבע הזה והלאה.
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
לוק
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 30 October 2007 בשעה 15:18 | | IP רשוּם
|
|
|
|
לגבי עיניין הסיבוכיות:
השאלה ששאלת היא פרמוטציה של בעיה ידועה בה מחפשים האם קיימת תת קבוצה
שמקיימת סכום נתון. במקרה שלך זו תת קבוצה היא עם חזרות ויש אילוץ על מס' האיברים.
פתרון הבעיה בוא מסדר גודל אקספוננציאלי, והבעיה המקורית ידועה כבעיית NP קשה.
לכן, לא נראה שישנו פתרון שיקטין את סדר הגודל של מס' הצעדים באופן משמעותי
והפתרון שלך הוא מסדר גודל כזה (אקספוננציאלי).
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
