ABA


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

   01:41   19.12.05   
אל הפורום  
  שאלה קשה ברקורסיה  
 
   יש לכם מטבעות של מדינת ישראל משנות ה80:
חצי שקל, שקל, 5 שקל, 10 שקל, 50 שקל, 100 שקל.

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

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


זאת שאלה מהמבחנים של גאמא, נחשבה להכי קשה שם, בהצלחה


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

  האשכול     מחבר     תאריך כתיבה     מספר  
  שאלה נחמדה... אפשר היה להריץ את זה כאתגר מתקדם :) nesher  19.12.05 21:36 1
  נו איך הלך בסוף? דני15  19.12.05 21:38 2
     פסדררררררר MO 19.12.05 22:33 3
         אפשר עוד פרטים על המבחנים של גאמא? bizho 19.12.05 22:36 5
         אחלה :) דני15  19.12.05 22:48 10
  אוקיי, כתבתי פתרון לזה. bizho 19.12.05 22:35 4
     לא הבנתי כל כך למה התכוונת, מחכה לפתרון שלך :) MO 19.12.05 22:42 6
         אפשר דוגמא לשאלות אמריקאיות שהיו שם bizho 19.12.05 22:47 9
             הייתי אומר אחי אבל אני לא זוכר MO 19.12.05 22:50 13
                 בוא ניקח לדוגמא את המבחן של ++C\C bizho 19.12.05 22:57 16
                     יש ויש MO 19.12.05 23:04 17
                         אוקיי, bizho 19.12.05 23:09 18
                             בהצלחה MO 19.12.05 23:10 19
     עכשיו הרצתי על תצורת Release, bizho 19.12.05 22:42 7
         לשלוח פה או בהודעה פרטית? bizho 19.12.05 22:44 8
             שלח פה מה אתה מתבייש? MO 19.12.05 22:48 11
                 חשבתי שאולי זה יהיה אתגר.. :) bizho 19.12.05 22:50 12
                     מחר אני אסתכל על זה, אה ועוד משו ממש חשוב MO 19.12.05 22:52 14
                         הנה זה בלינק קצת יותר מובן. bizho 19.12.05 22:55 15
                     :) ביקשו פונקציה ... לא 5 פונקציות ... אופירוש 20.12.05 00:43 20
                         יפה מאוד! איזה פישוט כל הכבוד! MO 20.12.05 08:11 21
                         אני מצדיע לך, bizho 20.12.05 15:56 22
                             אין צורך להצדיע , אתה לא חייל שלי :) אופירוש 21.12.05 17:35 23
                                 החודש חגגתי 17. bizho 21.12.05 19:43 24
                     מכתב, -ReDevil- 21.12.05 19:53 25
                         אני אספק הסברים מחר, bizho 21.12.05 21:32 26
                             מחזק MO 21.12.05 23:17 27
                                 נו, איך היה? :) bizho 22.12.05 19:15 31
                             אם אפשר בשניהם גם יהיה נחמד :P - אופיר אפשר הסבר גם? -ReDevil- 22.12.05 14:38 28
                                 הרעיון בפיתרון של אופירוש הוא bizho 22.12.05 19:26 33
                         הסברון: bizho 22.12.05 19:23 32
                             תודה רבה לך על ההסבר... -ReDevil- 27.12.05 13:21 36
  הפתרון שלי ב-C++ איש-האבוקות 22.12.05 15:07 29
     אתה יכול להעלות את זה לכאן: bizho 22.12.05 19:15 30
         טוב העלתי לשם כמו שרשמת איש-האבוקות 22.12.05 20:21 34
  הבעיה בתרגיל הזה זה בעיקר לעשות את זה ביעילות ... Gold Dragon 24.12.05 15:39 35

       
nesher 

   21:36   19.12.05   
אל הפורום  
  1. שאלה נחמדה... אפשר היה להריץ את זה כאתגר מתקדם :)  
בתגובה להודעה מספר 0
 
   יש לי רעיון אבל אין לי זמן כל כך למימוש


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
דני15 
חבר מתאריך 3.8.02
47437 הודעות, 8 פידבק
   21:38   19.12.05   
