Message Boards Message Boards

0
|
7271 Views
|
4 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Pseudocode, Recursion and Min. Search / Beginners

Posted 10 years ago

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 :)

POSTED BY: Frida Ferdandez
4 Replies
Posted 10 years ago

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

POSTED BY: Luis Ledesma
Posted 10 years ago

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

POSTED BY: Frida Ferdandez
Posted 10 years ago

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

POSTED BY: Luis Ledesma
Posted 10 years ago

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.

POSTED BY: Frida Ferdandez
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract