НОД . Рекурсивный алгоритм Евклида

@venera-8 · Регистрация: 06.04.2010

Author24 — интернет-сервис помощи студентам

1. Даны два натуральных числа X и Y. Найти их наибольший общий делитель, используя рекурсивный алгоритм Эвклида.
Вход:
В текстовом файле INPUT.TXT записаны числа X и Y (1 <= X, Y <= 2,000,000,000).
Выход:
В текстовый файл OUTPUT.TXT записать наибольший общий делитель чисел X и Y.
Пример входа:
785625672 652672514
Пример выхода:
26

есть вот это

Pascal    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var a,b:longint;
    f1,f2:Text;
 
function NOD(x,y:longint):longint; 
begin
   if x<>0 then NOD:=NOD(y mod x,x) else NOD:=y;
end;
 
 
begin 
     Assign(f1,'input.txt');
  Reset(f1);
  Assign(f2,'output.txt');
  Rewrite(f2);
   while not seekeof(f1) do begin
    readln(f1,a,b);
    writeln(f2, NOD(a,b) );
    readln;  end; close(f1); close(f2);
end.

это вообще верно?) и как сюда всунуть условие со значениями переменных х и у? помогите пожалуйста

@iama · 04.06.2011, 19:59

Используя рекурсию, найти наибольший общий делитель двух натуральных чисел

Pascal    
        
            
                
                
                
                
            
        
    Скопировано
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var a, b, answer: longint;
  inf, outf: text;
 
function gcd(m, n: longint): longint;
    var modulo: longint;
    begin
        modulo := m mod n;
        if modulo = 0 then
            gcd := n
        else
            gcd := gcd (n, modulo)
    end;
 
begin
    assign(inf, 'input.txt'); reset(inf);
    assign(outf, 'output.txt'); rewrite(outf);
    readln(inf, a, b);
 
    answer := gcd(a, b);
    writeln(outf, answer);
 
    close(inf);
    close(outf);
    readln
end.

Если что, отсюда

@venera-8 · 04.06.2011, 20:02 **[ТС]**

спасибо конечно) но как в моем случае обозначить границы переменных не подскажите?)

@iama · 04.06.2011, 20:05

venera-8, ограничения указываются для того, чтобы вы правильно выбрали типи переменных, где вы храните данные, и правильно оценили потенциальную сложность разрабатываемого алгоритма. Для этой задачи играет роль, что все переменные имеют тип longint, благодаря чему не будет переполнений.

@venera-8 · 04.06.2011, 20:07 **[ТС]**

ясно,спасибо что объяснили. Благодарю.

@Puporev · 04.06.2011, 20:22

Сообщение от venera-8

В текстовом файле INPUT.TXT записаны числа X и Y (1 <= X, Y <= 2,000,000,000).

Что ты еще собираешься ограничивать? Все уже записано в файле...

@venera-8 · 04.06.2011, 20:27 **[ТС]**

Стеки. Вычисление выражения.Запись. а с этим вы не могли бы помочь? может ссылкой на такую задачу..

Добавлено через 2 минуты
так если я в файле введу например х=0 - он мне ошибку не выдает...и не должен? в задании же сказано что больше или равно 1..

@iama · 04.06.2011, 20:30

venera-8, то, что в задании указано, что

Сообщение от venera-8

X и Y (1 <= X, Y <= 2,000,000,000)

означает, что программа должна работать правильно только при таких входных данных, остальные наборы входных данных - не рассматриваются

@Puporev · 04.06.2011, 20:34

Обычно это задачи с разных сайтов и там данные для тестов всегда корректные.

