Exercise 11.3 Class 9 - Chapter 11 Ganita Manjari NCERT Solutions - Exercise Set 11.3

part 2 - Ex 11.3, 1 - Exercise Set 11.3 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 3 - Ex 11.3, 1 - Exercise Set 11.3 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

part 4 - Ex 11.3, 1 - Exercise Set 11.3 - Chapter 11 Class 9 - The World of Algorithms (Ganita Manjari) - Maths Class 9

Remove Ads
Teachoo Β· Class 9 Explore Class 9

Transcript

Ex 11.3, 1 How would our original algorithm change if we computed the divisors of n by examining the numbers from 1 to n in reverse order, from n down to 1? Previously, we checked candidates in increasing order: 1, 2, 3,…,𝑛 Appending each successful candidate produced an increasing divisor list. If we instead check: 𝒏,π’βˆ’πŸ,π’βˆ’πŸ,…,𝟏 and continue appending successful candidates to the end, the list will be decreasing. Example: Divisors of 18 We examine 18, 17, . . , 1 . The successful candidates appear in this order: 18, 9, 6, 3, 2, 1 Therefore: divisors (πŸπŸ–)=[18, 9, 6, 3, 2, 1] Similarly: divisors (πŸπŸ’)=[24, 12, 8, 6, 4, 3, 2, 1] Now examine the divisors of 18 in order and retain those appearing in the list for 24 We examine 18, 17, . . , 1 The successful candidates appear in this order: 18, 9, 6, 3, 2, 1 Therefore: divisors (πŸπŸ–)=[18, 9, 6, 3, 2, 1] Similarly: divisors (πŸπŸ’)=[24, 12, 8, 6, 4, 3, 2, 1] Now examine the divisors of 18 in order and retain those appearing in the list for 24 The greatest common divisor is now the leftmost entry. 𝐠𝐜𝐝(πŸπŸ–,πŸπŸ’)=πŸ” Required change to the original GCD algorithm Replace: Report the rightmost entry of common-divisors. with: Report the leftmost entry of common-divisors. The remaining list-comparison steps can stay the same. If we continued choosing the rightmost entry, we would incorrectly report 1. Divisor of 18 | Also a divisor of 24? | Common-divisor list 18 | No | [] 9 | No | [] 6 | Yes | [6] 3 | Yes | [6, 3] 2 | Yes | [6, 3, 2] 1 | Yes | [6, 3, 2, 1] Report the rightmost entry of common-divisors. with: Report the leftmost entry of common-divisors. The remaining list-comparison steps can stay the same. If we continued choosing the rightmost entry, we would incorrectly report 1.

CA Maninder Singh's photo - Co-founder, Teachoo

Made by

CA Maninder Singh

CA Maninder Singh is a Chartered Accountant qualified since 2010 and an educator teaching since 2006. At Teachoo, he draws on his accounting and tax experience to explain Accounts, Income Tax and GST through step-by-step lessons and practical examples.

For an uninterrupted learning experience, students can use Teachoo Black to remove ads and focus better.