Define a function fm: N x N ->N as follows: fm(n, k) =k if 0 ≤ n < m, and fm(n, k) =fm(n-m, k+1) otherwise. Describe in terms of a single well-known arithmetic operation what fm(n, 0) is computing.
The Answer to the Question
is below this banner.
Can't find a solution anywhere?
NEED A FAST ANSWER TO ANY QUESTION OR ASSIGNMENT?
Get the Answers Now!You will get a detailed answer to your question or assignment in the shortest time possible.
Here's the Solution to this Question
If 0 ≤ n < m, then fm(n,0) = 0
Suppose m ≤ n < 2m
fm(n, 0) = fm(n-m, 0+1)
Now m – m ≤ n - m < 2m – m
=> 0 ≤ n – m < m
=> fm(n – m, 0 + 1) – 0 + 1 = 1
=> fm(n, 0) = 1 for m ≤ n < 2m
Suppose 2m ≤ n < 3m
fm(n,0) = fm(n – m, 0 + 1)
Now 2m – m ≤ n – m < 3m – m
=> m ≤ n – m < 2m
=> fm(n – 2m, 2) = 2
=> fm(n – m, 0 + 1) = 2
=> fm(n, 0) = 2 for 2m ≤ n < 3m
And so on
In other words, fm(n, 0) is computing the quotient of n ÷ m