Посчитать НОД больших чисел

@Anhain · Регистрация: 03.10.2022

Студворк — интернет-сервис помощи студентам

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

@alexu_007 · 07.12.2022, 20:31

Сообщение от Anhain

Нужно посчитать НОД ОЧЕНЬ большого числа, которое записано в строку.

Какого например? И эта, НОД вычисляется для двух чисел как бы...

@Anhain · 07.12.2022, 22:49 **[ТС]**

Сообщение от Kuzia domovenok

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class mylong {
    enum types { base = 1000000000, digit_base = 9 };
    vector<int> digits;
 
public:
    mylong(const string& src = "") {
        for (int i = src.size(); i > 0; i -= digit_base) {
            int j = i - digit_base < 0 ? 0 : i - digit_base;
            digits.push_back(stoi(string(src, j, i - j)));
        }
    }
    friend mylong operator -(const mylong& a, const mylong& b);
    friend int compare(const mylong& a, const mylong& b);
    friend ostream& operator << (ostream& out, const mylong& val);
    friend istream& operator >> (istream& in, mylong& val);
};
ostream& operator << (ostream& out, const mylong& val) {
    for (auto i = val.digits.rbegin(); i != val.digits.rend(); ++i)
        if (i != val.digits.rbegin())
            out << std::setfill('0') << std::setw(val.digit_base) << *i;
        else out << *i;
    return out;
}
istream& operator >> (istream& in, mylong& val) {
    string buffer;
    in >> buffer;
    val = mylong(buffer);
    return in;
}
int compare(const mylong& a, const mylong& b) {
    if (a.digits.size() != b.digits.size()) return a.digits.size() < b.digits.size() ? -1 : 1;
    for (int i = a.digits.size() - 1; i >= 0; --i) {
        if (a.digits[i] != b.digits[i])
            return a.digits[i] < b.digits[i] ? -1 : 1;
    }
    return 0;
}
mylong operator -(const mylong& a, const mylong& b) {
    int i, carry = 0;
    mylong result;
    for (i = 0; i < a.digits.size() && i < b.digits.size(); ++i) {
        int digit = a.digits[i] - b.digits[i] + carry;
        if (digit < 0) {
            result.digits.push_back(digit + mylong::base);
            carry = -1;
        }
        else {
            result.digits.push_back(digit);
            carry = 0;
        }
    }
    for (; i < a.digits.size(); ++i) {
        int digit = a.digits[i] + carry;
        if (digit < 0) {
            result.digits.push_back(digit + mylong::base);
            carry = -1;
        }
        else {
            result.digits.push_back(digit);
            carry = 0;
        }
    }
    auto rit = find_if(result.digits.rbegin(), result.digits.rend(), [](int v) { return v != 0; });
    result.digits.erase(rit.base(), result.digits.end());
    return result;
}
int main() {
    mylong x("1800000000000000"), y("1200000000000000");
    int c;
    while (c = compare(x, y))
        if (c > 0)
            x = x - y;
        else
            y = y - x;
    cout << x << endl;
}

А ты можешь объяснить программу? Просто я как новичок, не понимаю некоторый синтаксис

@alexu_007 · 08.12.2022, 03:04

Всё равно моя круче!

@gunslinger · 08.12.2022, 05:43

Ну так выложи свое решение. Чего стесняться?

@gunslinger · 08.12.2022, 12:39

Прошу прощения. Сразу не увидел, что уже выложил.
Лучше бы, конечно, вместе с ехе, ну да ладно.

@alexu_007 · 08.12.2022, 15:15

Пжалста ексешники, в папке bin. Нод-нок и проверка на простоту, до кучи.

@Anhain · 08.12.2022, 22:06 **[ТС]**

Добрый вечер, написал программу, а она почему-то считает НОД только двух одинаковых чисел. Если я ввожу разные, то она просто не идёт дальше.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
 
ifstream number_1;
ifstream number_2;
 
string divider[9]; // хранение делители умноженного на (i+1) для ускорения поиска для вычитания при делении
 
// возвращает реверс числа
string revers(string num_1) {
 
    for(int i = 0; i < num_1.length(); i++){
        swap(num_1[i], num_1[num_1.length() - i - 1]); // проходим циклом до середины меняя противолежащее значение местами 
    }
    return num_1;
}
 
