Logical Problem Solving: Before the Flowchart, with C++ and Visual Basic Applications

About

Features

• Straightforward rules introduced throughout the book—Reinforced and illustrated with many related problems.

  • Illustrate techniques for analyzing and solving a wide variety of problems. Also reinforce creative thinking. Ex.___

• Interesting and diverse problems—Include applications from finance, physics, math, and English as well as "entertaining" examples related to topics such as games.

  • Capture student attention. Ex.___

• Problems increase in complexity—Author revisits earlier problems when new rules are introduced, helping students better comprehend the problem in question.

  • As students gain experience, they learn how to build on the insight gained by each success and how new problems can be seen as adaptations or extensions of problems already solved. Ex.___

• Solutions to all problems in the book included in the discussion.

  • Students know what they are working toward. Ex.___

• Use of pseudocode and flowcharts.

  • Clarify plans for approaching each problem. Ex.___

• C++ and Visual Basic code used to implement the solution—Important sections of program code contain comments that relate it to the preceding pseudocode.

  • Students do not have to know how to program to follow the implementation of the programs, but the book can serve as a valuable main text in a course that precedes an introductory programming course or as supplement to introductory C++ or Visual Basic book. Ex.___

Description

This book shows readers how to best attack a wide variety of problems that they may not have previously solved. It focuses on techniques for developing the logic required to solve problems and how that logic is translated into writing effective computer programs. KEY TOPICS: The author uses a consistent structure throughout the book of introducing a problem and formulating the solution based on a set of rules for creative problem solving. The solution is then represented first in pseudocode, then in a flowchart, then in C++ and finally in Visual Basic. This approach provides readers with a strong foundation in problem solving that will benefit them in areas beyond programming. MARKET:

Sample Content

Table of Contents

1. Understanding the Problem.

In the Beginning. Including Common Information. Including Uncommon Information. Working Backwards. Working Backwards—A Ball is Dropped.

The Power of the Personal Computer. The Falling Ball. The Penny Problem. Grade Point Average. Binary Conversion. Daily Compounded Interest. The Wall Problem. Superfly. MacLaurin Series Expansions.

Strategic Guessing. Calculating Square Roots. Improved Strategic Guessing—Newton-Raphson Method. The Ladder Problem. The Unsolvable Equation.

Non-Strategic Guessing. The Liars Problem. The Comedians' Hats. Prime Numbers. Searching Routines. Sorting Routines. Combining Searching and Sorting.

The Look-Up Table. The Understood Look-Up Table. The Unsolvable Problem.

Probabilities. Calculating the Odds. The "What if" Scenario. Geometric Probability. Integral Calculus.

Limitations in Accuracy. Limitations in Scope. Limitations in Conditions. Elimination of the Random Number Bias. Limitations in Options. Limitations in Utility.

Error Trapping. Handling Input. The Advantages of Objects. Recursion.

Rule Zero.

A. The Rules. B. Derivation of the Ellipse Formula. C. Integration of the Ellipse Formula. D. Probability Calculations for Winning a Game of Craps. E. ASCII Table.

Preface

PROBLEM SOLVING SKILLS

The issue would seem to be intractable. How do you solve a problem that you have never been taught to solve? Or, from an instructor's point of view, how do you teach someone else to develop new, creative solutions to previously unseen problems? Are such solutions the province of the exceptionally creative? Are creative solutions truly the marks of rare sparks of genius? Or, on the other hand, are there techniques that can be taught to anyone that lead to inventive approaches to daunting problems and ultimately to solutions.

Science, mathematics, and programming instructors constantly face this question. In each field the mechanics are straightforward consisting of principles and formulas. Teaching usually involves explaining the formulas, indicating what is to be memorized, and demonstrating how the mechanics are implemented. And, with varying amounts of effort, these mechanics and the accompanying calculations, can be learned by nearly all students. The calculations involved in determining the speed of a falling object, the balancing of chemical equations, the use of the quadratic formula, and the use of the pow() function in a C++ program represent implantations of formulas that are eminently learnable. These operations are sometimes called "plug and chug" because finding a solution involves choosing the appropriate a formula (or syntax), plugging in the proper numbers, and letting a calculator (or computer) chug until an answer appears on the display.

