Форум программистов, компьютерный форум, киберфорум
Наши страницы
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
syuzka
0 / 0 / 0
Регистрация: 22.05.2011
Сообщений: 11
1

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

25.05.2011, 00:02. Просмотров 1714. Ответов 1
Метки нет (Все метки)

Андрей недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.
Алгоритм Евклида заключается в следующем:
1. Пусть a, b — числа, НОД которых надо найти.
2. Если b = 0, то число a — искомый НОД.
3. Если b > a, то необходимо поменять местами числа a и b.
4. Присвоить числу a значение a – b.
5. Вернуться к шагу 2.
Андрей достаточно быстро освоил алгоритм Евклида и вычислил с его помощью много наибольших общих делителей. Поняв, что надо дальше совершенствоваться, ему пришла идея решить новую задачу. Пусть заданы числа a, b, c и d. Требуется узнать, наступит ли в процессе реализации алгоритма Евклида для заданной пары чисел (a, b) такой момент, когда перед исполнением шага 2 число a будет равно c, а число b будет равно d.
Требуется написать программу, которая решает эту задачу.
Формат входных данных
Первая строка входных данных содержит количество наборов входных данных K (1 ≤ K ≤ 100). Далее идут описания этих наборов. Каждое описание состоит из двух строк. Первая из них содержит два целых числа: a, b (1 ≤a, b ≤ 1018). Вторая строка – два целых числа: c, d (1 ≤ c, d ≤ 1018).
Все числа в строках разделены пробелом.
Формат выходных данных
Для каждого набора входных данных выведите слово «YES», если в процессе применения алгоритма Евклида к паре чисел (a, b) в какой-то момент получается пара (c, d). В противном случае выведите слово «NO».
Пример

2
20 10
10 10
10 7
2 4 YES
NO
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.05.2011, 00:02
Ответы с готовыми решениями:

Алгоритм Евклида
Напишите пожалуйста программу!СПАСИБО!! Описать нерекурсивную функцию...

Задача на алгоритм Евклида
Даны три натуральных числа. Найти их наибольший общий делитель, используя...

Алгоритм Евклида. Где ошибка?
Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он...

НОД . Рекурсивный алгоритм Евклида
1. Даны два натуральных числа X и Y. Найти их наибольший общий делитель,...

Алгоритм Евклида. Найти наибольший общий делитель
Пожалуйста, помогите) нужно написать задачу в Паскале и написать блок-схему....

1
Small Lamer
143 / 143 / 141
Регистрация: 05.04.2011
Сообщений: 270
25.05.2011, 00:17 2
Лучший ответ Сообщение было отмечено syuzka как решение

Решение

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var
    x,i,k,a,b,c,d:longint;
    f:boolean;
    g:array[1..100] of boolean;
begin
  readln(k);
  for i:=1 to k do begin
  read(a,b,c,d);
  f:=false;
  while b<>0 do
    begin
      if (a=c)and(b=d) then f:=true;
      if b>a then begin
        x:=a;
        a:=b;
        b:=x;
      end;
      a:=a-b;
    end;
  g[i]:=f;
  end;
  for i:=1 to k do if g[i] then writeln('YES') else writeln('NO');
end.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.05.2011, 00:17

Построить алгоритм Евклида для нахождения НОД чисел
Заданы два натуральных числа a, b. Построить алгоритм Евклида для нахождения...

Описать процедуру NOD2(A, B) целого типа, используя алгоритм Евклида
Описать процедуру NOD2(A, B) целого типа, находящую наибольший общий ...

Алгоритм Евклида нахождения наибольшего общего делителя (НОД) неотрицательных целых чисел
Алгоритм Евклида нахождения наибольшего общего делителя (НОД) неотрицательных...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru