Old CCC question

[Martin]

Seriously, if you want to get really good at programming, go to http://ace.delos.com/usacogate first, it's a great way to learn c++, and secondly, if you can finish it, you will get first on the senior ccc I guarentee.

[Crono]

yea, catalyst ur rite, however my first proc works, guess i just wuzn't payin attention to all possible cases...

[Catalyst]

yup
i should fix mine....
...ill get to it eventually....

[Martin]

Iteratively:

code:

var nclubs : int var dist : int put "Number of clubs: " .. get nclubs put "Distance to hole: " .. get dist var club : array 1 .. nclubs of int for i : 1 .. nclubs     put "Club (", i, "): " ..     get club (i) end for var arr : array 0 .. 6000 of int for i : 0 .. 6000     arr (i) := 1542343 end for arr (0) := 0 for x : 0 .. dist     for y : 1 .. nclubs         if x + club (y) <= dist then             if arr (x) + 1 < arr (x + club (y)) then                 arr (x + club (y)) := arr (x) + 1             end if         end if     end for end for if arr (dist) = 1542343 then     put "It's raining, so Roberta short circuits and blows up the golf course." else     put "Roberta wins in ", arr (dist), " strokes" end if

[Martin]

Bugz showed me how to do this, so the bitz go to him

[Tony]

you'd have to explain

code:

if arr (x) + 1 < arr (x + club (y)) then                 arr (x + club (y)) := arr (x) + 1

whats arr? whats up with 1542343? and just what the line above means... I think the rest is understandable

[Martin]

1542343 is what happens when you press 7 random numbers on your keyboard. Arr is an array, used in the generation of the distance. The concept behind this is like so:

say, for example your input is:
Distance = 50
nclub = 4
club(1) = 4
club(2) = 5
club(3) = 20
club(4) = 36

Now, starting at 4, the least number of ways to get to 4 is 1, then the least number of ways to get to 5 is 1, you can't get to 6 or 7, then the least number of ways to get to 8 is 2 (4+4), 9 is 2 (4+5) and so on. After finding all of the ways, it just puts them together...I know it's not to detailed, but if you trace the program, it should make sense.

[Martin]

Arr(x) basically stores the minimum number of strokes to get to x

[bugzpodder]

Quote:

Bugz showed me how to do this, so the bitz go to him

before i went into this thread, i was thinking that you were about to take credit for my work! ^.^; guess i was wrong!

Darkness wrote:

Seriously, if you want to get really good at programming, go to http://ace.delos.com/usacogate first, it's a great way to learn c++, and secondly, if you can finish it, you will get first on the senior ccc I guarentee.

only if you are top 50 programmer in the world, then you are able to finish it. otherwise dont even think about it. i am still barely half-way (not even).

1542343 is only for convience. we just need a big number.

Quote:

Arr(x) basically stores the minimum number of strokes to get to x

true. but obviously 1542343 means unobtainable

btw this technique is called dynamic programming. it trades off memory for speed. a recursive method, while uses constant storage, also has exponential run-time. however, this method have only quadratic run-time with linear storage (however still very memory expansive, but can be improved with optimizations)

[Martin]

fibinacci sequence dynamically

code:

var a,b,c,n : int := 1 get n for i:3..n    c := a + b    a := b    b := c end for put c

[bugzpodder]

good memory!

recursively,

code:

fcn fib(n:int):int    if n<2 then        result 1    else        result fib(n-1)+fib(n-2)    end if end fib

[Martin]

Heh, I wrote a program to do that on my calculator. now I have to figure out how to graph them