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)
Subscribe to:
Comments (Atom)