Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Write a program for solving summation puzzles by enumerating and testing all possible configurations. Using your program, solve the three puzzles given in Section 5.3.3.

Write a program for solving summation puzzles by enumerating and testing all possible configurations. Using your program, solve the three puzzles given in Section 5.3.3.

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question

Java programming homework

please help with the question below:

 

P 5.28: Write a program for solving summation puzzles by enumerating and testing all possible configurations. Using your program, solve the three puzzles given in Section 5.3.3.

5.3.3 Multiple Recursion Generalizing from binary recursion, we define multiple recursion as a process in which a method may make more than two recursive calls. Our recursion for an- alyzing the disk space usage of a file system (see Section 5.1.4) is an example of multiple recursion, because the number of recursive calls made during one invoca- tion was equal to the number of entries within a given directory of the file system. Another common application of multiple recursion is when we want to enumer- ate various configurations in order to solve a combinatorial puzzle. For example, the following are all instances of what are known as summation puzzles: pot + pan = bib dog + cat boy + girl = = pig baby To solve such a puzzle, we need to assign a unique digit (that is, 0, 1, ..., 9) to each letter in the equation, in order to make the equation true. Typically, we solve such a puzzle by using our human observations of the particular puzzle we are trying to solve to eliminate configurations (that is, possible partial assignments of digits to letters) until we can work through the feasible configurations that remain, testing for the correctness of each one. If the number of possible configurations is not too large, however, we can use a computer to simply enumerate all the possibilities and test each one, without em- ploying any human observations. Such an algorithm can use multiple recursion to work through the configurations in a systematic way. To keep the description general enough to be used with other puzzles, we consider an algorithm that enu- merates and tests all k-length sequences, without repetitions, chosen from a given universe U. We show pseudocode for such an algorithm in Code Fragment 5.11, building the sequence of k elements with the following steps: 1. Recursively generating the sequences of k- 1 elements 2. Appending to each such sequence an element not already contained in it. Throughout the execution of the algorithm, we use a set U to keep track of the elements not contained in the current sequence, so that an element e has not been used yet if and only if e is in U. Another way to look at the algorithm of Code Fragment 5.11 is that it enumer- ates every possible size-k ordered subset of U, and tests each subset for being a possible solution to our puzzle. For summation puzzles, U = {0, 1,2,3,4,5,6,7,8,9} and each position in the sequence corresponds to a given letter. For example, the first position could stand for b, the second for o, the third for y, and so on.
Transcribed Image Text:5.3.3 Multiple Recursion Generalizing from binary recursion, we define multiple recursion as a process in which a method may make more than two recursive calls. Our recursion for an- alyzing the disk space usage of a file system (see Section 5.1.4) is an example of multiple recursion, because the number of recursive calls made during one invoca- tion was equal to the number of entries within a given directory of the file system. Another common application of multiple recursion is when we want to enumer- ate various configurations in order to solve a combinatorial puzzle. For example, the following are all instances of what are known as summation puzzles: pot + pan = bib dog + cat boy + girl = = pig baby To solve such a puzzle, we need to assign a unique digit (that is, 0, 1, ..., 9) to each letter in the equation, in order to make the equation true. Typically, we solve such a puzzle by using our human observations of the particular puzzle we are trying to solve to eliminate configurations (that is, possible partial assignments of digits to letters) until we can work through the feasible configurations that remain, testing for the correctness of each one. If the number of possible configurations is not too large, however, we can use a computer to simply enumerate all the possibilities and test each one, without em- ploying any human observations. Such an algorithm can use multiple recursion to work through the configurations in a systematic way. To keep the description general enough to be used with other puzzles, we consider an algorithm that enu- merates and tests all k-length sequences, without repetitions, chosen from a given universe U. We show pseudocode for such an algorithm in Code Fragment 5.11, building the sequence of k elements with the following steps: 1. Recursively generating the sequences of k- 1 elements 2. Appending to each such sequence an element not already contained in it. Throughout the execution of the algorithm, we use a set U to keep track of the elements not contained in the current sequence, so that an element e has not been used yet if and only if e is in U. Another way to look at the algorithm of Code Fragment 5.11 is that it enumer- ates every possible size-k ordered subset of U, and tests each subset for being a possible solution to our puzzle. For summation puzzles, U = {0, 1,2,3,4,5,6,7,8,9} and each position in the sequence corresponds to a given letter. For example, the first position could stand for b, the second for o, the third for y, and so on.
5.3. Further Examples of Recursion Algorithm PuzzleSolve(k, S, U): Input: An integer k, sequence S, and set U Output: An enumeration of all k-length extensions to S using elements in U without repetitions for each e in U do Add e to the end of S Remove e from U if k = 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output abc {a solution} {a recursive call} {e is now considered as unused} Code Fragment 5.11: Solving a combinatorial puzzle by enumerating and testing all possible configurations. else PuzzleSolve(k-1, S, U) Remove e from the end of S Add e back to U PuzzleSolve(2, a, {b,c}) In Figure 5.14, we show a recursion trace of a call to PuzzleSolve(3, S, U), where S is empty and U = {a,b,c}. During the execution, all the permutations of the three characters are generated and tested. Note that the initial call makes three recursive calls, each of which in turn makes two more. If we had executed PuzzleSolve(3, S, U) on a set U consisting of four elements, the initial call would have made four recursive calls, each of which would have a trace looking like the one in Figure 5.14. PuzzleSolve(1, ab, {c}) initial call PuzzleSolve(3, (), {a,b,c}) (PuzzleSolve(2, b, {a,c}) PuzzleSolve(1, ba, {c}) acb bac PuzzleSolve(1, ac, {b}) {e is now being used} PuzzleSolve(2, c, {a,b}) PuzzleSolve(1, ca, {b}) bca 213 cab PuzzleSolve(1, bc, {a}) PuzzleSolve(1, cb, {a}) cba Figure 5.14: Recursion trace for an execution of PuzzleSolve(3, S, U), where S is empty and U = {a,b,c}. This execution generates and tests all permutations of a, b, and c. We show the permutations generated directly below their respective boxes.
Transcribed Image Text:5.3. Further Examples of Recursion Algorithm PuzzleSolve(k, S, U): Input: An integer k, sequence S, and set U Output: An enumeration of all k-length extensions to S using elements in U without repetitions for each e in U do Add e to the end of S Remove e from U if k = 1 then Test whether S is a configuration that solves the puzzle if S solves the puzzle then add S to output abc {a solution} {a recursive call} {e is now considered as unused} Code Fragment 5.11: Solving a combinatorial puzzle by enumerating and testing all possible configurations. else PuzzleSolve(k-1, S, U) Remove e from the end of S Add e back to U PuzzleSolve(2, a, {b,c}) In Figure 5.14, we show a recursion trace of a call to PuzzleSolve(3, S, U), where S is empty and U = {a,b,c}. During the execution, all the permutations of the three characters are generated and tested. Note that the initial call makes three recursive calls, each of which in turn makes two more. If we had executed PuzzleSolve(3, S, U) on a set U consisting of four elements, the initial call would have made four recursive calls, each of which would have a trace looking like the one in Figure 5.14. PuzzleSolve(1, ab, {c}) initial call PuzzleSolve(3, (), {a,b,c}) (PuzzleSolve(2, b, {a,c}) PuzzleSolve(1, ba, {c}) acb bac PuzzleSolve(1, ac, {b}) {e is now being used} PuzzleSolve(2, c, {a,b}) PuzzleSolve(1, ca, {b}) bca 213 cab PuzzleSolve(1, bc, {a}) PuzzleSolve(1, cb, {a}) cba Figure 5.14: Recursion trace for an execution of PuzzleSolve(3, S, U), where S is empty and U = {a,b,c}. This execution generates and tests all permutations of a, b, and c. We show the permutations generated directly below their respective boxes.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Random Class and its operations
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS