| כותב |
|
bobo
משתמש מתחיל
הצטרף / הצטרפה: 25 December 2008
משתמש: מנותק/ת
הודעות: 5
|
| נשלח בתאריך: 25 December 2008 בשעה 13:53 | | IP רשוּם
|
|
|
|
משהוא יודע אך לבצע באיטרציה בזמן LOG N פעמים את הפונקציה : X בחזקת N
לדוגמא 2 בחזקת 8 יבוצע החישוב ב 3 פעמים לולאה.
|
| חזרה לתחילת העמוד |
|
| |
:)
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 25 December 2008 בשעה 15:09 | | IP רשוּם
|
|
|
|
פשוט לולאה ...
קוד:
int multiply=num;
int pow=power;
for (int i=1;i<=pow;i++)
{
multiply=num*multiply;
}
|
|
|
ולפי הדוגמה שלך :
2 * 2 * 2
___ ___
/\
סה"כ = 3
|
| חזרה לתחילת העמוד |
|
| |
bobo
משתמש מתחיל
הצטרף / הצטרפה: 25 December 2008
משתמש: מנותק/ת
הודעות: 5
|
| נשלח בתאריך: 25 December 2008 בשעה 16:35 | | IP רשוּם
|
|
|
|
זה לא( o(log n פעמים, זה( o(n מה שאמרתה .
השאלה שלי היא קצת יותר מורכבת מלולאה פשוטה.
|
| חזרה לתחילת העמוד |
|
| |
:)
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 25 December 2008 בשעה 18:56 | | IP רשוּם
|
|
|
|
טעות שלי קראתי לא נכון
בכול מקרה אני לא יודע את הפתרון לשאלה המקורית
|
| חזרה לתחילת העמוד |
|
| |
פתרון
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 25 December 2008 בשעה 19:30 | | IP רשוּם
|
|
|
|
שתי אפשרויות
אם אתה לא יודע את הבסיס X כלומר הוא יכול להיות כל דבר
מה שאתה יכול לעשות זה הדבר הבא:
פתרון רקורסיבי
public static int power(int x,int n){
int ans;
if (n==0)
ans =1;
else if (n%2 == 0) {
int k = power(x,n/2);
ans = k*k;
}
else
ans = X*power(x,n-1);
}
return ans;
}}
pפתרון נוסף
במקרה ואתה יודע שהבסיס הוא 2
אתה יכול לעשות y פעמים הזזות שמאלה
של הייצוג הבינארי
|
| חזרה לתחילת העמוד |
|
| |
ארי
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 26 December 2008 בשעה 17:14 | | IP רשוּם
|
|
|
|
בשביל שזמן הריצה של התוכנית יהווה-
צריך להתקיים 2 בחזקת k שווה 8 ולכן ניתן שיתקיים תנאי הלולאה הבא:
קוד:
while (i * x < n)
{
...
i *= x;
} |
|
|
כאשר i = 1. כך יתקבל: לוג 8 לפי בסיס 2 שווה ל-3.
|
| חזרה לתחילת העמוד |
|
| |
bobo
משתמש מתחיל
הצטרף / הצטרפה: 25 December 2008
משתמש: מנותק/ת
הודעות: 5
|
| נשלח בתאריך: 28 December 2008 בשעה 12:41 | | IP רשוּם
|
|
|
|
עם N ששוה ל 8 ,זה עובד טוב וגם לכל N שהוא LOG N ללא שארית.אבל הבעיה ש N למשל שווה ל 7 או 13 וכן הלאה.
|
| חזרה לתחילת העמוד |
|
| |
bobo
משתמש מתחיל
הצטרף / הצטרפה: 25 December 2008
משתמש: מנותק/ת
הודעות: 5
|
| נשלח בתאריך: 28 December 2008 בשעה 15:36 | | IP רשוּם
|
|
|
|
קיצור משהוא בפורום אחר נתן לי את התשובה וזה לא הכי טריויאלי .
הנה הפתרון (נ"ב צריך להפוך את ה N למספר בינארי קודם כל):
for each bit position that there is (ignoring the highest bit), you need to
square the number, and in addition if a bit is 1, you also need to multiply by
x. So for example, to raise to the power 18, that's n= 10010 in binary. Chop off
the first 1, then for the next two "0"s square the number each time (x^2^2 =
x^4), then for the "1" square and multiply by x (=x^4^2.x = x^9), then for the
final "0" we square again (x^9^2 = x^18).
|
| חזרה לתחילת העמוד |
|
| |
ארי
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 29 December 2008 בשעה 00:20 | | IP רשוּם
|
|
|
|
ואיך זה יתבטא בקוד עם זמן ריצה של לוג n ?
|
| חזרה לתחילת העמוד |
|
| |
bobo
משתמש מתחיל
הצטרף / הצטרפה: 25 December 2008
משתמש: מנותק/ת
הודעות: 5
|
| נשלח בתאריך: 01 January 2009 בשעה 11:35 | | IP רשוּם
|
|
|
|
זמן ריצה יהיה 2*LOGN .
לולאת LOG N ראשון יהיה להפוך את ה N לבינארי.
לולאת LOGN שני תהיה לביצוע האלגוריתם הנ"ל
והתשובה באמת יוצאת X בחזקת N
אתה יכול לבדוק את זה על דף טיוטה ,זה לא קשה.
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
מדעי המחשב
