« Reflections

- Login to post comments

Have any of you tried some more challengenig programs like described in

http://www.cs.uofs.edu/~mccloske/hs_prog_contest/index.html ?

If have tried the first three and uploaded EXE versions of my solutions .....

https://www.dropbox.com/sh/fbrnqg60qytz2sz/COgBWlPRCn

Problem 1: Multiplication `a la russe

The standard multiplication algorithm taught in elementary schools represents just one of

several ways to compute the product of two numbers. A different method, which was known in

ancient Egypt and is called multiplication `a la russe, more closely resembles how multiplication

is performed in electronic computers.

Using this method, we need not refer to (or memorize) the standard multiplication table (which,

for any two single-digit numbers, tells us their product). Rather, we need to know how to do four

things: add, decrement, double, and halve. Using these four operations, we can characterize

multiplication of two positive integers a and b as follows:

Develop a program that, given two positive integers, multiplies them according to this method

and outputs their product as the sum of numbers obtained during the process. For the example

above, this sum is 6 + 12 + 48 + 192 + 384.

Input: The first line contains a positive integer n indicating how many instances of the problem

are described thereafter. Each of the next n lines contains a pair of positive integers a and b

to be multiplied, separated by a space.

Output: For each pair a and b given as input, display on a single line the equation

a ¤ b = t1 + t2 + · · · + tr

where the ti’s are the elements of the sum obtained by multiplying a and b using multiplication

`a la russe. The ti’s should be in ascending order.

Resultant output

----------------

214 * 3 = 6 + 12 + 48 + 192 + 384

1 * 3543 = 3543

3543 * 1 = 1 + 2 + 4 + 16 + 64 + 128 + 256 + 1024 + 2048

134 * 18 = 36 + 72 + 2304

Replies