אני כותב מערכת למכירת כרטיסים ברכבת
בין שאר האפשרויות ניתן לשלם באמצעות המחאת נוסע.
המחאות נוסע באות רק בשטרות של 20,50,100 (רק לדוגמא, כמובן שזה דינמי)
אני צריך להתריע כאשר הוקלד בשדה זה סכום שאינו סביר אך אם הוקלד סכום הגיוני לתת לו להמשיך. לדוגמא: 30 הוא סכום לא סביר אך 130 כן (4X20 1X50)

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

הבעיה שלך דומה מאוד לזו: http://www.fresh.co.il/vBulletin/sh...ad.php?t=494617

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

רקורסיה:

קוד:

 class TravelCheques
	{
		private bool bStop = false;
		private bool bSuccess = false;
		private int nCount = 0;
 
		public bool Check(int[] nT, int nAmaunt)
		{
			 CheckNumber(nT, nT.Length - 1, nAmaunt);
			 Console.WriteLine(nCount.ToString() );
			 return bSuccess;
		}
 
		private void CheckNumber(int[] nT, int nTpos, int nAmaunt)
		{
			if (nCount > 100)
			{
				bStop = true;
				return;
			}
			if (bStop)
				return;
 
			nCount++;
			while (nTpos >= 0)
			{
				int nMax = nAmaunt/ nT[nTpos];
				if (nMax > 0)
				{
					for (int nX = nMax; nX > 0; nX--)
					{
						if (nAmaunt % nT[nTpos] == 0)
						{
							bSuccess = true;
							bStop = true;
							return;
						}
						else
						{
							if (nTpos > 0)
							{
								CheckNumber(nT, nTpos - 1, nAmaunt - nX * nT[nTpos]);
							}
						}
					}
				}
				else
				{
					if (nTpos > 0)
					{
						CheckNumber(nT, nTpos - 1, nAmaunt);
					}
				}
				nTpos--;
			}
		}
	}

כל רקורסיה אפשר להפוך ללולאה

במקרה הזה, תשתמש במערך כפול
תא עבור השטרות ותא עבור כמות השטרות

תרוץ על המערך כמה פעמים תוך הפחתת כמות השטרות (לפי האלגוריתם שלמטה)
עד שתקבל סכום מדוייק או עד שכל התאים התאפסו

אם הצלחת לכתוב את הרקורסיה - הלולאה צריכה להיות די טריוויאלית.

_________________________________________________

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

מנהל פורום מדע בדיוני ופנטסיה ופורום מדע טכנולוגיה וטבע בפרש

אם אינני טועה הפעולה צריכה להיות די פשוטה:

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

בדוגמא:

קוד:

 שטרות 20,50,100
סכום 130 
מחלקים ב 100 מקבלים  1 
130 - 100*1 = 30
מחלקים ב 50 מקבלים 0
30 - 0*50 = 30
מחלקים ב 20 מקבלים 1
30 - 1*20 = 10
חוזרים ל 50, הערך הוא כבר 0
חוזרים ל 100 מפחיתים 1
130 - 100 *0 = 30
מחלקים ב50 מקבלים 2
130 - 50 * 2 = 30
מחלקים ב 20 מקבלים 1
30 - 1*20 = 10
חוזרים ל 50, מפחיתים 1
130 - 50*1 = 80
מחלקים ב20 מקבלים 4
80 - 20*4= 0
הצלחה!

*עריכה*

אופס!
עד שמצאתי אלגוריתם מישהו העלה קוד שמבצע אותו

_________________________________________________

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

מנהל פורום מדע בדיוני ופנטסיה ופורום מדע טכנולוגיה וטבע בפרש

הנה פתרון שלי בשפת C# , תוכל להמיר בקלות לג'אבה:

קוד PHP:

 public static bool IsPossible(int[] Bills, int Amount)
{
    int Length = Bills.Length;
    return IsPossible(Bills, new int[Length], new bool[Length], Amount, Length);
}

private static bool IsPossible(int[] Bills, int[] Sums, bool[] shouldContinue, int Amount, int Length)
{
    for (int i = 0; i < Length; i++)
    {
        Sums[i] += Bills[i];

        if (Sums[i] == Amount)
            return true;

        else if (Sums[i] < Amount)
            shouldContinue[i] = true;
    }

    for (int i = 0; i < Length; i++)
        if (shouldContinue[i])
            return IsPossible(Bills, GetFormattedArray(Length, Sums[i]), new bool[Length], Amount, Length);

    return false;
}

private static int[] GetFormattedArray(int arrayLength, int defaultValue)
{
    int[] arr = new int[arrayLength];
    for (int i = 0; i < arrayLength; i++)
        arr[i] = defaultValue;

    return arr;
} 


תוכל להכניס מערך של שטרות שונים (או מטבעות, או כל מספר שלם אחר) :

קוד:

int[] allowedBills = { 20, 50, 100 };
Console.WriteLine(IsPossible(allowedBills, 130));

דרך אגב את הרשימה 20,50,100 ניתן לצמצם ולהעיף את ה 100 בגלל שהוא מתחלק ב 20 בלי שארית
אם למשל הרשימה היתה 5,20,50,100,200 היה אפשר לצמצם ל 5 בלבד.
זה תורם כמובן למהירות וליעילות.
יום נעים

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