short comparison(string num_1, string num_2) { // сравнение двух длинных чисел
 
    if (num_1.length() > num_2.length()) {
        return 1;
    }
 
    else if (num_1.length() < num_2.length()) {
        return -1;
    }
 
    else {
        for (int i = num_1.length() - 1; i >= 0; i--) { // перебираем индексы строк до тех пор,
            if (num_1[i] > num_2[i]) {                // пока один из них не будет больше другого 
                return 1;
            }
 
            else if (num_1[i] < num_2[i]) {
                return -1;
            }
 
            else {
                continue;
            }
        }
        return 0;
    }
}
 
string sum(string num_1, string num_2) { // сложение первого числа и второго
 
    bool flag = false; // flag = num_1[i] + num_2[i] > 9
 
    if (num_1.length() < num_2.length()) { // если длина num_1 < num_2, то меняем значения местами
        swap(num_1, num_2);
    }
 
    for (int i = 0; i < num_2.length(); i++) { // проходимся по двум строкам, идём по длине num_2
        int sum = num_1[i] - '0' + num_2[i] - '0'; // складываем num_1[i] & num_2[i]
 
        if (flag) { // если получили число > 9, то прибавляем 1. Опускаем флаг
            sum++;
            flag = false;
        }
 
        if (sum > 9) { // если sum > 9, то уменьшаем на 10 --> переводим значение в char --> записываем в num_1[i]
            num_1[i] = sum - 10 + '0';
            flag = true;
        }
        else {
            num_1[i] = sum + '0'; // если sum < 9, то переводим значение в char --> записываем в num_1[i]
        }
    }
 
    for (int i = num_2.length(); flag && i < num_1.length(); i++) { // если после прибавления num_2 + num_1 у нас поднят флаг,
                                                    //то +1 к последующим десяткам пока flag = true || не дойдём до конца num_1
        if (num_1[i] < '9') {
            num_1[i]++;
            flag = false;
        }
        else {
            num_1[i] = '0';
        }
    }
 
    if (flag) { // если после прохода flag = true, то +1 в конец строки
        num_1 += '1';
    }
    return num_1;
}
 
 
string subtraction(string num_1, string num_2) { // num_1 - num_2. Рассматриваем только num_1 >= num_2 без отрицательных чисел
 
    bool flag = false; // flag -->  num[i] + num_2[i] < 0
 
    for (int i = 0; i < num_2.length(); i++) {
        int sub = num_1[i] - '0' - num_2[i] - '0'; // num_1[i] - num_2[i], '0' - самоуничтожаются
 
        if (flag) { // если получили число < 0, то из этой разности дополнительно -1
            sub--;
            flag = false;
        }
 
        if (sub < 0) { // если sub < 0, то sub += 10 --> переводим в char --> записываем в num_1[i]
            num_1[i] = sub + 10 + '0';
            flag = true;
        }
        else {
            num_1[i] = sub + '0'; // если sub > 0 --> переводим в char --> записываем в num_1[i]
        }
    }
 
    for (int i = num_2.length(); flag && i < num_1.length(); i++) { // если после num_1 - num_2 flag = true, то -1 из предыдущих десятков
                                                           // пока flag = true или пока не дойдём до конца num_1
        if (num_1[i] > '0') {
            num_1[i]--;
            flag = false;
        }
        else {
            num_1[i] = '9';
        }
    }
 
    for (int i = num_1.length() - 1; num_1[i] == 0 && num_1.length() > 1; i--) { // удаляем незначащие нули
        num_1.erase(num_1.length() - 1, 1);
    }
    return num_1;
}
 
 
string remainder(string num_1, string num_2) { // получение остатка от деления num_1 на num_2, остаток в num_1
    
    string dividend; // делимое
    divider[0] = num_2; //делитель
 
    for (int i = 1; i < 9; i++) {
        divider[i] = sum(divider[i - 1], num_2); // заполнение массива делителя
    }
 
 
 
    /**
    * Выполняем деление столбиком. Берём часть dividend длинной  делителя, если делить больше,
    * то добавляем ещё один символ к делимому (чтобы было 100% больше)
    */
    do {
        if (num_1[num_1.length() - 1] - '0' >= num_2[num_2.length() - 1] - '0') {
            dividend = num_1.substr(num_1.length() - num_2.length(), num_2.length());
            num_1.erase(num_1.length() - num_2.length(), num_2.length());
        }
        else {
            dividend = num_1.substr(num_1.length() - num_2.length() - 1, num_2.length() + 1);
            num_1.erase(num_1.length() - num_2.length() - 1, num_2.length() + 1);
        }
 
 
        /**
        * Выбор на какой делитель из списка мы будем делить dividend.
        * Наш цикл идёт до тех пор, пока не найден нужный делитель, на который можно поделить dividend,
        * но при этом на следующий делитель нельзя
        */
        int count = 0;
        bool flag = true;
 
        while (flag && count < 8) {
            if (comparison(dividend, divider[count]) >= 0 && comparison(dividend, divider[count + 1]) == -1) {
                flag = false;
            }
            else {
                count++;
            }
        }
 
        dividend = subtraction(dividend, divider[count]); // вычитаем из divident делитель, чтобы получить остаток
 
        if (dividend.length() != 1 || dividend[0] != '0') { // если остаток != 0, то то припишем остаток в начало делимого
            num_1.insert(num_1.length(), dividend, 0, dividend.length());
        }
        if (num_1 == "") { // если остаток пустой, то делитель делится нацело на делимое
            num_1 = "0";
        }
        if (comparison(num_1, num_2) == -1) { // если остаток от деления num_1 < num_2, то деление закончено и выходим из цикла
            break;
        } 
 
    }
    while (true);
    return num_1;
}
 
 
bool num_check(string num_1) { // проверка на неправильный ввод
 
    if (num_1[0] == '0') { // первый символ не ноль
        return false; 
    }
 
    for (int i = 1; i < num_1.length(); i++) { // значение должны быть 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
        if (num_1[i] < '0' || num_1[i] > '9') {
            return false;
        }
    }
    return true;
}
 
 
int main() {
 
    setlocale(LC_ALL, "Rus");
 
    string num_1;
    string num_2;
 
    number_1.open("C:\\BigNum\\BigNum_1.txt");
    number_2.open("C:\\BigNum\\BigNum_2.txt");
    number_1 >> num_1;
    number_2 >> num_2;
 
    bool error_enter; // флаг ошибки ввода
 
    cout << "Your first num - " << num_1 << endl;
    cout << "Your second num - " << num_2 << endl;
 
    if (num_1[0] == '+' || num_1[0] == '-') {
        num_1.erase(0, 1);                         // в начале числа может быть + или - и это никак не повлияет
    }
    if (num_2[0] == '+' || num_2[0] == '-') {
        num_2.erase(0, 1);
    }
 
    if (!num_check(num_1) || !num_check(num_2)) {
        cout << "Error enter. Please, try again...:(" << endl;
        error_enter = true;
    }
    else {
        error_enter = false;
    }
 
    num_1 = revers(num_1); // все вычисления будут производиться с перевёрнутыми числами
    num_2 = revers(num_2);
 
 
    /**
    * Используется алгоритм Евклида:
    */
    bool flag = true;
 
    if (!error_enter) {
        do {
            short comparison_ans = comparison(num_1, num_2);
 
            if (comparison_ans == 0) {
                cout << "GCD first number and second number: " << revers(num_1) << endl;
                flag = false;
            }
            else if (comparison_ans == 1){
                num_1 = remainder(num_1, num_2);
            }
            else {
                num_2 = remainder(num_2, num_1);
            }
 
            if (num_1 == "0") {
                cout << "GCD first number and second number: " << revers(num_2) << endl;
                flag = false;
            }
            else if (num_2 == "0") {
                cout << "GCD first number and second number: " << revers(num_1) << endl;
                flag = false;
            }
        }
        while (flag);
    }
 
    system("pause");
}

