Программа нахождения НОД двух чисел (нужны комментарии)

@koyonn · Регистрация: 13.06.2017

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

Только недавно начал изучать С++, не могу осмыслить блок инструкций после while. Можете, пожалуйста, объяснить простыми словами как это происходит?

C++

#include <iostream>
using namespace std;
 
int main()
{
    int n1, n2;
    int nod;
    int r;
    cout<<"Input n1: \n";
    cin>>n1;
    cout<<"Input n2: \n";
    cin>>n2;
    while(n1%n2) {
        r=n1%n2;
        n1=n2;
        n2=r;
    }
    nod=n2;
    cout<<n2;
    return 0;
}

@Renji · 22.06.2017, 01:10

Алгоритм Евклида. Это не сюда, а на математический форум.
Наибольший общий делитель делит два числа A и B без остатка.
Представим A как B*N+X. Значит, НОД у нас делит без остатка B и B*N+X. Если X у нас здесь нулевой, значит НОД равен B.
Если НОД делит без остатка B, ясное дело он делит без остатка и B*N. Из чего следует что он должен делить без остатка и X (иначе сумма B*N+X не поделится).
Го в начало, поменяв A и B, на X и B.

@koyonn · 22.06.2017, 21:17 **[ТС]**

Ну а все-таки, может кто объяснить пошагово как здесь работает цикл while ?

@Renji · 22.06.2017, 21:20

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

Ну а все-таки, может кто объяснить пошагово как здесь работает цикл while ?

С самим то циклом что не ясно? % - остаток от деления. Цикл крутится пока этот остаток не нулевой (нулевое значение считается за ложь, не нулевое - за истину).

@koyonn · 22.06.2017, 21:48 **[ТС]**

Renji, в общих чертах я понимаю как это происходит, но только начал циклы изучать. В голове я не могу представить как одна переменная заменяется другою, если я правильно понял.
Вот взять числа 20(n1) и 15(n2), что будет с ними происходить в цикле, можете, пожалуйста, описать?

@Renji · 22.06.2017, 21:50

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

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

Через оператор присваивания =. Опять же, что непонятно то? r получает остаток от деления, n1 получает значение n2, n2 получает значение r. Именно в такой последовательности.

@koyonn · 22.06.2017, 22:31 **[ТС]**

Renji, сел и на бумаге подробно расписал по шагам и все получилось, спасибо

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	22.06.2017, 01:10	2
	Алгоритм Евклида. Это не сюда, а на математический форум. Наибольший общий делитель делит два числа A и B без остатка. Представим A как BN+X. Значит, НОД у нас делит без остатка B и BN+X. Если X у нас здесь нулевой, значит НОД равен B. Если НОД делит без остатка B, ясное дело он делит без остатка и BN. Из чего следует что он должен делить без остатка и X (иначе сумма BN+X не поделится). Го в начало, поменяв A и B, на X и B. 1

@koyonn 0 / 0 / 0 Регистрация: 13.06.2017 Сообщений: 8
	22.06.2017, 21:17 [ТС]	3
	Ну а все-таки, может кто объяснить пошагово как здесь работает цикл while ? 0

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	22.06.2017, 21:20	4
	Сообщение от koyonn Ну а все-таки, может кто объяснить пошагово как здесь работает цикл while ? С самим то циклом что не ясно? % - остаток от деления. Цикл крутится пока этот остаток не нулевой (нулевое значение считается за ложь, не нулевое - за истину). 0

@koyonn 0 / 0 / 0 Регистрация: 13.06.2017 Сообщений: 8
	22.06.2017, 21:48 [ТС]	5
	Renji, в общих чертах я понимаю как это происходит, но только начал циклы изучать. В голове я не могу представить как одна переменная заменяется другою, если я правильно понял. Вот взять числа 20(n1) и 15(n2), что будет с ними происходить в цикле, можете, пожалуйста, описать? 0

@Renji 2782 / 1935 / 570 Регистрация: 05.06.2014 Сообщений: 5,600
	22.06.2017, 21:50	6
	Сообщение от koyonn Я в голове не могу представить как одна переменная заменяется другою, если я правильно понял. Через оператор присваивания =. Опять же, что непонятно то? r получает остаток от деления, n1 получает значение n2, n2 получает значение r. Именно в такой последовательности. 1

@koyonn 0 / 0 / 0 Регистрация: 13.06.2017 Сообщений: 8
	22.06.2017, 22:31 [ТС]	7
	Renji, сел и на бумаге подробно расписал по шагам и все получилось, спасибо 0