רוטר - שאלה ב C

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"שאלה ב C"

גירסת הדפסה

קבוצות דיון פיתוח, תיכנות ובניית אתרים נושא #11077	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 11077

IDAN_500
חבר מתאריך 11.12.03
2321 הודעות

11:48 17.12.12

שאלה ב C

כתוב פונקציה לא רקורסיבית שמקבלת מספר טבעי n וערך ממשי x. פונקציה תחשב x^n
ותחזיר את התוצאה.
על הפונקציה לרוץ בסדר גודל logn.
התחלתי לכתוב משהו, אבל זה מתברר כלא נכון:
result=1;
while (n>0)
{
if n זוגי
result*=x;
else
result*=result*x;
n/=2;
}
return result;

יש מצב שמישהו עוזר לי לפתור את זה בסדר גודל של logn?

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
קח דרך פתרון..	VeNom	17.12.12 20:51	1

VeNom

חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק

20:51 17.12.12

1. קח דרך פתרון..
בתגובה להודעה מספר 0

תחשוב על משהו כזה:
2 בחזקת 8 = 256. אפשר לרוץ כאן בסדר גודל של N ולהכפיל N פעמים את 2 בעצמו.
אבל אפשר גם לצמצם את זה:

option 1:
res = 2^8 = 2*2*2*2*2*2*2*2 = 256 -> O(n).
option 2:
res = 2^8 = (2^2)^4 = (((2^2)^2)^2) = ((4^2)^2) = (16^2) = 256 => O(log(n)).
רק צריך לטפל במצב של חזקה אי זוגית..

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד