Thursday, April 4, 2013

Product of Sums Problem Solving


This is a problem solving episode for the 'products of sum' problem presented in class yesterday.
The problem can be found here: 
www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/prodSum.pdf

While in class, I wrote in pencil the following Python program that I believed would solve the problem.

1    def biggest_product_of_sums(pos_integer):
2        products = []

3        products.append(pos_integer)
4        first_num = pos_integer - 1
5        second_num = pos_integer - first_num

6        while second_num <= first_num:
7            products.append(first_num * second_num)
8            first_num -= 1
9            second_num += 1
10      return max(products) 


The while loops runs while second_num <= first_num, because beyond this point, there would only be repeated products being appended to the list.
I soon realized that this function would only work to find the the largest products of a sum made up of only 1 or 2 integers. This is not the problem. For example the largest product of the sum of integers that add to 9 is 3x3x3. But my function would only return 4x5.

I realized recursion would be necessary and only added two lines of code:
After line 5 I added:
first_num = biggest_product_of_sums(first_num)
second_num = biggest_product_of_sums(second_num)

I then ran the program and tested the result. This program was no good, it exceeded maximum recursion depth. I needed a base case and I had the recursion occuring in the wrong spot. After some trial and error, I created a function that works.

Here is the tidy final product:

def biggest_product_of_sums(n):
    '''(int) -> int
    Return the maximum product that can be formed of a list of positive
    integers that sum to n. Precondition: n must be a positive integer.
    '''
    products = []
    products.append(n)
    first_num = n - 1
    second_num = n - first_num
    while first_num > 0 and second_num <= first_num:
        products.append(biggest_product_of_sums(first_num) * biggest_product_of_sums(second_num))
        first_num -= 1
        second_num += 1
    return max(products) 

No comments:

Post a Comment