Question

In: Computer Science

The Problem Below are a series of problems you need to solve using recursive functions. You...

The Problem

Below are a series of problems you need to solve using recursive functions. You will write a program that will read commands from an input file, with each command referring to one of the recursive problems to be executed. Each command will be followed (on the same line of input) by the respective parameters required for that problem.

Implementation

Each recursive function MUST have a wrapper function enclosing it where you will do input/output file processing as well as calling the actual recursive function. From Wikipedia, “A wrapper function is a function in a computer program whose main purpose is to call a second function”.   As an example, here is one of the wrapper functions you will use:

     void KnightsFlip(FILE *fin, FILE *fout);

This would be the wrapper function for one of the recursive problems, called KnightsFlip (described, in detail, below). These wrapper functions will simply do three things:

  1. deal with the processing of the input file
  2. most importantly, the wrapper function will make the initial call to your recursive function that will actually solve the problem.
  3. Finally, the wrapper functions will print to the output file. Note: printing to the output file may also occur in the actual recursive functions.

Of course, at your own discretion (meaning, your own choice), you can make auxiliary functions for your recursive functions to use, such as functions to swap values in an array, take the sum of an array of values, printing functions, etc.

Five Problems to Solve Using Recursion:

(1) KnightsMultiply

Write a recursive function that multiplies all values from k up to n and returns the result (as a double). For example: if k = 5, and n = 10, then multiply 5 * 6 * 7 * 8 * 9 * 10 to return 151200.

(2) KnightsFlip

You have an index card with the letter K written on one side, and F on the other. You want to see ALL of the possible ways the card will land if you drop it n times. Write a recursive function that prints each session of dropping the cards with K's and F's.   For example of you drop it 4 times in a given session, all possible ways to drop it are as follows:

KKKK

KKKF

KKFK

KKFF

KFKK

KFKF

KFFK

KFFF

FKKK

FKKF

FKFK

FKFF

FFKK

FFKF

FFFK

FFFF

*Note: The possible ways would have to print in this specific order.

(3) KnightsShape

Simply write a recursive function that prints a large X composed of smaller X's with a given “width”, n, which is guaranteed to be odd. Example for an X of width n = 7:

X     X

X   X   X X

   X

X X

X   X

X     X

*Note: to be clear, the “width” is the length (number) of X’s along one line of the large X.

(4) KnightsScotch

No, this has nothing to do with drinking Scotch! Suppose you are playing a special game of hopscotch on a line of integer numbers drawn on the ground like so:

            4 4 1 5 2 6 3 4 2 0

The number, with a square around it, indicates where you are currently standing. You can move left or right down the line by jumping the number of spaces indicated by the number you are standing on. So if you are standing on a 4, you can jump either left 4 spaces or right 4 spaces. You cannot jump past either end of the line.

For example, the first number (4) only allows you to jump right, since there are no numbers to the left that you can jump to.

The goal: you want to get to the 0 at the far end (right side) of the line. You are also guaranteed that there will be only one zero, which, again, will be at the far right side.

Here is how you do that with the above line:

Starting           4 4 1 5 2 6 3 4 2 0 position

Step 1:               4 4 1 5 2 6 3 4 2 0

Jump right

Step 2:               4 4 1 5 2 6 3 4 2 0

Jump left

Step 3:               4 4 1 5 2 6 3 4 2 0

Jump right

Step 4:               4 4 1 5 2 6 3 4 2 0

Jump right

Step 5:               4 4 1 5 2 6 3 4 2 0

Jump left

Step 6:               4 4 1 5 2 6 3 4 2 0

Jump right

Some KnightsScotch lines have multiple paths to 0 from the given starting point. Other lines have no paths to 0, such as the following:

3 1 2 3 0

In this line, you can jump between the 3's, but not anywhere else.

You are to write a recursive function that returns an integer 1 (for solvable) or 0 (for not solvable), indicating if you are able to get to the rightmost 0 or not.

(5) KnightsDepot

