Не полное разложение на множители

297
20 декабря 2016, 22:33

Написал программу, которая бы разлагала любое целое число на множители.

#include <iostream>
#include <cstdlib>
using namespace std;
bool isLCM (int num, int denum);
int fill_array(int &num, int *arr);
int main() {
    setlocale(LC_ALL,"rus");
    int num;
    int *arr_of_denums = new int [1]; // массив для заполнения
    cin >> num;
    // в переменную n будет возвращен размер получившегося массива с делителями
    int n = fill_array(num, arr_of_denums);
    // вывод разложенного числа num на экран;
    for (int i = 0; i < n; i++) {
        if ( i == n - 1) cout << arr_of_denums[i]; //проверка на последний делитель
                            // если он последний, то ненадо после него ставить '*'
    else
        cout << arr_of_denums[i] << " * ";
    }
delete []arr_of_denums;
return 0;
}
// функция принимает число num и делитель denum
// в теле идет проверка на делимость num на denum
bool isLCM(int num, int denum) {
    if ( num%denum == 0 ) return true;
    else return false;
}
// функция принимает число num и указатель на массив для заполнения arr
// массив заполняется делителями числа num
// и возвращает размер заполненного вектора
int fill_array (int &num, int *arr) {
    int denums[] = { 2, 3, 5, 7, 11}; //массив делителей для числа num
    int j = 0;
        for (int i = 0; i < 5;) {
            if (isLCM(num, denums[i])) {
                arr[j] = denums[i];
                num = num/denums[i];
                j++;
            }
            else i++;
        }
    return j;
}

программа работает, все выводит корректно, но есть одно но: она разлагает не полностью. Я попробовал разложить 1824, она вывела 2^5 * 3, хотя полным разложением будет 2^5 * 3 * 19. Собственно, как заставить ее выводить это самое 19? И заодно оцените, пожалуйста, как написан код. Я только учусь, хочу писать не только правильно, но и понятно :)

Answer 1

Если вы действительно хотите рассматривать в цикле только делители, указанные в массиве denums, то после завершения цикла вам надо еще добавить в массив arr то, что осталось от числа num (при условии, что num в конце не равен 1). В примере с разложением 1824 это как раз и будет ваше 19.

Только массив arr_of_denums у вас выделен размером всего 1. Так что больше одного числа в arr_of_denums заносить никак нельзя. Почему вы выделяете такой маленький массив?

Если отказаться от "голого" массива и использовать взамен std::vector, то реализация вашего алгоритма может выглядеть так

void fill_array(int num, std::vector<int> &arr) 
{
  const int denums[] = { 2, 3, 5, 7, 11 }; //массив делителей для числа num
  for (int i = 0; i < sizeof denums / sizeof *denums;) {
    if (isLCM(num, denums[i])) {
      arr.push_back(denums[i]);
      num /= denums[i];
    }
    else 
      i++;
  }
  if (num != 1)
    arr.push_back(num);
}

и вызов

...
std::vector<int> arr_of_denums; 
fill_array(num, arr_of_denums);
// вывод разложенного числа num на экран;
for (int i = 0; i < arr_of_denums.size(); i++) {
  ...

Или даже так

std::vector<int> fill_array(int num) 
{
  const int denums[] = { 2, 3, 5, 7, 11 }; //массив делителей для числа num
  std::vector<int> arr;
  for (int i = 0; i < sizeof denums / sizeof *denums;) {
    if (isLCM(num, denums[i])) {
      arr.push_back(denums[i]);
      num /= denums[i];
    }
    else 
      i++;
  }
  if (num != 1)
    arr.push_back(num);
  return arr;
}

и вызов

...
std::vector<int> arr_of_denums = fill_array(num);
// вывод разложенного числа num на экран;
for (int i = 0; i < arr_of_denums.size(); i++) {
  ...

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

unsigned n = 1824;
unsigned d = 2;
while (d < n)
  if (n % d == 0) {
    cout << d << " ";
    n /= d;
  }
  else
    ++d;
if (n != 1)
  cout << n << " ";
cout << endl;

Только этому алгоритму совсем не нужен заготовленный заранее массив простых делителей - он их сам находит (пусть и неэффективно). Может и вам ваш массив denums совсем ни к чему? Или задание именно такое?

Answer 2

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

int *arr_of_denums = new int [1]; // массив для заполнения

выделяется массив, состоящий только из одного элемента. Однако в функции fill_array в цикле

    for (int i = 0; i < 5;) {
        if (isLCM(num, denums[i])) {
            arr[j] = denums[i];
            ^^^^^^
            num = num/denums[i];
            j++;
        }

имеет место попытка обращение к 5 элементам массива.

Вместо вручную выделения динамически массива значительно надежнее и проще использовать стандартный контейнер std::vector.

Что касается стиля программирования. Данная функция имеет непонятный интерфейс

int fill_array(int &num, int *arr);

Какой смысл передавать переменную num по ссылке?

При этом логичнее объявить параметры в обратном порядке

int fill_array( int *arr, int num);

Функция с непонятным названием isLCM может быть вообще написана в одну строчку

bool isLCM(int num, int denum) 
{
    return num % denum == 0;
}

Возникает вопрос: а нужно ли для одной арифметической встроенной операции определять целую функцию?

В программе используются "магические" числа, как, например, число 5 в этом цикле

for (int i = 0; i < 5;) {

Ну, и сам алгоритм страдает ограничением числа возможных простых чисел. Поэтому простое число 19 вы никак получить не можете. Для этого вам надо заново определять локальный массив, который на самом деле совершенно излишний.

READ ALSO
Заменить символ &#39;/&#39; на &ldquo;\\&rdquo;

Заменить символ '/' на “\\”

Нужно в строке заменить все символы / на \\Делал следующим образом:

269
Вопрос по шаблонным методам C++ [требует правки]

Вопрос по шаблонным методам C++ [требует правки]

Не получается пройти тестовый вопросПодскажите пожалуйста:

317
Подключение .lib/.dll в Qt проект

Подключение .lib/.dll в Qt проект

Пытаюсь подключить в Qt проект на С++ (никакие собственные библиотеки Qt не используются) библиотеки ole32 и oleaut32 из набора windows SDK

767
Рамка вокруг изображения в QLabel

Рамка вокруг изображения в QLabel

Есть QLabel, в который нужно запихнуть изображениеНужно сделать так, чтобы это изображение отображалось с рамкой различной толщины

424