חישוב חזקה בריקורסיה... ?! (שפת C )

  • פותח הנושא nvh
  • פורסם בתאריך

nvh

New member
חישוב חזקה בריקורסיה... ?! (שפת C )

נתבקשתי לבנות פונקציה המקבלת שני מספרים שלמים (INT) ומחזירה את המספר הראשון בחזקת השני.. (עם שימוש בריקורסיה) ניסיתי משהו, אבל הוא לא טוב.. התוכלו לעזור לי? זה דיי דחוף. תודה.
 

nvh

New member
אופס.. נראה לי שהבנתי

זה טוב?
int f(int n, int m) { if(m==0) return 1; else return f(n,m-1)*n; }​
פשוט שכחתי איך לאפס את n כי שכחתי את הצורה שבה ריקרסיה בעצם עובדת... (אני דיי חדש בזה..)
 
נשמע 100%...../images/Emo26.gif

רק שימי-לב שאמרת "שני מספרים שלמים" וכאן זה לא לגמרי מדוייק: (מה קורה אם m קטן מאפס?... לא יעבוד
) ומה קורה אם גם m וגם n שווים לאפס?... (אפס בחזקת אפס עפ"ר לא מוגדר)
 

finduilas

New member
0 בחזקת 0

בcalc של ווינדוס נותן 1, וכך גם תתן הפונקציה מלמעלה. זה לא נראה לי בעייתי. מספרים שליליים זו אכן בעיה, לפי מיטב זכרוני מספר שלילי זה בעצם 1 חלקי המספר בחזקה חיובית, אז אפשר לכתוב בדיקה אם M שלילי, ואז מכפילים אותו ב -1 ובסוף מחלקים את 1 בתוצאה.
 
בעייתי... בעייתי...../images/Emo26.gif

לדעתי זה לא מוגדר. אפשר גם אינטואיטיבית לראות שזה מריח לא טוב: כל מספר בחזקת 0 שווה ל-1 - לכן 0 בחזקת 0 שווה ל-1. 0 בחזקת כל מספר שווה ל-0 - לכן 0 בחזקת 0 שווה ל-0.
 

voguemaster

New member
לא מוגדר, זה אינפי בסיסי

אבל לא חושב שמיקרוסופט יודעים אינפי
 

nvh

New member
דבר ראשון, אני בן. דבר שני...

אני לא ממש בטוח אם מצפים ממני לעבוד כרגע עם מספרים שליליים.. היו לי (בבית הספר. כתה י'ב) רק שנים או 3 שיעורים על הנושא. אבל אני אנסה אח'כ. אני מתחיל לחבב ריקורסיות(בערך P: ) תודה רבה על העזרה.
 
הנה משהו יותר נחמד ../images/Emo3.gif

int power(int x, int y) { if(y == 0) { return 1; } else if( y == 1 ) { return x; } else { return power(x,y/2) * power(x,y - y/2); } }​
אמור לעשות את העבודה, אבל להיות קצת יותר זריז
 

the another one

New member
הנה משהו הרבה יותר נחמד ../images/Emo3.gif

#include <math.h> int power(int x, int y) { return pow(x,y); }​
 
למה זה יותר זריז?

אם אני סופר כמה פעמים קוראים לפונקציה, אז זה נראה לי לא פחות: למשל, אם תבקש לחשב 2 בחזקת 8, אז תאלץ לחשב פעם אחד 2 בחזקת 8 ועוד פעמיים 2 בחזקת 4 ועוד ארבע פעמים 2 בחזקת 4 ועוד שמונה פעמים 2 בחזקת 1. זאת אומרת, 15 פעמים להיכנס לפונקציה. במקור זה היה דורש רק 8 כניסות לפונקציה, לא?
 

ahab

New member
זה לא יותר זריז..

הרעיון עצמו היה נכון (לקחת כל פעם y/2, על מנת להגיע לסיבוכיות לוגריתמית ב-y). אבל היתרון הזה מתפספס במימוש שהוצע. אפשר בקלות לתקן את זה ע"י :
t=power(x,y/2); return t*t*((y%2)?x:1);​
(כמובן, בתוספת תנאי עצירה מתאימים...)
 
למעלה