Quiz 9
Discrete Mathematics · 2 problems · solutions hidden, click to reveal
Flashcards
Problems
Give an iterative algorithm that, on input a nonnegative integer \(n\) and an integer \(x\), computes \(x^n\) using only multiplication.
Show solution
Answer: a := 1; for i = 1 to n: a := a * x; return a.
Start with \(a = 1\) and multiply by \(x\) a total of \(n\) times:
Func f(x, n):
a := 1
for i = 1 to n:
a := a * x
return a
Func f(x, n):
a := 1
for i = 1 to n:
a := a * x
return a
Consider the program segment (with \(y\) an integer):
while y < 0
y := y + 1
(a) Determine all possible values of \(y\) after execution. (b) Justify using the loop invariant \(p\): "\(y\) is an integer."
while y < 0
y := y + 1
(a) Determine all possible values of \(y\) after execution. (b) Justify using the loop invariant \(p\): "\(y\) is an integer."
Show solution
Answer: All nonnegative integers.
Let \(C\): \(y < 0\) and \(S\): \(y := y+1\). If \(y\) is an integer then \(y+1\) is too, so \(p \land C\,\{S\}\,p\) holds; thus \(p\,\{\text{while } C \text{ do } S\}\,p \land \neg C\). After execution \(p \land \neg C\) holds: \(y\) is an integer and \(y \ge 0\), i.e. \(y\) is a nonnegative integer. Conversely every nonnegative integer is achievable (if \(y\) starts \(\ge 0\) the loop never runs). So the possible final values are exactly the nonnegative integers.