You are working on an engineering project with other students and are in need of 2x4s (2 by 4’s) of various lengths. Thankfully, UCF has its very own “Depot” store: KnightsDepot…so you don’t have to drive far. Unfortunately, KnightsDepot only carries 2x4s in fixed lengths. So your team will have to purchase the 2x4s and then cut them as needed. Because of your tight college student budget, you want to buy the least number of 2x4s in order to cover the lengths requested by your team.

The recursive function you are designing will return the minimum number of 2x4s you need to purchase, in order to cover the lengths requested by your team. Example:

Array of 2x4 lengths requested by your team: { 6, 4, 3, 4, 1, 3 }

Fixed length of 2x4s at KnightsDepot: 6 (so each purchased 2x4 has a length of 6)

A possible arrangement of of 2x4s: { 6 } { 3, 3 } { 4, 1 } { 4 }

Minimum number of 2x4s needed to purchase: 4

Wrapper Functions

As mentioned, you MUST use the following five wrapper functions EXACTLY as shown:

     void KnightsMultiply(FILE *fin, FILE *fout); void KnightsFlip(FILE *fin, FILE *fout); void KnightsShape(FILE *fin, FILE *fout); void KnightsScotch(FILE *fin, FILE *fout); void KnightsDepot(FILE *fin, FILE *fout);

Input File Specifications

You will read in input from a file, "KnightsRecurse.in". Have this AUTOMATED. Do not ask the user to enter “KnightsRecurse.in”. You should read in this automatically (this will expedite the grading process). The file will contain an arbitrary number of lines and on each line there will be a command. Each command will be followed by relevant data as described below (and this relevant data will be on the same line as the command).

We will not tell you the number of commands in the file. So how do you know when you’ve read all the commands in the input file? You can use the <stdlib.h> function feof(FILE * file) to determine if you have reached the end of the file.

The commands (for the five recursive functions), and their relevant data, are described below:

KnightsMultiply - This command will be followed by the following information: k and then n, as described above.

KnightsFlip - This command will be followed by a single integer, n, as described above.

KnightsShape - This command will be followed by a single integer, n, as described above.

KnightsScotch - This command will be followed by an integer, start, representing the initial position on the line you are playing on (0 means the far left, the first position); size, the number of integers drawn on the ground; size will be followed by size number of integers, the integers drawn on the ground. (see input file for examples)

KnightsDepot - This command will be followed by an integer maxlen, which represents the maximum 2x4 length the store sells; size, the number of 2x4s your team needs; size will be followed by size number of integers, the length of each 2x4 your team needs. It is guaranteed that the requested lengths will all be less than or equal to the maxlen sold by the store.

Solutions

Expert Solution

Complete Program:

File: main.c

// Header files section
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// function prototypes for auxiliary functions
void auxPrintKnightsShape(int n, int max, FILE *fout);
void auxSwap2x4s(int *team, int i, int j);

// function prototypes for recursive functions
double recKnightsMultiply(int k, int n);
void recKnightsFlip(char *str, int index, int n, FILE *fout);
void recKnightsShape(int n, int max, FILE *fout);
int recKnightsScotch(int *line, int size, int curr);
void recKnightsDepot(int *team, int size, int maxlen, int numberOf2x4sPlaced, int spaceRemainingOn2x4, int numberOf2x4sUsed, int *usedCount);

// function prototypes for wrapper functions
void KnightsMultiply(FILE *fin, FILE *fout);
void KnightsFlip(FILE *fin, FILE *fout);
void KnightsShape(FILE *fin, FILE *fout);
void KnightsScotch(FILE *fin, FILE *fout);
void KnightsDepot(FILE *fin, FILE *fout);

