שאלה מראיון עבודה

[royGal3]

שאלה מראיון עבודה

שלום לכולם,
שאלה שנשאלתי בראיון עבודה ולא מצאתי לה תשובה:
נתונים זוגות מספרים (x,y), יש למיין את הזוגות עפ"י הערך של x בחזקת y.
אך כמובן שאסור לחשב במפורש את הערכים מסיבות overflow ויעילות.

יתכן שהפתרון הסופי הוא רק מקורב, אינני יודע בוודאות.

 

[vinney]

משתתפים בצערך.

אז שתף אותנו, איך הלך הראיון? נתנו לך את השאלה, אמרת ״אויש, לא יודע...״ והלכת הבייתה?

 

[Netanel w]

הרעיון הראשון שקפץ לי לראש

(סטודנט, עוד לא בענייני ראיונות עבודה).

מניח שיש דרכים רבות לעשות זאת, אבל זאת הראשונה שקפצה לי לראש:
מכיוון שלוגריתם היא פונק' מונוטונית, ניתן במקום לחשב את x בחזקת y,
למיין על פי לוג של הביטוי, כלומר על פי (y כפול log x).
(אם x שלילי יש להתחשב בסימן..)

 

[royGal3]

נראה לגיטימי

במהלך הראיון באמת ניסו לכוון אותי להפעיל איזשהו אופרטור על x,y שיתן הערכה לסדר, לכן הפתרון שלך(נתנאל) נראה מתאים
אם יש רעיונות נוספים אשמח לשמוע.
ושאר הראיון היה בסדר גמור, לא היו שאלות מעניינות נוספות.

 

[rontech]

תודה על השאלה....

האם הם הגבילו את התחום של X?
וניזכר בחוקי החזקות....
X^ (-n) = 1 / x^n
X^ 1/n = n th root of X
המשך יבוא....

 

[rontech]

כאשר X גדול מ - 0 למיין לפי לוג

 

[rontech]

לדעתי בתחום X<0 תשתמש ב (log(-x

אבל תימנע מערכים של Y שאינם שלמים כדי לא ליפול על מספרים מרוכבים

 

[ישעיהו בודניוק]

Exponentiation by squaring

למיטב זיכרוני, באלגוריתם של rsa עושים משהו דומה, או שאולי אני טועה
https://en.wikipedia.org/wiki/Exponentiation_by_squaring
אבל בקיצור
לדוגמא: חמש בריבוע
חמש בחזקת 4 => 4 לחלק ל2 ואז עושים 5 בריבוע, ואז אתה התוצאה בריבוע.
וככה בודקים כל מספר