Yehudaa פורסם 2008 בפברואר 15 Share פורסם 2008 בפברואר 15 יש בעיה מפורסמת במדעי המחשב , והיא מיון מערך בסיבוכיות של n נתון מערך של תווים שהם או כחול או אדום או לבן ויש למיין אותן לפי דגל הולנד התווים הכחולים יש להצמיד לסוף המערך , התווים האדומים יש להצמיד לתחילת המערך , והתווים הלבנים באמצע כתבתי קוד כזה : public class Test{ public static void main(String[] args) { char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b'}; int BlueP=array.length-1 , RedP=0; char temp ; for (int i=0; i<array.length;i++) { if ( array[i]=='b' ) { temp=array[i]; array[i]=array[BlueP]; array[BlueP]=temp; BlueP--; } else if ( array[i]=='r' ) { temp=array[i]; array[i]=array[RedP]; array[RedP]=temp; RedP++; }}// for lopfor (int i=0 ; i<array.length ;i++)System.out.print ( array[i]);}// main} מה לא בסדר בקוד הזה ? הוא עובר קימפול , אבל לא מבצע את המשימה . קישור לתוכן שתף באתרים אחרים More sharing options...
exercise פורסם 2008 בפברואר 15 Share פורסם 2008 בפברואר 15 סתם מקריאה של הקוד, כשאתה מחליף את ה 'b' ב IF הראשון, מה קורה אם המיקום שב BlueP הוא כבר 'b' ? (הבנת את הרמז?) קישור לתוכן שתף באתרים אחרים More sharing options...
Yehudaa פורסם 2008 בפברואר 15 מחבר Share פורסם 2008 בפברואר 15 הוא יחליף בכל מקרה את ה 'b' זה לא מה שלא בסדר בתוכנית , התוכנית שלי גרועה מאוד , כנראה צריך שינוי מסיבי בה . קישור לתוכן שתף באתרים אחרים More sharing options...
Holy פורסם 2008 בפברואר 15 Share פורסם 2008 בפברואר 15 במקום זה פשוט תחזיק 2 מוניםתעשה לולאה שסופרת כמה כחול יש וכמה אדום ישמספר הלבנים הוא גודל המערך פחות מספר הכחולים פחות מספר האדומיםואז פשוט תכתוב לתוך המערך b כמספר הכחולים, r כמספר האדומים ו-w כמספר הלבנים.פשוט וקל קישור לתוכן שתף באתרים אחרים More sharing options...
exercise פורסם 2008 בפברואר 15 Share פורסם 2008 בפברואר 15 אם אתה רוצה למיין, פשוט תדאג כאשר אתה מבצע את ההחלפה לבדוק שהאיבר שאתה מחליף לתוכו הוא לא במקום שלו (אם יש שם איבר נכון, פשוט תקדם את המונה של ה bluep ותבצע את הבדיקה שוב), זה לפחות תיקון אחד שצריך לעשות. קישור לתוכן שתף באתרים אחרים More sharing options...
Yehudaa פורסם 2008 בפברואר 15 מחבר Share פורסם 2008 בפברואר 15 במקום זה פשוט תחזיק 2 מונים תעשה לולאה שסופרת כמה כחול יש וכמה אדום יש מספר הלבנים הוא גודל המערך פחות מספר הכחולים פחות מספר האדומים ואז פשוט תכתוב לתוך המערך b כמספר הכחולים, r כמספר האדומים ו-w כמספר הלבנים. פשוט וקל רעיון מעולה פשוט ומצוין וכנראה הוא בסיבוכיות O (n אבל צריך להיות פתרון לא על ידי דריסת נתונים , כלומר על ידי החלפת האיברים . אם מישהו יודע את האלגוריתם אשמח לשמוע . אם אתה רוצה למיין, פשוט תדאג כאשר אתה מבצע את ההחלפה לבדוק שהאיבר שאתה מחליף לתוכו הוא לא במקום שלו (אם יש שם איבר נכון, פשוט תקדם את המונה של ה bluep ותבצע את הבדיקה שוב), זה לפחות תיקון אחד שצריך לעשות. אני אבדוק את זה , אבל נראה לי שהאלגוריתם שלי לא בר ביצוע . ויש לתכנן אלגוריתם שונה לחלוטין , אלא אם כן מישהו הצליח לתקן את הקוד שלי , אז אשמח לראות . תודה למגיבים קישור לתוכן שתף באתרים אחרים More sharing options...
exercise פורסם 2008 בפברואר 15 Share פורסם 2008 בפברואר 15 לא בדקתי את זה יותר מדי: char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b'}; int BlueP=array.length-1 , RedP=0; char temp; for (int i=0; i<BlueP;i++) { if (array[i] == 'b') { temp=array[i]; while (array[BlueP] == 'b') BlueP--; array[i]=array[BlueP]; array[BlueP]=temp; BlueP--; } if (array[i] == 'r') { temp=array[i]; array[i]=array[RedP]; array[RedP]=temp; RedP++; } } for (int i=0 ; i<array.length ;i++) System.out.print ( array[i]); קישור לתוכן שתף באתרים אחרים More sharing options...
Yehudaa פורסם 2008 בפברואר 15 מחבר Share פורסם 2008 בפברואר 15 מתברר שהאלגוריתם שלי יעיל ובעל סיבוכיות כנדרש exercise אתה עלית על הבעיה מהרגע הראשון וזה הקוד הסופי בדוק ומנוסה public class Test{ public static void main(String[] args) { char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b','r','w','b','r','w','b','r','w','b'}; int BlueP=(array.length-1) , RedP=0; char temp ; for (int i=0; i<=BlueP;i++) { if ( array[i]=='b' ) { if (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++; }}// for lopfor (int i=0 ; i<array.length ;i++)System.out.print ( array[i]);System.out.println("");}// main} קישור לתוכן שתף באתרים אחרים More sharing options...
Jaman פורסם 2008 בפברואר 16 Share פורסם 2008 בפברואר 16 הקוד הסופי שלך לא נכון. תנסה להחליף את ה 'w' האחרון במערך ב 'b' ותראה.בהתחלה כשקראתי את הבעיה חשבתי שצריך לעבור על כל המערך ולשלוף כחולים ולדחוף אותם לסוף, ולשלוף אדומים ולדחוף להתחלה, אבל זה לא מתאים למערך, אלה לרשימה מקושרת..נראה לי שהפתרון של Holy הוא הכי טוב (ממה שהוצא כאן).הפתרון של exercise בכלל בסיבוכיות n? קישור לתוכן שתף באתרים אחרים More sharing options...
Yehudaa פורסם 2008 בפברואר 16 מחבר Share פורסם 2008 בפברואר 16 כן אתה צודק יש בקוד למעלה באג תבדוק את הקוד הזה לעניות דעתי הוא מושלם (מבחינת הביצוע ) public class Test{ public static void main(String[] args) { char[] array= {'r','w','b','r','w','b','r','w','b','r','w','b','r','w','r','w','b','r','w','b','r','w','b','r','w','b'}; int BlueP=(array.length-1) , RedP=0; char temp ; for (int i=0; i<=BlueP;i++) { 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++; }}// for lopfor (int i=0 ; i<array.length ;i++)System.out.print ( array[i]);System.out.println("");}// main} כן הוא בעל סיבוכיות n כי אנחנו עוברים על המערך פעם אחת בלוללאת FOR אחת קישור לתוכן שתף באתרים אחרים More sharing options...
Jaman פורסם 2008 בפברואר 16 Share פורסם 2008 בפברואר 16 מבחינה לוגית נראה לי שזה נכון.את נושא הסיבוכיות אני לא ממש יודע, אבל עכשיו כשאני מסתכל על זה נראה לי שזה כמו שצריך למרות הכל.. קישור לתוכן שתף באתרים אחרים More sharing options...
exercise פורסם 2008 בפברואר 16 Share פורסם 2008 בפברואר 16 נסה את הקלט 'w', 'w', 'w', 'r', 'w', 'b' ותראה אם הוא נכון...ובמקום להסתמך על האם זה נראה נכון, כדי אולי לשבת ולנסות להוכיח שזה נכון (או לא). קישור לתוכן שתף באתרים אחרים More sharing options...
Jaman פורסם 2008 בפברואר 16 Share פורסם 2008 בפברואר 16 צודק...ניסיתי עכשיו איזה שעה לתקן את זה כך שזה יתאים לכל המקרים, אבל כל פעם שאני פותר מקרה ספיציפי אחד, נוצר מקרה ספציפי אחר שהאלג' לא מתאים לו..ד"א גם האלג' שלך לא מתאים לכל המקרים. אם שמים בו רק אדומים ולבנים, כשיש אדום בסוף, אז יש באג.אולי אפשר להשתמש באלג' שלך יחד עם if בסוף שיבדוק את המקרה הספציפי הזה, אבל יכול ליהיות שיש עוד מקרים שהוא לא מתאים להם, כבר אין לי כח לנסות לחשוב על עוד.נמאס לי, אני מחפש פתרון באינטרנט. קישור לתוכן שתף באתרים אחרים More sharing options...
exercise פורסם 2008 בפברואר 16 Share פורסם 2008 בפברואר 16 את הבעיה בקלט שלי ניתן לפתור ע"י זה שבודקים בהחלפה של B האם הגענו כבר לרצף Bים, אם כן מפסיקים.וד"א הפתרון שלו זה לא העתק מדויק של הפתרון שלי ? קישור לתוכן שתף באתרים אחרים More sharing options...
Yehudaa פורסם 2008 בפברואר 16 מחבר Share פורסם 2008 בפברואר 16 כן זה אותו פתרון כמו שלך , רק בשינוי מזערי אני כתבתי כך : while (array[blueP]=='b') BlueP--; temp=array; array=array[blueP]; array[blueP]=temp; BlueP--; ואתה כתבת כך : temp=array; while (array[blueP] == 'b') BlueP--; array=array[blueP]; array[blueP]=temp; BlueP--; קישור לתוכן שתף באתרים אחרים More sharing options...
Recommended Posts
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.