/*********************************************************************************/ /* */ /* C Programs from Chapter 5 of */ /* Data Structures, Algorithms and Software Principles in C */ /* by Thomas A. Standish */ /* */ /* Copyright (C) 1995, Addison-Wesley, Inc., all rights reserved */ /* */ /*********************************************************************************/ /*********************************************************************************/ | void FindWinningAmount(void) | { | | (Get six input amounts from user) 5 | | (Make a Table of amounts and repetitions) | | (Print largest amount repeated three or more times) | | } Program Strategy 5.4 Top-Level Goals for Finding Winning Amount /*********************************************************************************/ | typedef int InputArray[6]; | | InputArray A; | 5 | void GetSixInputs(InputArray A) /* Get six dollar amounts */ | { /* and put them in array A */ | | int i; | 10 | printf("Give six dollar amounts separated by spaces:"); | | for (i = 0; i < 6; ++i) { | | scanf("%d",&A[i]); /* read in six dollar amounts */ 15 | | } | | } Program 5.5 Getting Six Inputs from the User /*********************************************************************************/ | void MakeTable(InputArray A) /* Create a Table of amounts */ | { /* and their repetitions */ | int i; | 5 | (Initialize the Table to be empty) | | (Insert each of the six amounts into the Table) | for (i = 0; i < 6; ++i) { | 10 | (Insert the amount A[i] into the Table) | InsertAmount(A[i]); | | } | } Program Strategy 5.6 For Making the Table /*********************************************************************************/ | void InsertAmount(int AmountToInsert) /* Insert an amount */ | { /* in the Table */ | | (If one of the rows in the Table already contains the amount to insert,) 5 | (increase the number of repetitions in the row and exit the procedure) | | for (each row in the Table) { | if ( (the row's amount) == AmountToInsert ) { | (increase the row's repetition count by one) 10 | (and return from the function) | } | } | | (If no row's amount matched the amount to insert, then add a new row to) 15 | (the table containing the amount to insert and a repetition count of one) | | } Program Strategy 5.7 Inserting an Amount in the Table /*********************************************************************************/ | void FindAndPrintWinner(void) /* Search the Table for a row having the */ | { /* largest amount repeated three */ | int AmountWon; /* or more times and print it */ | 5 | (Initially establish the AmountWon to be zero.) | (It will remain 0 unless a higher amount is discovered during the search.) | | (Search the Table to find the largest amount won among the rows) | (having three or more repetitions) 10 | | for (each row in the Table) { | if ( (the row's number of repetitions >= 3) && | (the row's amount > AmountWon) ) { | AmountWon = (the row's amount); 15 | } | } | | (Print AmountWon) | | } Program Strategy 5.8 Printing Largest Amount Repeated Three or More Times /*********************************************************************************/ | void MakeTable(InputArray A) /* Create a Table of amounts */ | { /* and their repetitions */ | int i; | 5 | /* To initialize the Table to be empty, we initialize */ | /* a pointer to the last row used in the Table */ | | LastRowUsed = -1; | 10 | /* Insert each of the six amounts into the Table */ | | for (i = 0; i < 6; ++i) { | InsertAmount(A[i]); /* Insert the amount A[i] into the Table */ | } | } Program 5.9 Making the Table /*********************************************************************************/ | void InsertAmount(int AmountToInsert) /* Insert an amount */ | { /* in the Table */ | | int row; 5 | | /* If one of the rows in the Table already contains */ | /* the amount to insert, then increase the number of */ | /* repetitions in that row, and return from the function. */ | 10 | for (row = 0; row <= LastRowUsed; ++row) { | | if (Table[row].Amount == AmountToInsert) { | | Table[row].Repetitions++; /* increase repetition count */ 15 | | return; /* and return immediately afterwards */ | } | | } 20 | | | /* If no row's amount matched amount to insert, */ | /* then add a new row to the table containing the */ | /* amount to insert and having a repetition count */ 25 | /* of one */ | | LastRowUsed++; | | Table[LastRowUsed].Amount = AmountToInsert; 30 | | Table[LastRowUsed].Repetitions = 1; | | } Program 5.10 Inserting an Amount in the Table /*********************************************************************************/ | void FindAndPrintWinner(void) /* Search the Table for a row having the */ | { /* largest amount repreated three */ | int row, AmountWon; /* or more times and print it */ | 5 | /* Initially establish the AmountWon to be zero. */ | /* It will remain 0 unless a higher amount is */ | /* discovered during the search. */ | AmountWon = 0; | 10 | /* Search the Table to find the largest amount won among the rows */ | /* having three or more repetitions */ | | for (row = 0; row <= LastRowUsed; ++row) { | if ( (Table[row].Repetitions >= 3) && 15 | (Table[row].Amount > AmountWon) ) { | AmountWon = Table[row].Amount; | } | } | 20 | /* Print the amount won */ | printf("You won $ %d\n",AmountWon); | } Program 5.11 Printing Largest Amount Repeated Three or More Times /*********************************************************************************/ | void FindWinningAmount(void) | { | GetSixInputs(A); /* Get six input amounts from user */ | MakeTable(A); /* Make a Table of amounts and repetitions */ 5 | FindAndPrintWinner(); /* Print the largest amount repeated */ | } /* three or more times */ Program 5.12 Program for Finding Winning Amount /*********************************************************************************/ | /* A Program for Finding a Lottery Winner */ | | typedef int InputArray[6]; | 5 | typedef struct { | int Amount; | int Repetitions; | } RowStruct; | 10 | InputArray A; | RowStruct Table[6]; | int LastRowUsed; | | /* Here, insert the definitions of the functions: */ 15 | /* GetSixInputs -- from Program 5.5 */ | /* InsertAmount -- from Program 5.10 */ | /* MakeTable -- from Program 5.9 */ | /* FindAndPrintWinner -- from Program 5.11 */ | /* FindWinningAmount -- from Program 5.12 */ 20 | | int main (void) | { | | FindWinningAmount(); /* Get inputs and print winning amount */ 25 | | } Program 5.13 Entire Program for Finding a Lottery Winner /*********************************************************************************/ | void FindWinningAmount2(void) | { | | (Get six input amounts from user) 5 | | (Sort the amounts into descending order) | | (Search for three in a row and print it) | | } Program Strategy 5.14 Top-Level Goals for Finding Winning Amount /*********************************************************************************/ | void FindAndPrintWinner2(void) | { | int AmountWon; /* the winning amount, if any */ | int i; /* i is an index for the array A */ 5 | | /* Initially establish the AmountWon to be zero, */ | | AmountWon = 0; | 10 | | /* For each possible starting position i == 0,1,2, and 3 where a run of */ | /* three identical values could start in the sorted InputArray, A, check */ | /* to see if a run of three identical values exists, and exit if it does. */ | 15 | for (i = 0; i < 4; ++i ) { | | if ( (A[i] == A[i+1]) && (A[i+1] == A[i+2]) ) { | | AmountWon = A[i]; /* a winning amount A[i] was found */ 20 | | break; /* break to exit the for loop */ | | } | } 25 | | /* Print the amount won */ | printf("You won $ %d\n",AmountWon); | | } Program 5.15 Finding the Largest Amount Repeated Three Times /*********************************************************************************/ | void FindWinningAmount2(void) | { | | GetSixInputs(A); /* Get six input amounts from user */ 5 | | SelectionSort(A,0,5); /* Sort the amounts into descending order */ | | FindAndPrintWinner2(); /* Search for three in a row and print it */ | | } Program 5.16 Top-Level Program for Finding Winning Amount /*********************************************************************************/ | /* A Program for Finding a Lottery Winner */ | | typedef int InputArray[6]; | 5 | InputArray A; | | /* Here, insert the definitions of the functions: */ | /* GetSixInputs -- from Program 5.5 */ | /* FindMax -- from Program 5.20, below */ 10 | /* SelectionSort -- from Program 5.19, below */ | /* FindAndPrintWinner2 -- from Program 5.15 */ | /* FindWinningAmount2 -- from Program 5.16 */ | | int main(void) 15 | { | FindWinningAmount2(); /* Get inputs and print winning amount */ | } Program 5.17 Second Program for Finding a Lottery Winner /*********************************************************************************/ | void SelectionSort(SortingArray A, int m, int n) | { | | 5 | if (there is more than one number to sort) { | | (Let MaxPosition be the index of the largest element in A[m:n] ) | | (Exchange A[m] <--> A[MaxPosition] ) 10 | | (SelectionSort the subarray A[m+1:n] ) | | } | | } Program Strategy 5.18 Selection Sorting /*********************************************************************************/ | void SelectionSort(InputArray A, int m, int n) | { | int MaxPosition; /* MaxPosition is the index of A's biggest item */ | int temp; /* temp is used to exchange items in A */ 5 | | | if (m < n) { /* if there is more than one number to sort */ | | /* Let MaxPosition be the index of the largest number in A[m:n] */ 10 | MaxPosition = FindMax(A,m,n); | | /* Exchange A[m] <--> A[MaxPosition] */ | temp = A[m]; | A[m] = A[MaxPosition]; 15 | A[MaxPosition] = temp; | | /* SelectionSort the subarray A[m+1:n] */ | SelectionSort(A, m+1, n); | 20 | } | | } Program 5.19 Selection Sorting /*********************************************************************************/ | int FindMax(InputArray A, int m, int n) /* assume m A[j]) { /* if A[i] > largest previous A[j] then */ 10 | j = i; /* save the position, i, of the largest in j */ | } | } while (i != n); /* stop when all i in m:n have been tested */ | | return j; /* return j == position of the largest */ | } /* number A[j] in A[m:n] */ Program 5.20 Finding the Position of the Largest Number /*********************************************************************************/ | int FindMax(InputArray A, int m, int n) | { | | /* Precondition: m < n */ 5 | /* Postcondition: returns position of largest item in subarray A[m:n] */ | | int i; | int j; | 10 | i = m; | j = m; | | {# ( i == m) and (j == m) and (m < n) #} | 15 | do { | | i++ ; | | if ( A[i] > A[j] ) j = i; 20 | | {# Loop Invariant: A[j] >= A[m:i] and (i <= n) #} | | } while (i != n); | 25 | {# Final Assertion: A[j] >= A[m:n] #} | | return j; /* return j as position of largest item in A[m:n] */ | | } Program 5.21 Finding the Position of the Largest Item /*********************************************************************************/ | void SelectionSort(InputArray A, int m, int n) | { | | /* Precondition: m <= n */ 5 | /* Postcondition: A[m:n] is sorted such that: A[m] >= A[m+1] >= ... >= A[n] */ | | int MaxPosition; | int temp; | 10 | if (m < n) { /* if there is more than one item to sort */ | | MaxPosition = FindMax(A,m,n); | | {# A[MaxPosition] >= A[m:n] #} 15 | | /* exchange A[m] <--> A[MaxPosition] */ | temp = A[m]; A[m] = A[MaxPosition]; A[MaxPosition] = temp; | | {# A[m] >= A[m:n] #} 20 | | SelectionSort(A, m+1, n); {# yields: A[m+1] >= A[m+2] >= ... >= A[n] #} | | {# A[m] >= A[m+1] >= ... >= A[n] #} | 25 | } | | {# Final Assertion: A[m] >= A[m+1] >= ... >= A[n] #} | | } Program 5.22 Selection Sorting /*********************************************************************************/ | void ImpishSelectionSort(InputArray A, int m, int n) | { | | /* Precondition: m <= n */ 5 | /* Postcondition: A[m:n] is sorted such that: A[m] >= A[m+1] >= ... >= A[n] */ | | int i; | | for (i = m; i <= n; ++i) { 10 | A[i] = A[m]; | } | {# Final Assertion: A[m] >= A[m+1] >= ... >= A[n] #} | | } Program 5.23 Impish Selection Sorting /*********************************************************************************/ if ( (i <= n) && (i != n) ) { /* original if-statement */ y = x*x*x + 3*x*x + 5*x + 2; } || /* the down arrow means "transforms to" */ \/ if (i < n) { /* first, replace condition in if-statement, */ y = x*x*x + 3*x*x + 5*x + 2; /* using results from Table 5.27 */ } || \/ if (i < n) { /* second, replace the polynomial on the */ y = ((x + 3)*x + 5)*x + 2; /* right side of the assignment */ } Program Transformation 5.28 Improving Expressions in an If-Statement /*********************************************************************************/ | void SelectionSort(InputArray A, int m, int n) | { | int MaxPosition, temp; | | if ( m < n ) { 5 | MaxPosition = FindMax(A,m,n); | temp = A[m]; A[m] = A[MaxPosition]; A[MaxPosition] = temp; | SelectionSort(A, m+1, n); | } | } Program 5.29 Recursive Selection Sorting Without Comments /*********************************************************************************/ | void P(a,b,c) | { | if (condition C1) { | (statements S1) 5 | P(e1, e2, e3); /* this line contains the tail recursion */ | } | } || \/ | void P(a,b,c) | { | while (condition C1) { | (statements S1) 5 | a = e1; b = e2; c = e3; | } | } Program Transformation 5.30 Tail-Recursion Elimination /*********************************************************************************/ | void SelectionSort(InputArray A, int m, int n) | { | int MaxPosition, temp; | 5 | while ( m < n ) { | MaxPosition = FindMax(A,m,n); | temp = A[m]; A[m] = A[MaxPosition]; A[MaxPosition] = temp; | A = A; m = m+1; n = n; | } | } Program 5.31 Selection Sorting after Tail-Recursion Elimination /*********************************************************************************/ | void SelectionSort(InputArray A, int m, int n) | { | int MaxPosition, temp; | 5 | while ( m < n ) { | MaxPosition = FindMax(A,m,n); | temp = A[m]; A[m] = A[MaxPosition]; A[MaxPosition] = temp; | m++; | } | } Program 5.32 Selection Sorting After Useless Assignment Elimination /*********************************************************************************/ | int FindMax(InputArray A, int m, int n) /* assume m A[j]) j = i; | } while (i != n); 10 | return j; | } Program 5.33 Finding the Position of the Largest Number /*********************************************************************************/ | SelectionSort(InputArray A, int m, int n) | { | int MaxPosition, temp, i, j; | 5 | while (m < n) { | | i = m; j = m; | do { | i++; 10 | if (A[i] > A[j]) j = i; | } while (i != n); | MaxPosition = j; | | temp = A[m]; A[m] = A[MaxPosition]; A[MaxPosition] = temp; 15 | | m++; | } | | } Program 5.34 Almost Final Iterative Selection Sorting /*********************************************************************************/ | void SelectionSort(InputArray A, int m, int n) | { | int MaxPosition, temp, i; | 5 | while (m < n) { | | i = m; | MaxPosition = m; | 10 | do { | i++; | if ( A[i] > A[MaxPosition] ) MaxPosition = i; | } while (i != n); | 15 | temp = A[m]; A[m] = A[MaxPosition]; A[MaxPosition] = temp; | | m++; | } | | } Program 5.35 Iterative Selection Sorting from Transformations /*********************************************************************************/ | double Compound(double A, double r, int n) | { | return ( A * Power(1 + r/100, n) ); | } Program 5.39 Investment Growth under Compound Interest /*********************************************************************************/ | double Power(double x, int n) | { | if ( (x == 1.00) || (n == 0) ) { | return 1.00; /* since 1n == 1 and x0 == 1 for any x and n */ 5 | } else if ( (x == 1.06) && (n == 5) ) { | return 1.3382256; /* since 1.065 == 1.3382256 */ | } | } Program 5.40 Stub for Power(x,n) /*********************************************************************************/ | int BinarySearch(Key K) /* to find the position of the search */ | { /* key K in the ordered array A[0:n-1] */ | | int L; /* L == left boundary of search interval */ 5 | int Midpoint; /* Midpoint == midpoint of search interval */ | int R; /* R == right boundary of search interval */ | | /* Initializations */ | L = 0; /* Initially, L is the leftmost index, 0, and */ 10 | R = n - 1; /* R is the rightmost index, n - 1 */ | | | /* While the interval L:R is non-empty test K against the middle key */ | 15 | while (L <= R) { /* while the interval is non-empty */ | | Midpoint = (L+R) / 2; /* Compute midpoint of interval L:R */ | | if (K == A[Midpoint]) { /* if key K was found at the Midpoint, */ 20 | /* return from the function */ | return Midpoint; /* with Midpoint as the result */ | | } else if (K > A[Midpoint]) { /* otherwise, if K is to the */ | /* right of the Midpoint, search */ 25 | L = Midpoint + 1; /* next in the interval Midpoint+1:R */ | | } else { /* whereas if K is to the */ | /* left of the Midpoint, search */ | R = Midpoint - 1; /* next in the interval L:Midpoint-1 */ 30 | } | | } | | 35 | /* If the search interval became empty, key K was not found */ | | return -1; /* -1 means K was not in A[0:n-1] */ | } Program 5.41 Iterative Binary Search /*********************************************************************************/ | int BinarySearch(Key K, int L, int R) | { | /* To find the position of the search key K in the subarray A[L:R]. */ | /* Note: To search for K in A[0:n-1], the initial call is */ 5 | /* BinarySearch(K,0,n-1). */ | | int Midpoint; | | Midpoint = (L+R) / 2; /* compute midpoint of interval L:R */ 10 | | if (L > R) { /* If the search interval is empty then */ | return -1; /* return -1 to signal K is not in A[L:R] */ | } else if ( K == A[Midpoint] ) { | return Midpoint; 15 | } else if ( K > A[Midpoint] ) { | return BinarySearch(K, Midpoint+1, R); | } else { | return BinarySearch(K, L, Midpoint-1); | } 20 | | } Program 5.42 Recursive Binary Search /*********************************************************************************/ | float G(float x, int n) | { | float p; | 5 | if (n == 0) { | | return 1.0; | | } else { 10 | | p = G(x, n / 2); | | if (n%2 == 0) { | return p * p; 15 | } else { | return x * p * p; | } | | } 20 | | } Program 5.46 Mystery ProgramÑWhat Does This Do? /*********************************************************************************/ | /* Program to compute the average rainfall in New Haven */ | | /* a translation into C from Soloway, CACM 9-86, p. 853 */ | 5 | float sum, rainfall, average; | int count; | | int main(void) | { 10 | | sum = 0.0; | count = 0; | | printf("Please input a rainfall: "); 15 | scanf("%f",&rainfall); | | while ( rainfall != 99999.0 ) { | | while ( rainfall < 0.0 ) { 20 | printf("Rainfall cannot be <0. Input again: "); | scanf("%f",&rainfall) | } | | sum += rainfall; 25 | count++; | printf("Please input a rainfall: "); | scanf("%f",&rainfall); | } | 30 | | if ( count > 0 ) { | average = sum/count; | printf("Average rainfall = %4.2f\n", average); | } else { 35 | printf("No valid inputs. No average calculated.\n"); | } | | } Program 5.47 Average Rainfall with Bug (translated into C with permission of the Association for Computing Machinery, Copyright (C) 1986) /*********************************************************************************/ | /* Program to compute the average rainfall in New Haven */ | /* with bug fixed */ | | #define SENTINEL 99999 5 | | float sum, rainfall; | int count; | | float GetValidInputFromUser(void) /* a valid input is either */ 10 | { /* a non-negative rainfall observation */ | float rainfall; /* or the sentinel */ | | printf("Please input a rainfall or 99999 to stop: "); | scanf("%f",&rainfall); 15 | | while ( rainfall < 0.0) { | printf("Rainfall cannot be < 0. Input again: "); | scanf("%f",&rainfall); | } 20 | | return rainfall; | } | | int main(void) 25 | { | | sum = 0.0; | count = 0; | 30 | rainfall = GetValidInputFromUser(); | | while ( rainfall != SENTINEL ) { | sum += rainfall; | count++; 35 | rainfall = GetValidInputFromUser(); | } | | if (count > 0) { | printf("Average rainfall = %4.2f\n", sum/count); 40 | } else { | printf("No valid inputs. No average calculated.\n"); | } | | } Program 5.48 Average Rainfall with Bug Fixed /*********************************************************************************/ | loop | rainfall := GetValidInputFromUser; | exit when (rainfall = sentinel); | sum := sum + rainfall; 35 | count := count + 1; | end loop; Program 5.49 Loop-Exit Control Structure /*********************************************************************************/ | while (1) { | rainfall = GetValidInputFromUser(); | if ( rainfall == SENTINEL ) break; | sum += rainfall; 35 | count++; | } Program 5.50 A Solution in C Using a While-Loop with a Break /*********************************************************************************/