Грани цензуры.

[valexey]

Кстати, я не совсем прав. У Евклида действительно использовалась разность, а не остаток от деления. Но в случае именно Евклида (и более ранних версий нахождения gcd) в качестве входных параметров нельзя было задать нуль, если не ошибаюсь, до Евклида (а возможно и во время него) люди ничего не знали о нуле, его просто не было.

Поэтому нужно либо использовать соответствующие типы, исключающие нуль, либо воткнуть ASSERT.

Ну а та форма которую я привел (и с валидным нулем, и остатком от деления), она много более современная, она уже появилась в нашей эре, аё автор, похоже, Леонардо Пизанский, по прозвищу Фибоначчи. Это 12xx год где-то.

[valexey]

А, ну да, точно, до Леонардо ведь все европейцы (которые считать конечно умели) пользовались римскими цифрами, а ну ка, изобразите ка римскими цифрами число нуль! :-)

Книга абака

[DIzer]

Ну а та форма которую я привел (и с валидным нулем, и остатком от деления), она много более современная, она уже появилась в нашей эре, аё автор, похоже, Леонардо Пизанский, по прозвищу Фибоначчи. Это 12xx год где-то.

Это и есть современное определение GSD (кстати программная реализация этого определения выглядит одинаково в большинстве языков программирования...(и конкретный ЯП тут "ВААЩЕ не причем")) .самое интересное что редуцирующая функция F(a,b) неоднозначна (вы привели 2 примера F(a,b)=a mod b и F=|a-b|).  

[valexey]

Ну а та форма которую я привел (и с валидным нулем, и остатком от деления), она много более современная, она уже появилась в нашей эре, аё автор, похоже, Леонардо Пизанский, по прозвищу Фибоначчи. Это 12xx год где-то.

Это и есть современное определение GSD (кстати программная реализация этого определения выглядит одинаково в большинстве языков программирования...) .самое интересное что редуцирующая функция F(a,b) неоднозначна (вы привели 2 примера F(a,b)=a mod b и F=|a-b|).  

Ненене, я же одну и ту же форму привел. rem и mod -- и то и другое есть отстаток от деления. И они полностью совпадают на положительных числах. Различаются на отрицательных

Код: [Выделить]

Prelude> rem 10 3
1
Prelude> mod 10 3
1
Prelude> rem 10 (-3)
1
Prelude> mod 10 (-3)
-2
Хотя, если подумать, то rem как раз через рекурсивный |a-b| и можно реализовать.

[DIzer]

Хотя, если подумать, то rem как раз через рекурсивный |a-b| и можно реализовать.

Вы о чем.... воистину горе от ума... 

[Geniepro]

Код: [Выделить]

  PROCEDURE GCD(x, y: INTEGER) : INTEGER;
  BEGIN
    WHILE x > y DO x := x - y
    ELSIF x < y DO y := y - x
    END;

    ASSERT(x = y);

    RETURN x
  END GCD;
За такой код я просто НЕЩАДНО наказываю студентов - почему, просто ЗАДАЧА не решена ...это не GCD - это ГОВНО (достаточно вычислить GSD(0,a)=GSD(a,0)=a по определению). Кроме того из этого кода следует, что Вирт просто не знает определения GSD... А между тем это код "виртухаями" тиражируется в кучу учебников и пособий...

Этот код является ТЕСТОМ для цикла Дейкстры (и его реализаций), а не промышленным кодом.

[DIzer]

Код: [Выделить]

  PROCEDURE GCD(x, y: INTEGER) : INTEGER;
  BEGIN
    WHILE x > y DO x := x - y
    ELSIF x < y DO y := y - x
    END;

    ASSERT(x = y);

    RETURN x
  END GCD;
За такой код я просто НЕЩАДНО наказываю студентов - почему, просто ЗАДАЧА не решена ...это не GCD - это ГОВНО (достаточно вычислить GSD(0,a)=GSD(a,0)=a по определению). Кроме того из этого кода следует, что Вирт просто не знает определения GSD... А между тем это код "виртухаями" тиражируется в кучу учебников и пособий...

Этот код является ТЕСТОМ для цикла Дейкстры (и его реализаций), а не промышленным кодом.

Вот ИМЕННО по этому у меня ЛИЧНО К ВАМ претензий нет 

[valexey]

Вот ИМЕННО по этому у меня ЛИЧНО К ВАМ претензий нет 

Кстати, я поискал (в гугле, по форумам, в книжках ручками) и повсеместного тиражирования этого ущербного кода не обнаружил. Быть может поделишься ссылочками где он растиражирован?

Например вот тут: http://sicp.org.ua/sicp/Exercise2-1  вполне вменяемая реализация.

[DIzer]

Кстати, я поискал (в гугле, по форумам, в книжках ручками) и повсеместного тиражирования этого ущербного кода не обнаружил. Быть может поделишься ссылочками где он растиражирован?

Например вот тут: http://sicp.org.ua/sicp/Exercise2-1  вполне вменяемая реализация.

У  Вирта и его эпигонов...

