The following flowchart represents an algorithm that processes a positive integer. (a) Trace through the flowchart for N = 16, showing the value of N and Co...
Question 1 Report
The following flowchart represents an algorithm that processes a positive integer.
(a) Trace through the flowchart for N = 16, showing the value of N and Count at each step. [4]
(b) State the output when N = 16. [1]
(c) State what this algorithm calculates for any given positive integer input. [2]
Answer Details
(a) The flowchart repeatedly divides N by 2 (integer division) and increments Count, stopping when N is no longer greater than 1:
| Iteration | N (start) | N > 1? | N DIV 2 | Count |
|---|---|---|---|---|
| Initial | 16 | - | - | 0 |
| 1 | 16 | TRUE | 8 | 1 |
| 2 | 8 | TRUE | 4 | 2 |
| 3 | 4 | TRUE | 2 | 3 |
| 4 | 2 | TRUE | 1 | 4 |
| Check | 1 | FALSE | - | 4 |
Each iteration halves N and adds 1 to Count. After 4 iterations, N reaches 1 and the loop exits. [4]
(b) The output is 4. [1]
(c) The algorithm calculates how many times N can be halved (using integer division by 2) before reaching 1. [1] For inputs that are exact powers of 2, this gives the exponent, equivalent to log base 2 of N. For example, 16 = 24, so Count = 4. For non-powers of 2, integer division still counts the halvings, but the result is the floor of log2(N). [1] [2]
Download The App On Google Playstore
Everything you need to excel in your exams
