פורסם 2008 בפברואר 1317 שנים חשבתי על שאלה לא פשוטה ב- JAVA שעלולה להופיע בבחינה... אם אני מעוניין לכתוב שיטה שמקבלת מערך באורך שאינו ידוע אשר בודקת האם המערך הינו פולינדרום בסיסוכיות O(n) האם זה אפשרי ע"י זה שלא ידוע אורך המערך ובכלל בסיבוכיות הנ"ל ? אם כן אשמח להצעת אלגוריתם פשוט ויעיל תודה !
פורסם 2008 בפברואר 1317 שנים לא ברור מה הכוונה ב "מערך באורך שאינו ידוע", אם הוא לא יודע, אז מה המשמעות של O(N)?
פורסם 2008 בפברואר 1317 שנים זה אמור להיות מעניין באיזושהי צורה ? :s05:תעשה לולאה אחת שעוברת על המערך רק בשביל לדעת מה האורך שלו (נניח אורך=N)לולאה שניה שרצה ומשווה בין המערך במיקום I לבין מיקום N-I באם הוא שונה התוצאה היא "לא" באם הגענו לI*2 =N אזי התשובה "כן"סה"כ רצנו פעמיים על המערך ולכן הסיבוכיות היא 2N~Nאתה רוצה לעשות את זה פחות יעיל בזכרון ויותר יעיל בזמן ריצה? תדחוף את החצי הראשון של המערך למחסנית ותשלוף תוך כדי השוואה בחצי השני של המערך. סה"כ עברנו על המערך פעם אחת ולכן הסיבוכיות היא N בדיוק.ניסיתי, ועדיין קשה לי לחשוב על שאלה יותר קלה מזאת...
פורסם 2008 בפברואר 1317 שנים השאלה הזאת לא ממש קשה... במיוחד אם יש לך פונקציה שמחזירה אורך מערך כמו בC#
פורסם 2008 בפברואר 1317 שנים ב JAVA אין דבר כזה מערך שלא ידוע אורכו. לכל מערך יש משתנה בשם length שנותן את המידע המבוקשלמשל private void someMethod(byte[] b){ int i = b.length ;{
פורסם 2008 בפברואר 1317 שנים מחבר זה אמור להיות מעניין באיזושהי צורה ? מצחיק מאוד ....תדחוף את החצי הראשון של המערך למחסנית ותשלוף תוך כדי השוואה בחצי השני של המערך. סה"כ עברנו על המערך פעם אחת ולכן הסיבוכיות היא N בדיוק.אני חושב שזה אחלה פתרון... למרות שלא צריך מחסנית ניתן להעביר למערך שני שאורכו כמחצית מאורך המערך הנתון...למשל private void someMethod(byte[] b){ int i = b.length ;{אבל למה ככה ???פשוט בלולאה לשים את b.length
פורסם 2008 בפברואר 1317 שנים אם אתה מגדיר מחסנית או מערך נוסף, אתה מוסיף גם סיבוכיות מקום ואז זה לא בדיוק O)N(, אתה יכול פשוט להגדיר 2 אינדקסים: אחד לתחילת המערך שרץ קדימה ואיחד בסוף שרץ אחורה, ולהשוות בין התאים במערך, אם זו אותה אות - ממשיך, אם לא - יוצא.צריך כמובן להתחשב באורך המערך (זוגי או אי זוגי) ובעוד כמה דברים קטנים, אבל זנ בהחלט אפשרי ולא מסובך.ניתן גם לעשות את זה ברקורסיה.
פורסם 2008 בפברואר 1317 שנים מה זה למה ככה.... לא באתי לתת פתרון מלא לבעיה. הדגמתי שכל מערך בג'אווה תמיד ידוע האורך שלו, גם אם הוא ארגומנט למתודה.
פורסם 2008 בפברואר 1317 שנים אם אתה מגדיר מחסנית או מערך נוסף, אתה מוסיף גם סיבוכיות מקום ואז זה לא בדיוק O)N(אז כמה זה בדיוק ? O)N+1( ? אפשר להפסיק להתפלפל בשאלה הלא הגיונית הזו ?
פורסם 2008 בפברואר 1417 שנים מצחיק מאוד ....אני חושב שזה אחלה פתרון... למרות שלא צריך מחסנית ניתן להעביר למערך שני שאורכו כמחצית מאורך המערך הנתון...אבל למה ככה ???פשוט בלולאה לשים את b.lengthזה לא מצחיק, זה עצוב.גם ישבתי לענות לך גם ירדת על התשובה שלי והצעת פתרון שהוא לא יותר טוב ממה שהצעתי.קודם כל תודה לכל המגיבים שעוזרים לך משום מה, אח"כ תנסה להבין אם השאלה מגבילה אותך מלדעת מה אורך המערך (אחרת מה הטעם בלהגיד שאורכה לא ידוע?) ואז תרכיב מכל התגובות פה את התשובה הנכונה ביותר.ואז תודה למגיבים שוב שלא רק שהם השקיעו מזמנם לנסות לעזור לך אלא שגם בזכותם למדת משו והגעת לפתרון השאלה שלך.ולגבי המצחיק\עצוב - השאלה הזו מגיעה ממבחן ביתספר או מקורס ראשוני בתחום ? איפה אתה לומד ?
פורסם 2008 בפברואר 1417 שנים וואי וואי ווווואאייי! תרגעו כבר יאללה איתכם! מה נסגר?! לא כל אחד מתכנת שנים כמוכם.בכל מקרה, הם צודקים. בג'אווה אין דבר כזה מערך באורך לא ידוע.הפיתרון שלי (אגב לי נתנו את אותה שאלה רק שהמערך בעצם היה מספר והיה צריך לפרק אותו למערך לפני כן)הוא למצוא את אורך המערך ואז לשים שני אינדקסים שהראשון (A) הוא בתחילת המערך והשני (B) בסופו ואז לעשות לולאה באורך חצי המערך.בכל שלב להשוות בין שני האיברים שעליהם מצביעים האינדקסים. אם לא שווה, מיידית להחזיר FALSE. אם שווה אז להמשיך הלאה. האינדקס הראשון יוגדל ב 1 והשני יופחת ב 1.את הלולאה אתה יכול לעשות ב WHILE כאשר התנאי הוא שכל עוד A<=B יש להמשיך. ככה אתה פותר את הבעייה של מערכים זוגיים\אי זוגיים.בהצלחה.נ.ב. שכחתי סיבוכיות - סך מספר הפעולות הוא חצי N אז הסיבוכיות היא O של N.
פורסם 2008 בפברואר 1417 שנים הפיתרון שלי (אגב לי נתנו את אותה שאלה רק שהמערך בעצם היה מספר והיה צריך לפרק אותו למערך לפני כן)הוא למצוא את אורך המערך ואז לשים שני אינדקסים שהראשון (A) הוא בתחילת המערך והשני (B) בסופו ואז לעשות לולאה באורך חצי המערך.בכל שלב להשוות בין שני האיברים שעליהם מצביעים האינדקסים. אם לא שווה, מיידית להחזיר FALSE. אם שווה אז להמשיך הלאה. האינדקס הראשון יוגדל ב 1 והשני יופחת ב 1.את הלולאה אתה יכול לעשות ב WHILE כאשר התנאי הוא שכל עוד A<=B יש להמשיך. ככה אתה פותר את הבעייה של מערכים זוגיים\אי זוגיים.בהצלחה.נ.ב. שכחתי סיבוכיות - סך מספר הפעולות הוא חצי N אז הסיבוכיות היא O של N.אם אתה מגדיר מחסנית או מערך נוסף, אתה מוסיף גם סיבוכיות מקום ואז זה לא בדיוק O)N(, אתה יכול פשוט להגדיר 2 אינדקסים: אחד לתחילת המערך שרץ קדימה ואיחד בסוף שרץ אחורה, ולהשוות בין התאים במערך, אם זו אותה אות - ממשיך, אם לא - יוצא.צריך כמובן להתחשב באורך המערך (זוגי או אי זוגי) ובעוד כמה דברים קטנים, אבל זנ בהחלט אפשרי ולא מסובך.ניתן גם לעשות את זה ברקורסיה.נראה לי הפיתרון הכי טוב.אז כמה זה בדיוק ? O)N+1( ? אפשר להפסיק להתפלפל בשאלה הלא הגיונית הזו ?תתפלא אבל סיבוכיות מקום תופסת חלק נכבד וכדאי להתחשב גם בה.
פורסם 2008 בפברואר 1417 שנים כן, רק שלהוסיף מחסנית ו/או מערך נוסף (או שתיהם) עדיין נחשב ל O)N( בדיוק (בתוכנית הזו).
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.