While this does involve one type of problem solving it limits students to solving problems that they have been taught to solve, problems that have a known algorithm for determining the solution to the problem. Unfortunately, in this electronic age, solving these types of problems is generally left to devices that work tirelessly, more reliably, and thousands of times faster than the most capable human. The execution of formulas has become the domain of computers. Those who only learn how to implement known formulas such as calculating a weighted average or the solution to two equations with two unknowns are preparing to compete directly with a computer. This is a competition that cannot be won.

However, computers fail when presented a novel problem for which there is no program available. Problem solving at this level requires creativity and the intervention of human thinking. Consequently determining creative solutions to previously unseen problems is a point of focus for mathematics, physics, economics, and numerous classes in the fields of technology and engineering.

This text concentrates on this higher level of problem solving and how it can be implemented by writing computer programs. That is, the expansion of basic principles and calculations to allow more complex problems to be solved. These are problems that involve the creative application of the more fundamental ideas rather than the mere resolution of a formula. For example, finding the solution to a quadratic equation is simple. Values for each tern are substituted into the quadratic formula and the resulting expression is evaluated. A more interesting and challenging problem is how to solve a fifth order equation. Since there is no algebraic solution for equations of order higher than four, this level of problem solving is not commonly taught. However, this seemingly difficult problem can be handled by combining the methods described in this text with the power of a personal computer.

This type of problem solving is difficult to learn and even more difficult to teach. However, in an age where calculators and computers have taken over most of the fundamental calculations and many not so fundamental calculations, it is important for students to learn to solve the problems that require the creative thinking that is (at least for the moment) beyond the abilities of electronic devices.

The formula for acceleration of a falling object can be read from a physics text and programmed into a calculator. Determining the velocity of a ball dropped from the top of a building after three seconds is as simple as entering a time value into the equation. Determining the speed required to keep a satellite in orbit is not so simple. Somewhere there is probably a formula that answers the question but because that formula is not readily available the problem becomes one of applying basic concepts from physics and mathematics in a creative fashion to determine a solution to the problem. This level of problem solving, finding answers to previously unseen problems, is still the realm of humans.

THE ROLE OF THE CALCULATOR

Approximately twenty-five years ago educators made the decision to introduce the use of calculators in the classroom. The goal was straightforward and seemed reasonable at the time. In the electronic age where a hand-held device could quickly, accurately, and reliably produce arithmetic answers, everyone should learn to use the new device.

In theory, the calculator would remove the tedium from the study of mathematics by making unnecessary the memorization of multiplication tables, decimal to fraction conversions, square root algorithms, and the standard constants, such as the number of feet in a mile. Students would benefit by the substitution of problem solving skills for the hours formerly spent practicing long division, dividing fractions, and calculating interest. Motivation would skyrocket as memorization and tedious practice was replaced with fascinating problems that appealed to students' imagination.

As the price of calculators plummeted and the capabilities expanded, calculators (and later computers) took over the tasks of solving equations, graphing functions, and calculating determinates. Again the use of calculators was justified from many directions. School should be fun and the tedium of arithmetic mechanics was not. The technology has become accepted in society and students must learn to make use of the most efficient tools. The memorization of formulas is irrelevant when the formulas can be programmed into the memory of the calculator. However, the primary rationalization was the increased time that could be devoted to problem solving once the mechanics were handled by electronic devices.

Unfortunately the promise of enhanced problem solving skill has failed to materialize. Some educators consider the skill to be innate and a given student either has the ability to think creatively or he does not. More commonly teachers acknowledge the difficulty in developing these problem-solving skills not to mention the unpopularity of "word problems", and choose to focus on more formula-based skills.

