чувствую себя дегенератом :(

И вот я, следуя советам многих, час назад начал читать монографию Д. Кнута "Исскуство программирования". Автор приводит алгоритм Евклида :
Алгоритм Е
E1. [Нахождение остатка.] Разделим m на n, пусть остаток от деления будет равен r (где 0<=r<n)
E2. [Сравнение с нулем.] Если r=0, то выполнение алгоритма прекращается; n- искомое значение.
E3. [Замещение.] присвоить m:=n, n:=r и вернуться к шагу E1.

Я решил, что следует быстренько реализовать на C++:

Код (Text):

1. #include <stdio.h>
2. #include <conio.h>
3.  int main()
4.   {
5.    int m,n,r;
6.    printf("введи m,n: ");
7.    scanf("%d%d",&m,&n);
8.    
9.    r=m%n;
10.    while(r!=0){
11.     m=n;
12.     n=r;
13.     r=m%n;
14.    
15.    }
16.   printf("наибольший общий делитель= %d",r);
17.   getch();
18.   return 0;
19. }

В конце раздела, в 3 упражнении: Измените алгоритм E (из соображений эффективности) таким образом, чтобы исключить из него все тривиальные операции замены типа "m:=n". Запишите этот новый алгоритм в стиле алгоритма E и назовите его алгоритомом F.

На C++ у меня получилось так:

Код (Text):

1. #include <stdio.h>
2. #include <conio.h>
3.  int main()
4.   {
5.    int m,n,r;
6.    printf("введи m,n: ");
7.    scanf("%d%d",&m,&n);
8.    
9.    r=m%n;
10.    while(r!=0){
11.     if(!(n%r)) break;
12.     r=n%r;
13.    
14.    }
15.   printf("наибольший общий делитель= %d",r);
16.   getch();
17.   return 0;
18. }

Вот только если после первого нахождения остатка он будет равен нулю, программа выведет 0. Почуствовал себя имбицилом, когда не смог решить вроде такое простое упражнение(хотя может время суток сказалось...).


ГЫ, посидел щас 3 минуты, и добавил

Код (Text):

1. #include <stdio.h>
2. #include <conio.h>
3.  int main()
4.   {
5.    
6.    int m,n,r;
7.    printf("введи m,n: ");
8.    scanf("%d%d",&m,&n);
9.    
10.    r=m%n;
11.    while(r!=0){
12.     if(!(n%r)){
13.        n=r;
14.        break;}
15.     r=n%r;
16.    
17.    }
18.   printf("наибольший общий делитель= %d",n);
19.   getch();
20.   return 0;
21. }

Хорошо хоть ананимно отписался. Все, пойду спать ) Только в результате от тривиальных операций избавиться не удалось. Что хочет автор???

 

anonimniy

В таком виде оно не будет работать вообще попробуй вычислить gcd(19,15), выйдет 3.

 

тут я окончательно запутался (

 

Эти операции никак нельзя исключить, хотя можно завуалировать при рекурсивной реализации.

 

Да можно в принципе, только смысл какой?

Код (Text):

1. #include <stdio.h>
2. #include <conio.h>
3.  int main()
4.   {
5.    
6.    int m,n;
7.    printf("enter m,n (m>=n): ");
8.    scanf("%d%d",&m,&n);
9.    
10.    int a[2];
11.    a[0]=m;
12.    a[1]=n;
13.  
14.    int i=1;
15.    do{
16.     i=1-i;
17.     a[i]%=a[1-i];
18.    } while(a[i]);
19.  
20.   printf("gcd(m,n)= %d",a[1-i]);
21.   getch();
22.   return 0;
23. }

 

А насколько баллов упражнение? если на <=10 то скорее всего вариант Stiver и будет являться решением.

 

за это упражнение автор дал 20 баллов. В примечаниях к упражнениям: упражнение с рейтингом 10- простая задача, которая заставляет задуматься над прочитанным, но не представляет особых трудностей. На ее решение вы затратите не больше минуты.
То, что представил Stiver, у меня для осмысления займет больше времени. С рейтингом 20- задача, требующая для решения от 15 до 20 минут.

 

Stiver
)) Такая идея у меня тоже вчера возникла, но я решил, что подобный изврат всё-таки противоречит условию эффективности.