ways to make change
03-05-2019, 10:17 PM
Post: #6
 Albert Chan Senior Member Posts: 2,643 Joined: Jul 2018
RE: ways to make change
We could also build ways formula from 5 points: x%100, x%100 + 1, ... x%100 + 4
Formula is good for cents = n * 100 + x%100

Example, if x%100 = 0, we have dollars ways formula

Code:
1    292  2435 9590  26517 ; forward diff = 5 coins ways, 0 to 4 dollars 291  2143 7155 16927 1852 5012 9772 3160 4760 1600

PNDQH ways ﻿ ﻿ = $$1\binom{n}{0}+291\binom{n}{1}+1852\binom{n}{2}+3160\binom{n}{3}+ 1600\binom{n}{4}$$
PNDQHB ways = $$1\binom{n+1}{1}+291\binom{n+1}{2}+1852\binom{n+1}{3}+3160\binom{n+1}{4}+ 1600\binom{n+1}{5}$$

Or, use Horner's rule:
PNDQH ways ﻿ ﻿ = ((((200n + 380)n + 238)n + 55)n + 3) / 3
PNDQHB ways = (((((80n + 390)n + 672)n + 483)n + 127)n + 6) / 6

Example, using either set of formulas, for n = 1000 dollars:

PNDQH ways ﻿ ﻿ = 66 793412 685001
PNDQHB ways = 13398 445413 854501
 « Next Oldest | Next Newest »

 Messages In This Thread ways to make change - Albert Chan - 03-02-2019, 05:37 PM RE: ways to make change - Albert Chan - 03-02-2019, 06:58 PM RE: ways to make change - Albert Chan - 03-02-2019, 10:33 PM RE: ways to make change - Albert Chan - 03-03-2019, 06:05 PM RE: ways to make change - Albert Chan - 03-04-2019, 04:31 PM RE: ways to make change - Albert Chan - 03-05-2019 10:17 PM

User(s) browsing this thread: 1 Guest(s)