Fortunately the microprocessor that has made it unnecessary for people to determine a 15% tip or to calculate their taxes (which maybe handled by a computer program or it can be a truly creative exercise requiring teams of accountants and lawyers), offers expanded options in methods for attacking novel problems. Consider the daily compounding of interest for a bank account. The formula for daily compounding is not commonly known and no one would be interested in actually calculating interest on an account by adding the interest to the principle on a daily basis for perhaps five years. However it only takes minutes to program a computer to perform the thousands of calculations required. The end result is an answer to the problem despite the fact that the formula for compound interest is unknown.

THE CHANGING ROLE FOR STUDENTS

The reality of the calculator and the computer has fundamentally changed the role of the student in the problem solving process. Prior to the introduction of electronic calculating devices all calculations were made by hand and the student's role was to execute the algorithms. The teacher provided the plan of attack whether it was the method for multiple digit multiplication, the formula for compound interest, or the equations for calculating probabilities. Students memorized formulas and performed calculations.

The execution of algorithms has, for better or worse, become the domain of the machine. The number of people able to balance a checkbook, perform long division, or calculate a square root without a calculator is rapid diminishing. While the loss of basic numeric skills may be unfortunate and appears to be accompanied by the loss of understanding of fundamental arithmetic concepts, it is clear that the most adept human is no match for a computer in terms of speed, accuracy, or the ability to work for days on end without getting hungry, sleepy, or careless.

However, if the student is no longer needed to manually make calculations, it becomes critical that he take on a new role previously filled by the teacher. It is the student who must develop creative solutions to problems previously unseen. That is, students must learn to develop new algorithms without the aid of a teacher, algorithms that may or may not be left to a computer to execute later. In short, problem-solving skills have become critically important.

The converse of this idea brings the concept into even higher relief. If students are only taught to execute algorithms then they are being prepared to compete directly with computers. This is an unnecessary and a futile contest. It is important that students learn to perform the higher functions that are beyond the abilities of computers.

PROBLEM SOLVING SKILLS

This returns us to the original problem. How can problem-solving skills be taught? How can insight into the resolution of an arbitrary problem be developed? How can the level of creative thinking be enhanced for the students in programming, science and mathematics classes? The problem is not intractable. There are two methods for developing precisely these skills.

The first step is to examine a set of approaches to problem solving. Because science and mathematics classes usually concentrate on individual principles and the applicable formulas, students often find that their first computer programming class is their first challenge in logical problem solving. In programming classes there is no way to avoid problem solving. Before anyone can write a program he must determine what to write. That is, there must be a plan for attacking the problem whether the program is to calculate square roots, calculate the number of days between widely separated dates, or determine the speed required to keep a satellite in orbit. For this reason many high schools, technical colleges, and universities are requiring classes in logical problem solving as a prerequisite for programming classes.

This is not to imply that mathematics classes are devoid of this level of problem solving. Algebra classes do contain word problems. Geometry classes require the proving of theorems. Trigonometry classes include the proving of trigonometric identities. However, these topics tend to be troublesome, unpopular with students, and difficult for teachers. Consequently far more time is spent on the mechanics of manipulating equations and the implementation of established algorithms, than on developing creative solutions. Similarly the proving trigonometric identities takes a back seat to calculating tangent function values. Geometry classes may not be required for graduation or the calculation of areas and volumes with their reliance on formulas may be substituted for the more creative, less structured, and more difficult task of proving theorems. In programming classes the student finds there is no way to avoid problem solving.

The traditional method for helping students learn to develop these plans is to have them first develop flowcharts or write pseudo-code that outlines the step-by-step procedure for solving the problem. The difficulty with this approach is that a flowchart is merely a description of a plan that is already developed. A student who does not know how to solve a problem will probably be unable to write a flow chart. In fact it is not uncommon for programming instructors who require the use of flowcharts to find that students have written the program first and then constructed the flowchart from the program. We could call this re-engineering at its worst.

