Notes on some of the tutorial questions.
/* PRE: N >= 1 */ biggest = A[0]; for(i=1; i < N; i++) /* INVARIANT: biggest is largest value in A[0..i-1] */ if(A[i] > biggest) biggest = A[i]; /* POST: biggest is largest value in A[0..i-1] and i=N, so biggest is largest value in A[], as required. */Termination: i increases, must reach N, program then halts.
search( Tree T; Int Lo, Hi ) // PRE: T is a binary search tree if T is not empty then e := T.element; if e > Hi then search( T.left, Lo, Hi ) // don't waste time on right else if e < Lo then search( T.right, Lo, Hi ) // don't waste time on left else // e is between Lo and Hi inclusive search( T.left, Lo, Hi ); print e; search( T.right, Lo, Hi ) end_if end_if
These questions were for general discussion.
#include <stdio.h> #include <stdlib.h> /* C by Tony Jansen, April 2001 */ void pb(int open, int closed, int index, char *s) /* PRE: open >= closed >= 0 */ { if (open + closed == 0) { /* none left to do, so done */ printf("%s\n", s); return; } if (open == closed) { /* only option is to add ( */ s[index] = '('; pb(open-1, closed, index+1, s); } else if (open == 0) { /* only option is to add ) */ s[index] = ')'; pb(open, closed-1, index+1, s); } else { /* assert: open > closed > 0 */ s[index] = '('; /* try both ... */ pb(open-1, closed, index+1, s); /* ( ... and */ s[index] = ')'; pb(open, closed-1, index+1, s); /* ) ... */ } } int main(int argc, char *argv[]) { int num; char *s; if (argc != 2) { printf("Usage: program num_pairs_brackets\n"); exit(0); } num = atoi(argv[1]); s = (char *) malloc (sizeof(char) * (2 * num + 1)); s[2 * num] = '\0'; pb(num, num, 0, s); return 0; }