3d7 פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 קיים מערך בגודל n שכל אחד מהאיברים שלו מכיל מספר מטיפוס long.כל אחד מהמספרים מופיע במערך מספר זוגי של פעמים, מלבד מספר אחד שמופיע במערך מספר אי-זוגי של פעמים.צריך למצוא את המספר שמופיע במערך מספר אי-זוגי של פעמים בסיבוכיות של (O(nlogn.דוגמה 1: 5 5 3 4 4 4 6 4 6 --> המספר שמופיע מספר אי-זוגי של פעמים הוא 3.דוגמה 2: 3 2 2 2 4 3 4 --> המספר שמופיע מספר אי-זוגי של פעמים הוא 2. קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 תמיין את המערך ותעבור מספר מספר ותספור האם המספר מופיע מספר זוגי או אי-זוגי של פעמים ? קישור לתוכן שתף באתרים אחרים More sharing options...
3d7 פורסם 2008 ביולי 25 מחבר Share פורסם 2008 ביולי 25 נכון! תביאו עוד חידות. : קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 יש לך מערך של מספרים בגודל N ומספר משתנה X. איך ניתן בצורה הכי יעילה להגיד האם סכום 2 מספרים במערך שווים ל X (אתה יכול לבחור לענות ביעילות זיכרון או יעילות זמן). קישור לתוכן שתף באתרים אחרים More sharing options...
שניצל פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 טוב, אני לא אהרוס את החידה (אני מכיר את האלגוריתם לפתרון של דברים כאלה), אבל אני אחוד עוד אחת:ממשו קלאס המייצג מערך של int (בגודל מוגדר מראש N) שבו ניתן לבצע שלוש פעולות: לשים ערך בתא מסוים, לקחת ערך מתא מסוים, ולשים ערך בכל התאים:class MyArray{public: void set(int i, int value); int get(int i); void setAll(int value);}; הקאץ' הוא ששלוש הפעולות צריכות לעבוד ב-(O(1. קישור לתוכן שתף באתרים אחרים More sharing options...
cold fire פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 יש לך מערך של מספרים בגודל N ומספר משתנה X. איך ניתן בצורה הכי יעילה להגיד האם סכום 2 מספרים במערך שווים ל X (אתה יכול לבחור לענות ביעילות זיכרון או יעילות זמן).int vec[8]={1,2,3,4,5,6,7,8};bool checkSum(int index1,int index2,int x){ return vec[index1]+vec[index2]==x;} קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 אתה צוחק או מה ? זה בכלל לא עושה את מה שאמרתי... (אם לא הבנת, הקלט הוא מערך ו X ולא 2 אינדקסים ו X).את הבעיה של שניצל הייתי פותר עם 2 מערכים. (ושניצל האם יש לך 2 אלגוריתמים, אחד שיעיל בזיכרון ואחד שיעיל בזמן ?) קישור לתוכן שתף באתרים אחרים More sharing options...
cold fire פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 אז כנראה שלא הבנתי את השאלהbool checkSum(int vec[],int x){ for(int i=0;i<N-1;i++) { if(vec[i]+vec[i+1]==x) return true; } return false; }אני מקווה שעכשיו הבנתי את השאלה קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 הרבה בעיות, גם לא אמרתי שהמערך ממויין וגם הכיוון שאתה הולך עליו יהיה לא יעיל בעליל (השאלה לא פשוטה ולא קלה בשביל יעילות מקסימלית). הנה דוגמה:עבור מערך 2 6 9 3 8 5 והמספר 17 התשובה היא שיש 2 מספרים כאלו, 8 ו 9. קישור לתוכן שתף באתרים אחרים More sharing options...
cold fire פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 bool checkSum(int vec[],int x){ for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { if(i!=j && vec[i]+vec[j]==x) return true; } } return false;}זה לא פתרון הכי יעיל אבל אני חושב שזה יעבוד קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 זה אפילו פתרון בכלל לא יעיל (אם כי נכון). מה שכן אפשר לעשות פתרון יותר יעיל מבחינת זמן אבל שיקח אותה כמות זיכרון (כמובן שאפשר לעשות פיתרון הרבה יותר יעיל מבחינת זמן אבל שיקח יותר זיכרון). קישור לתוכן שתף באתרים אחרים More sharing options...
EAD פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 יש לך מערך של מספרים בגודל N ומספר משתנה X. איך ניתן בצורה הכי יעילה להגיד האם סכום 2 מספרים במערך שווים ל X (אתה יכול לבחור לענות ביעילות זיכרון או יעילות זמן). פתרון נחמד (לא יחיד), תמיין הערכים במערך. שים שני מצביעים, אחד לסוף המערך ואחד לתחילתו. ותעבור עליו. בכל שלב אתה בודק האם הערכים שווים בסכומם למספר. אם לא אז יש מספר אפשרויות אם קטן, נעלה את המצביע של הראש (שמצביע לקטנים) ב1 אם הסכום גדול, נוריד את המצביע של הראש ב1 (המצביע של הגדולים) אם נגיע למצב ששני המצביעים מתהפכים או מגיעים לאותו אחד (אין יותר אפשרויות) נחזיר כי אין וטעות. מבחינת יעילות - סה"כ מיון של מערך NLOGN אבל אפשר ליצור שהמיון יהיה פה יותר יעיל. אם ידוע שכולם שלמים וחיובים, נוכל ישר להוריד במהלך המיון כל אלו שגדולים ממש מן המספר שלנו ולגבי האחרים נשתמש במיון "דלי" (אנחנו יודעים שזה מאפס ועד המספר שלנו כולל) ונקבל מיון בסדר גודל של N. זה כבר נראה לי די טוב ;D ולגבי השאלה עם המערך שצריך הכל בO של 1 וכו' - אני מכיר את הפתרון, מספיק שאגיד את השם כדי שאנשים יחפשו ברשת וישר ימצאו את הפתרון. שאלה ממש נחמדה למי שלא מכיר, וממש לא קלה קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 למה לא קלה ? נראה לי שפיתרון של שימוש במערך עזר מפשט את הפיתרון.והפיתרון שלך נכון. קישור לתוכן שתף באתרים אחרים More sharing options...
EAD פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 ^^יש לך עוד דרכים לפתור את הבעיה?אשמח מאוד לשמוע.חשבתי על דרכים נוספות, נניח בלי למיין בכלל.שימוש במבני נתונים כמו עצים מיוחדים וכו' (שזה די זהה למיון, אבל יכול להיות יפה יותר אולי)או דברים מתורת הגרפים - יש פה כמו זיווג בעצם על פי משקל מסויים.ולגבי מה שאמרת עם מערך עזר, לא כזה פשוט.תנסה ותראה. קישור לתוכן שתף באתרים אחרים More sharing options...
mandarin פורסם 2008 ביולי 25 Share פורסם 2008 ביולי 25 יש פיתרון של שימוש ב hashtable כאשר אתה עובר על המערך מספר מספר, עבור כל מספר אתה בודק האם X פחות המספר נמצא בפנים, אם כן, החזר אותם, אחרת עבור למספר הבא והכנס את המספר הקודם. אם סיימת לעבור החזר שאין תשובה כזו. קישור לתוכן שתף באתרים אחרים More sharing options...
Recommended Posts
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.