Problem-solving and program design - INFOTECH 100



Problem-solving and program designOutline the steps in problem-solvingIf you research the topic of Problem Solving by using either the internet or any reputable text book, most likely you will see the number of procedures range from probably four (4) to seven (7) steps. For example, you may come across the following seven (7) main steps when trying to solve a problem:Step 1.??? Define the Problem?Step 2.??? Analyze the ProblemStep 3.? ? Identifying Possible Solutions?Step 4.??? Selecting the Best SolutionsStep 5.??? Evaluating Solutions?Step 6.??? Develop an Action PlanStep 7.??? Implement the SolutionThe above seven steps above may be merged into four steps as follows:Step 1. Define the Problem?State the problem clearly.* Try to state the problem in your own words* Write down what are you trying to find out or supposed to do*?Describe what data is input and what information is output* Draw an INPUT-PROCESSING-OUTPUT (IPO) diagram* Describe what calculations are needed that use the input to produce the outputStep 2.??Identify and evaluate possible solutionsThis involves selecting the best solutions* Look for a pattern.* Examine related problems, and determine if the same technique can be applied.* Examine a simpler or special case of the problem to gain insight into the solution of the original problem.Step 3. Develop and represent the algorithm?? Develop a solution that is general in nature.*?Make a table.* Make a diagram (such as an algorithm).* Work backward.* Work the problem by hand (with a calculator or a using a trace table) for a specific set of data.Step 4. Test the solution with a variety of data to validate that you are solution correct to the problem given.Ensure that you include error messages for data that is not expected on input or in processing that may cause the program to crash?Here is another set of steps on the phases. Can you place the following three steps into the four step above?Problem-Solving Phase1.?Analysis and specification.(Define problem and what solution must do.)2. General solution (algorithm).(Develop logical sequence of steps to solve problem.)3. Verify.(follow steps - by hand.)Implementation?Phase1.?Specific solution (program).(Translate algorithm to code.)2. Test.(Check computed results manually.)Maintenance Phase1. Use the program.2. Maintain.(Modify to meet changed requirements or to correct errors.)Decompose a simple problem into its significant partsInput, Process, Output, StorageInputEntering data from an external source into the system can be achieved?either:1. Manually using keyboards which are often used to enter data into a system, or2. Automatically, where data can be entered into the system using hardware such as OMR, microphone, or sensors.ProcessingOnce this data is entered, it can be processed, meaning you can:– Search?– Sort, and?– Perform Calculations on the dataProcessing data is important as it leads to useful output from the system.OutputAfter the data is processed into information, it can be presented in different ways for the user, such as:– Printed to an output device such as a printer or fax (Hardcopy)– Printed on the screen (softcopy)– Sound (such as the sounds from ATMs when you are making a transaction or the sound from the cash register)– Light, (flashing lights on an ambulance; a flashing light to take your money or card from the ATM)?– Can you think of any more ways to output information?Output essentially deals with any data that is leaving the system.StorageIf data doesn’t need to be output immediately after processing it may be saved for later use?on a storage medium such as a hard drive.Also, stored data may be accessed to be processed with new data to output more information.Note the unique qualities of storage mediums such as CDs and Disk Drives. They can be input devices when data is being stored on them, but they become output devices when data is required from these devices.3. Distinguish between variables and constants? ??Variables and ConstantsThe ability to manipulate variables is one of the most powerful features of a programming language.Let's explain variables and constants by first understanding something that you are hopefully familiar with.Suppose each week Janus and Kikiyo go to a particular room in a building for a meeting. The room is the same location ?with the same furniture and may even have a name, such as Room LT4.Each week when they go to the meeting, Janus may or may not sit in the same seat since Kikiyo or someone else who got there earlier may have taken that seat, so Janus sits somewhere else.SO! The room LT4 is a?constant. It is located in the same place for the duration of your meeting.While, where Janus, Kikiyo and the other sit?varies. Their seats are?variable?each week when they go to the meeting. Sometimes Janus or Kikiyo or someone else may miss the meeting. Janus, Kikiyo and the other people have names but their seat location in the weekly meeting is what varies.In Pascal terms, the syllabus states that :a?variable?is an area of storage whose value can change during processing. In our example the variable is the seat locationa?constant?can contain a value that never changes during the processing of the program. In our example the constant is the room.VariablesProgrammers generally choose names for the variables that are meaningful. That is, the programmer uses a variable that indicates what the variable is used for. It is good programming practice to use meaningful variable names that suggest what they represent, since this makes the program more readable and easier to understand.For example:Tax, FirstName, DeptCode, SeatNo, HoursWorked,?and so on.The assignment statement creates a new variable and assigns them values. For example, in Pascal the following assignment statements are valid:SeatNo?:=?'Janus';HoursWorked?:=?35;Please note the following in every assignment statement:the variable to be assigned a value must appear on the left of the assignment operatorthe assignment operator is?:=a legal expression (value to be assigned) must appear on the right?ConstantsA constant represents a value that does not change for the duration of the program. So, for example, in Pascal , a value of 25% or .25 will be assigned to the variable Tax. However, Tax cannot change to any other percentage while the program is being run.Const Tax?=?0.25; {to represent 25 %}Note the use of the equal sign for the Constant Declaration.4. Use appropriate data types?Problem 1?Write an algorithm and draw a flowchart that reads two values, determines the largest value and prints the largest value with an identifying message.ALGORITHMStep 1:? ? Input VALUE1, VALUE2Step 2: ? if (VALUE1 > VALUE2) then? ? ? ? ? ? ? ? ?MAX = VALUE1? ? ? ? ? ? ? ?else?? ? ? ? ? ? ? ? ? ?MAX = VALUE2? ? ? ? ? ? ?endifStep 3: ? Print “The largest value is”, MAXFlowchart?Problem 2Write an algorithm and draw a flowchart to convert the length in feet to centimeter.??AlgorithmInput the length in feet (Len_FT)Calculate the length in cm (Lcm) by multiplying Len_FT by 30Print length in cm (Len_CM)??Pseudocode:?Step 1:? Input?Len_FTStep 2: ? Len_CM?Step 3: ? Print Len_CM??FlowchartProblem 3Write an algorithm and draw a flowchart that will read the two sides of a rectangle and calculate its area.AlgorithmInput the width (W) and Length (L) of a rectangleCalculate the area (Area) by multiplying L with WPrint Area?PseudocodeStep 1: ? Input W, LStep 2: ? Area = W * LStep 3: ? Print AreaFlowchart5. Explain the concept of algorithms?Algorithms and flowcharts?Using our steps in problem solving, a typical programming task can be divided into two phases:?1. Problem solving phaseThis phase is where you produce an algorithm ( an ordered sequence of steps) that describe solution of problem?2. Implementation phaseThis phase is where you implement the program in some programming language, in this case, Pascal.?Steps in Problem Solving?First produce a general?algorithm?An algorithm as a set or list of instructions for carrying out?some process step by step until it reaches the end of the algorithm.?A?recipe?in a cookbook is an excellent example of an?algorithm. So, the recipe includes the ingredients and the?method of cooking until you (hopefully) end up with a nice dish!?An example of an algorithm?people use would be a recipe:4 extra large eggs, beaten?1&1/2 C. stock?1/2 teaspoon salt?1 onion, minced?1 C. tuna flakes?1 t. soy sauce?1 Tablespoon oil?Mix all the ingredients, except the oil, in a deep bowlPut 1" water in wide pot, then place deep bowl of batter inside the potCover pot tightly and steam 15 min.Heat oil very hot and pour over custardSteam 5 more min.Serves 4 people?Examples of AlgorithmsAlgorithms can be represented as:Pseudocode - English like words that specify the sequence of steps in an algorithmFlowcharts - a graphical tool using standard symbols to show the sequence of steps in an algorithm?So whether you use pseudocode or flowcharts to expand your algorithm, here is why algorithm are so useful:Every algorithm must have an end, so there must be a set of steps followed in that algortihm to reach the end. For example, you follow the steps of the recipe to reach the end which is your dish that is ready to eat!Every instruction should therefore be clear, with short instructions and easily understoodThe instructions should be in a sequence from top to bottom. Using the example recipe above, you follow the instructions from step 1 to step 5.?To illustrate how we use algorithms (pseudocode and flowcharts) to a programming problem, let us use an example:?Example 1:Write an algorithm to determine a student’s final grade and indicate whether the student has passed or failed. The final grade is calculated as the average of four marks.?PseudocodeRemember, pseudocode is very similar to everyday English, which helps programmers develop their algorithms.Refine the pseudocode successively to get step by step detailed statements that are easy to understandPseudocode: First try?List the tasks that need to be performed. You can also use an IPO chart to help you:INPUTPROCESSINGOUTPUTM1,?M2,?M3,?M4calculate GRADE (average)as (M1+M2+M3+M4)/4Compare GRADE (less than 50)Print Message FAIL or PASSInput a set of 4 marks?Calculate their average by summing and dividing by 4?if average is below 50? Print “FAIL”else? Print “PASS”Detailed PseudocodeInput M1,M2,M3,M4GRADE = (M1+M2+M3+M4)/4If (GRADE < 50)Then? ? ? ? ?Print “FAIL”?Else? ? ? ? ?Print “PASS”EndifFlowcharts?Now we can also transform the pseudocode to a flowchart.?A flowchart is a graphical representation of the algorithm (again, a sequence of instructions that reach an end). Different symbols are used to draw each type of flowchart.?Flowcharts show how data flows from the input of data through the computer to final output or storage (note the IPOS diagram in a previous section).A Flowchartshows logic of an algorithm?emphasizes individual steps and flow of data from one action to the next?Flowcharting guidelines?The flowchart?should?flow from top to bottomEach symbol is connecting by lines that have arrows (not lines alone)Avoid having flow lines crossing each otherEach symbol has at least one flow line entering it and another one leaving it, except for the START and STOP symbols.The decision symbol has two exit points; these can be on the sides or the bottom?and one side (See the decision above for 'Is Grade < 50?')Use meaningful phrases in the symbolsIdentify ways of representing algorithms?Representation of algorithmsRepresent of Algorithms as Pseudocode and Flow ChartsDesign an algorithm and the corresponding flowchart for adding the test?scores as given below:?29, 38, 97, 85, 52, 55?Pseudocode? ? ? ? ? ? ? ? ? ? 1. Start? ? ? ? ? ? ? ? ? ? 2. Total = 0?? ? ? ? ? ? ? ? ? ? 3. Get the first testscore?? ? ? ? ? ? ? ? ? ? 4. Add first testscore to Total? ? ? ? ? ? ? ? ? ? 5. Get the second testscore?? ? ? ? ? ? ? ? ? ? 6. Add to Total? ? ? ? ? ? ? ? ? ? 7. Get the third testscore?? ? ? ? ? ? ? ? ? ? 8. Add to Total? ? ? ? ? ? ? ? ? ? 9. Get the Forth testscore?? ? ? ? ? ? ? ? ? ?10. Add to Total? ? ? ? ? ? ? ? ? ?11. Get the fifth testscore?? ? ? ? ? ? ? ? ? ?12. Add to Total? ? ? ? ? ? ? ? ? ?13. Get the sixth testscore?? ? ? ? ? ? ? ? ? ?14. Add to Total? ? ? ? ? ? ? ? ? 15. Output the Total? ? ? ? ? ? ? ? ? 16. StopRelated Flow chartThe example 1, algorithms (pseudocode and flowchart) illustrate the steps for solving the problem of?adding six testscores. Where one testscore is added to Total at a time.Note that the flowchart should have a Start step at the beginning and at least one stop step at the end.?Since we want the sum of six testscores, then we should have a?variable?to store the resulting?sum after each addition. In this example, the container is called?Total?and we make sure that?Total?should start?with a zero value by step 2.LOOPSFor loopSince we know that there are six testscores, we can can use a?FOR?loop. Here is the flowchart that uses a FOR loop:Pseudocode? ? ? ? ? ? ? ? ? ? ? ? ?1. Start?? ? ? ? ? ? ? ? ? ? ? ? ?2. Total = 0?? ? ? ? ? ? ? ? ? ? ? ? 3. Count = 0 (to count the six testscores)? ? ? ? ? ? ? ? ? ? ? ? 4. If the Count = 6, go to step 7?? ? ? ? ? ? ? ? ? ? ? ? 5. Get a testscore? ? ? ? ? ? ? ? ? ? ? ?6. Add the testscore to Total (Total = Total + testscore)?? ? ? ? ? ? ? ? ? ? ? ?7. Add 1 to the Count?? ? ? ? ? ? ? ? ? ? ? ?8. Go to step 4 to get next testscore? ? ? ? ? ? ? ? ? ? ? ?7. Output the Total? ? ? ? ? ? ? ? ? ? ? ?8. Stop?FlowchartWhile LoopHere is another way, we need to add a last number to the list of numbers given. This number should be special, so unique so?that each time we get a testscore, we test it to see if we have reached that special, unique number. Common numbers are -1, or 99. In this example, since we are using testscores, it may not be wise to use 99 as the unique number to stop the program.Pseudocode? ? ? ? ? ? ? ? ? ? ?1. Start?? ? ? ? ? ? ? ? ? ? ?2. Total = 0?? ? ? ? ? ? ? ? ? ? 3. Get a testscore? ? ? ? ? ? ? ? ? ? 4. If the testscore is equal to -1, go to step 7?? ? ? ? ? ? ? ? ? ? 5. Add to testscore ( Total = Total + testscore)?? ? ? ? ? ? ? ? ? ? 6. Go to step 3 to get next testscore? ? ? ? ? ? ? ? ? ? 7. Output the Total? ? ? ? ? ? ? ? ? ? 8. StopFlowchartIn this flowchart we use a?While?loop. While we have not entered that special unique testscore of -1, the user is prompted to enter another testscore.TRUTH TABLESBoolean Operators:? ANDWhen using the?AND?Operator, both expressions must be TRUE for the compound expression to be true.If (expression1)?AND?(expression2)THEN? Output?(‘Both expressions are true’);So if?a?is 4 and?b?is 2Then?(a <= 2) AND (b = 2)??Evaluates to(4 <= 2) AND (2 = 2)FALSE AND TRUEFALSEBoolean Operators:? ORWhen using the?OR?Operator, either one expression or both expressions can be TRUE for the compound expression to be true.If (expression1)?OR?(expression2)THEN??Output?(‘One or both expressions are true’);So if?a?is 4 and?b?is 2Then(a <= 2) OR (b = 2)?(4 <= 2) OR (2 = 2)FALSE OR TRUETRUEBoolean Operators: NOTThe?NOT?Operator simply reverses the?boolean?value of the?boolean?expression that appears immediately to its right.If NOT (expression)THEN??writeln(‘This expression?is FALSE’);So if?a?is 4 and?b?is 2ThenNOT ((a <= 2) OR (b = 2) ) will evaluate toNOT (4 <= 2) OR (2 = 2))NOT (FALSE OR TRUE)NOT (TRUE)to FALSE.??Precedence of Arithmetic OperatorsPriority???????????????? ? Operator(s)1st ? ? ? ? ? ? ? ? ? ? ? ? ? ? NOT2nd ? ? ? ? ? ? ? ? ? ? ? ? ? ?AND, *, /3rd ? ? ? ? ? ? ? ? ? ? ? ? ? OR, +, -4th ? ? ? ? ? ? ? ? ? ? ? ? ? ?=, <>, >, <, >=, <=Truth TablesNegation~pFTTF?ANDHere?both?statements are truepANDqp AND qT?TTT?FFF?TFF?FFConditional StatementRelational Operators compare two values. Let us assume that the values?A?and?B?contain two numbers. We can compare the two values as follows:NAMESYMBOL?MEANINGGreater thanA > B"A" is greater than BGreater-than or equalA >= B "A" is Greater-than or equal to "B" EqualsA = B "A" equals Bnot-equals"A" <> "B""A" does not equal "B"?Less-than"A" < "B"?"A" is Less than "B"Less-equal"A" <= "B"?"A" is less than or equal to "B"?Making decisionsConditional Statements are used to help with decisions that can be made based on the results of comparing two values. For example, the expression?A>B?is a logical expression. It describes a condition we want to test.?So:if A>B is true (if A is greater than B) we take one action, such as?print the value of Aif A>B is false (if A is not greater than B) we take another action, such as?print the value of BThe algorithm for conditional statements are shown below:If condition? then? true alternative? else? false alternativeendifAn algorithm for the conditional statement is:? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? If A>B?then? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? print A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?else? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?print B? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?endif?IF-THEN StatementIF (Boolean expression) THEN? STATEMENT;?In evaluating the?Boolean expression, ?If it is TRUE then the STATEMENT is executed.? If it is FALSE then the STATEMENT is skipped.??IF-THEN-ELSE StatementIF (Boolean expression) THEN? STATEMENT1ELSE? ?STATEMENT2;In evaluating the?Boolean expression,?If it is TRUE then? STATEMENT1 is executed.? If it is FALSE then STATEMENT2 is executed.Develop algorithms to solve simple?problems;Solving Simple problemsProblem 1?Write an algorithm and draw a flowchart that reads two values, determines the largest value and prints the largest value with an identifying message.ALGORITHMStep 1:? ? Input VALUE1, VALUE2Step 2: ? if (VALUE1 > VALUE2) then? ? ? ? ? ? ? ? ?MAX = VALUE1? ? ? ? ? ? ? ?else?? ? ? ? ? ? ? ? ? ?MAX = VALUE2? ? ? ? ? ? ?endifStep 3: ? Print “The largest value is”, MAXFlowchart?Problem 2Write an algorithm and draw a flowchart to convert the length in feet to centimeter.??AlgorithmInput the length in feet (Len_FT)Calculate the length in cm (Lcm) by multiplying Len_FT by 30Print length in cm (Len_CM)??Pseudocode:?Step 1:? Input?Len_FTStep 2: ? Len_CM?Step 3: ? Print Len_CM??FlowchartProblem 3Write an algorithm and draw a flowchart that will read the two sides of a rectangle and calculate its area.AlgorithmInput the width (W) and Length (L) of a rectangleCalculate the area (Area) by multiplying L with WPrint Area?PseudocodeStep 1: ? Input W, LStep 2: ? Area = W * LStep 3: ? Print AreaFlowchart8. Test Algorithm for correctnessTrace tablesA trace table is a useful technique used to test an algorithm with data to make sure that program does what it is supposed to do and no logical errors occurThe best way to use a trace table is through manual tracing or a dry run of the program statements.?Advantages of using a trace table include:Checking the sequence of steps of the program algorithm or code before you execute the codelocate errors in your algorithm or program code?Let us use some program code below along with a trace table for all the variables and outputs.Program Codey = 3For?x?=1to4? ? ? ? y?=?y?+?xLoopPrint (y)Trace Tablexyoutput13?24?36?49?41313Many times a question on trace tables will ask you to complete the table which will include headings and some values to use as input with sometimes a few values as output.Note the variables in the headings will also be found in the fragment of code givenFill in all values that are input to the variables in the columnsFill in all outputs from the statementsGo through EACH LINE of the programUse the top down approach to problem -down Design ApproachA problem may seem impossible to solve because at first glance it can be very plex problems can be solved using top-down design, also called stepwise refinement, where?We divide the problem into sub-problems (smaller parts)Then break those sub-problems into smaller partsSoon, it is easy to solve the small easy problemsThen the program as a whole will be solved?Advantages of Top-Down DesignSub-dividing the problem into parts helps clarify what needs to be done.At each step of refinement, the new sub-tasks become less complicated and, therefore, easier to program.Parts of the solution may turn out to be used in other parts of the programSubdividing the problem into sub-parts allows more than one person to work on the solution.??Example of Top-Down DesignProblem:Make some bakesUnfortunately, stating the problem isn't enough to actually make any bakes, we need to break the task down:Make some bakesOrganise KitchenMake bakesServeEach of these tasks can then be broken down further:Organise KitchenClean surfacesGet out mixing bowl, whisk, spoon, sieveGet out flour, sugar, salt, eggs, milk, butterPut on apronMake bakesSift salt and flour into bowlAdd sugarMix dry ingredientscream butter into dry ingredients until the mixture resembles breadcrumbsAdd water (milk is optional)Mix well. Add flour so that the batter is not too stickyCookServeAnd each of these tasks can be broken down further, let us take a look at the Cook:Fry BakesHeat pan to right temperatureScoop tablespoon of batterSpoon scoops of batter into panWhen brown, flip bakesRemove, when both sides are brown?Place bakes on paper towels or on rackWe can break down some of these tasks even further.So starting at a single point, making bakes, we have broken down the task into it individual parts. ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download