אל הפורום  
  2. נו איך הלך בסוף?  
בתגובה להודעה מספר 0
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   22:33   19.12.05   
אל הפורום  
  3. פסדררררררר  
בתגובה להודעה מספר 2
 
   כאילו בחלק של המבחנים הסגורים הלך טוב
אבל בשאלות הפתוחות כמו זאת, הלך גרוע

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

בכל מקרה למרות שזה 6 וחצי שעות של מבחנים נטו היה מעניין...


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:36   19.12.05   
אל הפורום  
  5. אפשר עוד פרטים על המבחנים של גאמא?  
בתגובה להודעה מספר 3
 
   אם לא פה, אז בהודעה אישית?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
דני15 
חבר מתאריך 3.8.02
47437 הודעות, 8 פידבק
   22:48   19.12.05   
אל הפורום  
  10. אחלה :)  
בתגובה להודעה מספר 3
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:35   19.12.05   
אל הפורום  
  4. אוקיי, כתבתי פתרון לזה.  
בתגובה להודעה מספר 0
 
   הוא עובד נהדר לנגיד 4 מטבעות, אבל כשאני מגדיר 10 מטבעות וסכום של 4 שקלים המחשב עובד על 100% ניצול עד שכבר לא היה לי נעים וסגרתי את התוכנית.

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   22:42   19.12.05   
אל הפורום  
  6. לא הבנתי כל כך למה התכוונת, מחכה לפתרון שלך :)  
בתגובה להודעה מספר 4
 
   בקשר לגאמא:
1. מבחן C/C++ - חובה
2. בחירה בין מבחן ב-Java לבין מבחן בC#
3. בחירה בשני מבחנים מבין הארבעה: רשתות\אסמבלר\דאטאבייסים\חומרה
4. בחירה בין מבחן לינוקס למבחן ווינדוס.
5. מבחן ידע כללי בתחום המחשוב

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

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

אחרי זה יש מבחן 300 שבעקרון אין לך הגבלת זמן בו...

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

קיבלת זימון למבחנים האלה?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:47   19.12.05   
אל הפורום  
  9. אפשר דוגמא לשאלות אמריקאיות שהיו שם  
בתגובה להודעה מספר 6
 
   מתחומים שונים?

אני חייב לעשות בסה"כ 6 מבחנים? מה אם אני לא ממש מתמצא ברשתות/אסמבלר/DB/חומרה? להתחיל ללמוד או שהם ישבצו אותי לפי התוצאות במבחנים האחרים?

מה זה מבחן 300?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   22:50   19.12.05   
אל הפורום  
  13. הייתי אומר אחי אבל אני לא זוכר  
בתגובה להודעה מספר 9
 
   בכל מקרה אמרו לנו שמשבצים באמת לפי המבחן שבו הלך לך הכי טוב, אז בעיקרון אתה לא צריך לדעת את כל הנושאים האלה
לי הלך הכי טוב באסמבלר דווקא... וגם בDB שזה בעצם SQL


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:57   19.12.05   
אל הפורום  
  16. בוא ניקח לדוגמא את המבחן של ++C\C  
בתגובה להודעה מספר 13
 
   על מה הם מתמקדים? אספקטים של השפה שאף אחד לא משתמש בהם? פעולות בסיסיות? מבני נתונים? פעולות בינאריות? OOP?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   23:04   19.12.05   
אל הפורום  
  17. יש ויש  
בתגובה להודעה מספר 16
 
   ערכתי לאחרונה בתאריך 19.12.05 בשעה 23:10 בברכה, MO
 
נגיד שואלים מה ההבדל בין --X לX--
והיה די הרבה על OOP
סה"כ יש 20 שאלות בכל פרק.

גם שואלים דברים שממש הפריקים בד"כ רק יודעים, כמו איזה שגיאה תקבל מהקופילציה של הקוד, ואתה צריך לדעת איפה הבעיה בחלק מהקודים
גם בחלק של הJAVA זה היה אותם עקרונות, להכיר ממש טוב את השפה ואת הייחודיות שלה
אני זוכר ששאלו מה ההבדל בין הCHAR בJAVA לCHAR בC

