שלום

קיבלנו שאלה ברקורסיה:

נתונה מטריצה בגודל M על N בה שמורים כל המספרים מ-1 עד M*N, כך שכל שורה תהיה ממויינת בסדר עולה משמאל לימין, וכל עמודה תהיה ממויינת בסדר עולה מלמעלה למטה

א. כתוב אלגוריתם רקורסיבי המחשב בכמה אפשרויות ניתן למלא מטריצה בגודל M*N באופן שהוסבר

ב. כתוב אלגוריתם רקורסיבי המדפיס את כל האפשרויות למילוי מטריצה בגודל M*N באופן שהוסבר

אם זה משנה בעקרון את התרגילים אנחנו מגישים בשפת C

ניסיתי כל מיני כיוונים ולא הלך כל כך

אם מישהו יוכל לכוון אותי אני אודה לו מאוד

האלגוריתם מקבל בתור קלט מטריצה m*n, וקטור v בגודל n (מספר העמודות) שמאותחל לאפס, וקטור u עם המספרים שעדיין לא השתמשנו בהם, ואת גודל המטריצה.

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

עכשיו בלולאה על כל הסידורים האפשריים: בשורה הראשונה תבחר סידור של המספרים ב- u בסדר עולה (משמאל לימין), כך שבעמודה ה- k כשמתחילים לספור מ-0, המספר יהיה לכל היותר ((M*N-m*(N-k) ועוד 1, וגם שהערך יהיה גדול מהערך המתאים בוקטור v (כדי שכל עמודה תהיה ממוינת).

לאחר מכן שנה את ערכי הוקטור v לערכי השורה הראשונה, הורד מהוקטור u את הערכים שב- v ותן אותם לאלגוריתם עם המטריצה בלי השורה הראשונה, ועם הגודל m-1*n.

אם האלגוריתם מקבל שורה אחת (m=1) שיסדר, ידפיס את המטריצה ויגדיל counter.

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

מצד שני אם יש סידור טוב של המטריצה, בשלב כלשהו נקבל אותו.

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

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

בכל אופן תודה סיימתי עם זה