PDA

צפה בגרסה המלאה : בעיה נחמדה במחשבים



עשהאל
23-06-2008, 23:39
בס"ד

נתונים שני מערכים. אחד בגודל n ואחד בגודל n+1.

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

איך תמצאו אותו באופן יעיל?

אריאל
24-06-2008, 00:41
אותו , את האיבר הנוסף?
לא יודע אם זה מה שהתכוונת("יעיל") אבל זה אפשרי:
בונים פונקציה המקבלת איבר ומערך , הבודקת האם האיבר נמצא במערך, אם כן TRUE אחרת FALSE ..
עושים לולאה אשר עוברת על כל איברי המערך הגדול(כאשר כל לופ גדל עוברת לאיבר הבא) עד אשר הפונקציה תחזיר FALSE עבור המערך הקטן והאיבר עבור הסיבוב הנתון של הלולאה.

אריאל
24-06-2008, 00:45
כמובן הכל בהנחה שכל האיברים שונים זה מזה.
ואפשר לעשות פה משו עם סכום גם כן..

Tomer
24-06-2008, 06:37
בהשראת הרעיון של הסכום שלאריאל
אפשר לסכם את כל המערך הגדול והקטן, לחסר את הסכום הקטן מהגדול וזה המספר הנוסף.
וכאן אני חושב שלא כל המספרים חייבים להיות שונים זה מזה

orenef11
24-06-2008, 12:57
Tomer
תומר מה שאמרת נראה לי התשובה עשהאל התכוון.
כי מה שאריאל התכוון זה שהוא עובד על המערך בסיבוכיות {יעילות} n^2
ומה שאתה אמרת זה סיבוכיות של n^1.

עשהאל
24-06-2008, 16:11
בס"ד

יפה מאוד!

אגב, סכום יעבוד על מספרים שלמים, בשפות תכנות מסויימות. באופן כללי, אני חושב שאפשר לעשות xor.

orenef11
24-06-2008, 20:17
עשהאל שאתה אמרת xor מה זה?

אריאל
24-06-2008, 22:26
חפש שערים לוגים בגוגל

עשהאל
24-06-2008, 23:59
בס"ד

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

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

orenef11
25-06-2008, 02:52
תודה רבה!!
אבל זה כמו שאמרת בהנחה שאותם סיביות וזה לא מתאים לכל שפת תכנות.

עשהאל
25-06-2008, 10:36
בס"ד

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