(C++)

אז ככה, יש לי מערך (לדוגמא מערך בגודל 5 שמכיל [1,0,1,1,1]) הפונקציה הרקורסיבית צריכה להחזיר את המספר השלם המתאים (במקרה זה 23)

הפונקציה בנוייה כך:

int BinArr2Int (int arr[], int length)

0

בניתי את הפונקציה בלי רקוסיה וזה לקח חצי דקה, אבל ברגע שאני מתחיל לחשוב רקוסיבית אני נתקע.

השאלה שלי היא איך בונים את הפונקציה הזאת ???

בצורה לא רקוסיבית זה נראה כך:

int BinArr2IntN (int arr[], int length)

{

int i;

int temp = 0;

int powr = 1;

int num= 0;

for (i = length-1; i>=0; i--)

{

temp = arr * (powr);

powr *= 2;

num+=temp;

}

return num;

}

כיוון אחד של arr - מהספרה הגבוה לנמוכה.

[left]int BinArr2IntN (int arr[], int length)
{
if(length==0) return 0;
return arr[length-1] +2 * BinArr2IntN (arr,length-1);
}[/left]

כיוון שני

int BinArr2IntN (int arr[], int length)
{
   if(length==0) return 0;
   return arr[0] +2 * BinArr2IntN (arr+1,length-1);
}

אפשר בבקשה הסבר קצרצר על דרך החשיבה, איך ניגשים לבעיה כזאת?

פתרת את זה פשוט בשנייה...

איזה עצבים שאי אפשר ליישר את זה כמו שצריך בעעעעעע

בכל מקרה איזה מתאים לך? הראשון או השני? (אין לי כוח לקרוא את הדוגמא)

טוב הראשון כנראה מתאים לך

תנאי העצירה ממש פשוט וברור - אם האורך הוא 0 מן הסתם המספר שמתאים לו הוא 0

עכשיו נשאר לך לעשות את תנאי הרקורסיה

בהנתן מספר בינארי 11010 נסמן את הערך העשרוני שלו ב-dec(11010 עכשיו מתכונות של מספר עשרוני מתקיים

dec(11010) = 0 + 2*dec(1101)

נמשיך ברקורסיה ונקבל

dec(11010) = 0 + 2 * (1 + 2*dec(110)) = 0 + 2 * (1 + 2 * (0 + 2 * (1 + 2 * (0 + dec()))))

dec() זה בעצם תנאי העצירה

עכשיו נשאר רק לממש את זה

בכל שלב אתה לוקח את ספרת האחדות של המספר העשורי שנמצא במקום האחרון במארך

arr[length-1]

ומוסיף אותו ל-2 כפול המארך בלי האיבר היחידות כלומר נשאר לך רק להקטין את האורך ב-1 ולהעביר את תחילת המארך

הדרך הראשונה

תודה, ואללה אתה מסביר יותר טוב מהמרצה שלי