באחת הוא לוקח 16 בתים בשניה 8 בתים

אלה שאלות של ידע בעיקרון יותר מאשר מחשבה... אבל יש גם מחשבה בחלק


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   23:09   19.12.05   
אל הפורום  
  18. אוקיי,  
בתגובה להודעה מספר 17
 
   אז אני אתחיל לחרוש.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   23:10   19.12.05   
אל הפורום  
  19. בהצלחה  
בתגובה להודעה מספר 18
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:42   19.12.05   
אל הפורום  
  7. עכשיו הרצתי על תצורת Release,  
בתגובה להודעה מספר 4
 
   לקח למעבד כמה דקות אבל בסוף הוא נתן את התשובה הנכונה. :-)


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:44   19.12.05   
אל הפורום  
  8. לשלוח פה או בהודעה פרטית?  
בתגובה להודעה מספר 7
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   22:48   19.12.05   
אל הפורום  
  11. שלח פה מה אתה מתבייש?  
בתגובה להודעה מספר 8
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:50   19.12.05   
אל הפורום  
  12. חשבתי שאולי זה יהיה אתגר.. :)  
בתגובה להודעה מספר 11
 
  

#include <iostream>
using namespace std;

const int n = 10;

int findFirstEmpty(double arr)
{
for (int i = 0; i < n; i++)
{
if (arr == 0)
return i;
}
return (n - 1);
}

double getNextNumber(double f)
{
if (f == 0)
return 0.5;
if (f == 0.5)
return 1;
if (f == 1)
return 5;
if (f == 5)
return 10;
if (f == 10)
return 50;
if (f == 50)
return 100;
else
return -1;
}

double getSum(double arr)
{
double sum = 0;
for (int i = 0; i < n; i++)
{
sum += arr;
}
return sum;
}

bool areAllUsed(double arr)
{
for (int i = 0; i < n; i++)
{
if (0 == arr)
{
return false;
}
}
return true;
}

bool solve(double x, double arr)
{
if ((getSum(arr) == x) && (areAllUsed(arr)))
{
return true;
}
else
{
bool flag = false;
int empty = findFirstEmpty(arr);

while (getNextNumber(arr) != -1)
{
arr = getNextNumber(arr);
double arr2;
for (int i = 0; i < n; i++)
arr2 = arr;
flag = solve(x, arr2);
if (flag)
return true;
}
arr = 0;
return false;
}
}

int main()
{
double vec = {0};
double a = 0;
cout << "Enter a number." << endl;
cin >> a;
cout << solve(a, vec);
return 0;
}


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   22:52   19.12.05   
אל הפורום  
  14. מחר אני אסתכל על זה, אה ועוד משו ממש חשוב  
בתגובה להודעה מספר 12
 
   ערכתי לאחרונה בתאריך 19.12.05 בשעה 22:54 בברכה, MO
 
בשאלות הפתוחות, יש לך קצת פחות מחצי עמוד להכניס את התשובה, והם בכוונה עושים את זה ככה.
אז הפתרון שלך, נכון או לא, בחיים לא היה מתקבל שם כי לא היית מצליח להכניס אותו בצורה כתובה ברורה.
למעשה להכניס את זה בריבוע הקטן שנותנים לך זה האתגר האמיתי בתכנות שם =\
פתרון יותר יעיל יקבל יותר נקודות, ואת זה הם מחפשים.

בכל מקרה, יפה מאוד


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   22:55   19.12.05   
אל הפורום  
  15. הנה זה בלינק קצת יותר מובן.  
בתגובה להודעה מספר 14
 
   http://www.rafb.net/paste/results/VFFyfK73.html

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


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

   00:43   20.12.05   
אל הפורום  
  20. :) ביקשו פונקציה ... לא 5 פונקציות ...  
בתגובה להודעה מספר 12
 
   ערכתי לאחרונה בתאריך 20.12.05 בשעה 00:46 בברכה, אופירוש
 
