Programming Challenge.

Associate
Joined
18 Oct 2002
Posts
761
Location
Berkshire
This was sent to me by a friend, so before anyone acuses me of trying to cheat work im not, I just know theres an elegant soloution but cant work it out! Question is copied directly and follows below.....

The following shows a person’s workings to perform a multiplication using a technique known as ‘partitioning’. Partitioning involves breaking the multiplier into smaller sections, which can be calculated by doubling the number being multiplied.

Thus in the example below 150 can be broken into 128,16,4 and 2 – all of which can easily be multiplied by 2012 by simple doubling. Then it is simply necessary to add up all of the different partitions.

Example Here:
http://www.rgreenhalf.f2s.com/Example.htm

Now the question is...

"Write a function in pseudo code that implements this such that the user could invoke the function Partition(a,b) and the correct answer would be returned, calculated using the partitioning approach"

Ill post my solution in a bit, just trying to make it work better!
 
Last edited:
sorry, i don't know pseudo code, but i know some C:

Code:
#include <stdio.h>

unsigned int Partition(unsigned int a, unsigned int b) {
        int x;
        for (x = 0; a; a >>= 1, b <<= 1)
                if (a & 1) x += b;
        return x;
}

int main(int argc, char *argv[]) {
        unsigned int a = 150, b = 2012;
        printf("Partition(%u,%u) = %u\n", a, b, Partition(a, b));
        return 0;
}

output:
Partition(150,2012) = 301800

I'm sure there's an even more elegant recursive method.
 
Last edited:
recursive method in C++, using a default parameter

Code:
int Partition(int a, int b, int c = 0) {
        if (a) return Partition(a >> 1, b << 1, c + (a & 1 ? b : 0));
        return c;
}
 
Back
Top Bottom