This is not to minimize the value of flow-charting. Flow charting and the writing of pseudo-code are a useful tools for clarifying a plan before beginning to write code and will be used extensively in this text but they are of little help in developing the plan. The intention of this text is to back-up one step from the flowchart and present a set of techniques for analyzing problems that leads to a plan for simultaneously answering the question of how to make the flowchart and how to write the program.

The second method for developing problem solving skills is to build a repertoire of problems that have already been solved. There is no substitute for experience in any endeavor and it is an unfortunate truth that no one starts out experienced. However experience in problem solving can be built by beginning with simple problems and building on the insight gained by each success. Clearly the problem of calculating the necessary speed to keep a satellite in orbit is not the place to begin developing problem-solving skills. It is more reasonable to begin with simple problems that can be solved by combining just a few well-known formulas or involve an easily followed train of logic. As experience grows new problems are often seen as mere variations or extensions of problems already solved.

Will readers who follow this book to its conclusion be able to solve the problems of planning a sustainable ecology, developing a clean energy source, and returning astronauts safely from Mars? Possibly not. But my experience in teaching computer programming over fourteen years makes me absolutely sure that anyone's problem solving abilities can be enhanced and that this enhanced ability is a valuable skill that pays dividends far beyond the confines of a programming class.

THE TEXT LAYOUT

Each of the following chapters explores a different method for solving problems and variations on the method for expanding its usefulness. The chapters begin with an explanation of the approach and then proceed through a series of examples that demonstrate the application of the approach. In general each example will add increased complexity and difficulty in implementing the method.

After the plan for attacking the problem has been described in detail, pseudocode and a flowchart are developed to clarify the plan. Finally computer programs are written in C++ and Visual Basic to implement the plan and produce a solution to the problem. The important sections of the source code contain comments that relate the code to steps in the pseudo-code. While most readers will be learning or preparing to learn either C++ or BASIC, in general it is not necessary to be able to program to follow the implementation of the programs. Both C++ and BASIC computer code are sufficiently readable for non-programmer that the logic of the pseudo-code can be followed.

Those who are studying programming and/or have access to C++ or Visual Basic programming environment will want to duplicate the solutions to the problems presented. The C++ source code for this text has been generated using Visual C++ Ver. 6 but will run equally well on Turbo-C++ or on a UNIX system. The Visual Basic code was written using Visual Basic Ver. 6. Both Visual C++ and Visual Basic are included in Visual Studio Ver. 6

Consequently this text is intended for two groups. First, those who are attempting to expand their ability to solve problems by making use of the processing power of a computer. Commonly this would be a student in an introduction to programming logic class but might also might be a self-study individual attempting to maximize the usefulness of his computer. Second, students currently in a C, C++, or BASIC programming class should use this text as a supplement to their programming textbook in order to get the maximum utility from their study of programming.

Logical Problem Solving: Before the Flowchart is concerned with methods for discovering creative approaches and solutions for problems that the reader has never been taught to solve. It uses C++ and BASIC to implement those solutions and to demonstrate that the method leads to success and a solution. It is not a text for learning how to program or even how to create flowcharts or write pseudo-code but will effectively supplement programming books.

THE WEBSITE

To supplement this text Prentice-Hall has built a website to serve as a central repository for material that support and enhance this text. The URL for the website is www.prenhall.com/lamey.

For instructors using Logical Problem Solving as the core of a problem solving class, a sample syllabus is provided. For both problem solving classes and programming classes using the text as a supplemental work, the entire text has been converted to PowerPoint presentations. The problem solving lessons that are detailed in the following chapters are presented in outline form allowing instructors to add insight and explanation as the Rules and the problems are introduced.

Chapter objectives are posted as well as practice problems and Internet hyperlinks to problem solving related sites. Some of these sites address problem solving in general and some address the more traditional problems solved in this text. As might be expected there are often many ways to solve any particular problem.

THE RULES

The core of this text is the set of rules for solving problems. The rules represent a heuristic rather than an algorithm for problem solving. Obviously there is no formula that can be applied universally to every problem. Instead the rules represent a set of approaches and guidelines that can lead a problem solver in the direction of a solution.

