Дана задача: Дано множество A из N точек. Найти наименьший|наибольший периметр треугольника, вершины которого принадлежат различным точкам множества A, и сами эти точки (точки выводятся в том же порядке, в котором они перечислены при задании множества A). Я её сделал, но если задать четыре точки (N=4), то компилятор выдает ошибку 205 ... Это так должно быть или у меня в решении ошибка?
Malice
26.07.2005 13:18
Цитата(kent @ 26.07.05 13:13)
Это так должно быть или у меня в решении ошибка?
Если у тебя ошибка, то так быть точно не должно :D Как ты делал ?
kent
26.07.2005 13:40
Вот решение:
uses crt; type TPoint = record x,y,id : Integer; end; type TIndex = record first,second,third : Integer; end;
{---------------------------------------} Function Space(a,b : TPoint) : Double; begin Space := sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); end; {---------------------------------------}
{---------------------------------------} Function Range(a,b : Integer) : Extended; var fac_a,fac_b,fac_dif : Extended; p1,p2,p3 : Integer; begin fac_a := 1; p1 := 1; repeat inc(p1); fac_a := fac_a * p1; until p1 = a; fac_b := 1; p2 := 1; repeat inc(p2); fac_b := fac_b * p2; until p2 = b; fac_dif := 1; p3 := 1; repeat inc(p3); fac_dif := fac_dif * p3; until p3 = a - b; Range := fac_a / (fac_b * fac_dif); end; {---------------------------------------}
var a : array [1..1000] of TPoint; id : array[1..1000] of TIndex; Perimeter : array [1..1000] of Double; N,i,j,m : Integer; indx,count_indx : Integer; max_Perimeter,min_Perimeter : Double; min_id,max_id : TIndex; begin {$R+} Clrscr; Write('Input N:'); ReadLn(N); WriteLn('Input set A:'); for i := 1 to N do begin Write('Point <',i,'> (X,Y):'); Read(a[i].x,a[i].y); a[i].id := i; end; m := 3; for i := 1 to m do a[i].id := i; indx := 0; repeat inc(indx); for i := 1 to m do if (i > 2) then begin id[indx].first := a[i - 2].id; id[indx].second := a[i - 1].id; id[indx].third := a[i].id; end; Perimeter[indx] := Space(a[a[i - 2].id],a[a[i - 1].id]) + Space(a[a[i - 1].id],a[a[i].id]) + Space(a[a[i - 2].id],a[a[i].id]); i := m; while (i > 1) and (a[i].id = N - m + i) do dec(i); inc(a[i].id); for j := i + 1 to m do a[j].id := a[j - 1].id + 1; until (i = 0) or (indx = 1000) or (indx = Range(N,m)); count_indx := indx; min_Perimeter := 500000; max_Perimeter := 0; for indx := 1 to count_indx do begin if (Perimeter[indx] < min_Perimeter) then begin min_Perimeter := Perimeter[indx]; min_id.first := id[indx].first; min_id.second := id[indx].second; min_id.third := id[indx].third; end; if (Perimeter[indx] > max_Perimeter) then begin max_Perimeter := Perimeter[indx]; max_id.first := id[indx].first; max_id.second := id[indx].second; max_id.third := id[indx].third; end; end; WriteLn; WriteLn('------------------------------------------'); WriteLn('Min perimeter:',min_Perimeter,';'); WriteLn('Min perimeter points: ',min_id.first,'-',min_id.second,'-',min_id.third,';'); WriteLn('*******************************************'); WriteLn('Max perimeter:',max_Perimeter,';'); WriteLn('Max perimeter points: ',max_id.first,'-',max_id.second,'-',max_id.third,';'); WriteLn('-------------------------------------------'); Readkey; end.
Malice
26.07.2005 14:06
Цитата(kent @ 26.07.05 13:40)
Вот решение:
Ой, опять кучу массивов нагородил, зачем ?
Перебор делай так:
for I:=1 to n-2 do for j:=i+1 to n-1 do for k:=j+1 to n do begin pr:=space(i,j)+space(j,k)+space(k,i); { тут же сравниваешь на мин и макс и сохраняешь i, j и k в переменных, например min1, min2, min3 и max1, max2, max3 } end; {все, здесь уже результат выводишь }
И не нужны тебе массивы, кроме "A". Из TPoint id тоже выкинь, зачем он там?
kent
26.07.2005 14:15
А что уменя вообще неправильно что ли?
Цитата
Ой, опять кучу массивов нагородил, зачем ?
Перебор попроще просто не знал...
volvo
26.07.2005 14:20
kent, ты все время описываешь массивы заведомо бОльшего размера, чем тебе нужно. А зачем? Есть же более удобные способы
Type TPoint = Record { твое описание ... } End; PArrPoint = ^ArrPoint; ArrPoint = Array[0 .. Pred(maxInt Div SizeOf(TPoint))] Of TPoint;
... Var arr: PArrPoint; ... { вводишь размерность массива: N } { и размещаешь массив в "куче" } GetMem(arr, N * SizeOf(TPoint)); { и так же, как ты работал со своим массивом, работаешь с массивом расположенным в "куче", просто вместо arr[i] делаешь arr^[i], и не надо никаких массивов по 1000 элементов... }
... { по окончании работы с массивом - осввобождаешь память } FreeMem(arr, N * SizeOf(TPoint)); ...
kent
26.07.2005 14:30
volvo, а что такое куча?
Malice
26.07.2005 14:31
Цитата(kent @ 26.07.05 14:15)
Перебор попроще просто не знал...
Теперь знаешь Проще исправить, чем ошибку найти, имхо. А volvo дело говорит, так делай, или не вводи N вообще, а выведи в константы.
kent
26.07.2005 14:53
Надо ещё теорию подучить...
Malice
26.07.2005 15:08
Если не хочешь исправлять, то так:
Function Range(a,b : Integer) : Extended; ............. fac_dif := 1; p3 := 1; repeat inc(p3); fac_dif := fac_dif * p3; until p3 = a - b; ............. end;
В выделенном фрагменте поставь p3=0; иначе если (a-B )=1 у тебя сразу p3 становится=2 и цикл крутится ооочень долго . И еще, в Tpoint поставь тип longint, а то функция space может лажаться.
kent
26.07.2005 15:41
Malice, спасибо... :thanks: Теперь вроде врубаюсь почему при (N=4) выдает ошибку...
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.