☰ Contents · Computing

Mixed algorithms

Lessons 18 · 1 lessons · M. R. Fayziyeva, D. M. Sayfurov, N. S. Xaytullayeva. Informatics and Information Technologies, Grade 9. “Nashriyot uyi Tasvir”, Tashkent, 2020
18

Mixed (combined) algorithms

Textbook: pp. 44–46
GoalKnows what a mixed (combined) algorithm contains; writes algorithms for counting, finding the GCD and solving a quadratic equation in words.
New words
mixed (combined) algorithm: an algorithm that uses several of the basic structures together · aralash algoritmcounter: a variable that grows by 1 each time something is counted · hisoblagichdiscriminant: D = b² – 4ac, which decides how many roots a quadratic equation has · diskriminantEuclid’s algorithm: finds the greatest common divisor by repeated subtraction or division with remainder · Yevklid algoritmi
Explanation

A mixed algorithm uses linear, branching and repeating structures together; most real algorithms are like this. In a counting problem the counter K starts at 0, a loop looks at each element, a branch checks whether the element meets the condition, and if it does K = K + 1 is done. Euclid’s algorithm consists of a loop and a branch: while A ≠ B the smaller number is subtracted from the larger; when A = B that number is the GCD. For the quadratic equation ax² + bx + c = 0 (a ≠ 0) we first compute D = b² – 4ac: if D < 0 there is no real root; if D = 0 there is one root x = –b / (2a); if D > 0 there are two roots x₁,₂ = (–b ± √D) / (2a). Here the branching separates the kinds of solution. In the flowchart of a mixed algorithm an arrow can go back up after a rhombus to form a loop.

Worked examples
Counting the positive numbers. Algorithm: start; K = 0; for i from 1 to 6: input x; if x > 0 then K = K + 1; output K. For the inputs 3, –2, 0, 5, 8, –1, K is 1, 1, 1, 2, 3, 3. Answer: 3.
In x² – 5x + 6 = 0 we have a = 1, b = –5, c = 6. D = 25 – 24 = 1 > 0, so there are two roots: x₁ = (5 + 1) / 2 = 3, x₂ = (5 – 1) / 2 = 2. In x² – 4x + 4 = 0, D = 16 – 16 = 0, so there is one root x = 4 / 2 = 2.
Class activity

“The counter”: the class counts those wearing glasses, those wearing blue clothes and so on: one student checks each person at the “rhombus”, another keeps the counter K.

Practice
1
What kind of algorithm is called mixed?
2
How many positive numbers are there among 4, –3, 7, –8, 2? Find the final value of the counter K.
3
Find the GCD of 56 and 42 by subtraction.
4
Why does the quadratic-equation algorithm need branching?