|
Тема |
Re: Задача с вектори [re: MyзMaт] |
|
Автор |
Orнeдишaщ (змей) |
|
Публикувано | 24.09.08 23:24 |
|
|
Идеята да се разгледат подробно случаите с малък брой вектори изглежда добра.
Наистина при 2 вектора дължината на тяхната сума не се променя при размяна на местата им. Това е така и при 3 вектора (обратно на това, което казваш) и е очевидно от съображения за симетрия - даже не е нужно да се пишат формули.
Те стават необходими чак при 4 вектора. Тук в общия случай могат да се направят 3 нееквивалентни подреждания (всички останали могат да се получат от тях чрез ротации и отражения) със съответните 3 суми. Лесно се вижда, че подреждането, минимизиращо дължината на сумата, е следното:
Нека векторите имат дължини L1...L4 и L1<=L2<=L3<=L4. Тогава оптималното подреждане е в реда на съседство L1-L3-L2-L4- (двата най-къси са един срещу друг и двата най-дълги също).
За 5 ще се опитам да помисля утре. Задачата е интересна... и май не чак толкова силова, колкото отначало ми се видя.
|
| |
|
|
|