For example, rule one states that it is critically important to be clear about the information that is available for solving the problem and exactly what the end point of the problem is. While this would appear obvious on the surface, ignoring this rule will usually leave the problem solver with inadequate information and no sure end where the problem can be considered solved. In many cases merely restating the problem can bring enough clarity that a solution becomes apparent. Better still, making a list of known facts about the problem can make clear valuable information that was less obvious in the original problem statement.

None of the rules or even all of them combined will create a guaranteed formula for solving any given problem. Creative thought cannot be reduced to an equation. However, the rules do represent a set of approaches that steer the problem solver to that critical moment of insight when a plan forms linking initial conditions to the problem solution.

EXPERIENCE

The second element in problem solving is the experience gained in previously solved problems. Everyone in every endeavor begins as a novice. Experience is accumulated slowly as progressively more difficult problems are encountered and solved. Experience includes the both the work of the problem solver and the problems that the problem solver has encountered that were solved by others. Sir Isaac Newton pointed out. "If I have seen farther (than you and Descartes), it is by standing upon the shoulders of Giants."1 Problem solving is similar to playing an instrument, playing a sport, or playing chess. One individual may have greater initial ability than another but practice and experience always bring improvement. Just as no one starts playing in a symphony orchestra or playing in the Olympics, problem solvers begin with simpler problems involving straightforward problems requiring few steps. With practice more complex problems can often be seen as adaptations or expansions of previously solved problems.

This text begins with simple problems that can be solved quickly by applying the most elemental rules. As experience in problem solving is gained more rules are introduced and the level of complexity of the problems increases. Already solved problems maybe used as a single steps in finding the solutions to larger or more general problems.

Many of the early problems are simplified versions of more general problems that were intentionally limited in order to find a partial solution. Partial solutions are often more useful than no solution at all. Chapter seven considers more general problems and is dedicated to removing the limits that were imposed on problem considered in earlier chapters.

THE BIG PICTURE

Problem solving is an accumulative effort. The more the skill is practiced the greater it grows. To keep the examples simple, i.e. short, many of the examples in this book were taken from the fields of mathematics, physics, and data acquisition. But problem solving is a general skill that, once learned and practiced, pays dividends in almost every field.

Biologists need to know why a given cell will not multiply in a given culture or how the three-dimensional structure of a protein can be determined. Bankers need to determine whether the value of a loan can be recovered if a company fails. Any one who ever takes a chance would like to have some idea what the odds for success are. Truck drivers need to know how to minimize time and cost, and maximize their profit. For some problems the solution is a matter of experience rather than a computer program but the problem solving, maybe through trial and error, is the same.

Learning the rules presented in the following chapters and analyzing the problems presented will lead the reader to a general and valuable skill. It is a skill that will stay with you and pay dividends in widely diverse areas and in unexpected places. Good luck and go forward.

Acknowledgments

It is reasonable and proper to acknowledge several individuals who have contributed insight, effort, or support to the creation of this text.

David Wilhelm of the University of California provided the necessary skill at integral calculus for the creation of Appendix C. His integration of the ellipse described in Problem 6.6 is clear, complete, and creative.

My technical assistants, Brett Jungels and Jie Chi of Purdue University, saved me hours of work by translating a significant number of my C++ solutions into Visual Basic.

Jamie Van Landuyt and Trina Zimmerman showed extraordinary patience, supporting this project through more years than it should have taken. For their endurance through numerous, unavoidable interruptions, they have my thanks.

My special thanks belongs to Bob Wilhelm whose late night discussions contributed so much insight to the formulation of this text. Tapping into his 30 years of teaching experience led to the formulation of Chapter 9 and Rule Zero.

Finally, I would like to thank the reviewers of this text: C. Robert Putnam, California State University Northridge, Mary Veronica Kolesar, Utah State University, Lynn Kelly, New Mexico State University.

Updates

Submit Errata