מבוא לתכנות ולמדעי המחשב בשפת C/תרגיל 4

לדף הקורס

תרגיל 4 -רקורסיה

q1 - סידרה פשוטה

נתונה סידרה המוגדרת לפי כלל הנסיגה הבא:

<m> a_1 = 1 </m>

<m> a_n = 3 \cdot a_{n-1} + 1 </m>

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

<m> 1,4,13,40,.. </m>

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

הפונקציה הראשונה תעשה זאת בצורה רקורסיבית, כאשר היא עוקבת אחרי ההגדרה של הסידרה. הסיבוכיות שלה תהיה לינארית, כלומר: <m> O(n) </m> . כאשר n הוא האינדקס של האיבר.

הפונקציה השנייה תחשב את אותה תוצאה ע"י שימוש בלולאה פשוטה והסיבוכיות שלה תהיה גם היא לינארית (אם כי יעילה יותר)

הפונקציה השלישית תחשב את הערך ע"י שימוש בנוסחה מפורשת. הסיבוכיות שלה תהיה: <m> O(1) </m>

כלומר זמן החישוב לא היה תלוי בגודל של n.

התוכנית תכתב בקובץ q1.c בעל פונקציית ה main הבאה:

int main() {
  int i,min=1,max=15; 

  while(1) {
    printf("Index: "); 
    scanf("%d",&i); 
    if(i>=min && i<=max)
      break; 
    printf("Index must in [%d..%d], please try again.\n",min,max); 
  }

  printf("aRec(%d) = %d\n",i,aRec(i));  
  printf("aLoop(%d) = %d\n",i,aLoop(i));  
  printf("aFormula(%d) = %d\n",i,aFormula(i));  
  return 0; 
}

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

• aRec - הגרסה הרקורסיבית
• aLoop - גרסת הלולאה
• aFormula - גרסת הנוסחא המפורשת

קובץ הריצה הזה מדגים את ההתנהגות שמצופה מהתוכנית שלכם.

q2 - מגדלי האנוי עם אילוץ נוסף

בשאלה זו תתבקשו לכתוב גירסה חדשה של מגדלי האנוי. בגרסה זו, שמות העמודים הם B, A ו - C. בהתחלה, כל הטבעות נמצאות על עמוד A והמטרה להעביר את כולם לעמוד C.

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

את הקוד של שאלה זו יש להגיש בקובץ q2.c.

q3 - תמורות

בשאלה זו אתם מתבקשים לכתוב תוכנית המדפיסה את כל התמורות (פרמוטציות) של המספרים: <m>1,2,..,n</m>. התמורות הן כל הסידורים האפשריים של האלמנטים. לדוגמה, כאשר n שווה ל 3, התמורות תהיינה:

1, 2, 3, 
1, 3, 2, 
2, 1, 3, 
2, 3, 1, 
3, 2, 1, 
3, 1, 2,

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

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

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

יש לכתוב את הקוד של שאלה זו בקובץ q3.c

