Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.94/16: Рейтинг темы: голосов - 16, средняя оценка - 4.94
1 / 1 / 1
Регистрация: 25.10.2011
Сообщений: 42
1

Задача "Треугольник" Нахождения минимального периметра.

23.11.2011, 22:25. Показов 3147. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Задание:
На плоскости даны N точек. Никакие две точки не совпадают, никакие три не лежат на одной прямой. Найдите треугольник с вершинами в этих точках, имеющий наименьший возможный периметр.

Все это должно браться из файла, такого вида:
Input
5 - Кол-во точек
0 0 -т1
1.3 0 -т2
-2 0.1 -т3
1 0 -т4
10 10 - т5

В выходной файл выведите три числа – номера точек, которые должны быть вершинами треугольника, чтобы его периметр был минимален. Если решений несколько выведите любое из них.
Запись ответа в файл, такого вида:
Output
1 2 4


Есть примерный код:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
type Tpoint = record { тип Точка }
    x: double; { координата x }
    y: double; { координата y }
  end;
 
const N = 6;
 
const PArr : array[1..N] of TPoint =
  ((x:1;y:1),
   (x:2;y:2),
   (x:4;y:6),
   (x:4;y:7),
   (x:6;y:2),
   (x:7;y:1)
   );
 
function Distance(t1, t2 : integer) : extended;
begin
  Distance := sqrt( sqr(PArr[t1].x-PArr[t2].x) + sqr(PArr[t1].y-PArr[t2].y)  )
end;
 
var i1, i2, i3, k : integer;
  ab, bc, ac, per, minPer : extended;
  i1m, i2m, i3m : integer;
begin
  k := 0;
  i1m := -1;
  minPer := 1e10;
  for i1:=1 to N do
    for i2:=i1+1 to N do
      for i3:=i2+1 to N do
       if (i1<>i2) and (i2<>i3) and (i1<>i3) then begin
          ab := Distance(i1, i2);
          bc := Distance(i2, i3);
          ac := Distance(i1, i3);
          per := (ab+bc+ac);
          Writeln(i1, ' ', i2, ' ', i3,
                ' ab=',ab:7:3, ' bc=',bc:7:3, ' ac=',ac:7:3,
                ' perimeter = ', per:7:3);
          if per<minPer then begin
             minPer := per;
             i1m := i1; i2m := i2;  i3m := i3;
          end;
          inc(k)
       end;
  WriteLn('Сочетаний всего: ',k);
  WriteLn('Минимальный периметер = ',minPer:7:3,
       ' в точках ',
          i1m, ' ', i2m, ' ', i3m);
  Readln
end.
Нужно переделать немного, чтобы точки брались из файла !!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.11.2011, 22:25
Ответы с готовыми решениями:

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

Найти другой треугольник минимального периметра, вписанный в данный треугольник
Дан треугольник. Найти другой треугольник минимального периметра, вписанный в данный треугольник, ...

Организовать класс треугольник определенный по 3-ем сторонам содержащий методы нахождения периметра и площади(По формуле герона)
Помогите написать прогу:wall: Организовать класс треугольник определенный по 3-ем сторонам...

Задача на нахождения периметра многоугольника
На плоскости заданы n точек своими декартовыми координатами. Найти минимальный периметр...

Задача на структуры: выбор точек, образующих треугольник наибольшего периметра
Заданные координаты N точек на плоскости XY.Все точки различны.Найдите треугольник с минимально...

3
31 / 31 / 9
Регистрация: 23.11.2011
Сообщений: 58
24.11.2011, 12:38 2
Объяви в var
f:file of integer;

А после begin
reset(f,x,y);

Только тебе нужна еще переменная, которая отвечает за количество строк (в примере 5)
0
Почетный модератор
64300 / 47595 / 32743
Регистрация: 18.05.2008
Сообщений: 115,181
24.11.2011, 15:48 3
Файл в одном каталоге с программой.
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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
type Tpoint = record { тип Точка }
              x:real; { координата x }
              y:real; { координата y }
              end;
function Dist(t1, t2 : Tpoint):real;
begin
  Dist := sqrt( sqr(t1.x-t2.x) + sqr(t1.y-t2.y))
end;
 
var f:text;
    t:array[1..100] of TPoint;
    n,i,i1, i2, i3, k : integer;
    i1m, i2m, i3m : integer;
    minPer:real;
begin
assign(f,'input.txt');
reset(f);
read(f,n);
for i:=1 to n do
read(f,t[i].x,t[i].y);
close(f);
minPer := Dist(t[1],t[2])+Dist(t[2],t[3])+Dist(t[1],t[3]);
i1m:=1;
i2m:=2;
i3m:=3;
for i1:=1 to n-2 do
for i2:=i1+1 to n-1 do
for i3:=i2+1 to n do
if Dist(t[i1],t[i2])+Dist(t[i2],t[i3])+Dist(t[i1],t[i3])< minPer then
 begin
  minPer:=Dist(t[i1],t[i2])+Dist(t[i2],t[i3])+Dist(t[i1],t[i3]);
  i1m:=i1;
  i2m:=i2;
  i3m:=i3;
 end;
WriteLn('Минимальный периметер = ',minPer:0:2,' в точках ',
         i1m,'[',t[i1m].x:0:2,';',t[i1m].y:0:2,']','  ',
         i2m,'[',t[i2m].x:0:2,';',t[i2m].y:0:2,']','  ',
         i3m,'[',t[i3m].x:0:2,';',t[i3m].y:0:2,']');
end.
1
1 / 1 / 1
Регистрация: 25.10.2011
Сообщений: 42
24.11.2011, 20:25  [ТС] 4
Спасибо огромное.
0
24.11.2011, 20:25
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.11.2011, 20:25
Помогаю со студенческими работами здесь

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

Треугольник наибольшего периметра
Друзья, никак не могу осилить задачку, заранее благодарю!) Найти три различные точки из...

Найти треугольник наименьшего периметра
Здравствуйте.Помогите,пожалуйста)С Рисунком)Буду всем благодарна Найти треугольник наименьшего...

Треугольник наибольшего периметра(Графика)
С помощью графики отобразить на экране монитора ход решения следующей задачи: из заданного на...

Равнобедренный треугольник: определение площади и периметра
Объект «равнобедренный треугольник заданный длиной равнобедренной стороной и углом между ними»....


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru