не могу разобраться с условием

[blackcat]

условие задачи: задан массив целых чисел четной длины.каждая пара соседних чсел образует метрику вектора(квадратны корень из суммы квадратов этих двух чисел).мне нужно удалять постепенно пары элементов,считая метрику удаляемых пар.все до тех пор,пока массив не опустеет.в итоге мне нужно получить минимальную метрику - минимальную сумму метрик всех удаленных пар.

преподавателем были предложены след.типы данных:
Tinp = array of integer; //исходный массив
Tpoz = array of integer; //массив позиций удаления
Trec = record //запись хранит частичное решение - позиции удаления и метрику для них
poz:Tpoz;
metr:real; //метрика
end;
Tmas = array of Trec; //массив частичных решений.

например
1 2 3 4 - массив
1 2 3 - позиции удаления

было предложено сначала сделать перебор позиций удаления(рекурсивно).частичное решение заполняется по ост.точкам(элементам).частичное решение постепенно заполняется и в конце - поный набор - решение.

помогите понять условие.может быть на пальцах на примере объяснить.т.к.насчет этого частичного решения вообще не понимаю,как это должно быть(

 

[0dayAlgorithm]

Вот всегда думал, что курят составители подобных задач? Как у них получается какой-нибудь повсеместно используемый алгоритм завернуть в такую "Голландскую" обертку.

Насколько я понял, етсь массив целых чисел типа: 4, 3, 1, 2, 5, 6
Нужно попарно брать эти числа и высчитывать метрику, но что значит попарно?
берем 4 и 3, получаем 16+9=25, sqrt(25)=5 - метрика первой пары.
берум следущую пару 1 и 2, получаем 1+4=5, sqrt(5)=2.22 - вторая пара.
берем третью пару sqrt(36+25)=7.8

получили массив 5, 2.2, 7.8
В итоге получаем массив чисел в два раза меньшей длины (правда числа дробные). И теперь мне несовсем понятно, тебе нужно из полученного массива найти самое маленькое чисто, или тебе нужно полученый массив теперь рассматривать как исходный и также попарно отработать (число элементов может быть нечетным, поэтому врятли)? Мне непонятна фраза

нужно получить минимальную метрику - минимальную сумму метрик всех удаленных пар

- если это сумма всех метрик она не будет минимальной или максимальной. В нашем случае сумма метрик примерно равна 15.

Что-то сдесь прорущено, если нужно просто найти сумму или минимальную метрику, то зачем нужны все эти доп массивы и записи (позиции, и т.п.)? Короче неясно что нужно получить в результате. Автор ты уверен что задача пересказана верно?

 

[blackcat]

0dayAlgorithm как верно сказано насчет курения))) задача пересказана верно,я ж записвала с его слов) на примере объясню

есть массив 4,0,0,5. берем и удаляем сначала пару 4,0. ее метрика = 4.в массиве осталась пара 0,5.удаляем ее.метрика 5.суммируем два полученных ответа,получим 9. теперь,если вновь взять исходный массив и удалить сначала пару 0,0 (метрика 0),а затем пару 4,5 (числа окажутся соседними после удаления первой пары),получим метрику 6.4. суммируем 0+6.4=6.4. в итоге из двух возможных метрик 9 и 6.4 минимальной будет вторая. ответ:пары удалять в порядке (0,0),(4,5),минималтная метрика 6.4.

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

 

[0dayAlgorithm]

О да, это неслабая задачка =)

Попробуем просчитать как генерируются варианты удаления пар.
Грубо говоря возьмем Х = количество цифр в массиве, тогда возможные варианты удаления
для первой пары абсолютная позиция удаления в массиве может быть от 1 до Х-1
для второй пары от 1 до Х-2-1
и так для каждой последующей пары, возможная позиция удаления может быть от 1 до Х-1-(2*порядковый номер пары)
Мда, прочитал и понял, что уже звучит хуже чем условие задачи...

Если взять самый простой пример, когда у нас всего 2е пары, скажем 4,0,0,5 тогда вариантов удаления пар 3:
1,1 - (4,0) (0,5)
2,1 - (0,0) (4,5)
3,1 - (0,5) (4,0)
Грубо говоря позиция первый удаляемой пары может быть от 1 до 4-1, второй уже от 1 до 4-3, третьей пары нет.
Если это записать схематично то это так (1..3)(1)

Когда пары 3, тогда кол-во вариантов заметно подрастет
(1..5)(1..3)(1), иначе говоря 5*3=15 вариантов

Когда пары 4, (1..7)(1..5)(1..3)(1)=105 вариантов их удаления (причем большинство вариантов дадут одинаковый результат, ну и черт с ними (Microsoft style) ).
алгоритм подсчета кол-ва вариантов
sum:=1;
for i:=0 to N-1 do sum:=sum*(i*2+1) //где N-кол-во пар

теперь нужно перебрать все эти варианты, скорее всего используя рекурсию (внимание очень просто ошибиться)
грубо говоря для 3х пар мы должны перебрать варианты:
111,121,131,211,221,231,311,321,331,411,421,431,511,521,511
В общем пишем процедуру - генератор возможных вариантов. Если получилось - 45% задачи решено.


Теперь нужно реализовать фунуцию выщитывания суммы метрик причем функция вида
function makesum(InitialArray,DeletionSteps):real; (InitialArray - массив пар чисел введенных в программу, DeletionSteps - последовательность удаления)
К слову способов реализации этой функции можно предумать немало. Сдесь могут пригодиться предложеные типы данных. Я бы например завел массив длины InitialArray, но булеан типа. Сначала назначил всем элементам 1, и потом обрбатывая DeletionSteps присваивал нули элементам, чья позиция соответствует удаляемым. На следующем шаге удаления игнорировал
бы те ячейки которым соответствуют нули. (ИМХО так проще чем замарачиваться с динамическими массивами, и удалять элементы). Это другие 45% решения.


Теперь когда две эти ф-ции есть мы просто запускаем перебор, каждый полученый вариант отправляем в makesum,
На первом шаге сохраняем в отдельные переменные InitialArray и Результат ф-ции,
на всех последующих,если новый результат меньше того что лежит в этой отдельной переменной, перезаписываем их новыми данными.
Так по окончании перебора всех вариантов будет минимальная сумма метрик и в другой переменной искомая последовательность. (самая простая часть)


Фууф, надеюсь более менее понятно обьяснил %-)
В таких задачах главное понять логику перебора вариантов, самому кодить откровенно говоря в лом - это уже дело техники.