q4 - בונוס: חידת מסע הפרש (20 נק')

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

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

האנימציה הבאה מדגימה מסלול כזה:

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

+----+----+----+----+----+
|  1 | 14 | 19 |  8 | 25 |
+----+----+----+----+----+
|  6 |  9 |  2 | 13 | 18 |
+----+----+----+----+----+
| 15 | 20 |  7 | 24 |  3 |
+----+----+----+----+----+
| 10 |  5 | 22 | 17 | 12 |
+----+----+----+----+----+
| 21 | 16 | 11 |  4 | 23 |
+----+----+----+----+----+

מסלול זה מתחיל מהנקודה השמאלית-עליונה ומסתיים בנקודה הימנית-עליונה.

בתחילת התוכנית מתבקש המשתמש להכניס את גודל הלוח (נסו להתחיל מ 5 או 6) ואז היא מדפיסה את כל הפתרונות האפשריים.

קובץ הריצה הזה מדגים איך התוכנית אמורה להתנהג.

את שאלת הבונוס יש להגיש כקובץ בשם q4.c.

הגשה

מועד הגשה: יום חמישי ה - 8.12.11, עד סוף היום.

יש להגיש ב"תרגיל רביעי" במודל, קובץ ex4.tgz המכיל את q1.c, q2.c, q3.c, ואת q4.c אם בחרתם לממש אותו. אל תשכחו לבדוק את ex4.tgz לפני ההגשה ולוודא שהוא מכיל את כל מה שהוא אמור להכיל.

איכות הקוד: כרגיל - תיעוד, עימוד ושמות משמעותיים לפונקציות.

בהצלחה!

פתרון

q1.c

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

int aRec(int i) {
  if(i==1)
    return 1; 
  return aRec(i-1)*3+1; 
}

int aLoop(int i) {
  int j; 
  int ret = 1; 
  for(j=1; j<i; ++j)
    ret = 3*ret+1; 
  return ret; 
}  

int aFormula(int i) {
  return (int) (pow(3,i)-1)/2; 
}

int main() {
  int i,min=1,max=15; 

  while(1) {
    printf("Index: "); 
    scanf("%d",&i); 
    if(i>=min && i<=max)
      break; 
    printf("Index must in [%d..%d], please try again.\n",min,max); 
  }

  printf("aRec(%d) = %d\n",i,aRec(i));  
  printf("aLoop(%d) = %d\n",i,aLoop(i));  
  printf("aFormula(%d) = %d\n",i,aFormula(i));  
  return 0; 
}

q2.c

#include <stdio.h> 

void hanoi(int n, char from, char by, char to) {
    if(n < 1)
	return; 
    hanoi(n-1,from,by,to);
    printf("Move from %c to %c\n",from,by);
    hanoi(n-1,to,by,from);
    printf("Move from %c to %c\n",by,to);
    hanoi(n-1,from,by,to);
}


void hanoiMain(int n) {
    hanoi(n,'A','B','C'); 
}

int getN() {
    int n; 
    while(1) {
	printf("Please enter number of rings: "); 
	scanf("%d",&n); 
	if(n>0 && n <=10)
	    return n; 
	printf("%d is out of range, please try again.\n",n); 
    }
}

int main() {

    int n = getN(); 
    hanoiMain(n); 

    return 0; 
}

q3.c

#include <stdio.h>

int n;
int max = 100; 
int array[100];
int count; 

void init() {
  int i; 
  for(i=0; i<n; ++i)
    array[i] = i+1; 
}

void printArray() {
  int i; 
  for(i=0; i<n; ++i)
    printf("%d, ",array[i]); 
  printf("\n"); 
}

void swap(int i, int j) {
  int tmp = array[i]; 
  array[i] = array[j]; 
  array[j] = tmp; 

}

void permutations(int i) {
  // function should leave the array exactly as it recieved it. 

  if(i == n-1) {
    ++count;
    printArray(); 
    return; 
  }
  int j; 
  for(j=i; j<n; ++j) {
    swap(i,j); 
    permutations(i+1); 
    swap(i,j); 
  }
} 

void permutationsMain() {
  count = 0; 
  permutations(0); 
  printf("\nTotal number of permutations: %d\n\n",count); 
}

void getN() {
  while(1) {
    printf("n: "); 
    scanf("%d",&n); 
    if(n >= 1 || n < max)
      return;
    printf("n should be in [1..%d]\n",max-1); 
  }
}

int main() {
  getN(); 
  init();
  permutationsMain(); 
  return 0; 
}

q4.c

#include <stdio.h> 

int board[8][8]; 
int counts[8][8]; 
int count = 0; 

int gi,gj; 

int moves[][2] = {{1,2},{-1,2},{1,-2},{-1,-2},
		  {2,1},{-2,1},{2,-1},{-2,-1}}; 

void initBoard(int size) {
  int i,j; 
  for(i=0; i<size; ++i) 
    for(j=0; j<size; ++j) {
      board[i][j] = 0; 
      counts[i][j] = 0; 
    }
}

void drawLine(int n,int size) {
  int j,k; 
  for(j=0; j<size; ++j) {
    printf("+-");
    for(k=0; k<n; ++k)
      printf("-");
  }
  printf("+\n"); 
}

void printBoard(int size) {
  int i,j; 
  printf("\n\nSolution %d:\n\n",count);
  drawLine(3,size); 
  for(i=0; i<size; ++i) { 
    for(j=0; j<size; ++j)
      printf("| %2d ",board[i][j]);
    printf("|\n");
    drawLine(3,size); 
  }
}

void printCounts(int size) {
  int i,j; 
  printf("\n\nCounts:\n\n");
  drawLine(5,size); 
  for(i=0; i<size; ++i) { 
    for(j=0; j<size; ++j)
      printf("| %4d ",counts[i][j]);
    printf("|\n");
    drawLine(5,size); 
  }
}

void knight(int n, int i, int j, int size) {
  if(i < 0 || i>= size || j < 0 || j >= size|| board[i][j] != 0)
    return;

  board[i][j] = n; 

  if(n == size*size) {
    ++count; 
    ++ counts[gi][gj]; 
    printBoard(size); 
    board[i][j] = 0; 
    return; 
  }
 
  int k; 
  for(k=0; k<8; ++k) {
    int i1 = i+moves[k][0];
    int j1 = j+moves[k][1]; 
    knight(n+1,i1,j1,size); 
  }
 
  board[i][j] = 0; 

}
 
void solveKnight(int size) {
  initBoard(size); 
  for(gi=0; gi<size; ++gi)  
    for(gj=0; gj<size; ++gj)
      knight(1,gi,gj,size);

  //  printCounts(size); 
}

int main() {
  int size; 
  int min = 3, max = 8; 
  while(1) {
    printf("Size: ");
    scanf("%d",&size);
    if(size<min || size > max) 
      printf("Valid range: %d..%d\n",min,max); 
    else
      break; 
  }

  solveKnight(size); 
  return 0; 
}

לדף הקורס