НОД - C++

@Leff · Регистрация: 15.11.2010

Извиняюсь за вопрос, просмотрел все но не нашел того, что нужно

Задание: Найти НОД 2 чисел

C++

# include <iostream>
# include <conio.h>
using namespace std;
int main(){
    int a,b,i;
cout<< "vvedite 2 4isla";
cin>>a;
cin>>b;
while (a%i!=0)||(b%i!=0){
 
    i=a<b?a:b;
    i--;}
cout<<"max="<< i;
return 0;
}

Что я неправильно написал ? Она даже не запускается...

valeriikozlov · 26.01.2011, 10:14

Leff,

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

Что я неправильно написал ? Она даже не запускается...

Вы неправильно написали вот что:

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

while (a%i!=0)||(b%i!=0){// значение i не определено и еще оба условия нужно брать в круглые скобки

К тому же Вы здесь пытаетесь использовать два алгоритма в одном. Лучше использовать какой-нибудь один алгоритм, например так:

C++

# include <iostream>
# include <conio.h>
using namespace std;
int main(){
int a,b,i;
cout<< "vvedite 2 4isla";
cin>>a;
cin>>b;
i=a;
while ((a%i!=0)||(b%i!=0)){
i--;}
cout<<"max="<< i;
return 0;
}

Но есть еще более оптимальный по времени алгоритм.

@no0ker · 26.01.2011, 16:01

не знаю почему, но мне этот алгоритм показался каким то чУдным =)

C

1 2	while ((a%i!=0)\|\|(b%i!=0)){ i--;}

а мой первый реализованный алгоритм был вообще ужас.
раскладывал каждое из чисел на простые множители. и коэфициенты при них.
потом собирал результат как произведение простых множителей с бОльшими коэфициентами при них. =)

valeriikozlov · 26.01.2011, 16:08

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

не знаю почему, но мне этот алгоритм показался каким то чУдным =)

Вообще-то этот алгоритм читался в Вашем коде.
Вот нормальный алгоритм:

C

int NOD(int a, int b)
{
    while(a>0 && b>0) 
        if(a>b)
            a%=b; 
        else
            b%=a; 
    return a+b;
}

Опции темы

С++ для начинающих

НОД - C++