?

[JohnnyPiloni]

?

נתון מערך [ a[1..n לא ממויין המכיל את כל הערכים בין 0 ל n חוץ מאחד מהם. תכננו אלגוריתמים הפרד ומשול שמוצא איזה איבר חסר ב ( O(n תוך שימוש של ( O(1 זיכרון. נתחו סיבוכיות האלגוריתם שלכם.

 

[אנדרומארי]

אתה פשוט צריך לעבור על המערך

ולהחזיק משתנה sum שסוכם את כל האיברים בו. האיבר החסר הוא כמובן

(1+2+...+n)-sum​

 

[JohnnyPiloni]

ביקשו הפרד ומשול

 

[Okuryo]

../images/Emo119.gif

http://www.tapuz.co.il/tapuzforum/main/Viewmsg.asp?forum=1428&msgid=108683282