// start main function
int main()
{
   FILE *fin = fopen("KnightsRecurse.in", "r");
   FILE *fout = fopen("KnightsRecurse.out", "w");

   if (!fin)
   {
       printf("The KnightsRecurse.in file is not found!\n");
       printf("Terminating Program...\n");
       exit(EXIT_FAILURE);
   }

  
   if (!fout)
   {
       printf("The KnightsRecurse.out file is not found!\n");
       printf("Terminating Program...\n");
       exit(EXIT_FAILURE);
   }

   while (!feof(fin))
   {
       char command[50];

       fscanf(fin, "%s", command);

       if (!strcmp(command, "KnightsMultiply"))
           KnightsMultiply(fin, fout);
       else if (!strcmp(command, "KnightsScotch"))
           KnightsScotch(fin, fout);
       else if (!strcmp(command, "KnightsDepot"))
           KnightsDepot(fin, fout);
       else if (!strcmp(command, "KnightsShape"))
           KnightsShape(fin, fout);
       else if (!strcmp(command, "KnightsFlip"))
           KnightsFlip(fin, fout);
   }

   fclose(fin);
   fclose(fout);
  
   exit(EXIT_SUCCESS);
} // end of main function

// implementations of wrapper functions

// function implementation
void KnightsMultiply(FILE *fin, FILE *fout)
{
   int k;
   int n;
   double result;
   fscanf(fin, "%d %d", &k, &n);

   result = recKnightsMultiply(k, n);
   fprintf(fout, "KnightsMultiply: %.0f\n\n", result);
} // end of function

// function implementation
void KnightsFlip(FILE *fin, FILE *fout)
{
   int n;
   fscanf(fin, "%d", &n);
   fprintf(fout, "KnightsFlip:\n");

   char *str = malloc((n + 1) * sizeof(char));  
   str[n] = '\0';

   recKnightsFlip(str, 0, n, fout);
   fprintf(fout, "\n");
   free(str);
} // end of function

// function implementation
void KnightsShape(FILE *fin, FILE *fout)
{
   int n;
   fscanf(fin, "%d", &n);
   fprintf(fout, "KnightsShape:\n");
   recKnightsShape(n, n, fout);
   fprintf(fout, "\n");
} // end of function

// function implementation
void KnightsScotch(FILE *fin, FILE *fout)
{
   int start;
   int size;
   int *ground;
   int i;

   fscanf(fin, "%d %d", &start, &size);
   ground = malloc(size * sizeof(int));
  
   for (i = 0; i < size; i++)
   {
       fscanf(fin, "%d", &ground[i]);
   }

   int result = recKnightsScotch(ground, size, start);
  
   if (result)
       fprintf(fout, "KnightsScotch: Solvable\n\n");
   else
       fprintf(fout, "KnightsScotch: Not Solvable\n\n");

   free(ground);
} // end of function

// function implementation
void KnightsDepot(FILE *fin, FILE *fout)
{
   int maxlen;
   int size;
   int *team;
   int i;

   fscanf(fin, "%d %d", &maxlen, &size);
   team = malloc(size * sizeof(int));
  
   for (i = 0; i < size; i++)
   {         
       fscanf(fin, "%d", &team[i]);
   }

   int numberOf2x4sPlaced = 0;
   int spaceRemainingOn2x4 = maxlen;                              
   int numberOf2x4sUsed = 0;
   int usedCount = size;

   recKnightsDepot(team, size, maxlen, numberOf2x4sPlaced, spaceRemainingOn2x4, numberOf2x4sUsed, &usedCount);

   fprintf(fout, "KnightsDepot: %d\n\n", usedCount);
   free(team);
} // end of function


// implementation of recursive functions

// function implementation
double recKnightsMultiply(int k, int n)
{
   if (n == k)
       return k;
   else
       return (n * recKnightsMultiply(k, n - 1));
} // end of function

// function implementation
void recKnightsFlip(char *str, int index, int n, FILE *fout)
{
   if (index == n)
   {
       fprintf(fout, "%s\n", str);
       return;
   }

   str[index] = 'K';
   recKnightsFlip(str, index + 1, n, fout);

   str[index] = 'F';
   recKnightsFlip(str, index + 1, n, fout);
} // end of function

