Найти все факторизации числа
Например, 16 можно выразить следующими способами:
2 * 2 * 2 * 2
4 * 2 * 2
4 * 4
8 * 2
(исключая тривиальный случай 1 * 16)
36:
2 * 2 * 3 * 3
2 * 2 * 9
2 * 18
4 * 3 * 3
12 * 3
4 * 9
Поэтому мне нужно найти все представления любого данного числа, как указано выше.
Для начала мне удалось придумать все делители заданного числа с кодами ниже:
void FindDivisors(int n)
{
vector<int> my_vector;
for (int i = 2; i < n/2 + 1; i++)
{
if (n % i == 0)
my_vector.push_back(i); //store divisors in a vector.
}
}
После этого я застрял. Как мне добраться от всех делителей до всех желаемых факторизаций?
Я могу подумать о методе рекурсии, который, кажется, работает, но точно не знает, как его реализовать:
Возьмите 16 в качестве примера. Давайте назовем функцию, чтобы найти все представления n, чтобы быть «фактором (n)». Все нетривиальные делители 16 равны {2,4,8}. Разобьем 16 на каждый его делитель и получим {8, 4, 2}. Тогда Фактор (16) = объединение 2 * Фактора (8), 4 * Фактора (4) и 8 * Фактора (8). Тем не менее, это насколько я получил. Я новичок в рекурсии и не уверен, что этот маршрут работает. Мне нужна помощь в том, как все сложить.
Решение
Пока вы не знаете, сколько факторов, наиболее эффективным решением является рекурсия.
Вам понадобится вектор для хранения текущего пути:
vector<int> path; // it will store all current factors
и рекурсивная функция.
Для каждой итерации вы пытаетесь разделить текущий остаток и помните:
void OutputRec(int value)
{
if (value == 1) // We have divided the whole number
{
for (int i = 0; i < path.size(); i++) cout << path[i] << " ";
cout << endl;
return;
}
for (int i = value; i > 1; i--)
{
if (value % i == 0) { // if it is divisible
path.push_back(i); // add to path
OutputRec(i, value / i); // continue working
path.pop_back(); // remove from path
}
}
}
void Output(int value)
{
cout << "Result for " << value << ": " << endl;
path = vector<int>();
OutputRec(value);
}
int main() {
Output(4);
Output(16);
Output(36);
Output(256);
return 0;
}
Например, пусть у нас есть 8. Вот как это работает:
OutputRec(8), path = []:
i = 8: divisible (8 / 1 = 1)
OutputRec(1), path = [8], value == 1 > output "8".
i = 7, 6, 5: not divisible
i = 4: divisible (8 / 4 = 2)
OutputRec(2), path = [4]:
i2 = 2: divisible (2 / 2 = 1)
OutputRec(1), path = [4 2], value == 1 > output "4 2".
i = 3: not divisible
i = 2: divisible (8 / 2 = 4)
OutputRec(4), path = [2]:
i3 = 4: divisible (4 / 4 = 1)
OutputRec(1), path = [2 4], value == 1 > output "2 4".
i3 = 3: not divisible
i3 = 2: divisible (4 / 2 = 2)
OutputRec(2), path = [2 2]:
i4 = 2: divisible (2 / 2 = 1)
OutputRec(1), path = [2 2 2], value == 1 > output "2 2 2"Результат:
8,
4 * 2,
2 * 4,
2 * 2 * 2
Теперь вы видите проблему: [2 4] и [4 2] дублированный ответ. Как мы можем избежать дублирования ответов? Самый простой подход — выводить значения только в порядке возрастания (не имеет значения).
Давайте добавим max переменной и сохраните последнее число, вставленное в путь, и найдите только те разделители, которые меньше или равны ему.
Например, если текущий путь равен [2], то рекурсия не должна идти для [2 4], а должна идти для [2 2]. Начальная стоимость max равно value в качестве первого числа в пути может быть любой.
void OutputRec(int max, int value)
{
if (value == 1) {
for (int i = 0; i < path.size(); i++) cout << path[i] << " ";
if (path.size() == 1) cout << "1";
cout << endl;
return;
}
for (int i = max; i > 1; i--) // loop from max. Min(max, value) would be better
{
if (value % i == 0) {
path.push_back(i);
OutputRec(i, value / i);
path.pop_back();
}
}
}
void Output(int value)
{
cout << "Result for " << value << ": " << endl;
path = vector<int>();
OutputRec(value, value);
}
Вот как это работает сейчас:
OutputRec(8), path = []:
i = 8: divisible (8 / 8 = 1)
OutputRec(1), path = [8], value == 1 > output "8".
i = 7, 6, 5: not divisible
i = 4: divisible (8 / 4 = 2)
OutputRec(2), path = [4]:
i2 = 2: divisible
OutputRec(1), path = [4 2], value == 1 > output "4 2".
i = 3: not divisible
i = 2: divisible (8 / 2 = 4)
OutputRec(4), path = [2]:
// notice i3 starts from 2, because last inserted is 2
i3 = 2: divisible (4 / 2 = 2)
OutputRec(2), path = [2 2]:
i4 = 2: divisible (2 / 2 = 1)
OutputRec(1), path = [2 2 2], value == 1 > output "2 2 2"Результат:
8,
4 * 2,
2 * 2 * 2
Все отлично работает! Единственное, что выглядит некорректно — это «8». Вероятно, это должно быть «8 * 1». Вы можете добавить строку как if (path.size() == 1) cout << "1"; на выход.
Результат:
8 * 1,
4 * 2,
2 * 2 * 2
Здесь рабочая Ideone демо.
Я надеюсь, что я не смутил вас еще больше. Действительно трудно объяснить, что такое рекурсия в первый раз.
Рекурсия — это как плавание или езда на велосипеде — сначала это выглядит сложно. Затем вы попробуете это и изучите это, и как только вы поймете это — вы будете удивляться, почему вы не могли сделать это раньше 🙂 Удачи.
Другие решения