High School Programming Problems: How Do I Love Thee?

Posted

I’m in the process of working with some high school student on preparing for an upcoming programming competition, and their teacher kindly sent me a few past examples of questions they’ve had to work through.  I thought it would be fun to make these available for everyone to see and try their hand at.  Choose the language of your choice.  For reference, the language requested by this example was Java (I know… now you have TWO problems).

Write a program which asks the user to input a whole number (positive integer). The program should respond by printing out all the ways that smaller numbers could be used to add up to the user’s number. Here is a sample of the way the user dialog might look:

Do you wish to quit the program (Y/N)? N
What is your number? -12.7
Illegal number; try again.
What is your number? 5
The ways of adding to 5 are:
1+4
1+1+3
1+1+1+2
1+1+1+1+1
1+2+2
2+3
Do you wish to quit the program (Y/N)? etc…………


The exact dialog and the order of output might vary in your program. However, you should avoid giving the same answer twice. For example, “1+4″ and “4+1″ are both the same answer.

How would you solve this problem?  Let me know in the comments!

Do your Windows Servers need an easy monitoring solution? Try Winsitter today!

Don't forget to follow me on Twitter! I'm @1kevgriff

Have the bytes gotten you bit? When in doubt, Consult with Griff
  • http://twitter.com/rmcastil Ryan Castillo

    High School kids are solving this? All the recursion is making my head hurt.

  • http://twitter.com/taylorka taylorka

    Wow…that is combinatorics and you really need a partition function (part of partition theory) to solve that efficiently. Guess I was a slacker/underachiever in highschool. :) That being said, I guess you could brute force it, but it is not going to scale very well…

  • http://twitter.com/taylorka taylorka

    If java where not an impediment and I could use Ruby, I think James Edward Gray II’s solution to this type of problem is pretty elegant (I added the “if nums[0] != x” to exclude the number entered):

    def partition(largest, rest = Array.new, &block)
    block.call([largest] + rest)
    (rest.first || 1).upto(largest / 2) do |i|
    partition(largest – i, [i] + rest, &block)
    end
    end

    # call the partition function with “5″ as a test
    partition(5) { |nums| p nums if nums[0] != 5 }