ТЕМАТИКА: МАТЕМАТИКА
Отиди на страница:
Точките са дадени. Не може да ги разполагате по върхове на многоъгълник, окръжност или под 120 градуса. Дадени са. Решението трябва да работи винаги, независимо дали точките са на една права, на окръжност или разположени по друг начин. Решението е един от възможните графове, който свързва дадените точки и няма други върхове извън тези точки.  |
| Ми значи като става въпрос за това, си има елементарно, макар и брутално решение. Предполагам, че знаем координатите на точките, значи си конструираме пълен граф и смятаме разстоянията. После по един от известните алгоритми му намираме minimum spanning tree. Бруталничко е, щото би трябвало да се хитрее още при конструирането на графа - ако имаш например точки А, Б, В на една права в този ред, е тъпичко освен АБ и БВ да слагаш и АВ в графа, ама той алгоритъмът после все ще си отсее излишното. _______________________ Интеллигент — это тот, у кого ума больше, чем умения, знаний больше, чем ума, сведений больше, чем знаний, а амбиций больше, чем всего перечисленного… Блогът на Манрико |
| Това е така, ако си чувал предварително за minimum spanning tree. За тези, които не са задачата си е добро упражнение. Аз чак сега, като прочетох твоя постинг погледнах в уикито и видях, че е същото. Иначе знаех, че има някаква теория по въпроса, понеже ме питаха как се казва това нещо, но аз отговорих че не знам и те решиха да не ми кажат. |
| Математик, на половин оборот е завъртяна (гледано от центъра на вътрешната монета, около която въртиш ). Като довършиш въртенето ще се е завъртяла веднъж и ще застане в изходно положение. Ало я гледаш като някой господ или поне като ББ отгоре е друго и не се брои. По въпроса с графа, не си видял решението въпреки подсказването. Не става да се изброят всички възможности. Между другото, всички възможни отсечки са 50*49/2=1225. Броят на всички възможни графи от тези отсечки е равен на броя на всички подмножества на множеството от 1225 елемента, което е 2^1255-1 (2 на степен 1225 минус 1). Разбира се, голяма част отпадат поради това че не минават през всички точки или съдържат цикли. Но все пак с пълно изброяване няма да решиш задачата за разумен срок дори с помощта на най-добрия компютър |
| абе що ми се струва че това е вехтата задача за търговския пътник и декартовото решение на графите ? |
| най-после прочетох за кво става въпрос... става въпрос че Ста са занимава с пълни глупости , дето се написват за 2 часа и не искат никаква мисъл, на всичко отгоре ползва и рекурсия горкия , аи да не казвам кои ползват рекурсия в програмирането , те са едни ... китки. за едни пермутации на 50 позиции виждам че не може да сметнете , позор. и туи ми било сборище на програмисти и математици , язък. в общи линии Карата пак блести с мозък , макар и да не се занимава с програмиране и математика. |
| Математик - заповядаи си програмката - Натиснете тук Решението е малко грубичко , но си работи. Всъщност в практиката малко са задачи с повече от 50 тина параметъра, затова изброяването е лесно , а хипотетически може да натоварим алгоритъма със над 100 и дори 1000 и повече но трябва да се доошлаифа и за всеки конкретен случаи да се оптимизира. Освен това има и подвидове със забранени графи и със повторение на графи но те са отделен случаи и не ги разглеждам. |
| >>><<< Нанизват се 50 точки на една права, след което тя се проектира в перперндикулярна равнина и се получава мегаполис с нулеви отсечки! |
| . | |
Редактирано: 1 път. Последна промяна от: Математик |
| >>><<< Това е вече нов проблем, старият гооо решихме...това е като проблема за последния вагон, който много се люлеел и от БАН решили проблема - предложили последния вагон да отпадне. Добре ама някъв даскал в журито на конкурса промърморил:"Ми, нали тогава предпоследния вагон става последен?!" - Ааа, това е вече нов проблем и може да го планираме, ако има субсидии... |
Колкото и да търсих по магазините, днес водка с тази настойка не се намира. На бутилките на джин "Bombay sapphire" са изписани билките, които се слагат и произходът им, Ангелика от Саксония е една от тях._______________________ Интеллигент — это тот, у кого ума больше, чем умения, знаний больше, чем ума, сведений больше, чем знаний, а амбиций больше, чем всего перечисленного… Блогът на Манрико |
| ... кАжи му я, кАжи ... само да не е за построение, че ще си бутне къщата, и пак нищо няма да стане ... нещо с цветенца .... |
| Прочие, кой преведе книгата? От далечната 1990, когато се възторгвахме от студията на Георги Гаргов, остана угнетяващото (!) впечатление, че тази книга е невъзможно да бъде преведена. Най-малкото - че няма български преводач, който да се справи с това, тъй като тук въпросът опира най-малко до знаене на английски. Молодец, който я е превел!! Редактирано от - Геновева на 28/4/2011 г/ 01:57:31 |