תראד עזרה לקראת המבחן במבוא ג'אווה *עדכון* ע"מ 5 שאלה ברקורסיה !

[Jaman]

1* את הבעיה בקלט שלי ניתן לפתור ע"י זה שבודקים בהחלפה של B האם הגענו כבר לרצף Bים, אם כן מפסיקים.

2* ו2ד"א הפתרון שלו זה לא העתק מדויק של הפתרון שלי ?

1* - לא ממש הבנתי.. אם אין Bים, מה זה משנה מה תבדוק שמה?

2* - ההבדל המהותי בין התוכניות שלכם הוא שאצלך לולאה ה for היא:

(int i=0; i<BlueP;i++)

(ולכן הבאג כשאין כחול ויש בסוף אדום)

ואצל אודי היא כך:

(int i=0; i<=BlueP;i++)

(ולכן הבאג עם הקלט - 'r', 'w', 'b')

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

[exercise]

ואם משנים את השורה של בדיקת ה 'B' ל:

if (array == 'b' && i < BlueP)

?

[Yehudaa]

קצת שאלה לא קשורה הלכתי קצת לאיבוד ב API

אני רוצה לצור אובייקט מטיפוס המחלקה Scanner

Scanner scan = new Scanner(System.in

איזה מתודה קוראת את התו הראשון בלבד מהקלט ?

[TheReaper]

בנוגע לפלט 'w', 'w', 'w', 'r', 'w', 'b'

הצלחתי לתקן את הבעיה בעזרת משתנה בוליאני

char[] array= {'w', 'w', 'w', 'r', 'w', 'b'};
      int BlueP=(array.Length-1) , RedP=0;
      char temp ;
      bool endit;
      for (int i=0; i<=BlueP;i++) 
      {
        if (endit=false) 
        if ( array[i]=='b' )
        {
         while (array[BlueP]=='b')
           BlueP--;
         temp=array[i];
         array[i]=array[BlueP];
         array[BlueP]=temp;
         BlueP--;
        }
        if ( array[i]=='r' )
        {
          temp=array[i];
          array[i]=array[RedP];
          array[RedP]=temp;
          RedP++; 
        }
        if (array[i] == 'w')
        {
          int tempi = i;
          while (array[tempi] == 'w')
            tempi++;
          if (array[tempi] != 'b')
          {
            temp = array[i];
            array[i] = array[tempi];
            array[tempi] = temp;
          }
          else
            endit=true;
        }
      }// for lop
      for (int i = 0; i < array.Length; i++)
        Console.Write(array[i] + " ");
      Console.Read();

(כתוב בC# אבל לא אמורה להיות בעיה לתרגם הם ממש דומות)

זה אמור להיות עדיין N

אם מישהו יכול למצוא קלט שיכתוב פה

[Jaman]

ואם משנים את השורה של בדיקת ה 'B' ל:

if (array == 'b' && i < BlueP)

?

לא משנה, עכשיו הבנתי למה התכוונת, קודם לא הייתי מרוכז..

באותה מידה אפשר להשאיר את התוכנית כמו שהיא (כלומר מ0 עד BlueP לא כולל), ורק בסופה לבדוק מקרים מסויימים.

גם יש אפשרות שכל המערך יהיה 'r', התוכנית בתרגיל הזה צריכה בכלל להתמודד עם קלט כזה?

[TheReaper]

קבלו תיקון לתוכנית הקודמת שלי... כאשר עושים WHILE בתוך FOR זה בעצם N^2

אם רוצים N אז המקרה היחיד שאני מצליח לחשוב עליו זה קודם לעשות FOR שיסדר את האדומים

ואז FOR שיסדר את הכחולים שיתחיל ממקום אחד אחרי הRED האחרון

ואז עוד FOR ממקום אחרי הR האחרון עד מקום לפני הB הראשון שיסדר את הW וB שנשארו

[exercise]

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

[TheReaper]

אם המערך מכיל N תאים הWHILE יכול לעבוד N פעמים במקרה הכי ארוך

ובגלל שהוא מקונן הסיבוכיות היא N^2

[NJorl]

חברים, אני לא ממש עקבתי אחרי קטעי הקוד ששלחתם כאן

אבל אף מכם לא שם לב שהתרגיל היא למעשה שאלת מיון פשוטה סטנדרטית ביותר במסווה של שאלה כאילו יותר מורכבת

תחשבו שיש לכם מערך ובו איברים 1 , 2 ו-3 , כל מספר מייצג צבע

יש ב-וויקיפדיה מספר אלגוריתם למיון

במקרה הספציפי של דגל הולנד יש רק יוצא מן הכלל אחד לפיו b (צבע כחול) גדול משני הקודים האחרים , בניגוד לסדר ה- ascii הרגיל

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

[exercise]

NJorl אני לא יודע אם זה נאמר פה במפורש, אבל הכוונה פה היא לעשות את המיון בסיבוכיות של O)N( ולכן המיונים הרגילים לא יעזרו פה.

TheRepear אתה טועה, אתה מדבר בהכללות בלי לראות מה משמעות, אם ה WHILE ירוץ N פעמים, הוא יקצר את המצביע BlueP ב N ואז הלולאת FOR לא תרוץ יותר.

[Yehudaa]

כן השאלה מותנת במעבר אחד על המערך הווה אומר O)N

[Niseg]

אני חושב שאני יודע את הפתרון כל עוד עושים את זה על מערך אחר זה די קל אחרת אני חושב שצריך counting sort עם סיבוכיות של כ3N אולי פחות אבל צריך לעשות איזה מערך תרגום של האינדקסים כי הסדר הוא לא אלפאבתי.

הנה פתרון אחד לוקחים מערך ומשתמשים בשני הקצוות שלו כמחסניות מצד ימין w ומצד שמאל r . הבעיה היא בעיקר עם ה blue . הפתרון הכי פשוט זה למלא את המערך ב b ואז זה נותן סיבוכיות של 2n אפשרות נוספת זה להתעלם מה b ואז מקבלים סיבוכיות של n עד סיבוכיות של 2n (בסוף צריך למלא את האמצע בb ) .

לא פירטתי יותר מדי אבל אפשר לקחת את זה ולבנות פתרון

כן השאלה מותנת במעבר אחד על המערך הווה אומר O)N

חייבים רק מעבר אחד או חייבים O(N) ? כי זה לא אותו דבר. כי הO(n) אומר שאין לולאות בתוך הלולאות . מעבר אחד זה מקרה מיוחד של O(N)

[Yehudaa]

נראה לי שאפשר 2n 3n 4n 5n .......

אבל אסור n^2

אבל הנוסח של השאלה היה "במעבר אחד על המערך " [br]פורסם בתאריך: 17.02.2008 בשעה 22:42:07

---

טוב חברים אחרי שטחנו מכל הכיוונים את הבעיה

הנה השאלה המקורית ופתרונה

השאלה נמצאת בשקף 14-64 והלאה

[attachment deleted by admin]

[david_borohov]

קראתי את כל הת'רד עד לפה, ולא הבנתי על מה כל המהומה...

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

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

במעבר הראשון על המערך פשוט עבור כל צבע שאתה רואה , תעשה ++ על המקום המתאים שלו במערך.

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

שים לב שהדבר מתבצע בזמן לינארי.

מקווה שעזרתי.

[Jaman]

1) כבר הציעו את זה בעמוד הראשון.

2) שים לב שהדרישה היא למעבר אחד על המערך (בקובץ שudi הביא).