Форум "Другие языки"

Языки бывают разные...

#0 Go © 16.05.06 14:08:24 - 04.07.06 15:44:18

Векторная алгебра

Вот есть задачка.
Входные данные: массив векторов
Нужно получить максимальную длину вектора суммы какого-то подмножества входного массива :)

сумма векторов (x1,y1) + (x2,y2) = (x1+x2, y1+y2)
длина вектора L( (x, y) ) = sqrt(x*x + Y*y)

Вроде бы задачка то простая.. а вот с ответами не сходится :) Устала ломать голову :) Теперь просто интересно, а какой же алгоритм правильный :)

Один из примеров:
int[] x = {-4,4,4,-4};
int[] y = { 3,3,2,-4};
Получается максимальный суммарный вектор (4,3) + (4,2) = (8,5) и его длина 9.433981132056603

#1 VictorT © 16.05.06 14:17:37

Тут скорее комбинаторику смотреть надо больше, чем векторную алгебру.
А какой алгоритм используешь?
З.Ы. Ты уже не на дельфях пишешь?

#2 Go © 16.05.06 14:26:27

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

А какой алгоритм используешь?
просто не хочется своим алгоритмом замыливать решение :)

З.Ы. Ты уже не на дельфях пишешь?
да пока на делфях.. куда от них, горемычных :(
хотя пробую и другое :)

#3 Go © 16.05.06 14:38:39

вот еще примеры, вдруг кого заинтересует :)

   int[] x = {17,8,-5,-8,-8,-11,-3,2,19,4,22,15,20,13,-7,15,-23,17,-9,-10,17,24,20,-22,-1,-7,-19,18,-17};
   int[] y = {7,-5,-2,18,-9,-24,14,9,-21,14,-23,7,14,23,23,17,17,22,-3,-21,-10,1,24,-17,25,12,-21,12,13};
  289.4563870430224

   int[] x = {-22, -21, -1, 5, -19, 20, -24, -18, 8, -16, -6, 11, 11, 13, 24, -6, 14, -6, 9};
   int[] y = {25, 9, -17, -17, -7, -21, 5, -14, -8, -21, 7, 16, 20, -1, -13, 17, 15, -18, 25};
  143.09786860746738

   int [] x = {-23, 10, -10, -6, 15, 20, 5, 14, 20, 22, 1, -16, 3, -16, -23, 2, -4, 19};
   int [] y = {-20, -17, -4, -16, -10, -1, 3, 3, -7, 18, 24, 1, -11, -20, 24, 8, 23, -10};
  132.19682295728592

у меня на этом вываливает :(
   int [] x = {-117, 912, 424, -878, -688, 463, 42, -538, 650, 609, -531, -908, 415, -518, 737, 568, 750, -930, -534, -539, 639, -417, 149, 308, 242, -47, 545, 656, 365, 453};
   int [] y = {-639, 687, -411, 437, 69, -410, 41, -75, 894, -852, 832, -527, -855, -103, 896, -726, -616, -236, 244, 768, -515, -73, 357, 301, 347, -709, 191, -573, -793, -403};
  9559.394384583158

#4 Go © 16.05.06 14:48:32

Урааа!! получилосс :)
мда. сортировала не совсем корректно.

#5 VictorT © 16.05.06 14:48:32

> чно при таком подходе правильное решение однозначно найдется..
> но ведь хочется как-то красивше :)
Мне пока приходит в голову только такое: складывать все вектора, у которых одна из координат (х или y) с одинаковым знаком. Таким образом получаем 4-ре или меньше векторов, среди которых исчем наибольший.

А какое пратическое применение этой задачи?

> да пока на делфях.. куда от них, горемычных :(
> хотя пробую и другое :)
Дельфист так не пишет ;)
> int[] x = {-4,4,4,-4};

#7 Go © 16.05.06 16:34:18

по идее все тем же перебором только отсортированного массива векторов :) просто никак уложиться не могло почему такой алгоритм не работает

#8 Googla 04.07.06 15:44:18

Напишите пожалуйста подробно весь алгоритм нахождения максимальной длины!

Написать ответ