חידה יפה

[nautilus7791]

חידה יפה

נתונות N מטבעות זהות כאשר מטבע אחד יותר קל משאר המטבעות.יש נואזניים שבעזרתם עליינו לברר מהו המטבע הקל.כמה שקילות במקרה הגרוע נצטרך לעשות (בעזרת אלגוריתם אופטימלי) אם אפשר לשים בכל צד של המאזניים מספר כלשהו של מטבעות בשקילה אחת?

 

[DyingToLiVe]

תשובה

trunc של Log 2 N מי שיודע פסקל

הקיצר זה עץ בינארי שלכל תא יש שני תאי המשך.

 

[DyingToLiVe]

הינה יותר יפה ככה

trunc(logN/log2)=מספר השקילות

 

[nautilus7791]

אסור להשתמש ב trunc

 

[טלמון סילבר]

תיקון -

לוגריתם 3.

 

[Fingertip]

../images/Emo127.gif

אהד.

 

[DyingToLiVe]

עוד סוג של ניסיון

זה עץ בינארי מלא, רק אין לי מושג איך מייצגים אותו ע"י משוואה! עזרו לי!

 

[nautilus7791]

נכון,זה לוג בבסיס 3.יש המשך לחידה

כעת מותר לשים על כל צעד של המאזניים עד K מטבאות.מה הסיבוכיות כעת?

 

[DyingToLiVe]

א. לא כותבים תשובות בכותרת

ב. אתה יכול להסביר לי?