MODULE СборНОД;
   IMPORT  L := StdLog, In;
 
  (* Алгоритм Евклида, рекурсивный вариант *)
   PROCEDURE НОД_рек( a, b: INTEGER ) : INTEGER;
     VAR  s: INTEGER;
 BEGIN
     IF a > b THEN s := НОД_рек( a - b, b )
     ELSIF a < b THEN s := НОД_рек( a, b - a )
      ELSE s := a
       END;
      RETURN  s
   END НОД_рек;
 
  (* Алгоритм Евклида, циклический вариант без рекурсии *)
  PROCEDURE НОД( a, b: INTEGER ) : INTEGER;
 BEGIN
     WHILE a # b DO
            IF a > b THEN a := a - b ELSE b := b - a END
       END;
      RETURN  a
    END НОД;
 
  PROCEDURE Делать*;
        VAR a, b: INTEGER;
    BEGIN
     In.Open; In.Int( a );  In.Int( b );
     L.Int( НОД_рек( a, b ) );
     L.Int( НОД( a, b ) )
  END Делать;
 
END СборНОД.

    Вычислить наибольший общий делитель, используя рекурсивный алгоритм Евклида, который словесно формулируется так1: для того чтобы найти НОД двух чисел a и b, необходимо сравнить эти числа. Если они равны, то их НОД есть a. Если же одно больше другого, то нужно из большего вычесть меньшее и снова применить изложенный алгоритм к разности и меньшему из двух чисел. Процесс завершается, когда числа становятся равными.
   Здесь приведены рекурсивный и нерекурсивный варианты алгоритма, адаптированные на Компонентный Паскаль по книге1.
________________    
1Долинский М.С. Алгоритмизация и программирование на Turbo Pascal: от простых задач до сложных. Учебное пособие. - СПб.: Питер, 2005.-237 с.

Этот код из проекта информатика21.... И мне часто, увы, приходилось видеть подобную реализацию на паскале и си...

[igor]

Ненене, я же одну и ту же форму привел. rem и mod -- и то и другое есть отстаток от деления. И они полностью совпадают на положительных числах. Различаются на отрицательных

Зря Вы упомянули остатки от деления.  С ними в языках программирования (и в головах) полный разброд.

[DIzer]

Ненене, я же одну и ту же форму привел. rem и mod -- и то и другое есть отстаток от деления. И они полностью совпадают на положительных числах. Различаются на отрицательных

Зря Вы упомянули остатки от деления.  С ними в языках программирования (и в головах) полный разброд.

Вы говорите про реализацию , я говорю про сущность...

[igor]

Этот код является ТЕСТОМ для цикла Дейкстры (и его реализаций), а не промышленным кодом.

Вот ИМЕННО по этому у меня ЛИЧНО К ВАМ претензий нет 

А! Так Вы не знали того, что озвучил Geniepro?  

[valexey]

Код: [Выделить]

MODULE СборНОД;
  IMPORT  L := StdLog, In;
 
  (* Алгоритм Евклида, рекурсивный вариант *)
   PROCEDURE НОД_рек( a, b: INTEGER ) : INTEGER;
     VAR  s: INTEGER;
 BEGIN
     IF a > b THEN s := НОД_рек( a - b, b )
     ELSIF a < b THEN s := НОД_рек( a, b - a )
      ELSE s := a
       END;
      RETURN  s
   END НОД_рек;
END СборНОД.
Ой, оно ещё и на дикой смеси английского с русским... Поубивал бы.
Вообще, я у Вирта нашел такую реализацию алгоритма ровно в одном месте: http://www.inr.ac.ru/~info21/pdf/programming_in_oberon.pdf на странице 5.

Код: [Выделить]

PROCEDURE Gcd*;
  VAR x, y: INTEGER; S: Texts.Scanner;
BEGIN Texts.OpenScanner(S, Oberon.Par.text, Oberon.Par.pos);
  Texts.Scan(S); x := S.i; Texts.WriteString(W, " x ="); Texts.WriteInt(W, x, 6);
  Texts.Scan(S); y := S.i; Texts.WriteString(W, " y ="); Texts.WriteInt(W, y, 6);
  WHILE x # y DO
    IF x > y THEN x := x-y ELSE y := y-x END
  END;
  Texts.WriteString(W, " gcd ="); Texts.WriteInt(W, x, 6); Texts.WriteLn(W);
  Texts.Append(Oberon.Log, W.buf)
END Gcd.
А начинается все страницей раньше:

Let us follow the steps of development of a simple program and thereby explain some of the
fundamental concepts of programming and of the basic facilities of Oberon. The task shall be, given
two natural numbers x and y, to compute their greatest common divisor (gcd). The mathematical
knowledge needed for this problem is the following:

 1. if x equals y, x (or y) is the desired result
  2. the gcd of two numbers remains unchanged, if we replace the larger number by the difference of the
numbers, i.e. subtract the smaller number form the larger one.

Expressed in mathematical terms, these rules take the form
   1. gcd(x, x) = x
  2. if x > y, gcd(x, y) = gcd(x-y, y)

Ну собственно и все.

[DIzer]

Этот код является ТЕСТОМ для цикла Дейкстры (и его реализаций), а не промышленным кодом.

Вот ИМЕННО по этому у меня ЛИЧНО К ВАМ претензий нет 

А! Так Вы не знали того, что озвучил Geniepro?  

А что он сказал какое то непотребство в адрес Вирта а меня рядом не было...?  

[DIzer]

Ну собственно и все.

И вам этого мало?