InsideDarkWeb.com

Почему не корректно работает программа? Нахождение НОД чисел с использованием модифицированного алгоритма Евклида(метод деления)

#include <iostream>
#include <string>
#include <Windows.h>
using namespace std;
int Proverka2(int* M, int m, int* N, int n);
int sdvig(int* a, int n);
int Vychitanie(int* M, int sizem, int* N, int sizen) // функция вычитания массивов
{
int s;
for (int i = 1; i <= sizen; i++)
{
s = 1;
if (M[sizem - i] >= N[sizen - i])
M[sizem - i] -= N[sizen - i];
else
{
M[sizem - i] = M[sizem - i] - N[sizen - i] + 10;
while (M[sizem - i - s] == 0)
{
M[sizem - i - s] = 9;
s++;
}
M[sizem - i - s] -= 1;
}
}
return 0;
}
string Stroka(int sizem, int* M) //функция перевода массива в строку
{
string f, g;
for (int i = 0; i < sizem; i++)
{
f = to_string(M[i]);
g.append(f);
f.clear();
}
return g;
}
int Delenie(int* M, int sizem, int* N, int sizen)// деление столбиком
{
int count = 0;
while (Proverka2(M, sizem, N, sizen) == 1)
{
count = 0;
while (Proverka2(M, sizen, N, sizen) == 1)
{
Vychitanie(M, sizen, N, sizen);
}
while (M[0] == 0)
{
sdvig(M, sizem);
sizem--;
count++;
}
if (count == 0)
{
M[1] += M[0] * 10;
sdvig(M, sizem);
sizem--;
}
}
return sizem;
}

int sdvig(int* a, int n) //сдвиг массива
{
for (int i = 0; i < n - 1; i++)
a[i] = a[i + 1];
return 0;
}
int Proverka2(int* M, int sizem,int* N , int sizen ) //если первое число больше, возвращает 1, если нет, то 0
{
int count=0;
if (sizem > sizen)
return 1;
if (sizen > sizem)
return -1;
if (sizem == sizen)
{


for (int e = 0; e < sizem; e++)
{
if (M[e] != N[e])
{
if (M[e] > N[e])
return 1;
else return -1;
}
}
}
return 0;
}

bool Proverka(string m, string n) //если одинаковые строки или какая-то из строк равна нулю, то возвращается ноль,
//чтобы в дальнейшем не производить преобразований
{

if (m == n || m == "0" || n == "0")
return false;
else
return true;
}

int preobrazovanie(string s, int *M) //разбиваем строку по массиву
{
for (int i = 0; i <s.size(); i++)
{
M[i] = s[i] - '0';
}

return 0;
}
bool check(string s) //проверка неверного пользовательского ввода
{
if (s == "0") return 0;
if (s.size() < 15) return 0;
int i = 0;
while (s[i] >= '0' && s[i] <= '9' && i < s.size())
{

i++;
}
return (i >= s.size());
}
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
string n, m;

cout « "Введите первое число от 15 знаков" « endl;
cin » m;
int j = 0;
if (m[j] == '-') { //удаляем минус если он есть, так как НОД все равно положительный
m.erase(0, 1);
}
if (not check(m)) //проверка на неверный пользовательский ввод первого числа, В УСЛОВИИ ЗАДАЧИ ЧИСЛА ОТ 15 ЗНАКОВ
{
while (not check(m))
{
cout « "Вы ввели неправильно" « endl;
cout « "Введите первое число от 15 знаков" « endl;
cin » m;
}
}

cout « "Введите второе число от 15 знаков" « endl;
cin » n;
j = 0;
if (n[j] == '-') { //удаляем минус у второго числа
n.erase(0, 1);
}
if (not check(n)) //проверка на неверный пользовательский ввод второго числа
{
while (not check(n))
{
cout « "Вы ввели неправильно" « endl;
cout « "Введите второе число от 15 знаков" « endl;
cin » n;
}
}
unsigned long int y=0, z = 0;
int sizem = m.size();
int sizen = n.size();
int* M = new int [m.size()]; //выделяем память под массивы
int* N = new int[n.size()];
preobrazovanie(n,N); // разбиваем строку по массиву
preobrazovanie(m,M);
while (Proverka(m, n)) //пока строки не одинаковые и какая-то из них не равна нулю
{
if (sizem > 9 || sizen > 9) //если количество цифр в числе больше девяти
{
if (Proverka2(M, sizem, N, sizen) == 1) // определяем какое число больше
{
sizem = Delenie(M, sizem, N, sizen); // если первое число больше, то делим его столбиком на второе
while (M[0] == 0) //убираем незначащие нули
{
sdvig(M, sizem);
sizem--;
}
m = Stroka(sizem, M); //переводим массив в строку
}
 
else
{
sizen = Delenie(N, sizen, M, sizem); // делим столбиком второе число на первое
while (N[0] == 0) //удаляем незначащие нули
{
sdvig(N, sizen);
sizen--;
}
n = Stroka(sizen, N); //переводим массив в строку
}
}
else
{
for (int i = 0; i < sizem; i++)
{
y = y * 10 + M[i];
}
for (int i = 0; i < sizen; i++)
{
z = z * 10 + N[i];
}
while (y && z)
{
if (y >= z)
y %= z;
else z %= y;

}
cout « "Наибольший общий делитель:";
if (y)
cout « y;
else cout « z;
return 0;
}
}

cout « "Наибольший общий делитель:";

if (m.size() > n.size())
cout « m;
else cout « n;
return 0;
}

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

При делении двух чисел будем использовать следующий алгоритм:

  1. Обозначим диапазон цифр в делимом числе, из которого мы будем вычитать делитель. Для начала берем диапазон, равный количеству цифр в делителе, если число в диапазоне меньше делителя, то увеличиваем диапазон на одну цифру с помощью прибавления к первому элементу нулевого, умноженного на 10 и сдвига массива влево.
  2. Вычитаем из диапазона делитель до тех пор, пока он не станет равным делителю или меньше его. Увеличиваем диапазон с помощью алгоритма, прописанного выше, если это потребуется. Таким образом мы доберемся до предпоследнего остатка от деления.
  3. Меняем числа местами в зависимости от того, какое число больше.
  4. Выполняем данный алгоритм до тех пор, пока количество цифр в каждом числе не станет меньше или равно девяти. Потом заносим числа в переменные типа unsigned long int и производим обычный алгоритм Евклида (метод деления). Для некоторых чисел это не требуется (например, если ввести одинаковое количество восьмерок и двоек), поэтому просто выполним модифицированный алгоритм Евклида до тех пор, пока одно из чисел не станет равным нулю, и выведем большее.

Как происходит вычитание?
Вычитание происходит в цикле for. Если i- тый элемент массива делимого больше i-того элемента массива делителя, то из первого вычитается второе, если нет, то также вычитается, но с прибавлением десяти к результату. Если следующий элемент в цикле первого массива не равен нулю, то из него вычитается единица, если нет, то все элементы равные нулю до первого встретившегося неравного нулю заменяются на девятки, и из первого неравного нулю вычитается единица.
Числа для проверки gcd of 687684531654854365498888 and 687816884684645465537888
Должно быть 8, выводит 24.

Add your own answers!

Related Questions

Android WebView не работает корректно

1  Asked on October 12, 2020 by nearpin

   

webview определенного элемента

1  Asked on October 5, 2020 by samoilov

   

Ask a Question

Get help from others!

© 2021 InsideDarkWeb.com. All rights reserved.