Pseudocode, Recursion and Min. Search / Beginners

Questions
1

Hello everyone,

I have a little problem understanding a Pseudocode. Maybe because of the notation…

Input : k1......kn, goal k

Data : Array K := [k + 1]

begin

K[0] := 0;

for i = 1..... k do

K[i ] := 1 + minj=1....n(K[i - kj])

return K[k ]

I tried to make an example with k1=1 and k3=3 and goal k = 4

K[1] := 1 + K[1-1] folglich = K[1] := 1 + K[0]

K[2] := 1 + K[2-1] ( = K[2] := 1 + K[1] )

K[3] := 1 + K[3-1] ( = K[3] := 1 + K[2] ) = K[3] := 1 + 1 + K[1] )

and so on, but it doesn’t make sense to me. I think i understand the minj=1…n(K[i - kj] part the wrong way.
What I need exactly to understand is, what the algorithm is doing every step and how the solution Array look like.
For a little hint, i would be very thanksfull!

Best :slight_smile:

2

Hi Frida, I’d like to be able to help you to solve your problem, but not for what is the algorithm that you portray, it would be useful something of prior information, i think you are missing some points and commas at the end of the assignments, you should do something like this.:

K[1] := 1 + K[1-1] ;

folglich =  1 + K[0];

K[2] := 1 + K[2-1] ;

K[3] := 1 + K[3-1];

taking advantage of the opportunity I would like to ask you where you define k[0], since you call it and not defined, I hope your answer.

Greetings

3

After trying to understand your description of how it should be the recursion, i have come to believe that what you need is something like the following

k[0] := 0;

k[1] := 1;

k[2] := 2;

k[3] := 3;

k[n_] := 1 + k[n - 1] /; n > 3;

I tried the following values to try to make sure that works well the recursion,

Table[k[i], {i, {4, 5, 9, 13, 7, 11, 13, 17, 43, 47, 53, 59, 61, 67, 
   71}}]

I think that the following link may help you to understand more things about how to solve your problem, applied the same idea to your project.

Mathematica, Fibonacci sequence using While and Module commands

4

Hello,

first, thanks for the fast reply!

I think it’s important to say, that k1…kn are integers, and the goal k is an integer too. For example:
k1=8, k2=9, k3=12 and “goal” k=20

so i = 1,2,3,…20 and j=1,2,3.

I’m not sure what minj=1…n(K[i - kj]) is actually doing.

5

Thanks, I’ll try to find something that can help me out in your Link!