Форум программистов, компьютерный форум, киберфорум
Наши страницы
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Aleksandr666
6 / 6 / 15
Регистрация: 09.10.2017
Сообщений: 55
1

Алгоритм Евклида. Где ошибка?

25.10.2017, 19:18. Просмотров 209. Ответов 1
Метки нет (Все метки)

Дима недавно начал изучать информатику. Одним из первых алгоритмов, который он изучил, был алгоритм Евклида для нахождения наибольшего общего делителя (НОД) двух чисел. Напомним, что наибольшим общим делителем двух чисел a и b называется наибольшее натуральное число x, такое, что и число a, и число b делится на него без остатка.

Алгоритм Евклида заключается в следующем:

Пусть a, b - числа, НОД которых надо найти.
Если b = 0, то число a - искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a - b.
Вернуться к шагу 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 в противном случае.


Лимит времени 1 секунда

Лимит использования памяти 122.17 MiB
Входные данные #1
2
20 10
10 10
10 7
2 4
Выходные данные #1
YES
NO

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var
  a, b, c, d, bx, x, k, i: int64;
 
 
begin
  readln(k);
  for i := 1 to k do
  begin
    readln(a, b);
    readln(c, d);
    bx := b;
    while b <> 0 do
    begin
      x := a mod b;
      a := b;
      b := x;
    end;
    if (a = c) and (bx = d) then writeln('YES') else writeln('NO');
  end;
end.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2017, 19:18
Ответы с готовыми решениями:

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

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

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

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

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

1
ФедосеевПавел
Модератор
3759 / 2112 / 861
Регистрация: 01.02.2015
Сообщений: 7,017
25.10.2017, 21:15 2
Вы сопоставьте словесное описание алгоритма строкам кода - увидите несоответствие.
Если b = 0, то число a - искомый НОД.
Если b > a, то необходимо поменять местами числа a и b.
Присвоить числу a значение a - b.
Вернуться к шагу 2.
Запишите в виде комментариев.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2017, 21:15

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

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

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


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

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

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