Новые блоги и статьи Все статьи Все блоги /
Миграция монолита в Event-Driven микросервисную архитектуру на C# stackOverflow 11.04.2025 Монолитная архитектура – классический подход к разработке программного обеспечения. Это приложение, построенное как единое целое, где все компоненты тесно связаны между собой. Большинство проектов. . .	Go в Kubernetes: Управление ресурсами golander 11.04.2025 Разработчики Go-приложений в Kubernetes часто сталкиваются с неожиданными проблемами производительности и даже внезапными отказами контейнеров. Причина этого кроется в особенностях взаимодействия. . .	Агрегаты и сущности в DDD микросервисах Javaican 10.04.2025 Разработка современных программных систем часто приводит на распутье: монолит или микросервисы? Даже при выборе микросервисной архитектуры многие команды сталкиваются с проблемой правильного. . .	Многопоточность в C#: Task и параллельное программирование UnmanagedCoder 10.04.2025 Современные процессоры уже давно перестали наращивать тактовую частоту в пользу увеличения количества ядер. Это создало интересную ситуацию: разработчики, привыкшие к последовательному. . .	Линейное решение нелинейной задачи будет иметь приблизительный результат вычисления для метода обработки данных из double buffering. Hrethgir 10.04.2025 Вообще изначально я пренебрёг квадратурой числа, но потом понял, что для вычисления приблизительного значения - сгодится, формулу можно будет корректировать по ходу. Это потому что прямое соотношение. . .
Переменные в Python py-thonny 10.04.2025 Переменная в программировании — это символическое имя, связанное с областью памяти, в которой хранится значение. Она позволяет получать доступ к данным через понятные человеку идентификаторы, а не. . .	Многопоточность в C#: Task и асинхронные операции UnmanagedCoder 10.04.2025 Многопоточность позволяет выполнять несколько операций одновременно, что важно для решения двух основных задач: повышения скорости выполнения вычислительно-сложных операций и сохранения отзывчивости. . .	Запуск контейнеров Docker на ARM64 Mr. Docker 09.04.2025 Появление таких решений, как Apple M1/ M2, AWS Graviton, Ampere Altra и Raspberry Pi, сделало использование ARM-систем обыденностью для многих разработчиков и DevOps-инженеров. При этом Docker,. . .	Vue SFC компонент на PHP с Fusion Jason-Webb 09.04.2025 PHP на сервере и JavaScript на клиенте — классическое сочетание, которое, несмотря на свою эффективность, создает определенный когнитивный диссонанс при разработке. В этом контексте появляются. . .	TypeScript vs JavaScript: Отличия и когда что использовать Reangularity 09.04.2025 JavaScript появился в 1995 году как творение Брендана Эйха и быстро стал основой интерактивности в вебе. За свою историю он прошел путь от простого языка для манипуляций с DOM до полноценной. . .

@venera-8 0 / 0 / 0 Регистрация: 06.04.2010 Сообщений: 27
	04.06.2011, 20:02 [ТС]
	спасибо конечно) но как в моем случае обозначить границы переменных не подскажите?) 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	04.06.2011, 20:05
	venera-8, ограничения указываются для того, чтобы вы правильно выбрали типи переменных, где вы храните данные, и правильно оценили потенциальную сложность разрабатываемого алгоритма. Для этой задачи играет роль, что все переменные имеют тип longint, благодаря чему не будет переполнений. 0

@venera-8 0 / 0 / 0 Регистрация: 06.04.2010 Сообщений: 27
	04.06.2011, 20:07 [ТС]
	ясно,спасибо что объяснили. Благодарю. 0

@Puporev Почетный модератор 64312 / 47609 / 32742 Регистрация: 18.05.2008 Сообщений: 115,181
	04.06.2011, 20:22
	Сообщение от venera-8 В текстовом файле INPUT.TXT записаны числа X и Y (1 <= X, Y <= 2,000,000,000). Что ты еще собираешься ограничивать? Все уже записано в файле... 0

@venera-8 0 / 0 / 0 Регистрация: 06.04.2010 Сообщений: 27
	04.06.2011, 20:27 [ТС]
	Стеки. Вычисление выражения.Запись. а с этим вы не могли бы помочь? может ссылкой на такую задачу.. Добавлено через 2 минуты так если я в файле введу например х=0 - он мне ошибку не выдает...и не должен? в задании же сказано что больше или равно 1.. 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	04.06.2011, 20:30
	venera-8, то, что в задании указано, что Сообщение от venera-8 X и Y (1 <= X, Y <= 2,000,000,000) означает, что программа должна работать правильно только при таких входных данных, остальные наборы входных данных - не рассматриваются 0

@Puporev Почетный модератор 64312 / 47609 / 32742 Регистрация: 18.05.2008 Сообщений: 115,181
	04.06.2011, 20:34
	Обычно это задачи с разных сайтов и там данные для тестов всегда корректные. 0