הלכת ממש רחוק עם הפתרון שלך ...
קודם כל השתמשת ב - 5 (!!!) פונקציות במקום באחת כמו שביקשו ... איפה היופי בריקורסיה פה ? עשית עיקופים במקום להבין את הריקורסיה . - כאן כבר היו פוסלים לך את התשובה מראש .
שנית ... השתמשת מלא בלולאות - אין צורך אפילו באחת ...
וכתוצאה מהבלגן לוקח לתוכנית כמה דקות לרוץ ...

מצורפת דוגמא שכתבתי עכשיו (ב - VB - תתאר לעצמך באיזה מהירות היא תרוץ ב - C).

בפונקציה אחת , פחות מ - 15 שורות .
הפונקציה רצה בפחות משניה בממוצע (עבור ערך True) ופחות מ -10 שניות (עבור ערך False) - כמובן שמדובר על 10 מטבעות בדיוק .

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


Private Function FindCombination(ByVal CoinsLeft As Integer, ByVal SumLeft As Currency) As Boolean
Dim blnFlag As Boolean

If CoinsLeft = 1 Then
Test = (SumLeft = 0.5) Or (SumLeft = 1) Or (SumLeft = 5) Or (SumLeft = 10) _
Or (SumLeft = 50) Or (SumLeft = 100)
Else
blnFlag = Test(CoinsLeft - 1, SumLeft - 0.5)
If Not blnFlag Then blnFlag = Test(CoinsLeft - 1, SumLeft - 1)
If Not blnFlag Then blnFlag = Test(CoinsLeft - 1, SumLeft - 5)
If Not blnFlag Then blnFlag = Test(CoinsLeft - 1, SumLeft - 10)
If Not blnFlag Then blnFlag = Test(CoinsLeft - 1, SumLeft - 50)
If Not blnFlag Then blnFlag = Test(CoinsLeft - 1, SumLeft - 100)
Test = blnFlag
End If
End Function

ובכתיב קצר (ללא יתרון למקרה ה - True)


Private Function FindCombination(ByVal CoinsLeft As Integer, ByVal SumLeft As Currency) As Boolean
If CoinsLeft = 1 Then
FindCombination = (SumLeft = 0.5) Or (SumLeft = 1) Or (SumLeft = 5) Or (SumLeft = 10) _
Or (SumLeft = 50) Or (SumLeft = 100)
Else
FindCombination = FindCombination(CoinsLeft - 1, SumLeft - 0.5) Or FindCombination(CoinsLeft - 1, SumLeft - 1) _
Or FindCombination(CoinsLeft - 1, SumLeft - 5) Or FindCombination(CoinsLeft - 1, SumLeft - 10) _
Or FindCombination(CoinsLeft - 1, SumLeft - 50) Or FindCombination(CoinsLeft - 1, SumLeft - 100)
End If
End Function

תעשו חיים ...


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   08:11   20.12.05   
אל הפורום  
  21. יפה מאוד! איזה פישוט כל הכבוד!  
בתגובה להודעה מספר 20
 
   ערכתי לאחרונה בתאריך 20.12.05 בשעה 08:11 בברכה, MO
 
וואלה הפחת בי תקווה


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   15:56   20.12.05   
אל הפורום  
  22. אני מצדיע לך,  
בתגובה להודעה מספר 20
 
   בכלל לא חשבתי על פתרון כזה.

הערה קטנה - אני חושב שהשם של הפונקציה הראשונה התחרבש לך.


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

   17:35   21.12.05   
אל הפורום  
  23. אין צורך להצדיע , אתה לא חייל שלי :)  
בתגובה להודעה מספר 22
 
   שאלה , בן כמה אתה ?

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   19:43   21.12.05   
אל הפורום  
  24. החודש חגגתי 17.  
בתגובה להודעה מספר 23
 
   אף פעם לא למדתי ריקורסיה באופן מסודר, זה בסה"כ הניסיון השני שלי. הראשון היה פותר סודוקו.

מה שעשיתי זה Backtracking, לא?


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
-ReDevil-

   19:53   21.12.05   
אל הפורום  
  25. מכתב,  
