Помоги решить задачки в Паскаль

[Timofeus]

Сообщение от Nadir Zaitov

Типа вы его специально создали, чтоб постебаться над "a:=a-b"?

Вы о чём?

[Nadir Zaitov]

Оффтоп:

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

Вы о чём?

О том, что алгоритм крайне медленный. Брутфорс.

[Vitaliy Fioktistov]

Пара красивых и быстрых алгоритмов)

//алгоритм Евклида через остатки
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}
 
// Алгоритм Евклида через разности
long Nod(long a, long b)
{
    while (a && b)
        if (a >= b)
           a -= b;
        else
           b -= a;
    return a | b;
}

И совсем уж непонятныйкомпактный:

int Nod( int a, int b )
{
   while( b^=a^=b^=a%=b );
   return a;
}

[Nadir Zaitov]

Сообщение от Vitaliy Fioktistov

{
    while (a && b)
        if (a >= b)
           a %= b;
        else
           b %= a;
    return a | b;
}

Я такой же алгоритм нарисовал. Также использовать идею с "и" и "или", только в нотации умножения и сложения. Конечно с использованием логики красивее, согласен.

А непонятный не разобрал.

[German Stimban]

Сообщение от Nadir Zaitov

Я такой же алгоритм нарисовал. Также использовать идею с "и" и "или", только в нотации умножения и сложения. Конечно с использованием логики красивее, согласен.

"Ифы" замедляют работу программы.
Я предпочитаю запускать функцию с заранее гарантированным неравенством a>=b и не париться с проверками каждую итерацию - проще проверить условие перед вводом данных в функцию.

[Nadir Zaitov]

Сообщение от German Stimban

"Ифы" замедляют работу программы.

Так "лупы" те же "ифы". Заменять "ифы" лишними "лупами" бессмысленно. Или вы как хотели? Можете более быстрый вариант расписать?

[German Stimban]

Сообщение от Nadir Zaitov

Так "лупы" те же "ифы". Заменять "ифы" лишними "лупами" бессмысленно. Или вы как хотели?

Сорри, криво посмотрел на код.
Если использовать рекурсию вместо цикла, будет чуть попроще в решении. Однако, рекурсия несёт и свои минусы.

[Vitaliy Fioktistov]

Сообщение от Nadir Zaitov

Я такой же алгоритм нарисовал. Также использовать идею с "и" и "или", только в нотации умножения и сложения. Конечно с использованием логики красивее, согласен.

А непонятный не разобрал.

Он при всей своей вырвиглазности, тем не менее работает). Правда, на Паскаль его из C++ вряд ли удастся настолько же красиво портировать)

[Nadir Zaitov]

Сообщение от Vitaliy Fioktistov

int Nod( int a, int b )
{
   while( b^=a^=b^=a%=b );
   return a;
}

Разобрался. Тут с помощью ряда xor реализована команда обмена данными между a и b.
Также красиво в Паскале не написать, но будет похоже. Я пишу в нотации сумм, а не xor, чтобы был "как бы" другой алгоритм )

function NOD(a,b: integer):integer;
var a,b,:integer;
  Begin
     Repeat
         a:=a mod b;
         a:=a+b;
         b:=a-b;
         a:=a-b;
     Until b=0;
     NOD:=a;
  End;