Учитывая список простых чисел и шаблон факторизации, как построить все числа, чьи простые факторизации соответствуют данному шаблону? - PullRequest
Новая
       34

Учитывая список простых чисел и шаблон факторизации, как построить все числа, чьи простые факторизации соответствуют данному шаблону?

2 голосов
/ 25 декабря 2011

Хотя я попытался обобщить вопрос в заголовке, я думаю, что будет лучше, если я начну с примера проблемы:

Список простых чисел = {2 3 5 7 11 13}
Шаблон факторизации = {1 1 2 1}

Для вышеуказанного ввода программа должна генерировать следующий список чисел:

  • 2.3.5 ^ 2.7
  • 2.3.5 ^ 2,11
  • 2.3.5 ^ 2,13
  • 2.3.7 ^ 2,11
  • 2.3.7 ^ 2,13
  • 2.3.11 ^ 2,13
  • 2.5.7 ^ 2,11
  • 2.5.7 ^ 2,13
  • 2.7.11 ^ 2,13
  • 3.5.7 ^ 2,11
  • 3.5.7 ^ 2,13
  • 3.5.11 ^ 2,13
  • 3.7.11 ^ 2,13
  • 5.7.11 ^ 2,13

Пока я понимаю, что, поскольку длина шаблона произвольно велика (как и список простых чисел), мне нужно использовать рекурсивную функцию для получения всех комбинаций. Я действительно застрял в том, как сформулировать аргументы функции / когда вызывать и т.д. Это то, что я разработал до сих пор: 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

static const int factors[] = {2, 3, 5, 7, 11, 13};
vector<int> vFactors(factors, factors + sizeof(factors) / sizeof(factors[0]));
static const int powers[] = {1, 1, 2, 1};
vector<int> vPowers(powers, powers + sizeof(powers) / sizeof(powers[0]));

// currPIdx [in]  Denotes the index of Power array from which to start generating numbers
// currFidx [in]  Denotes the index of Factor array from which to start generating numbers
vector<int> getNumList(vector<int>& vPowers, vector<int>& vFactors, int currPIdx, int currFIdx)
{
    vector<int> vResult;

    if (currPIdx != vPowers.size() - 1)
    {
        for (int i = currPIdx + 1; i < vPowers.size(); ++i)
        {
            vector<int> vTempResult = getNumList(vPowers, vFactors, i, currFIdx + i);
            vResult.insert(vResult.end(), vTempResult.begin(), vTempResult.end());
        }

        int multFactor = pow((float) vFactors[currFIdx], vPowers[currPIdx]);
        for (int i = 0; i < vResult.size(); ++i)
            vResult[i] *= multFactor;
    }
    else
    {   // Terminating the recursive call
        for (int i = currFIdx; i < vFactors.size(); ++i)
        {
            int element = pow((float) vFactors[i], vPowers[currPIdx]);
            vResult.push_back(element);
        }
    }
    return vResult;
}

int main()
{
    vector<int> vNumList = getNumList(vPowers, vFactors, 0, 0);
    cout << "List of numbers: " << endl;
    for (int i = 0; i < vNumList.size(); ++i)
        cout << vNumList[i] << endl;
}

Когда я запускаю вышеупомянутое, я получаю неправильный список: 

List of numbers: 
66
78
650
14
22
26

Я как-то натолкнулся на ментальный блок, так как не могу понять, как правильно изменить последний параметр в рекурсивном вызове (что, по-моему, и является причиной того, что моя программа не работает) !!

Было бы здорово, если бы кто-то был достаточно хорош, чтобы настроить мой код с отсутствующей логикой (или даже указать мне на это - я не ищу полное решение!). Буду очень признателен, если вы ограничите свой ответ стандартным C ++!

(В случае, если кто-то заметит, что я пропускаю перестановки данного шаблона, что может привести к другим числам, таким как 2.3.5.7 ^ 2 и т. Д. - не волнуйтесь, я намерен повторить этот алгоритм на всех возможных перестановках данного шаблона с помощью next_permutate!).

PS: не проблема домашней работы / собеседования, а лишь часть алгоритма для очень интересной задачи Project Euler (думаю, вы даже можете догадаться, какая именно:)).

РЕДАКТИРОВАТЬ: Я решил проблему самостоятельно - который я отправил в качестве ответа. Если вам это нравится, проголосуйте против (я не могу принять его как ответ, пока он не наберет больше голосов, чем другой ответ!) ...

Ответы [ 2 ]

2 голосов
/ 25 декабря 2011

Забудьте о факторизации на мгновение.Проблема, которую вы хотите решить, состоит в том, чтобы иметь два списка P и F и найти все возможные пары (p, f) для p в P и f в F. Это означает, что у вас будет | P |* | P | -1 ... * | P | - (| F | -1) возможные пары (назначение одного из P первому элементу F оставляет возможности | P | -1 для сопоставления со вторым элементом и т. Д.).Возможно, вы захотите отделить эту часть проблемы в вашем коде.Если вы повторяете этот путь, последний шаг - выбор оставшегося элемента от P до последнего элемента F. Помогает ли это?Должен признать, что я недостаточно хорошо понимаю ваш код, чтобы дать ответ, адаптированный к вашему текущему состоянию, но в целом я подхожу к нему.

1 голос
/ 01 января 2012

Ну, я понял это сам!Вот код для этого (который, я надеюсь, говорит само за себя, но я могу уточнить, если кому-то понадобится более подробная информация): 

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

static const int factors[] = {2, 3, 5, 7, 11, 13};
vector<int> vFactors(factors, factors + sizeof(factors) / sizeof(factors[0]));

static const int powers[] = {1, 1, 2, 1};
vector<int> vPowers(powers, powers + sizeof(powers) / sizeof(powers[0]));

// idx - The index from which the rest of the factors are to be considered. 
//       0 <= idx < Factors.size() - Powers.size()
// lvl - The lvl of the depth-first tree
//       0 <= lvl < Powers.size()
// lvlProd - The product till the previous level for that index.
void generateNumList
(  
    vector<int>& vPowers, 
    vector<int>& vFactors,
    vector<int>& vNumList, 
    int idx, 
    int lvl, 
    long lvlProd
)
{
    // Terminating case
    if (lvl == vPowers.size() - 1)
    {
        long prod = pow((float) vFactors[idx], vPowers[lvl]) * lvlProd;
        vNumList.push_back(prod);
    }
    else
    {
        // Recursive case
        long tempLvlProd = lvlProd * pow((float) vFactors[idx], vPowers[lvl]);
        for (int i = idx + 1; i < vFactors.size(); ++i)
            generateNumList(vPowers, vFactors, vNumList, i, lvl + 1, 
                            tempLvlProd);
    }
}

vector<int> getNumList(vector<int>& vPowers, vector<int>& vFactors)
{
    vector<int> vNumList;
    for (int i = 0; i < vFactors.size(); ++i)
        generateNumList(vPowers, vFactors, vNumList, i, 0, 1);
    return vNumList;
}

int main()
{
    vector<int> vNumList = getNumList(vPowers, vFactors);
    cout << endl << "List of numbers (" << vNumList.size() << ") : " << endl;
    for (int i = 0; i < vNumList.size(); ++i)
        cout << vNumList[i] << endl;
}

Вывод вышеуказанного кода (мне пришлось очень долго работать, чтобы получитьизбавиться от повторяющихся записей алгоритмически!): 

List of numbers (15) : 
1050
1650
1950
3234
3822
9438
5390
6370
15730
22022
8085
9555
23595
33033
55055

real    0m0.002s
user    0m0.001s
sys     0m0.001s
...