Алгоритм Евклида — НОД на C++

Алгоритм Евклида c вычитанием

#include "stdafx.h"
#include <iostream>
using namespace std;

int NOD(int first, int second)
{
while (first!=second)
{
if (first>second) first-=second;
else second-=first;
}
return first;
}

void main ()
{
setlocale(LC_ALL,"Rus");
int first, second;
cout<<"Введите первое значение"<<endl;
cin>>first;
cout<<"Введите второе значение"<<endl;
cin>>second;
cout<<"НОД("<<first<<", "<<second<<")="<<NOD(first, second)<<endl;
system("pause");
}

результат выполнения программы НОД Евклида на C++


Алгоритм Евклида c делением

#include "stdafx.h"
#include <iostream>
using namespace std;

int NOD(int first, int second)
{
while (first!=0 && second!=0)
{
if (first>second) first%=second;
else second%=first;
}
return first+second;
}

void main ()
{
setlocale(LC_ALL,"Rus");
int first, second;
cout<<"Введите первое значение"<<endl;
cin>>first;
cout<<"Введите второе значение"<<endl;
cin>>second;
cout<<"НОД("<<first<<", "<<second<<")="<<NOD(first, second)<<endl;
system("pause");
}

результат выполнения программы НОД Евклида на C++


Алгоритм Евклида c вычитанием и рекурсией

#include "stdafx.h"
#include <iostream>
using namespace std;

int NOD(int first, int second)
{
if(first==second)return first;

if (first<second) return NOD(first, second-first);
else return NOD(first-second, second);

}

void main ()
{
setlocale(LC_ALL,"Rus");
int first, second;
cout<<"Введите первое значение"<<endl;
cin>>first;
cout<<"Введите второе значение"<<endl;
cin>>second;
cout<<"НОД("<<first<<", "<<second<<")="<<NOD(first, second)<<endl;
system("pause");
}

результат выполнения программы НОД Евклида на C++


Алгоритм Евклида c делением и рекурсией

#include "stdafx.h"
#include <iostream>
using namespace std;

int NOD(int first, int second)
{
if (first*second==0) return first+second;
if (first<second)return NOD(first, second%first);
else return NOD(first%second, second);
}

void main()
{
setlocale(LC_ALL,"Rus");
int first, second;
cout<<"Введите первое значение"<<endl;
cin>>first;
cout<<"Введите второе значение"<<endl;
cin>>second;
cout<<"НОД("<<first<<", "<<second<<")="<<NOD(first, second)<<endl;
system("pause");
}

результат выполнения программы НОД Евклида на C++


Бинарный алгоритм вычисления наибольшего общего делителя


#include "stdafx.h"
#include <iostream>
using namespace std;

int NOD(int first, int second)
{
int k=1;
while ((first!=0) && (second!=0))
{
while ((first%2==0) && (second%2==0))
{
first/=2;
second/=2;
k*=2;
}
while (first%2==0) first/=2;
while (second%2==0) second/=2;
if (first>=second) first-=second; else second-=first;
}
return second*k;
}

void main()
{
setlocale(LC_ALL,"Rus");
int first, second;
cout<<"Введите первое значение"<<endl;
cin>>first;
cout<<"Введите второе значение"<<endl;
cin>>second;
cout<<"НОД("<<first<<", "<<second<<")="<<NOD(first, second)<<endl;
system("pause");
}

результат выполнения программы НОД Евклида на C++

Leave a Reply

Ваш e-mail не будет опубликован.