C ++ int массив указателей рекурсивно, чтобы найти простые факторы - PullRequest
Новая
       11

C ++ int массив указателей рекурсивно, чтобы найти простые факторы

0 голосов
/ 08 ноября 2011

Я пытаюсь создать функцию, которая может возвращать простые множители заданного числа в массиве (или множественном множестве, но я пытаюсь использовать массив).

Например, если я введу 12, я хочу получить 2, 2 и 3, а не 2 и 3, как в наборе. Это делается для того, чтобы я мог использовать их, чтобы узнать, является ли это число Смита или нет, поэтому мне нужны цифры отдельно.

Также я использую рекурсивный подход.

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

Я попытался просто инициализировать массив в функции, а затем вернуть его.

Из того, что я могу сказать, я могу получить массив из базовой итерации, а затем при попытке создать новый массив с размером oldArray+1 для копирования значений, все становится беспорядочным. Вот где я заблудился.

Из того, что я прочитал, хотя это не самая эффективная реализация, я должен быть в состоянии заставить ее работать.

У меня есть функция, nextPrime(int n), которая с учетом n вернет следующее простое число от этого числа.

См. Источник ниже: 

int* find(int n, int p) {

int root = (int) floor(sqrt(n));
if (p > root) {
    // Base case, array gets initialized and returned
    // depending on value of n and p.
    if (n > 1) {
        factors = new int[1];
        factors[0] = n;
        return factors;
    }
    else {
        factors = new int[0];
        return factors;
    }
}
else
    if (n%p == 0){
        // Inductive step if p is a factor
        int newFloor = (int) floor(n/p);
        factors = find(newFloor, p);

        // Initialize new array.
        int* newFactors;
        newFactors = new int[(sizeof(factors) / sizeof(int)) + 1];

        // Add p to first slot, fill rest with contents of factors.
        factors[0] = p;
        for (int i = 0; i < (sizeof(factors) / sizeof(int)); i++) {
            newFactors[i+1] = factors[i];
        }

        return newFactors;
    }
    else {
        // Inductive step p isn't a factor of n
        factors = find(n, factors, nextPrime(p));
        return factors;
    }
}

Как я уже сказал, ошибка в возврате массива и использовании его значения, но почему он возвращает OK с первой итерации?

Ответы [ 2 ]

1 голос
/ 08 ноября 2011

Вы должны использовать std::vector для этого. Основная проблема, с которой вы столкнулись, состоит в том, что указатель на массив не может узнать количество элементов, содержащихся в массиве. Конкретно, часть, где вы говорите sizeof(factors), неверна. Как я понимаю, вы ожидаете, что вы получите количество элементов в массиве, на которое указывает factors, но оно действительно даст вам количество байтов, необходимое для хранения указателя на int.

Вы должны либо вернуть vector<int>, либо передать его в качестве справочного материала и обновлять его каждый раз, когда вы находите коэффициент.

1 голос
/ 08 ноября 2011

Нечто подобное может работать.Не очень эффективно !! 

void FindFactors( int number , std::vector<int>&  factors )
{
    for ( int i = 2; i <= number; ++i )
    {
        if ( number % i == 0 )
        {
            factors.push_back( i );
            FindFactors( number / i , factors);
            break;
        }
    }
}

int main()
{

    std::vector<int> factors;
    FindFactors( 121 , factors );
    return 0;
}

После вызова функции factor будет содержать только простые множители.

...