שאלית קצת דחופה בC...

[Zack DA]

זה אשכול ארוך, אני מסכים איתך בנוגע

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

 

[neko]

הממ... זה הזמן להתוודות שאנחנו

בשנה ב'?

 

[ChipsMan]

אממ..

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

 

[ChipsMan]

והנה פתרון שעובד ../images/Emo13.gif

נניח ויש לי מערך בעל N איברים בשם A. אנו נסתכל על תת המערך שמכיל את כל האיברים מהראשון עד האיבר במקום ה-i, נקרא לו Ai. נחלק את תת הסדרה המקסימאלית במערך Ai לשני מקרים: 1) סדרה שמסתיימת לפני האיבר ה-i. נסמן את סכומה ב-before a. 2) סדרה שמסתיימת בדיוק באיבר ה-i. נסמן את סכומה ב-exact a. סדרה בעלת סכום מקסימאלי שמסתיימת לפני האיבר ה-i היא אחת מהשתיים: 1) סדרה בעלת אורך מקסימאלי שמסתיימת לפני האיבר ה-i-1 או 2) סדרה בעלת אורך מקסימאלי שמסתיימת בדיוק באיבר ה-i-1 מכאן נובעת המקסנה:

before = max{before[i-1],exact[i-1]}​

סדרה בעלת סכום מקסימאלי שמסתיימת בדיוק באיבר ה-i תהיה בעלת הסכום הכי גדול שמסתיים בדיוק באיבר ה-i-1 ועוד האיבר במקום ה-i, או הסדרה הריקה. ולכן:

exact = max{0,exact[i-1]+A}​

(גם הסדרה הריקה נכללת) צריך לתת גם תנאי התחלה:

before[0] = 0 exact[0] = A[0]​

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

 

[ChipsMan]

ותסלחו לי על תקלה טכנית..

קטנה

סדרה שמסתיימת בדיוק באיבר ה-i חייבת לכלול את האיבר ה-i ולכן היא לא יכולה להיות הסדרה הריקה. אז קבלו תיקון:

exact = exact[i-1]+A​

 

[ChipsMan]

טוב, החלטה סופית ../images/Emo3.gif

exact[0] = max{0,A[0]} before[0] = 0 exact = max{0,A[i-1]+A} before = max{before[i-1],exact[i-1]}​

עובד

 

[neko]

שני דברים לגבי שאלה אחרת מהמבחן:

1. האם INT הוא 16BIT? 2. האם נסיון לקרוא לאחר EOF בקובץ TEXT בC יקריס את התוכנית, או פשוט יוציא שוב EOF?

 

[ChipsMan]

תשובה

1. לפי הסטנדרט ANSI-C גודלו של INT מובטח להיות לפחות 16 ביטים. זה אומר שגודלו האמיתי תלוי במימוש, אבל מובטח לך שהוא לא יהיה מתחת ל-16 ביט. בקשר לשאלה 2 - אין לי מושג. תנסה