Форум программистов, компьютерный форум, киберфорум
Наши страницы

Turbo Pascal

Войти
Регистрация
Восстановить пароль
 
Aleksandr666
6 / 6 / 0
Регистрация: 09.10.2017
Сообщений: 47
#1

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

25.10.2017, 19:18. Просмотров 158. Ответов 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
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Алгоритм Евклида. Где ошибка? (Turbo Pascal):

где ошибка? - Turbo Pascal
задание прикреплено в ворде, я написал вот так: program 1; var a,b,c,d,y:real; function tg(a,b,c:real):real; begin ...

Где ошибка? - Turbo Pascal
Program P1; var a,b,y:real; bagin; read(b,a); y:=abs(a)/b); write(y); end.

Где ошибка? - Turbo Pascal
Написал программу-задача:Дана вещественная матрица D размером 8х12. Сформировать одномерный массив,состоящий из номеров столбцов,элементы...

Где ошибка? - Turbo Pascal
Люди помогите понять где ошибка в программе. постоянно выдает ошибка 85! PROGRAM MAX_3; USES CRT; VAR A,B,C,MAX:INTEGER; BEGIN ...

Где ошибка? - Turbo Pascal
Помогите не могу понять где ошибка,переделываю программу с использованием процедур и функций,но ошибка помогите отладить. Program lab_92;...

Где ошибка - Turbo Pascal
Ввести m, n. Вывести квадраты чисел от m до n включительно. uses crt; var a:array of integer; m,n,i:integer BEGIN clrscr; ...

1
ФедосеевПавел
Модератор
3048 / 1775 / 726
Регистрация: 01.02.2015
Сообщений: 6,126
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
Привет! Вот еще темы с ответами:

Где ошибка? - Turbo Pascal
Вобщем суть программы, представленной ниже перевод чисел из десятичной системы в систему с основанием меньше 10, но моя программа почему-то...

Где ошибка? - Turbo Pascal
Поиск подстроки в строке!!!! и как исправить? выдает ошибку: выход за границы диапазона изменения индекса 1..10000 ошибка в 17 строке ...

Где ошибка? - Turbo Pascal
помогите найти ошибку program nod; uses crt; var function Nod (a,b: longint): longint ; begin while (a&lt;&gt;0) and...

где ошибка - Turbo Pascal
ошибка 202 {Program sort: Программа решает следующую задачу: Дано натуральное чисо N (1&lt;=N&lt;=100), целочисленнй линейный массив a0,...


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

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

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