☰ Contents · Computing

Branching algorithms

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
15

Practical lesson: linear and branching algorithms

Textbook: p. 39
GoalPresents problems with linear and branching structure in words and as flowcharts; calculates the value of a function with two or three branches.
New words
two-branch function: a function given by different formulas for different conditions · ikki tarmoqli funksiyanested condition: a condition checked inside a branch of another condition · ichma-ich shartmodulus (absolute value): the distance of a number from zero, |x| · modulsign function: gives –1 for negative, 0 for zero and 1 for positive numbers · ishora funksiyasi
Explanation

Whether a problem is linear or branching depends on whether it has a condition. In a linear problem (for example, the number of tiles to cover a wall) we calculate by a formula: the wall area is divided by the area of one tile. In a branching problem (a taxi fare, the sign of a number) a condition is tested. With three cases (x < 0, x = 0, x > 0) two conditions are tested one after the other: first, if x < 0, the first formula; otherwise x = 0 is tested, and if true the second formula, if false the third. In the flowchart of such an algorithm two rhombuses follow each other. To find a value of a function, decide which condition the given x meets and use the formula of that branch.

Worked examples
A wall is 6 m × 3 m and a tile is 30 cm × 30 cm. Wall area: 600 · 300 = 180 000 cm²; tile area 900 cm²; number of tiles 180 000 / 900 = 200. This is a linear algorithm.
A taxi costs 15 000 so‘m up to 5 km and 2 000 so‘m for each extra km. Algorithm: input d; if d ≤ 5, price = 15 000, otherwise price = 15 000 + (d – 5) · 2 000. For d = 8: price = 15 000 + 3 · 2 000 = 21 000 so‘m.
Class activity

“Two rhombuses”: students “walk” through the algorithm for the sign of a number: first rhombus – negative?, second rhombus – zero?; at each branch they say the answer aloud.

Practice
1
A wall is 4 m × 2 m and a tile is 20 cm × 20 cm. How many tiles are needed?
2
Taxi fare: 15 000 so‘m up to 5 km, then 2 000 so‘m for each km. Find the fare for 9 km.
3
y = –1 (x < 0), y = 0 (x = 0), y = 1 (x > 0). Find y for x = –7 and x = 12.
4
Why is one rhombus not enough for a problem with three cases?