Новые блоги и статьи Все статьи Все блоги /
Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .	Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .
В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .	Сам себя обучал rest api anaschu 02.07.2026 Педагогический лайфхак: Почему чистый REST API для ученика намного круче, чем готовые библиотеки Когда мы отказались от капризного JAR-файла AnyLogic и переписали код на стандартный HttpClient,. . .

@Anhain 0 / 0 / 0 Регистрация: 03.10.2022 Сообщений: 26

	Посчитать НОД больших чисел 04.12.2022, 13:22. Показов 2033. Ответов 26 Метки нет (Все метки) Здравствуйте, у меня есть индивидуальное задание, в котором нужно разработать консольное приложение для нахождения НОД для двух больших чисел. Мне подсказали, что длинные числа можно реализовать с помощью массивов, но как именно это сделать? 0

@alexu_007 737 / 704 / 110 Регистрация: 29.05.2015 Сообщений: 4,316
	08.12.2022, 03:04
	Всё равно моя круче! Миниатюры 0

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,026
	08.12.2022, 05:43
	Ну так выложи свое решение. Чего стесняться? 0

@gunslinger place status here 3192 / 2227 / 640 Регистрация: 20.07.2013 Сообщений: 6,026
	08.12.2022, 12:39
	Прошу прощения. Сразу не увидел, что уже выложил. Лучше бы, конечно, вместе с ехе, ну да ладно. 0