// function implementation
void recKnightsShape(int n, int max, FILE *fout)
{
   if (n <= (max / 2 + 1))
   {
       auxPrintKnightsShape(n, max, fout);
       return;
   }
  
   auxPrintKnightsShape(n, max, fout);
   recKnightsShape(n - 1, max, fout);
   auxPrintKnightsShape(n, max, fout);
} // end of function

// function implementation
int recKnightsScotch(int *ground, int size, int curr)
{
   if (ground[curr] == 0)
       return 1;
  
   int left = 0;
   int right = 0;
   int jump = ground[curr];
   ground[curr] = -1;

   if ((curr - jump) >= 0 && ground[curr - jump] != -1)
   {
       left = recKnightsScotch(ground, size, curr - jump);
   }
  
   if ((curr + jump) < size && ground[curr + jump] != -1)
   {
       right = recKnightsScotch(ground, size, curr + jump);
   }

   if (left || right)
       return 1;
   else
       return 0;
} // end of function

// function implementation
void recKnightsDepot(int *team, int size, int maxLength, int numberOf2x4sPlaced, int spaceRemainingOn2x4, int numberOf2x4sUsed, int *usedCount)
{
   int i;
   int j;
   int flag = 1;

   if (numberOf2x4sPlaced == size)
   {
       if (numberOf2x4sUsed + 1 < *usedCount)
       {
           *usedCount = numberOf2x4sUsed + 1;
       }
   }
   else
   {
       for (i = numberOf2x4sPlaced; i < size; i++)
       {
           auxSwap2x4s(team, numberOf2x4sPlaced, i);

           if (team[numberOf2x4sPlaced] <= spaceRemainingOn2x4)
           {
               spaceRemainingOn2x4 -= team[numberOf2x4sPlaced];              
               numberOf2x4sPlaced++;
           }
           else
           {
               numberOf2x4sUsed++;              
               spaceRemainingOn2x4 = maxLength - team[numberOf2x4sPlaced];              
               numberOf2x4sPlaced++;
           }

           recKnightsDepot(team, size, maxLength, numberOf2x4sPlaced, spaceRemainingOn2x4, numberOf2x4sUsed, usedCount);

           numberOf2x4sPlaced--;
           spaceRemainingOn2x4 += team[numberOf2x4sPlaced];

           if (spaceRemainingOn2x4 == maxLength && numberOf2x4sUsed > 0)
           {
               numberOf2x4sUsed--;

               for (flag = 1, j = 1; flag; j++)
               {
                   if (numberOf2x4sPlaced - j >= 0)
                   {
                       if (spaceRemainingOn2x4 - team[numberOf2x4sPlaced - j] >= 0)
                       {
                           spaceRemainingOn2x4 -= team[numberOf2x4sPlaced - j];
                       }
                       else
                       {
                           flag = 0;
                       }
                   }
                   else
                   {
                       flag = 0;
                   }
               }
           }

           auxSwap2x4s(team, i, numberOf2x4sPlaced);
       }
   }
} // end of function

// implementations of auxilary functions

// function implementation
void auxPrintKnightsShape(int n, int max, FILE *fout)
{
   int i;
   for (i = 1; i <= max; i++)
   {
       if (i == n || i == (max - n + 1))
           fprintf(fout, "X");
       else
           fprintf(fout, " ");
   }
   fprintf(fout, "\n");
} // end of function

// function implementation
void auxSwap2x4s(int *team, int i, int j)
{

   int temp = team[i];
   team[i] = team[j];
   team[j] = temp;
} // end of function

Input file: KnightsRecurse.in

NOTE: You are not given the input file KnightsRecurse.in. So, I have assumed the below file from the description of the question.

Output file: KnightsRecurse.out


Related Solutions

