Оптимизация НОД

@nimfa2077 · Регистрация: 02.07.2021

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

Всем привет, на лето задали дз по информатике задача звучит так : "Дано N чисел. Найти самое большое число, на которое делятся все N чисел".
Решение которое я придумал -

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function Nod(a,b:integer):integer;
begin
 while b <> 0 do
 if a>b then a:=a mod b else b:=b mod a;
 Nod:=a;
end;
 
var a:array[1..100] of integer;
    n,i:byte;
    k:integer;
begin
read(n);
writeln;
for i:=1 to n do
 begin
  read(a[i]);
 end;
for i:=1 to n do
k:=Nod(a[1],a[2]);
for i:=3 to n do k:=nod(k,a[i]);
writeln;
write(k);
end.

Но сайт для провероку видает превишение времени работи.Помогите пожалуста!

@volvo · 02.07.2021, 14:49

18-я строка здесь вообще зачем? На кой в цикле n раз делать одно и то же?

@nimfa2077 · 02.07.2021, 14:57 **[ТС]**

уже удалил,но всё равно проблема осталась.

@mr-Crocodile · 02.07.2021, 16:28

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

Pascal
1
2
3
4
5
6
function Nod(a,b:integer):integer;
begin
 while b <> 0 do
 if a>b then a:=a mod b else b:=b mod a;
 Nod:=a;
end;

возьми функцию NOD отсюда - Найти НОД трёх чисел. Примечание. НОД(a,b,c)=НОД(НОД(a,b),c).
или отсюда НОД

@nimfa2077 · 02.07.2021, 17:49 **[ТС]**

Так а чем они отличаются?

@mr-Crocodile · 02.07.2021, 17:56

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

Так а чем они отличаются?

реализацией немного отличаются.
какая из реализаций быстрее - не берусь судить.

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

видает превишение времени работи.

я бы ещё добавил выход по условию, если k стало равно 1.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Function Nod(a,b:integer):integer;
Begin
    While a<>b do
     if a>b then a:=a-b
      else b:=b-a;
    Nod:=a;
End;
 
var 
  a,k,n,i:integer;
begin
  read(n);
  writeln;
  Readln(k);
  for i:=2 to n do begin
     read(a);
     k:=nod(k,a);
     if k=1 then Break
  end;
  write(k);
end.

@Cyborg Drone · 02.07.2021, 19:46

Наименьшее количество итераций у алгоритма с остатками. Для большинства наборов данных он и самый быстрый.

Алгоритм с вычитанием медленнее, особенно, если числа сильно различаются. Пример: НОД(1000000000, 3). Согласитесь, 2 деления по модулю куда быстрее 333333335 вычитаний.

Бинарный алгоритм Евклида, казалось бы, должен быть быстрее, но это далеко не всегда так, поскольку количество итераций в нём не менее количества значащих двоичных разрядов в бОльшем числе. Этот алгоритм, может быть, даёт выигрыш по скорости, если вместо целочисленного деления на 2 использовать операцию арифметического сдвига вправо, но не для любых наборов данных.

nimfa2077, у Вас алгоритмическая ошибка в функции. Например, a=6, b=3. На первой итерации получим a=0, b=3, а на второй итерации программа завершится аварийно из-за попытки деления на 0. Поэтому в заголовке цикла нужно проверять и a, и b.

Если нужна скорость, то зачем тратить время на вызов функции и возврат из неё? Функция не нужна.

Для сдачи на проверочный сайт.

Простейший вариант:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var
  a, b, n: integer;
begin
  read(n, a);
  for n := 2 to n do
    begin
      read(b);
      while (a <> 0) and (b <> 0) do
        if a > b then a := a mod b
        else b := b mod a;
      inc(a, b)
    end;
  write(a)
end.

Можно исключить вычисления при достижении a=1, но не думаю, что этот вариант будет быстрее:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var
  a, b, n: integer;
begin
  read(n, a);
  for n := 2 to n do
    begin
      read(b);
      if a = 1 then continue;
      while (a <> 0) and (b <> 0) do
        if a > b then a := a mod b
        else b := b mod a;
      inc(a, b)
    end;
  write(a)
end.

Если на проверочном сайте все числа, может быть, за исключением n, вводятся в одной строке, то можно при достижении a=1 не просматривать оставшиеся числа, и не использовать n. Не знаю, правильно ли будет воспринят readln ботом сайта: если правильно, то этот вариант программы будет наилучшим, если нет - то бот будет ждать ввода на этом самом readln до скончания веков:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var
  a, b: integer;
begin
  read(a, a);
  while not EoLn and (a <> 1) do
    begin
      read(b);
      while (a <> 0) and (b <> 0) do
        if a > b then a := a mod b
        else b := b mod a;
      inc(a, b)
    end;
  readln;
  write(a)
end.

Если бот поймёт readln неправильно, можно попробовать удалить строку с readln.

Добавлено через 20 минут
Хотя... На проверочном сайте можно использовать файловый ввод-вывод, тогда последний вариант прокатит по-любому:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var
  a, b: integer;
  f: text;
begin
  assign(f, 'input.txt');
  reset(f);
  read(f, a, a);
  while not EoF and (a <> 1) do
    begin
      read(f, b);
      while (a <> 0) and (b <> 0) do
        if a > b then a := a mod b
        else b := b mod a;
      inc(a, b)
    end;
  close(f);
  assign(f, 'output.txt');
  rewrite(f);
  write(f, a);
  close(f)
end.

Добавлено через 13 минут
В последних двух программах можно применить цикл с постусловием:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var
  a, b: integer;
begin
  read(a, a);
  repeat
    read(b);
    while (a <> 0) and (b <> 0) do
      if a > b then a := a mod b
      else b := b mod a;
    inc(a, b)
  until EoLn or (a = 1);
  readln;
  write(a)
end.

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var
  a, b: integer;
  f: text;
begin
  assign(f, 'input.txt');
  reset(f);
  read(f, a, a);
  repeat
    read(f, b);
    while (a <> 0) and (b <> 0) do
      if a > b then a := a mod b
      else b := b mod a;
    inc(a, b)
  until EoF or (a = 1);
  close(f);
  assign(f, 'output.txt');
  rewrite(f);
  write(f, a);
  close(f)
end.

Новые блоги и статьи Все статьи Все блоги /
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .	Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ

@volvo Супер-модератор 33411 / 21521 / 8236 Регистрация: 22.10.2011 Сообщений: 36,922 Записей в блоге: 12
	02.07.2021, 14:49
	18-я строка здесь вообще зачем? На кой в цикле n раз делать одно и то же? 0

@nimfa2077 0 / 0 / 0 Регистрация: 02.07.2021 Сообщений: 12
	02.07.2021, 14:57 [ТС]
	уже удалил,но всё равно проблема осталась. 0

@nimfa2077 0 / 0 / 0 Регистрация: 02.07.2021 Сообщений: 12
	02.07.2021, 17:49 [ТС]
	Так а чем они отличаются? 0