 |
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|
||
|
|
||
|
|
||
|
|
|
|
|
|||||||||||||||||
Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic |
Last Thread Next Thread |
| Algorithmic Forays Part 7 |
|
 |
yzfuture Member since: 1/30/2005 From: China |
|||
 Posted - 1/30/2005 4:25:39 AM |
||||
| I got it. Thanks. |
||||
|
||||
|
ToohrVyk Member since: 9/12/2002 From: Paris, France |
|||
 Posted - 1/30/2005 2:07:24 PM |
||||
| As always, this is an excellent series of articles. However, I'd like to nitpick on the first paragraph of it: 0 is natural n is natural => n+1 is natural does not define natural numbers: it actually defines a variety of mathematical objects, inside which natural numbers as we know them are included. For instance, define alpha = beta + 1 and beta = alpha + 1, and it's impossible to prove alpha and beta aren't natural, while they aren't natural. Blog — Facebook |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 2/16/2005 4:14:04 AM |
||||
| For fibonacci numbers x[n], if you take the matrix 1 1 1 0 And consider postmultiplying by the vector [ x[n], x[n-1] ] then you can see it works out [ x[n+1], x[n] ] applied recursively. Simply diagonalise the matrix, and you have a general formula for fib numbers... :) |
||||
|
||||
|
Anonymous Poster |
|||
Posted - 7/28/2005 5:24:03 PM |
||||
| The count change problem can be implemented easier by using an iterative method using dynamic programming (related to memoization). cache [ 0 ] = 1 (rest of cache is initialised to 0) for all possible coins loop from face_value to required_amount by step 1 cache [ loop_index_value ] += cache [ loop_index_value - face_value ] When the algorithm terminates the number of ways to return change for a given value is found as cache [ required_amount ]. The algorithm runs in O(n*m), where n is number of distinct coins and m is the required amount to give change for, and it has memory consumption for the cache in O(m). |
||||
|
||||
| All times are ET (US) |
Last Thread Next Thread |
|
