החידה:

ציטוט:

Starting in the top left corner of a 2 [התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://projecteuler.net/images/symbol_times.gif] 2 grid, there are 6 routes (without backtracking) to the bottom right corner. [התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://projecteuler.net/project/images/p_015.gif] How many routes are there through a 20 [התמונה הבאה מגיעה מקישור שלא מתחיל ב https ולכן לא הוטמעה בדף כדי לשמור על https תקין: http://projecteuler.net/images/symbol_times.gif] 20 grid?

http://projecteuler.net/index.php?s...=problems&id=15

כתבתי פיתרון רקורסיבי לחידה,(brute force) הבעייה שהוא עובד בערך עד size = 13 ואח"כ הקוד טוען יותר מדי זמן...

הקוד:

קוד:

		const long size = 2;
		static void Main(string[] args)
		{
			Console.WriteLine(grid(0, 0));
			Console.Read();
		}
		static long grid(long x, long y)
		{
			if (x == size && y == size) return 1;
			if (x == size) return grid(x, y + 1);
			if (y == size) return grid(x + 1, y);

			return grid(x + 1, y) + grid(x, y + 1);
		}

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

יש למישהו רעיונות איך לשפר את הקוד?

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

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

אם יש לך חזרה אחת בדיוק אז מתוך 21 המקומות האפשריים לעשות בהם את הצעד הכפול למטה אתה צריך לבחור אחד - משמע יש לך בדיוק 21 מסלולים כאלו. [tex] \left(^{21}_1\right)[/tex] שזה בחר מקום 1 מבין 21.
עכשיו, לכל מקום כזה, אתה גם צריך לבחור 2 מקומות בהם לא תוכל לעשות כעת צעד למטה מבין 20 המקומות הנותרים, כלומר [tex] \left(^{20}_2\right) =\frac{20!}{18! \cdot 2!}[/tex]

אם יש לך 2 חזרות בדיוק אז יש לך 2 אפשרויות: יש מקום אחד בו יורדים 3 פעמים או שיש 2 מקומות בהם יורדים פעמיים.
לכן יש לך 21 מקומות אפשריים בהם יורדים 3 פעמים במקום מסויים, ולכל אחד מהם יש [tex] \left(^{20}_3\right) =\frac{20!}{17! \cdot 3!}[/tex] אפשרויות למקומות בהם לא יורדים כלל.
ויש לך [tex] \left(^{21}_2\right) =\frac{21!}{19! \cdot 2!}[/tex] אפשורויות לבחור 2 מקומות מתוך 21 בהם יורדים פעמיים ו-[tex] \left(^{19}_3\right) =\frac{19!}{16! \cdot 3!}[/tex] אפשרויות לבחור 3 מקומות בהם לא יורדים כלל מתוך 19 המקומות הנותרים.

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

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

קישורים בוויקיפדיה: http://en.wikipedia.org/wiki/Catalan_number - באנגלית וכולל את הדוגמא הספציפית שלך
http://he.wikipedia.org/wiki/%D7%9E...%98%D7%9C%D7%9F - בעברית אבל בלי הדוגמא

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

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

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

ציטוט:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

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

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

שים לב שהפתרון שאני הצעתי לך הוא פתרון איטרטיבי (משמע לולאה)

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

מצורף פתרון שמתי השוואה לפתרון רקורסיבי דומה למה שאתה עשית
הפתרון האיטרטיבי עובד עבור size = 20

קוד:

public class Test {

	static int size = 10;
	static int[][] memo = new int[size+1][size+1];
	
	public static int recursive(int x,int y){
	   if (x == y && x == size) return 1;
	   if (x == size) return recursive(x,y+1);
	   if (y == size) return recursive(x+1,y);
	   
	   return recursive(x+1,y) + recursive(x,y+1);
	}
	
	public static int iterative(int x,int y){
		memo[0][0] = 0;
		for (int i=0; i <= size; i++){	// we could got to those points only in one way
			memo[0][i] = 1;
			memo[i][0] = 1;
		}
		for (int i=x+1; i <= size; i++){
			for (int j=x+1; j <= size; j++){
				memo[i][j] = memo[i-1][j] + memo[i][j-1];
			}
		}
		return memo[size][size];
	}
	
	public static void main(String[] args){
		System.out.println("recursive " + recursive(0,0));
		System.out.println("iterative " + iterative(0,0));
	}
}

בדיוק קראתי על משולש פסקאל כשראיתי את הפיתרון שלך, פיתרון פשוט ויפה

תודה רבה (אנסי) טנקאדו !!

נניח שצריך לעשות x צעדים ימינה ו-y צעדים למטה.
אפשר להסתכל על זה כמו פיזור y עצמים זהים ל-x+1 תאים שונים. ואם אתה מכיר קצת קומבינטוריקה אז:

D(n,k) = C(n-1+k,k)
C(n,k) = n!/(k!(n-k)!)

D(x+1,y) = C(x+y,y) = (x+y)!/(x!y!)

מדובר פה על לוחות NxN

סה"כ יש 2n צעדים להגיע מהפינה העליונה השמאלית לתחתונה הימנית
אתה צריך לבחור n צעדים ימינה ו n צעדים למטה

כלומר אפשר להסתכל על זה כעל בחירת n צעדים למטה מתוך 2n כלומר
C(2n,n) z

שזה 2n עצרת חלקי n עצרת בריבוע

ו n זה כמובן גודל הלוח

הקיצר יצא אותו דבר