Euler Solution 76

From ProgSoc Wiki

Revision as of 06:56, 23 June 2009 by Althalus (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

t is possible to write five as a sum in exactly six different ways:

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

How many different ways can one hundred be written as a sum of at least two positive integers?

Solutions

Python by Althalus

Runtime: 373 seconds (slow and steady wins the race?)

"""
I cheated a little. I might do that more often.                
Psyco acts kind of like a Just In Time compiler, drastically   
improving run times.... (copy and paste down to and including  
psyco.full() to use the psyco module in your own python apps...)
"""
import sys
sys.path.append('/home/progsoc-users/althalus/python/')
import psyco
from psyco.classes import *
psyco.full()

#This is a slight rewrite of my solution to problem 31. hence the random references to coins.
coins = range(1,101)
def recurse(total,n):
    count = 0
    total -= n
    if total == 0:
        return 1
    elif total < 0:
        return 0
    elif total > 0:
        for i in coins[:n]:
            count += recurse(total,i)
        return count
    return total


total = 0
for i in range(1,101):
 total+= recurse(100,i)
 print i,total
print total
Personal tools