1 (???) (15 points)
a. Show a NEAT drawing of the resulting list when F(list) is executed and explain briefly what the function F does.

list

Node* & F(Node* &  list){
	if (list)   
		if (list->next){
			Node* p1 = list;
			Node* p2 = list->next;
			list = F(list->next);
			p2->next = p1;
			p1->next = NULL;
	}
	return list;  
}

b. Show the output generated by a call to G(5);

void G(int N){
	if (N > 0){
		cout << "starting G  " << N << endl;
		G(N-1);
		cout << "ending   G  "<< N << endl;
	}
}

starting G  5
starting G  4
starting G  3
starting G  2
starting G  1
ending   G  1
ending   G  2
ending   G  3
ending   G  4
ending   G  5

void H(int N){
	if (N > 0){  
		cout << "starting H  " << N << endl;
		H(N-1);
		cout << "middle   H  " << N << endl;
		H(N-1);
		cout << "ending   H  " << N << endl;
	}
}

H(1)	H(2)	H(3)
starting H 1 middle H 1 ending H 1	starting H 2 starting H 1 middle H 1 ending H 1 middle H 2 starting H 1 middle H 1 ending H 1 ending H 2	starting H 3 starting H 2 starting H 1 middle H 1 ending H 1 middle H 2 starting H 1 middle H 1 ending H 1 ending H 2 middle H 3 starting H 2 starting H 1 middle H 1 ending H 1 middle H 2 starting H 1 middle H 1 ending H 1 ending H 2 ending H 3

d. Show the output generated by the statement:

     cout << "J(2,2):  " << J(2,2) << endl;

int J(int N, int K){
// count is initialized at 1 and incremented by 1 in each call
	static int count = 1;
	cout << setw(8) << count++ << setw(8) << N << setw(8) << K << endl;
	if (N == 0) return 1;
	if (K == 0) return 1;
	return (J(N, K-1) + J(N-1, K));
}

1       2       2      
2       1       2       
3       0       2       
4       1       1       
5       0       1       
6       1       0      
7       2       1      
8       1       1       
9       0       1       
10      1       0      
11      2       0       
J(2,2):  6

void Squares(int x, int y, int size){
	int half = size / 2;
	int quarter = size / 4;
	if (size > 10){ 
		FrameRect(x - half, y - half, x + half, y + half);
		Squares(x - quarter, y - quarter, half);
		Squares(x + quarter, y + quarter, half);
	}
}

bool pal(char* s, int length){ // length is length of s
	if (length <= 1) return true;
	if (s[0] == s[length-1]) return pal(s+1, length -2);
	return false;
}

// Sample calls
char* s = "madamimadam";
char* t = "madamimeve";

cout << pal(s, strlen(s)) << endl;
cout << pal(t, strlen(t)) << endl;

int nottwoones(int n){
	if (n == 1) return 2; // 0  or  1
	if (n == 2) return 3; // 00, 01, or 10
	// count good strings of length n that start with 0 = nottwoones(n-1)
	// count good strings of length n that start with 1 = nottwoones(n-2)
	return nottwoones(n-1) + nottwoones(n-2);
}

Last Updated: April 22, 1997 8:14 pm by