"חידה חדשה"

[ron369]

"חידה חדשה" ../images/Emo13.gif

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

 

[ש ב ו ז]

טוב כמה רעיונות

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

 

[ש ב ו ז]

טעות...

למעשה חלק מהפירוקים של N-2 עם 2 בסוף יופיעו בפירוקים של N-1 עם 1 בסוף למעשה מספר המשותפים יהיה שווה למס הפירוקים של N-3 (כי 1 ושתיים חייבים להופיע)

 

[ש ב ו ז]

אהההה

או קיי פתרון שנבדק ונמצא עובד f=f(n-1)+f(n-2)-f(n-4)+f(n-6)-f(n-8)...f(0 כאשר אפ של 0 שווה 1. (עם המספר עצמו כפירוק.