Целые точки отрезка

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

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

Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат отрезку.

Входные данные
Даны четыре целых числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 1000.

Выходные данные
Требуется вывести количество точек отрезка, имеющих целочисленные координаты.

@Cyborg Drone · 03.08.2021, 03:26

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

Pascal

var
  x1, y1, x, y: integer;
begin
  readln(x1, y1, x, y);
  x := abs(x1 - x);
  y := abs(y1 - y);
  while (x <> 0) and (y <> 0) do
    if x > y then x := x mod y
    else y := y mod x;
  writeln(x + y + 1)
end.

@nimfa2077 · 03.08.2021, 11:28 **[ТС]**

К сожалению решение не правильное,на проверочном чайте видало 1 из 36.
Смог найти другое решение, но оно тоже не верно . 15 из 36

Pascal

var
  n,x1,y1,x2,y2,k,i: integer;
  y: real;
begin
  read(x1,y1,x2,y2);
  writeln;
  i:=x1;
  while i<x2 do
  begin
    inc(i);
    y:=((i-x1)*(y2-y1))/(x2-x1)-y1;
    if frac(y)=0 then inc(k);
  end;
  write(k+1);
end.

Новичок · 05.08.2021, 23:15

Сообщение от Cyborg Drone

while (x <> 0) and (y <> 0) do

А может быть or надо ? Пишу "может быть", потому что уже сонный, мог ерунду сказать.

@mr-Crocodile · 06.08.2021, 13:40

Сообщение от Новичок

А может быть or надо ? Пишу "может быть", потому что уже сонный, мог ерунду сказать.

нет.
там далее операции деления на y и на x - если одно из них будет нулевое - будет exception при делении на ноль.

ФедосеевПавел · 06.08.2021, 16:33

У меня чувство, что эта задача на нахождение НОД.

Добавлено через 56 секунд
А из НОД нахождение количества подобных треугольников с целочисленными координатами.

Добавлено через 32 минуты
Разобрался.

Cyborg Drone, именно такое решение и предложил, только я не сразу понял как НОД вычисляется.

Всё правильно, код рабочий.

@Cyborg Drone · 07.08.2021, 19:11

Был некоторое время занят.

nimfa2077, найденный Вами код - это неэффективное решение методом полного перебора. В этом коде есть алгоритмических ошибки:

Вовсе не обязательно должно быть x1 < x2, поэтому примерно в половине случаев цикл while не выполнится ни разу.
Если отрезок параллелен оси Y, то есть, если (x1 = x2) и (y1 ≠ y2), то результат будет неверным.
Не ошибка, но переменная n не используется.

Можно избавиться от вещественных операций. Поскольку y1 по условию целое, и поэтому дробная часть чисел (i-x1)*(y2-y1)/(x2-x1)-y1 и (i-x1)*(y2-y1)/(x2-x1) одна и та же, можно заменить первое число на второе, после чего заменить операцию / и функцию frac на операцию mod. Исправить можно так:

Pascal

var
  x1, y1, x2, y2, x, k: integer;
begin
  readln(x1, y1, x2, y2);
  if x1 = x2 then
    begin
      x := x1;
      x1 := y1;
      y1 := x;
      x := x2;
      x2 := y2;
      y2 := x
    end;
  if x1 > x2 then
    begin
      x := x1;
      x1 := x2;
      x2 := x;
      x := y1;
      y1 := y2;
      y2 := x
    end;
  for x := x1 + 1 to x2 do
    if (x - x1) * (y2 - y1) mod (x2 - x1) = 0 then inc(k);
  writeln(k + 1)
end.