The Problem Below are a series of problems you need to solve using recursive methods BY...
The Problem Below are a series of problems you need to solve using recursive methods BY using java . You will write a program that will read commands from an input file, with each command referring to one of the recursive problems to be executed. Each command will be followed (on the same line of input) by the respective parameters required for that problem. (15 points for main method) DescArrayCheck (15 points) Write a recursive method that checks whether an...
PYTHON PYTHON Recursive Functions. In this problem, you are asked to write three recursive functions. Implement...
PYTHON PYTHON Recursive Functions. In this problem, you are asked to write three recursive functions. Implement all functions in a module called problem1.py. (10 points) Write a recursive function called remove char with two parameters: a string astr and a character ch. The function returns a string in which all occurrences of ch in astr are removed. For example, remove char("object oriented", ’e’) returns the string "objct orintd". Your implementation should not contain any loops and may use only the...
For this problem, solve the problems by answering a) state the claim using a sentence, b)...
For this problem, solve the problems by answering a) state the claim using a sentence, b) Ho H1 and place the claim with either one of the two, c) Test statistic, show and label the formula you use, d) find critical value(s), and reject Ho or fail to reject Ho. You may use p-value. e) Write a formal conclusion and final statement (Please show all work and label answer a,b,c,d,e) The Pew Research Center claims that at least 54% of...
For this problem, solve the problems by answering a) state the claim using a sentence, b)...
For this problem, solve the problems by answering a) state the claim using a sentence, b) Ho H1 and place the claim with either one of the two, c) Test statistic, show and label the formula you use, d) find critical value(s), and reject Ho or fail to reject Ho. You may use p-value. e) Write a formal conclusion and final statement (Please show all work and label answer a,b,c,d,e) A sample of 106 body temperatures with a mean of...
For this problem, solve the problems by answering a) state the claim using a sentence, b)...
For this problem, solve the problems by answering a) state the claim using a sentence, b) Ho H1 and place the claim with either one of the two, c) Test statistic, show and label the formula you use, d) find critical value(s), and reject Ho or fail to reject Ho. You may use p-value. e) Write a formal conclusion and final statement (Please show all work and label answer a,b,c,d,e) A golf balls manufacturer requires that the weights of its...
Solve the following financial problems using the time value of money functions in Excel (PV, FV,...
Solve the following financial problems using the time value of money functions in Excel (PV, FV, PMT, NPER, RATE, EFFECT) OR using your financial calculator. Assume you deposit $3,000 today, and $300 at the end of each year, in an account earning 4% per year for 20 years. What is the future value? General Electric has an unfunded pension liability of $300 million that must be paid in 15 years. The CFO deposits $10 million in account today to help...
Solve the following financial problems using the time value of money functions in Excel (PV, FV,...
Solve the following financial problems using the time value of money functions in Excel (PV, FV, PMT, NPER, RATE, EFFECT) OR using your financial calculator. Assume you deposit $3,000 today, and $300 at the end of each year, in an account earning 4% per year for 20 years. What is the future value? General Electric has an unfunded pension liability of $300 million that must be paid in 15 years. The CFO deposits $10 million in account today to help...
Solve the initial value problem once using power series method and once using the characteristic method....
Solve the initial value problem once using power series method and once using the characteristic method. Please show step for both 3) 3y”−y=0, y(0)=0,y’(0)=1 Note that 3y” refers to it being second order differential and y’ first
Using the method of separation of variables and Fourier series, solve the following heat conduction problem...
Using the method of separation of variables and Fourier series, solve the following heat conduction problem in a rod. ∂u/∂t =∂2u/∂x2 , u(0, t) = 0, u(π, t) = 3π, u(x, 0) = 0
I have the answer for this problem but I need to solve it using Excel's PV...
I have the answer for this problem but I need to solve it using Excel's PV function for both products and I cannot seem to figure it out. What would I insert for each portion of the equation into excel? It has been answered on another question as number 2. http://www.chegg.com/homework-help/questions-and-answers/lou-barlow-divisional-manager-sage-company-opportunity-manufacture-sell-one-two-new-produc-q12342389?trackid=297667da&strackid=464d9914&ii=8
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT