Pierre's microwave has keys to input reheating time, with possible positive times described by the set K . For instance, we could have K=\{1,10,60\} . Pierre is wondering what the minimum number of keys to press to input the time t . Each key can be pressed multiple times. For example, the minimum number of keys to press for a time t=25 is 7 : pressing 10 twice and pressing 1 five times. In order to solve this problem, we decompose the problem into subproblems defined as minPresses[t]= {the minimum number of key presses required to input a time t using keys from K }.
Give a recurrence relation for minPresses by giving all cases in the expression minPresses[t] = \begin{cases} ext{first case}\ \dots\ ext{last case},
\end{cases} . (Recall that a recurrence relation needs at least one base case and one general case.)

Question

Pierre's microwave has keys to input reheating time, with possible positive times described by the set   K . For instance, we could have   K=\{1,10,60\} . Pierre is wondering what the minimum number of keys to press to input the time   t . Each key can be pressed multiple times. For example, the minimum number of keys to press for a time   t=25  is   7 : pressing   10  twice and pressing   1  five times. In order to solve this problem, we decompose the problem into subproblems defined as   minPresses[t]=  {the minimum number of key presses required to input a time t using keys from   K }. 
 Give a recurrence relation for   minPresses  by giving all cases in the expression   minPresses[t] = \begin{cases} 	ext{first case}\ \dots\ 	ext{last case},
\end{cases}  . (Recall that a recurrence relation needs at least one base case and one general case.)

Answer

minPresses[t] = 1 	ext{ if } t=30

Answer

minPresses[t] = 0 	ext{ if } t\leq0

Answer

minPresses[t] = \min_{k \in K}(minPresses[t-k]) +1	ext{ otherwise.}

Answer

minPresses[t] = 30 	ext{ if } t=30

Answer

minPresses[t] = \max_{k \in K}(minPresses[t-k]) +1	ext{ otherwise.}

Answer

minPresses[t] = \max_{k \in K}(minPresses[t-k] + 1) 	ext{ otherwise.}

Answer

minPresses[t] = 1 	ext{ if } t=0

Answer

minPresses[t] = \sum_{k\in K}(minPresses[t-k] ) 	ext{ otherwise.}

Answer

minPresses[t] = \infty  	ext{ if } t < 0

Answer

minPresses[t] = \infty  	ext{ if } t \leq 0

Answer

minPresses[t] = 0 	ext{ if } t=0

Answer

minPresses[t] = \sum_{k \in K}(minPresses[t-k] ) + 1 	ext{ otherwise.}

Answer

minPresses[t] = \min_{k \in K}(minPresses[t-k]) 	ext{ otherwise.}

Answer

minPresses[t] = 1 	ext{ if } t\leq0

Crowdly

Pierre's microwave has keys to input reheating time, with possible positive time...

Want instant access to all verified answers on learning.monash.edu?