בתגובה להודעה מספר 12
 
   תוכל לרשום בקצרה הסבר למה שעשית? אני לא הכי מתקדם בתיכנות אבל אני בשלבי למידה וזה ממש מעניין אותי איך עשית הכל. אם תוכל לעשות את זה פה בפרטי איך שנוח לך. תודה


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   21:32   21.12.05   
אל הפורום  
  26. אני אספק הסברים מחר,  
בתגובה להודעה מספר 25
 
   כרגע יש לי מבחן בספרות על הראש.

אבל בעיקרון הפתרון של אופיר הרבה יותר יפה משלי. הייתי מציע לך ללמוד ממנו.


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
MO

   23:17   21.12.05   
אל הפורום  
  27. מחזק  
בתגובה להודעה מספר 26
 
   גם לי יש מבחן בספרות מחר


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   19:15   22.12.05   
אל הפורום  
  31. נו, איך היה? :)  
בתגובה להודעה מספר 27
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
-ReDevil-

   14:38   22.12.05   
אל הפורום  
  28. אם אפשר בשניהם גם יהיה נחמד :P - אופיר אפשר הסבר גם?  
בתגובה להודעה מספר 26
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   19:26   22.12.05   
אל הפורום  
  33. הרעיון בפיתרון של אופירוש הוא  
בתגובה להודעה מספר 28
 
   לשלוח כל פעם לפונקציה את מספר המטבעות שנותר ואת הסכום שנותר.
תנאי העצירה הוא הבדיקה אם נשאר מטבע אחד ואם הסכום עצמו שווה לאחד מערכי המטבעות המותרים.

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   19:23   22.12.05   
אל הפורום  
  32. הסברון:  
בתגובה להודעה מספר 25
 
   הרעיון הכללי הוא ליצור מערך שיכיל את הקומבינציה של המטבעות שתפתור את הבעייה. לדוגמא, עבור 10 מטבעות וסכום כללי של 10 שקל, יהיה מערך בגודל 10 שיכיל בכל אחד מתאיו את המספר 1.

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

getNextNumber מחזירה את המספר הבא שאמור להיכנס לכל תא במערך.

getSum מחזירה את סכום כל האיברים במערך - למעשה הסכום של הכסף שיש לנו עד עכשיו.

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

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


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
-ReDevil-

   13:21   27.12.05   
אל הפורום  
  36. תודה רבה לך על ההסבר...  
בתגובה להודעה מספר 32
 
  


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

   15:07   22.12.05   
אל הפורום  
  29. הפתרון שלי ב-C++  
בתגובה להודעה מספר 0
 
   ערכתי לאחרונה בתאריך 22.12.05 בשעה 15:25 בברכה, איש-האבוקות
 
הפתרון שלי דומה לפתרון של לוח סודוקו,
הוא יוצר עץ מצבים לכל מטבע שהוא בוחר ואם הוא מצא פתרון הוא מפסיק את פריסת העץ מדפיס את המטבעות ומחזיר אמת

int is_pos10(int num, int n, float sum)
{
int i;
float coins={0.5,1,5,10,50,100};

if (sum > num)
return 0;

if (n==10)
{
if (sum==num)
{
return 1;
}
return 0;
}


for (i=0; i<6; i++)
{
if (is_pos10(num,n+1,sum+coins )==1)
{
cout<<coins<<endl;
return 1;
}

}
return 0;
}

עריכה: זה הוריד לי את כל הסוגריים המרובעות ומה שבתוכם


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
bizho

   19:15   22.12.05   
אל הפורום  
  30. אתה יכול להעלות את זה לכאן:  
בתגובה להודעה מספר 29
 
   http://www.rafb.net/paste/


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

   20:21   22.12.05   
אל הפורום  
  34. טוב העלתי לשם כמו שרשמת  
בתגובה להודעה מספר 30
 
   http://www.rafb.net/paste/results/hwKBsi55.html


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Gold Dragon

   15:39   24.12.05   
אל הפורום  
  35. הבעיה בתרגיל הזה זה בעיקר לעשות את זה ביעילות ...  
בתגובה להודעה מספר 0
 
   ערכתי לאחרונה בתאריך 24.12.05 בשעה 15:42 בברכה, Gold Dragon
 


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net