Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Задача, Разработать процедуру, помогите

13K
13 февраля 2006 года
NEON_UA
3 / / 01.10.2005
Помогите плз решить задачу, очень сложно...
Тема: Разработать процедуру.
Задача: Из заданного на плоскости множества точек выбрать три такие, которые составляют треугольник наименьшей площади.
13K
16 февраля 2006 года
NEON_UA
3 / / 01.10.2005
Цитата:
Originally posted by NEON_UA
Помогите плз решить задачу, очень сложно...
Тема: Разработать процедуру.
Задача: Из заданного на плоскости множества точек выбрать три такие, которые составляют треугольник наименьшей площади.


Плз помогите, даже идей нету. :(

534
18 февраля 2006 года
HarryAxe
448 / / 19.01.2006
Цитата:
Originally posted by NEON_UA
Плз помогите, даже идей нету. :(


Код я тебе писать не буду, не жди. А вот идею расскажу. Площадь треугольника вычисляй по формуле Герона. После небольшой оптимизации она выглядит так: abs((X2 - X1)*(Y3 - Y1) - (X3 - X1)*(Y2 - Y1))/2. Abs - это модуль числа. Для удобства я бы на твоём месте объединил координаты точек в структуру (типа

private type Point
x as single
y as single
end type

), а вычисление площади вынес бы в отдельную функцию (напр. Square). В основной функции объявляешь переменную (напр. MinSquare as Single), где хранить будешь площадь минимальную, и присваеваешь ей значение площади от первых трёх точек. После этого, поскольку разницы в порядке перебора точек нет, пишешь набор вложенных циклов

 
Код:
for i = 2 to n - 2
    for j = i + 1 to n - 1
        for k = j + 1 to n
    ...
        next k
    next j
next i

внутри последнего из которых (вместо многоточия) вычисляешь площадь треугольника от точек pi, pj, pk. n у тебя - общее количество точек. Так вот полученную площадь ты сравниваешь с минимальной (на первм шаге она у тебя равна площади от первых трёх точек, помнишь? Именно поэтому индекс в первом for начинается с 2). И если полученная меньше минимальной, присваиваем значению минимальной площади значение только что полученной. А ещё и порядковые номера точек сохрани (т. е. i, j и k, до цикла значения переменных для хранения индексов у тебя должны быть равны 1, 2 и 3 соответственно). В итоге, после выхода из циклов, в переменной MinSquare у тебя будет минимальное значение площади, а номера точек, которые её дают, ты знаешь (потому что сохранил их). Всё. Задача на этом решена, а с тебя, как минимум, ОГРОМНОЕ СПАСИБО за то, что я не обломался поискать и модернизировать формулу, а ещё и столько строк печатного текста накрапать. Желаю удачи!
534
18 февраля 2006 года
HarryAxe
448 / / 19.01.2006
Хотя погоди, в цикле for i индексацию начинай с 1, я подзатупил немножко...
13K
04 марта 2006 года
NEON_UA
3 / / 01.10.2005
Спасибо большое. :)
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог