Блог

Я выполняю упражнение, в котором мне нужно найти положительные целые p числа , q которые являются множителями другого натурального числа n . Следуя формуле n=pq*q , где p — бесквадратичное число.

Однако для некоторых экземпляров программы мой компилятор обнаруживает ошибку памяти, сообщающую, что я обращаюсь к неинициализированному значению.

Логика, которую я попробовал, заключается в следующем. Во-первых, я взял число, которое необходимо учесть (назовите его n). Затем я нашел все множители числа n и поместил их в вектор. После этого проверьте, является ли каждый элемент этого вектора бесквадратным. Если true, поместите элемент в другой вектор (вектор бесквадратичных множителей числа n). После этого пройдите по каждому элементу вектора бесквадратных множителей и решите уравнение q=sqrt(n/p) , где p — бесквадратный множитель из вектора. Кроме того, я проверяю условие if(int(sqrt(n/p))==sqrt(n/p)) , потому что квадратный корень должен быть положительным целым числом.

 #include <iostream>
#include <vector>
#include <cmath>
using namespace std;
// Function that checks if the number is squarefree

bool isSquareFree(int n)
{
    if (n % 2 == 0)
        n = n / 2;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i <= sqrt(n); i  = 2)
    {
        if (n % i == 0)
        {
            n = n / i;
            if (n % i == 0)
                return false;
        }
    }
    return true;
}

void Factorise_the_number(int n, int amp;p, int amp;q)
{
    if (n <= 0)
        return 0;
    vector<int> factors(0); // vector of factors
    vector<int> sqfree_factors(0); // vector of squarefree factors
    int sqfree_number; // the number "p"
    int squared; // is essentially the number "q"

    for (int i = 1; i <= n / 2; i  )
    {
        if (n % i == 0)
            factors.push_back(i); // takes all factors of the number "n"
    }

    for (int i = 0; i < factors.size(); i  )
    {
        if (isSquareFree(factors.at(i)))
            sqfree_factors.push_back(factors.at(i));
    } // checks if each factor is squarefree. if yes, put it in a separate vector

    for (auto x : sqfree_factors)
    {

        if (int(sqrt(n / x)) == sqrt(n / x))
        { // if true, we found the numbers
            squared = sqrt(n / x);
            sqfree_number = x;
            break;
        }
    }

    p = sqfree_number;
    q = squared;
}

int main()
{

    int n, p = 0, q = 0;
    cin >> n;

    Factorise_the_number(n, p, q);
    cout << p << " " << q;

    return 0;
}
 

Например, моя программа работает, если я ввожу номер 99 , но не работает, если я ввожу 39 . Кто-нибудь может дать какое-либо представление?

Спасибо!

Как вы сказали, для 39 это не работает. Вы проверили, что он делает с 39? Вы должны это сделать, так как это лучший способ отладки вашей программы.

Давайте посмотрим на это вместе. Сначала он пытается найти все факторы и находит 1, 3 и 13: это выглядит нормально.

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

Затем он проверяет, удовлетворяет ли какой-либо из факторов без квадрата искомому равенству. Ни один из них этого не делает (39 равно 3 x 13, он никак не может содержать коэффициент в квадрате). Это означает, что if (int(sqrt(n / x)) == sqrt(n / x)) это никогда не бывает истинным, и этот блок никогда не выполняется. Какое значение sqfree_number и squared в этот момент? Он никогда не инициализируется. Использование неинициализированных значений приводит к «неопределенному поведению», то есть ваша программа может делать что угодно. В этом случае p и q в конечном итоге содержит случайные значения.

Как вы можете это исправить? Подумайте об этом: если n не удовлетворяет вашему уравнению, то есть оно не может быть выражено как pq * q, что именно должна выводить программа? Будет ли ваш вывод, как сейчас, когда-либо иметь смысл? Нет. Это означает, что вы должны изменить свою программу таким образом, чтобы она охватывала случай, который вы не рассматривали.

Один из способов — добавить a bool found = false; непосредственно перед вашим последним for циклом. Когда вы найдете факторы, перед разрывом установите для этой переменной значение true . Затем, вне цикла, проверьте это: так ли это true ? Затем вы можете вернуть правильные значения. Но если это все равно false , это означает, что равенство не выполняется, и вы не можете вернуть правильные значения. Вы должны найти способ сообщить об этом вызывающей стороне (которая является вашей main функцией), чтобы она могла напечатать соответствующее сообщение.

И как вы можете это сигнализировать? В общем, вы могли бы изменить свой Factorise_the_number (кстати, имя функций должно начинаться со строчной буквы; для классов обычно используются прописные буквы), чтобы вернуть a bool . Или вы можете использовать хитрость: вернуть специальное значение для p и q , которое не может быть результатом вычисления. Например, -1. Затем, перед печатью, проверьте: если значения равны -1, это означает, что число не может быть выражено как pq * q.