מבוא לתכנות ולמדעי המחשב בשפת C/רקורסיה (פיבונאצ'י, האנוי)

מספרי פיבונאצ'י

סדרת מספרי פיבונאצ' היא סדרה שבה כל איבר שווה לסכום אלה שלפניו. האיבר במקום ה 0 מוגדר כ 0 והאיבר במקום ה - 1 מוגדר כ 1. הקוד הרקורסיבי הבא מחשב את המספר הפיבונאצ'י ה n-י:

#include <stdio.h> 

int fibonacci(int n) {
    if(n==0)
	return 0; 
    if(n==1)
	return 1; 
    return fibonacci(b, b+a, n-1); 
}


int main() {
    printf("fibonacci(10) = %d \n",fibonacci(10)); 
    return 0; 
}

פלט:

fibonacci(10) = 55

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

#include <stdio.h> 

int counts[100]; 

int fibonacci(int n) {
    ++ counts[n]; 
    if(n==0)
	return 0; 
    if(n==1)
	return 1; 
    return fibonacci(n-1)+fibonacci(n-2); 
}


int main() {
    int i; 
    for(i = 0; i<100; ++i)
	counts[i] = 0; 
    printf("fibonacci(30) = %d \n",fibonacci(30));
    for(i=0; i<=30; ++i)
	printf("%d, ",counts[i]); 
    printf("\n"); 
    return 0; 
}

פלט:

fibonacci(30) = 832040 
514229, 832040, 514229, 317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181,
 2584, 1597, 987, 610, 377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1,

הרבה יותר יעיל היה לכתוב את הפונקציה באמצעות לולאה פשוטה:

int fibonacci(int n) {
    int t1=0, t2=1,i; 
    if(n==0)
	return t1; 
    for(i=0; i<n-1; ++i) {
	int tmp = t2; 
	t2 = t1+t2;
	t1 = tmp;  
    }
    return t2; 
}

גם את הבעיה הקודמת, של חישוב עצרת, היה יעיל יותר, הן מבחינת מקום בזיכרון והן מבחינת זמן ריצה, לכתוב כלולאה:

int factorial(int n) {
    int i, ret = 1;
    for(i=2; i<=n; ++i)
	ret *= i; 
    return ret; 
}

הרקורסיה הקודמת המטפלת במספרי פיבונאצ'י אינה יעילה כאשר מעבירים אליה מספרים גדולים; לדוגמה מספר 500, התוכנית תצטרך לעבוד שעות ואפילו ימים על מנת להגיע לתוצאה.
מצורפת תוכנית אשר מטפלת באופן זריז ביותר במספרי פיבונאצ'י גם כאשר מדובר במספרים גדולים.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

double fibonacci(int n) {
    return (((1/sqrt(5))*(pow((1+sqrt(5))/2, n)) - ((1/sqrt(5))*(pow((1-sqrt(5))/2, n)))));
}
int main() {
    int n = 500;
    printf("fibonacci(%d) = %.0f", n, fibonacci(n));
    return 0;
}

פלט:

fibonacci(500) = 139423224561700228711116466856628305532793116368214754989670287848858933271320300167384646404854199091200

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

מגדלי האנוי

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

המצב התחילי כאשר יש ארבע טבעות

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

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

זמן ריצה

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

אבחנה: בכדי שאפשר יהיה להעביר את הטבעת הגדולה ביותר, כל שאר הטבעות חייבות להיות מסודרות על העמוד הנותר

האבחנה הראשונה שנעשה היא שבאיזה שלב הם חייבים להעביר את הטבעת הגדולה ביותר ממקומה במוט הראשון למוט השלישי. בשביל לעשות זאת כל הטבעות האחרות צריכות להיות מסודרות לפי הסדר על המוט השני. אפשר היה לחשוב אולי שכדאי להעביר את הטבעת הגדולה קודם למוט השני אבל קצת מחשבה נוספת מראה שזה סתם ביזבוז. בשביל להעביר 63 טבעות מהמוט הראשון למוט השני, היינו צריכים לפתור בעיה שקולה לבעיית מגדלי הנוי עם 63 טבעות (הרי זה לא באמת משנה לאיזה מוט אנו קוראים 1, לאיזה 2 ולאיזה 3) אחרי שיעבירו את הטבעת הגדולה למוט השלישי, תהיה להם בעיה נוספת של העברת 63 טבעות מהמוט השני למוט השלישי. הראינו שבשביל לפתור את הבעיה עם 64 טבעות, צריך (ואפשר!) לפתור שתי בעיות עם 63 טבעות ולהוסיף עוד העברה אחת (של הטבעת הגדולה).

לכן, אם נסמן את (H(n כמספר ההעברות לבעיית מגדלי האנוי עם n טבעות, אז מתקיים:

$H(n)=2\cdot H(n-1)+1$

משחק עם טבעת בודדת דורש העברה בודדת מ 1 ל 3 ולכן:

$H(1)=1$

ואז, אם נפעיל את השיקול הקודם, נקבל:

$H(2)=(2\cdot 1+1)$

ואם נפעיל שוב, נקבל:

$H(3)=2\cdot (2\cdot 1+1)+1$

ושוב:

$H(4)=2\cdot (2\cdot (2\cdot 1+1)+1)$

...

כך שהתבנית ברורה ואנחנו יכולים להבין איך נראית התבנית הכללית.

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

$H(n)=2^{n-1}+2^{n-2}+..+2+1={\frac {2^{n}-1}{2-1}}=2^{n}-1$

(המעבר השני התבסס על סכום של סידרה הנדסית)

נשערך בכמה פעולות מדובר, עבור הנזירים:

$H(64)=2^{64}-1=2^{4}\cdot {2^{10}}^{6}-1>16\cdot 1000^{6}=16,000,000,000,000,000,000$

הנחנו שכל פעולה לוקחת שניה. מספר השניות בשנה הוא:

$60\cdot 60\cdot 24\cdot 365=31536000$

לכן, מספר השנים שיקח לנזירים לסיים את המשימה הוא לא פחות מ:

${\frac {H(64)}{3.1536\cdot 10^{7}}}>{\frac {16\cdot 10^{18}}{3.1536\cdot 10^{7}}}={\frac {16}{3.1536}}\cdot 10^{11}>4\cdot 10^{11}=400\cdot 10^{9}$

כלומר יותר מ 400 מיליארד שנה.

בסופו של יום, נראה שלא נזכה..

מימוש

בזמן שניתחנו את זמן הריצה, מצאנו למעשה את האלגוריתם היעיל ביותר לפתור את הבעיה לכל מספר של טבעות:

• בשביל להעביר n טבעות ממגדל 1 למגדל 3:
  • מעבירים n-1 טבעות ממגדל 1 למגדל 2,
  • אז מעבירים את הטבעת הגדולה מעמוד 1 לעמוד 3
  • ואז מעבירים n-1 טבעות מעמוד 2 לעמוד 3.

נתחיל לממש:

#include <stdio.h> 

int main() {
    int n; 
    printf("How many rings? ");
    scanf("%d",&n); 
    hanoi(n); 
    return 0; 
}

וכעת נכתוב את הפונקציה העיקרית

void hanoi(int n) {
     if(n == 1)
	 printf("Move from 1 to 3"); 
     hanoi(n-1); 
     ...
}

קצת נתקענו.. רצינו לממש את האלגוריתם בצורה רקורסיבית, לחלק את הבעיה המקורית לבעיות משנה ואז לצרף את פיתרונן על מנת לפתור את הבעיה המקורית. הבעיה שבאופן בו hanoi כתובה קשה לממש את האלגוריתם שכתבתנו. אנחנו רוצים להגיד שאנחנו מעבירים n-1 טבעות מעמוד מסויים לעמוד מסויים. הממשק של הפונקציה כרגע מאפשר לנו רק להגיד מה מספר הטבעות שאנחנו מעבירים. כל זה מוביל אותנו לצורך להרחיב את ממשק הפונקציה. אבל הממשק הנוכחי נקבע ע"י הצורך שעלה ב main.

מה עושים?

אפשר להינות משני העולמות: משאירים את הפונקציה המקורית בשביל הממשק ל - main ומוסיפים פונקציה עם ממשק יותר רחב בשביל לממש את האלגורים עצמו:

#include <stdio.h> 
 
void hanoi_towers(int n, int from, int by, int to) {
    if(n<1)
	return; 
    hanoi_towers(n-1,from,to,by);
    printf("Move ring from %d to %d\n", from, to); 
    hanoi_towers(n-1,by,from,to); 
}
 

void hanoi(int n) {
  hanoi_towers(n,1,2,3); 
}


int main() {
    int n; 
    printf("How many rings? ");
    scanf("%d",&n); 
    hanoi(n); 
    return 0; 
}

(שימו לב שבסוף החלטנו לתת תנאי עצירה ב 0 טבעות, שם אין צורך לעשות דבר)

פלט:

How many rings? 4
Move ring from 1 to 2
Move ring from 1 to 3
Move ring from 2 to 3
Move ring from 1 to 2
Move ring from 3 to 1
Move ring from 3 to 2
Move ring from 1 to 2
Move ring from 1 to 3
Move ring from 2 to 3
Move ring from 2 to 1
Move ring from 3 to 1
Move ring from 2 to 3
Move ring from 1 to 2
Move ring from 1 to 3
Move ring from 2 to 3

• 
  מצב התחלתי
• 
  Move ring from 1 to 2
• 
  Move ring from 1 to 3
• 
  Move ring from 2 to 3
• 
  4
• 
  5
• 
  6
• 
  7
• 
  8
• 
  9
• 
  10
• 
  11
• 
  12
• 
  13
• 
  14
• 
  1- 4^2 = 15

נחזור רגע אל הנזירים בהר הבודד וננסה לעזור להם:

How many rings? 64
Move ring from 1 to 2
Move ring from 1 to 3
Move ring from 2 to 3
Move ring from 1 to 2
Move ring from 3 to 1
Move ring from 3 to 2
Move ring from 1 to 2
Move ring from 1 to 3
Move ring from 2 to 3
Move ring from 2 to 1
Move ring from 3 to 1
Move ring from 2 to 3
Move ring from 1 to 2
Move ring from 1 to 3
Move ring from 2 to 3

...

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

אפשר להפנות את הפלט לקובץ:

hanoi > out.txt

גם אם המחשב מהיר פי מילארד מהנזירים, זה יסתיים עוד יותר מ - 400 שנה. מה לגבי כמות הזיכרון? האם גם זו בעיה?