asked on
recursive function in c++
I want to find how many possible combinations that a number
can be decomposed into the multiple of integers (smaller than the number itself) by a
recursion function.
Suppose I have a positive number 𝑋 as input, and it need to be decomposed into the
multiple of several integers, 𝑥i, where each 𝑥i, is smaller than 𝑋(e.g., 𝑋=𝑥1∗𝑥2∗
𝑥3∗...∗𝑥n). In addition, these decomposed integers can only be arranged in an
ascending order (𝑥1<=⋯<=𝑥n). Then, output how many kinds of combinations in
total.
For example, when 𝑋 is 20, the combinations are: 1*20, 2*10, 2*2*5, 4*5. So my
program should output 4.
When X is 100, It should output 9.
When X is 10000. It should output 109
However, my program cannot solve when X is 10000. How can I fix it? Here, my idea is to find the last two elements in the equation and decompose them.
My coding are as follows:
#include <iostream>
using namespace std;
int combination(int factor, int subfactor, int last_e, int x);
int main() {
int x, result, last_e;
int factor = 1;
int subfactor = 2;
//input
cout << "Please input the number: ";
cin >> x;
last_e = x;
//output
result = combination(factor, subfactor, last_e, x);
cout << "The amount of possible combinations is " << result;
return 0;
}
int combination(int factor, int subfactor, int last_e, int x) {
//largest factor
//cout << factor;
int count=0;
//handle case of first comparison
if (x == 1) {
return 1;
}
if (factor == 1) {
count = count + 1;
factor = factor + 1;
if (last_e % (x / subfactor) != 0) {
subfactor = subfactor + 1;
if (subfactor <= x) {
return 1;
}
}
last_e = x / factor;
//cout << count << " " << last_e;
return count + combination(factor, subfactor, last_e, x);
}
//handle cases for remaining comparison
if (factor <= x/factor) {
for (int i = subfactor; i <= last_e; ++i) {
for (int j = subfactor; j <= last_e; ++j) {
//calculate whether elements can be divided
if ((i * j == last_e) && (j >= i) && (i >= factor)) {
count = count + 1;
return count + combination(factor, i, j, x);
}
}
}
// find next possible subfactor
subfactor = subfactor + 1;
while (x / factor % subfactor != 0) {
subfactor = subfactor + 1;
}
if (x / factor / subfactor >= subfactor) {
last_e = x / factor / subfactor;
count = count + 1;
return count + combination(factor, subfactor, last_e, x);
}
//find next possible factor
factor = factor + 1;
while (x % factor != 0) {
factor = factor + 1;
}
count = count + 1;
return count + combination(factor, 2, x / factor, x);
}
else {
return 0;
}
}
Your description of the problem and your expected results do not show any logic as far as I can see.
Start by explaining the math behind the problem. Cause I don't see why there should be a recursive function.
This is a three part puzzle that solves a lot easier if you think of it that way.
The first partis to find all of the prime factors of a target number. This is nearly trivial. You've selected 20. It has prime factors of 2 and 5. 1, 4, and 20 are also factors. 4 is the square of one of the primes. 1 and 20 are special cases 1 isn't considered to be truly prime, but if you need them in your solution then they must be included.
The second part is to just do the math on the list of primes.
Your answer will be of the form:
P1^A * P2^B * P3^C *...Pn^N
Where P1, P2, P3, etc. are the list of primes. A, B, C, etc is the exponent of that prime.
20 breaks down to 2 primes, 5 and 2.
So your equation is 5^1 * 2^2.
For programming ease, this is 2 arrays (vectors) and a counter.
int Prime[];
int Exp[];
int Items.
Put the list of primes (5, 2) into the Prime array.
Put the list of exponents (1, 2) into the Exp array.
Items will contain 2.
Using a larger number, 360, the equation 5^1 * 3^2 * 2^3. Prime contains 5, 3, 2. Exp contains 1, 2, 3.
The third part of the problem is the program that prints the answers from the arrays (vectors).
ASKER
ASKER
#include <iostream>
using namespace std;
int c = 0;
void combination(int first_e, int product, int n) {
//base condition for recursive end to function
//if first_e or product equals to n
if (first_e > n || product > n) {
return;
}
//when product is equal to n(got one combination)
if (product == n) {
c++;
return;
}
//iterate throught firste to x and get the factors of n (then find out combination)
for (int i = first_e; i < n; i++) {
if (i * product > n) {
break;
}
//check if i is factor of n
if (n % i == 0) {
combination(i, i * product, n);
}
}
}
int main() {
int n;
cout << "Please input the number: ";
cin >> n;
combination(2, 1, n);
cout << "The amount of possible combinations is " << c + 1;
return 0;
}Cause it is still unclear, what you're actually trying to do. But it sounds like an interesting problem. And I still think your far from an optimal solution,
ASKER
2 x 2 x 5
4 x 5
1 x 20
2 x 10
So, any suggestion to code this recursive function ?