אלגוריתמים
היום במקרה הסתכלתי על המבחן שלי מימי התואר (כמובן שהרוב נראה לי כמו סינית), אבל בין השאלות מצאתי אחת שאני זוכר שפתרתי בצורה מאוד מתוחכמת, אבל עכשיו אין לי מושג איך! אולי אתם תוכלו לעזור... יש מסילת רכבת באורך d, ומספר
קטעי מסילה באורכים t_1.....t_n. צריך להרכיב מהם (או חלק מהם )מסילה באורך המדויק d, או להחזיר פלט שאי אפשר לבצע את המשימה. האלגוריתם צריך להיות פולינומיאלי בN ו-D, כמובן. אני זוכר שבזמנו פתרתי את זה עם מטריצה משולשת, אני רק לא זוכר איך..... ונראה לי שהסיבוכיות היתה (o(D*N^2 מה דעתכם?
היום במקרה הסתכלתי על המבחן שלי מימי התואר (כמובן שהרוב נראה לי כמו סינית), אבל בין השאלות מצאתי אחת שאני זוכר שפתרתי בצורה מאוד מתוחכמת, אבל עכשיו אין לי מושג איך! אולי אתם תוכלו לעזור... יש מסילת רכבת באורך d, ומספר
קטעי מסילה באורכים t_1.....t_n. צריך להרכיב מהם (או חלק מהם )מסילה באורך המדויק d, או להחזיר פלט שאי אפשר לבצע את המשימה. האלגוריתם צריך להיות פולינומיאלי בN ו-D, כמובן. אני זוכר שבזמנו פתרתי את זה עם מטריצה משולשת, אני רק לא זוכר איך..... ונראה לי שהסיבוכיות היתה (o(D*N^2 מה דעתכם?