In section 1.2.2, SICP gives an incredibly inefficient recursive procedure for counting change and then later leaves it up to the reader to come up with a better one.
Here's what I was able to come up with (in Python because I like it better than Scheme):
def count_change(n):
n /= 5
if n%2:
b = -1
else:
b = 1
c = 1425*b + 26799 + n*(150*b + 21850 + n*(4760 + n*(380 + 10*n)))
m = n%10
if m==0 or m==1:
c -= 4224
elif m==2:
c += (576+480*n)
elif m==3 or m==8:
c -= 384
elif m==4:
c -= (1344+480*n)
elif m==5 or m==6:
c += 5376
elif m==7:
c += (7776 + 480*n)
elif m==9:
c -= (8544 + 480*n)
c /= 24000
return c
I attempted to solve the recurrence relation exactly (lots of complicated sums involving roots of unity to simplify). I haven't proven that the above is indeed correct, but it seems to work well for all the values I've tested.
O(1) for the win.
Name:
Anonymous2007-05-13 6:51 ID:3BavM5m3
Do something about these magic numbers.
Name:
Anonymous2007-05-13 7:15 ID:2OVbkhoY
>>2
Here ya go.
def count_change(n):
"""BLACK VOODOO MAGIC"""
n /= 5
if n%2:
b = -1
else:
b = 1
c = 1425*b + 26799 + n*(150*b + 21850 + n*(4760 + n*(380 + 10*n)))
m = n%10
if m==0 or m==1:
c -= 4224
elif m==2:
c += (576+480*n)
elif m==3 or m==8:
c -= 384
elif m==4:
c -= (1344+480*n)
elif m==5 or m==6:
c += 5376
elif m==7:
c += (7776 + 480*n)
elif m==9:
c -= (8544 + 480*n)
c /= 24000
return c
'''
def count_change(n):
n /= 5
if n%2:
b = -1
else:
b = 1
c = 1425*b + 26799 + n*(150*b + 21850 + n*(4760 + n*(380 + 10*n)))
m = n%10
if m==0 or m==1:
c -= 4224
elif m==2:
c += (576+480*n)
elif m==3 or m==8:
c -= 384
elif m==4:
c -= (1344+480*n)
elif m==5 or m==6:
c += 5376
elif m==7:
c += (7776 + 480*n)
elif m==9:
c -= (8544 + 480*n)
c /= 24000
return c
'''
Hi, Do you like lisp? When I first stumbled into Lisp advocacy on various corners of the web I was already an EXPERT PROGRAMMER. At that point I had grokked what seemed at the time a wide range of programming languages. I was proud to have under my belt (Java, C, C++, C#, C-, FORTRAN, BBCODE, etc.) I was under impression that I knew EVERYTHING there is to know about programming languages, I had written HUGE PROGRAMS you couldn't even COMPREHEND at age 12. I couldn't have possibly been more wrong. My initial attempt to learn Lisp came to a crashing halt as soon as I saw some sample code. I suppose the same thought ran through my mind that ran through thousands of other minds who were ever in my shoes: "OMG WTF LOOKS SHIT WTF IS UP WITH THAT ())()))))(((() FUCK!!!!11111" I couldn't be bothered to learn a language if its creators couldn't be bothered to give it a BBCode like syntax. After all, I was almost blinded by the infamous suave space toad Lisp! For many months the Lisp advocates pressed on. I was baffled. Many extremely intelligent people I knew and had much respect for were praising Lisp with almost religious dedication. There had to be something there, something I couldn't afford not to get my hands on! Eventually my thirst for knowledge won me over. I took the plunge, bit the bullet, got my hands dirty, and began months of mind blending exercises. It was a journey on an endless lake of frustration, I am stupid fuck. I turned my mind inside out, rinsed it, and put it back in place. I went through seven rings of hell and came back. And then I got it. I KNOW LISP. I AM SO SMART. I AM SO EXPERT, NOW I KNOW EVERYTHING ABOUT PROGRAMMMING, I DONT HAVE TO LEARN ANY OTHER LANGUAGE EVER.
IF U WERE DROPPED TO /opt TOMORROW, I WOULDNT GO 2 UR DELETION CUZ ID B N UPSTREAM BUGZILLA FLAMIN DA CUNT THAT MADE UR EBUILD!
__
.' `.
|a_a |
\<_)__/
/( )\
|\`> < /\
\_|=='|_/
WE TRUE NERDS
WE OPTIMIZE OUR CFLAGS TOGETHER
WE TALKIN ON IRC WITH www.opera.com TOGETHER
send this PENGUIN to every thread you care about including this one if you care. C how many times you get this, if you get 256 your A TRUE NERD
Name:
Anonymous2007-06-13 10:53 ID:apV1cArR
sub count_change($){
my$n=pop/5,$b=n&1?-1:1,$c=26799+1425*$b+10*$n*($n*(476+$n*(38+$n))+15*$b),$m=$n%10;
$c-=4224 if$m|1==1;
$c+=576+480*$n if$m==2;
$c-=384 if 1.6*($n-3)|8==8;
$c-=1344+480*$n if$m==4;
$c+=5376 if$m-5|1==1;
$c+=7776+480*$n if$m==7;
$c-=8544+480*$n if$m==9;
return$c/24000}
THERES SOME SICK FUCKER THAT DELETES AND EDITS MY POSTS AROUND HERE I SUSPECT IT IS FAIRX THE HAXXOR MY SWORN ENEMY I WILL SEEK HIM DOWN RIGHT NOW AND HAVE OUR FINAL SHOWDOWN -- IN HELL !!
>>28
you could post with MrVacBob's tripcode and find out if it's him...
Name:
Anonymous2007-06-13 14:44 ID:XoGfq6j0
>>29
How would I find out? Also, I don't know his tripcode, the only one I know of is moot's :'( And I don't use tripcodes anyway, when I used them back in the old days when I hanged out with the cool kids in /b/ my tripcodes were getting banned to the left and right :'(
All is not lost, I have managed to restore the copypasta from memory!
IF U WERE FLAMED FOR USING LISP TOMORROW, I WOULDNT GO 2 UR SUICIDE CUZ ID B N DAT CUNTS HOUSE N SHOVE SICP DOWN HIS THROAT! //`'''```,
o // LISP `.,
,....OOo. .c;.',,,.'``.,,.`
.' ____.,'.//
/ _____ \___/.'
| / || \\---\|
|| || \\ ||
co co co co
WE TRUE SMUG LISP WEENIES
WE READ SICP TOGETHER
WE COUNT PARENTHESES TOGETHER
send this SUAVE SPACE TOAD to every thread you care about including this one if you care. C how many times you get this, if you get 6001 your A TRUE SMUG LISP WEENIE
Name:
Anonymous2007-06-13 14:48 ID:XoGfq6j0
Oh yes, the moderators do not only moderate posts, they also mess up the CSS once in a while, turning w4ch further from its roots.
>>30
check out the TRIPCODE CRACKING THREAD on http://4-ch.net/dqn/.
i just noticed that that thread was started on the one year anniversary of the "sasebo slashing".
lol internet.
Name:
Anonymous2007-06-13 15:14 ID:kpBWzhCc
>>34
Yes, whenever they're bored they just fuck with world4ch and they always manage to come up with an even-worse theme.
Hi, Do you like lisp? When I first stumbled into Lisp advocacy on various corners of the web I was already an EXPERT PROGRAMMER. At that point I had grokked what seemed at the time a wide range of programming languages. I was proud to have under my belt (Java, C, C++, C#, C-, FORTRAN, BBCODE, etc.) I was under impression that I knew EVERYTHING there is to know about programming languages, I had written HUGE PROGRAMS you couldn't even COMPREHEND at age 12. I couldn't have possibly been more wrong. My initial attempt to learn Lisp came to a crashing halt as soon as I saw some sample code. I suppose the same thought ran through my mind that ran through thousands of other minds who were ever in my shoes: "OMG WTF LOOKS SHIT WTF IS UP WITH THAT ())()))))(((() FUCK!!!!11111" I couldn't be bothered to learn a language if its creators couldn't be bothered to give it a BBCode like syntax. After all, I was almost blinded by the infamous suave space toad Lisp! For many months the Lisp advocates pressed on. I was baffled. Many extremely intelligent people I knew and had much respect for were praising Lisp with almost religious dedication. There had to be something there, something I couldn't afford not to get my hands on! Eventually my thirst for knowledge won me over. I took the plunge, bit the bullet, got my hands dirty, and began months of mind blending exercises. It was a journey on an endless lake of frustration, I am stupid fuck. I turned my mind inside out, rinsed it, and put it back in place. I went through seven rings of hell and came back. And then I got it. I KNOW LISP. I AM SO SMART. I AM SO EXPERT, NOW I KNOW EVERYTHING ABOUT PROGRAMMMING, I DONT HAVE TO LEARN ANY OTHER LANGUAGE EVER.