Найти наименьший периметр треугольника, вершины которого принадлежат различным точкам множества

@DimaGG · Регистрация: 23.04.2013

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

Дано множество A из N точек с координатами (x,y). Найти наименьший периметр треугольника, вершины которого принадлежат различным точкам множества A, и сами эти точки (точки выводятся в том же порядке, в котором они перечислены при задании множества A).

@Good-Morning · 05.10.2013, 14:46

Какой диалект?

@DimaGG · 05.10.2013, 15:48 **[ТС]**

Всмысле?

@Good-Morning · 05.10.2013, 15:52

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

Всмысле?

Вам это нужно написать на каком Бейсике? Quick Basic? Turbo Basic? Free Basic? Visual Basic? VBA?

@DimaGG · 05.10.2013, 16:00 **[ТС]**

QBASIC

@Good-Morning · 05.10.2013, 16:28

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

QBASIC

Ясно.

Не по теме:

(Я уж дамал GW Basic :yahoo::D)

Значит, предлагаю следующее:
1). Создать процедуру нахождения растояния между точек
2). Создать процедуру нахождения минимального расстояния между данной точкой и остальными (используя процедуру 1)
3). Используя данные процедуры находить 3 минимальных значений и вывести полученные точки.
Тупо методом перебора (в том варианте немного страдала логика).

Добавлено через 18 минут
Кстати... Если точек n, то вариантов
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{n}^{3}-3{n}^{2}+2n$
При n=10 значение этого выражения достигает 720, а при n=100 значение зашкаливает за 970 тысяч. Да и вообще:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\lim {n}^{3}-3{n}^{2}+2n={n}^{3}$
При n->∞

@DimaGG · 07.10.2013, 13:57 **[ТС]**

Можно по подробней?

@Good-Morning · 07.10.2013, 16:12

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

Можно по подробней?

Можно.
Перебираем все варианты треугольников. Находим тот, чей периметр меньше периметра либого другого. Выводим результат.

@DimaGG · 07.10.2013, 16:29 **[ТС]**

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

@Good-Morning · 07.10.2013, 16:35

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

Это не подходит, нужно оптимальный вариант.

Такой вариант я пока придумать не могу... Тут нужна, скорее, геометрия.

@DimaGG · 07.10.2013, 17:15 **[ТС]**

Формула определения длины: d=sqr((x2-x1)^2+(y2-y1)^2)

@Good-Morning · 07.10.2013, 17:22

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

Формула определения длины: d=sqr((x2-x1)^2+(y2-y1)^2)

Это-то понятно

. Стандартная формула такая - я о другом немного, сложно объяснить. В общих чертах - как алгоритм желаемой программы выглядит на словах?

@DimaGG · 07.10.2013, 17:34 **[ТС]**

Я так понял, что у тебя как и у меня идей нет?

@Good-Morning · 07.10.2013, 17:35

Надо подумать.

@DimaGG · 07.10.2013, 17:40 **[ТС]**

Я думаю, что нужно задать 2 массива, в 1 вводим все x, а в другой все y.
Что-то типа такого получиться d=sqr((M1[1]-M1[0])^2+(M2[1]-M2[0]^2)

@Good-Morning · 07.10.2013, 17:48

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

Что-то типа такого получиться

По-моему, мы с этим уже решили, нет? Я говорю про алгоритмы решения. Вот с этим у меня проблема. У Вас есть идеи по поводу алгоритма?

@Апострофф · 07.10.2013, 20:20

У Вас есть идеи по поводу алгоритма?

Какие идеи

Ведь всё банально до неприличия
ввод и вывод массивов смотрим здесь - Как заполнить массив и вывести его на экран

QBasic/QuickBASIC
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
CONST n=10 'к-во точек
REDIM x(1 TO n)AS DOUBLE, y(1 TO n)AS DOUBLE 'координаты
DIM a%, b%, c%, p#
DIM am%, bm%, cm%, pm# 'здесь  будет сохранен результат
 
'ввод и вывод массивов смотрим здесь - [url]https://www.cyberforum.ru/qbasic/thread122284.html[/url]
 
pm=1.79769313486231E308
FOR a=1 TO n-2
  FOR b=a+1 TO n-1
    FOR c=b+1 TO n
      p=SQR((x(b)-x(a))^2+(y(b)-y(a))^2)+SQR((x(c)-x(b))^2+(y(c)-y(b))^2)+SQR((x(c)-x(a))^2+(y(c)-y(a))^2)
      IF p<pm THEN pm=p: am=a: bm=b: cm=c
    NEXT
  NEXT
NEXT
'вывод pm, am, bm, cm

@Good-Morning · 07.10.2013, 20:23

Сообщение от Апострофф

Ведь всё банально до неприличия

DimaGG упоминал, что метод перебора не годится...

@Апострофф · 07.10.2013, 20:26

А ещё его слова -

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

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

@DimaGG · 07.10.2013, 21:30 **[ТС]**

Большое вас спасибо за помощь, очень помогли)

Добавлено через 38 минут
только откуда это значение pm=1.79769313486231E308?

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .	Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .	Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32

	Найти наименьший периметр треугольника, вершины которого принадлежат различным точкам множества 05.10.2013, 13:16. Показов 4191. Ответов 22 Метки нет (Все метки) Дано множество A из N точек с координатами (x,y). Найти наименьший периметр треугольника, вершины которого принадлежат различным точкам множества A, и сами эти точки (точки выводятся в том же порядке, в котором они перечислены при задании множества A). 0

@Good-Morning 1045 / 315 / 74 Регистрация: 13.07.2013 Сообщений: 1,270
	05.10.2013, 14:46
	Какой диалект? 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	05.10.2013, 15:48 [ТС]
	Всмысле? 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	05.10.2013, 16:00 [ТС]
	QBASIC 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	07.10.2013, 13:57 [ТС]
	Можно по подробней? 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	07.10.2013, 16:29 [ТС]
	Это не подходит, нужно оптимальный вариант. Можно создать тройной цикл где и будет выходить решение, у меня не получается сделать. 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	07.10.2013, 17:15 [ТС]
	Формула определения длины: d=sqr((x2-x1)^2+(y2-y1)^2) 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	07.10.2013, 17:34 [ТС]
	Я так понял, что у тебя как и у меня идей нет? 0

@Good-Morning 1045 / 315 / 74 Регистрация: 13.07.2013 Сообщений: 1,270
	07.10.2013, 17:35
	Надо подумать. 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	07.10.2013, 17:40 [ТС]
	Я думаю, что нужно задать 2 массива, в 1 вводим все x, а в другой все y. Что-то типа такого получиться d=sqr((M1[1]-M1[0])^2+(M2[1]-M2[0]^2) 0

@DimaGG 0 / 0 / 1 Регистрация: 23.04.2013 Сообщений: 32
	07.10.2013, 21:30 [ТС]
	Большое вас спасибо за помощь, очень помогли) Добавлено через 38 минут только откуда это значение pm=1.79769313486231E308? 0