Lessons 14–15 · 2 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
14
Branching algorithms
Textbook: pp. 37–39
GoalKnows the ideas of a branching algorithm, a condition and a branch; writes the full and short forms of an algorithm in words and as a flowchart.
New words
branching algorithm: the steps taken depend on whether a condition is true · tarmoqlanuvchi algoritmcondition: a statement that is checked and is either true (yes) or false (no) · shartbranch: a group of instructions carried out when the condition has a certain result · tarmoqfull and short forms: with both branches (agar – u holda – aks holda) or with only one (agar – u holda) · to‘liq va qisqartirilgan ko‘rinish
Explanation
In many problems the next step depends on a condition: if the condition is true one set of actions is done, if false another. Such an algorithm is called branching; each branch is carried out at most once and only one of the two ways is chosen. The full form is written in words as “if condition, then group 1, otherwise group 2”: group 1 runs when the condition is true and group 2 when it is false. The short form has no “otherwise” part: when the condition is true the instructions run, and when it is false nothing is done and the algorithm goes on. In a flowchart the condition is written in a rhombus with “yes” and “no” lines leaving it; in the short form the “no” line goes straight back to the main path. Conditions are usually comparisons (x < 0, a = b).
Worked examples
Short form: 1) start; 2) input score; 3) if score > 90, output “Excellent”; 4) end. With score 95 “Excellent” is printed; with 70 nothing is printed.
Full form: 1) start; 2) input n; 3) if the remainder of n divided by 2 is 0, output “even”, otherwise output “odd”; 4) end. For n = 17 the remainder is 1, answer “odd”; for n = 40 the remainder is 0, answer “even”.
Class activity
“Yes–no path”: a rhombus is drawn on the floor. The teacher states a condition (“those wearing glasses”), students step to the “yes” or “no” branch and do the task there.
Practice
1
What is the difference between the full and the short branching form?
The full form has both branches (if – then – otherwise); the short form has only the “then” branch.
2
Write in words an algorithm that finds the larger of two numbers a and b.
Start; input a, b; if a > b, the result is a, otherwise the result is b; output the result; end.
3
Algorithm: if x < 0 then y = –x, otherwise y = x. What is y for x = –4?
4
4
Why are both branches of the full form not carried out at the same time?
A condition is either true or false, never both, so only one way is chosen.