Naughty

Naughty

Naughty Boys Try Multiplication

A. First Edition

This is a small puzzle and it is a small practice for backtrack algorithm which I would always like to call

as DFS.

B.The problem

Do you like small games? Here it is an interesting one.

Two boys are given 99 balloons with a distinct number between 1 to 99 on each of them. That is,

each number between 1 to 99 will appear once and only once on any of these 99 balloons. Then the

two boys are given several minutes to try to destroy these balloons. Whichever the balloon each boy

destroy, he will try to remember its number. Ironically, these two boys are genius of maths who

will only be able to remember number by multiply it with previous result. That means, if boy Peter

destroyed balloon with numbers of 2, 19, 20, 50 and 80, what he remembered is

2x19x20x50x80=3040000.

Of course the two little boys cannot destroy all the 99 balloons. Some of them will surely fly

away. When time is up, you will ask them how many balloons they have destroyed each. The two

naughty boys would give you the multiply result of his memory. You are the judge to tell whether

they are kidding you with some impossible numbers. For example, it is impossible for two boys to

give answers of 134 and 201 because 134 = 2x67 and 201 =3x67 and they cannot destroy no.67 balloon

at the same time. You can assume that these two boys are so extremely clever that unless you spot

the impossible number combination like above, they can always explain themselves by possible way

of multiplication as long as there is no contradiction between them. So, the only way to make sure

they are not cheating you is to make sure you find out the all possible combinations of factors of

two reported number. Only if you try all possible multiply factors for two numbers and make sure

each combination of factors of two numbers has some common factors, can you proudly declare that

the naughty boys are kidding with you. Otherwise, do reward them with some candies for their

cleverness in maths.

That is:

number1=Pfactor_1 x Pfactor_2 x ... Pfactor_n and for all n factors, they are distinct and <=99

number2=Qfactor_1 x Qfactor_2 x ... Qfactor_m and for all m factors, they are distinct and <=99

And for all n Pfactors has no common one with all m Qfactors.

　

Are you bored till now?

　

C.The idea of program

　

It is a typical searching problem with backtrack algorithm or DFS, if you want to call it my way. The greedy

algorithm simply won't work.

D.The major functions

E.Further improvement

It is a small game and no one would bother to treat them seriously, I presume.

F.File listing

1. Naughty.cpp(main)

file name: naughty.cpp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

const int MaxNumber=100;
const int MaxFactorNumber=5;
const int MinFactorNumber=2;

int bigCount=0;
int smallCount=0;
int bigNumbers[MaxFactorNumber*20];
int smallNumbers[MaxFactorNumber*20];

bool tested[MaxNumber]={false};

bool findFactor(int divider, int start, int& divisor);

bool backTrack(int small, int big);

void initialize();

void display(int big, int small);

int randNumber(int includes);

int main()
{
    int small, big;
    int includes=1;
    srand(time(0));
    initialize();
    small=randNumber(includes);
    big=randNumber(includes);
    printf("MaxFactorNumber= %d and includes = %d\n", MaxFactorNumber, includes);
    if (backTrack(small, big))
    {

        display(small, big);
    }
    else
    {
        printf("no result\n");
    }

    return 0;
}

int randNumber(int includes)
{
    //make sure the factor number is in between the max and min
    int count=rand()%(MaxFactorNumber-MinFactorNumber)+MinFactorNumber;
    int result=includes;
    int number;
    for (int i=0; i<count; i++)
    {
        //make sure factors are among 1--99
        number=rand()%(MaxNumber-1) +1;
        result*=number;//since we don't want 0
    }
    return result;
}

void doDisplay(int array[], int numbers)
{
    for (int i=0; i<numbers; i++)
    {
        if (i!=numbers-1)
        {
            printf("%d x ", array[i]);
        }
        else
        {
            printf(" %d\n", array[i]);
        }
    }
}

void display(int small, int big)
{
    void doDisplay(int array[], int numbers);

    printf("the big number %d has %d factors:", big, bigCount);
    doDisplay(bigNumbers, bigCount);
    printf("the small number %d has %d factors:", small, smallCount);
    doDisplay(smallNumbers, smallCount);
}

void initialize()
{
    smallCount=bigCount=0;
    for (int i=0; i<MaxNumber; i++)
    {
        tested[i]=false;
    }
}

bool findFactor(int divider, int start, int& divisor)
{
    int boundary=divider/start;
    if (boundary>MaxNumber)
    {
        boundary=MaxNumber;
    }
    for (int i=start; i<boundary; i++)
    {
        if (!tested[i])
        {
            if (divider%i==0)
            {
                divisor=i;
                return true;
            }
        }
    }
    return false;
}

bool backTrack(int small, int big )
{
    int smallFactor, bigFactor;
    int smallStart=2, bigStart=2;
    if (small<MaxNumber&&big<MaxNumber)//reach a solution
    {
        if (small!=big&&!tested[small]&&!tested[big])//if they are brand new
        {
            bigNumbers[bigCount++]=big;
            smallNumbers[smallCount++]=small;
            return true;
        }
    }
    while (findFactor(small, smallStart, smallFactor))
    {
        tested[smallFactor]=true;
        smallNumbers[smallCount++]=smallFactor;
        bigStart=2;
        while (findFactor(big, bigStart, bigFactor))
        {
            tested[bigFactor]=true;
            bigNumbers[bigCount++]=bigFactor;
            if (!backTrack(small/smallFactor, big/bigFactor))
            {
                tested[bigFactor]=false;
                bigCount--;
                bigStart=bigFactor+1;
            }
            else
            {
                return true;
            }


        }

        tested[smallFactor]=false;
        smallCount--;
        smallStart=smallFactor+1;
    }
    return false;
}

The result is like following:

I will show you some results by changing the constant "MaxFactorNumber" and

deliberately "includes" common factors at function "randNumber(includes)",

MaxFactorNumber= 4 and includes = 34
the big number 9089424 has 5 factors:3 x 6 x 136 x 47 x 79
the small number 174080 has 5 factors:2 x 4 x 5 x 64 x 68
Press any key to continue

MaxFactorNumber= 4 and includes = 34
the big number 47124 has 4 factors:3 x 6 x 34 x 77
the small number 105774 has 4 factors:2 x 17 x 51 x 61
Press any key to continue

MaxFactorNumber= 4 and includes = 1
the big number 533120 has 3 factors:64 x 85 x 98
the small number 3483 has 3 factors:3 x 27 x 43
Press any key to continue

MaxFactorNumber= 5 and includes = 1
the big number 2156 has 2 factors:22 x 98
the small number 27 has 2 factors:3 x 9
Press any key to continue

MaxFactorNumber= 5 and includes = 1
the big number 180950 has 5 factors:5 x 7 x 10 x 11 x 47
the small number 22670928 has 5 factors:2 x 17 x 81 x 84 x 98
Press any key to continue

MaxFactorNumber= 5 and includes = 1
the big number 1462 has 3 factors:2 x 17 x 43
the small number 57564 has 3 factors:9 x 78 x 82
Press any key to continue