Новые блоги и статьи
Как проводить научные вычисления на Python InfoMaster 15.01.2025 Python стал одним из наиболее востребованных языков программирования в области научных вычислений благодаря своей простоте, гибкости и обширной экосистеме специализированных библиотек. Научные. . .	Создание игры типа Minecraft на PyGame/Python: пошаговое руководство InfoMaster 15.01.2025 В данном руководстве мы рассмотрим процесс создания игры в стиле Minecraft с использованием библиотеки PyGame на языке программирования Python. Этот проект идеально подходит как для начинающих. . .	Как создать свою первую игру в стиле Doom на Unreal Engine InfoMaster 15.01.2025 Разработка шутера от первого лица в стиле классического Doom представляет собой увлекательное путешествие в мир игрового программирования, где сочетаются творческий подход и технические навыки. . . .	Параллельное программирование: основные технологии и принципы InfoMaster 15.01.2025 Введение в параллельное программирование Параллельное программирование представляет собой фундаментальный подход к разработке программного обеспечения, который позволяет одновременно выполнять. . .	Как написать микросервис на C# с Kafka, MediatR, Redis и GitLab CI/CD InfoMaster 15.01.2025 В современной разработке программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот подход позволяет разделить сложную систему. . .	Что такое CQRS и как это реализовать на C# с MediatR InfoMaster 15.01.2025 Концепция CQRS и её роль в современной разработке В современном мире разработки программного обеспечения архитектурные паттерны играют ключевую роль в создании масштабируемых и поддерживаемых. . .
Как настроить CI/CD с Azure DevOps InfoMaster 15.01.2025 CI/ CD, или непрерывная интеграция и непрерывное развертывание, представляет собой современный подход к разработке программного обеспечения, который позволяет автоматизировать и оптимизировать процесс. . .	Как настроить CI/CD с помощью Jenkins InfoMaster 15.01.2025 Введение в CI/ CD и Jenkins В современной разработке программного обеспечения непрерывная интеграция (CI) и непрерывная доставка (CD) стали неотъемлемыми элементами процесса создания качественных. . .	Как написать микросервис на Go/Golang с Kafka, REST и GitHub CI/CD InfoMaster 14.01.2025 Определение микросервиса, преимущества использования Go/ Golang Микросервис – это архитектурный подход к разработке программного обеспечения, при котором приложение состоит из небольших, независимо. . .	Как написать микросервис с нуля на C# с RabbitMQ, CQRS, Swagger и CI/CD InfoMaster 14.01.2025 В современном мире разработки программного обеспечения микросервисная архитектура стала стандартом де-факто для создания масштабируемых и гибких приложений. Этот архитектурный подход предполагает. . .	Как создать интернет-магазин на PHP и JavaScript InfoMaster 14.01.2025 В современном мире электронная коммерция стала неотъемлемой частью бизнеса. Создание собственного интернет-магазина открывает широкие возможности для предпринимателей, позволяя достичь большей. . .	Как написать Тетрис на Ассемблере InfoMaster 14.01.2025 Тетрис – одна из самых узнаваемых и популярных компьютерных игр, созданная в 1984 году советским программистом Алексеем Пажитновым. За прошедшие десятилетия она завоевала симпатии миллионы людей по. . .

@nimfa2077 0 / 0 / 0 Регистрация: 02.07.2021 Сообщений: 12
		1
	Целые точки отрезка 02.08.2021, 14:40. Показов 6219. Ответов 6 Метки нет (Все метки) Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат отрезку. Входные данные Даны четыре целых числа – координаты концов отрезка (x1, y1) и (x2, y2). Каждая из координат не превышает по абсолютной величине значения 1000. Выходные данные Требуется вывести количество точек отрезка, имеющих целочисленные координаты. 0

Новичок 1682 / 1095 / 489 Регистрация: 17.07.2012 Сообщений: 5,360
	05.08.2021, 23:15	4
	Сообщение от Cyborg Drone while (x <> 0) and (y <> 0) do А может быть or надо ? Пишу "может быть", потому что уже сонный, мог ерунду сказать. 0

@mr-Crocodile 3048 / 1668 / 656 Регистрация: 19.03.2019 Сообщений: 5,375
	06.08.2021, 13:40	5
	Сообщение от Новичок А может быть or надо ? Пишу "может быть", потому что уже сонный, мог ерунду сказать. нет. там далее операции деления на y и на x - если одно из них будет нулевое - будет exception при делении на ноль. 0

ФедосеевПавел Модератор 8561 / 4409 / 1655 Регистрация: 01.02.2015 Сообщений: 13,698 Записей в блоге: 9
	06.08.2021, 16:33	6
	У меня чувство, что эта задача на нахождение НОД. Добавлено через 56 секунд А из НОД нахождение количества подобных треугольников с целочисленными координатами. Добавлено через 32 минуты Разобрался. Cyborg Drone, именно такое решение и предложил, только я не сразу понял как НОД вычисляется. Всё правильно, код рабочий. 0

	07.08.2021, 19:11

Целые точки отрезка

Решение