CODEWITHSUNDEEP
algorithm
Kaki Master Of Time
Kaki Master Of Time

Reputation: 1633

Specific Algorithm for determining all multiple of a number

I am trying to determine an algorithm for a project i am doing. the goal is to get all number combination sequence where each adjacent number's maximum are multiples of each other. The numbers and sequence length are inputs.

example : if I give an input of sequence length 3 and a max number 5 i should get an output like this one.

[ 1, 1, 1 ]
[ 1, 1, 2 ]
[ 1, 1, 3 ]
[ 1, 1, 4 ]
[ 1, 2, 4 ]
[ 1, 3, 3 ]
[ 1, 4, 4 ]
[ 2, 2, 2 ]
[ 2, 2, 4 ]
[ 2, 4, 4 ]
[ 3, 3, 3 ]
[ 4, 4, 4 ]

in all sequences, each number is a multiple of its previous neighbour, while all numbers are less than 5 which is the maximum given as input.

Upvotes: 0

Views: 414

Answers (2)

신동원
신동원

Reputation: 11

int seq[105];

void f(int idx) {
    if(idx == length) print();
    for(int i=1;1;i++) {
        if(i*seq[idx-1] > max_number) break;
        seq[idx]=i*seq[idx-1];
        f(idx+1);
        seq[idx]=0;
    }

Upvotes: 0

신동원
신동원

Reputation: 11

You can use backtracking to get all the sequences you want.

Backtracking is really similar to DFS. You can make recursive function which uses parameter {how many numbers you put in sequence yet}, and you call recursive function after putting proper value in sequence(parameter + 1). At the end of function, you have to clear the number you put in sequence. Also you will kill the function if sequence is full.

Upvotes: 1

Related Questions