ТЕМАТИКА: МАТЕМАТИКА
Отиди на страница:
| . | |
Редактирано: 1 път. Последна промяна от: Математик |
| Вземете последните две цифри на годината в която сте роден (а). Прибавете годините които навършватв в сегашната година. Получава се винаги числото : 111 например роден 1950 , навършва 61 ; 50 + 61 = 111 |
Роден 2001, навършва 10 - 1 + 10 = 11  Роден 1899, навършва 112 - 99 + 112 = 211 Аре без "комунистически" пинизи моля  Редактирано от - nikola_tsanev на 22/3/2011 г/ 19:58:19 |
| Математик, ей, дебна, дебна, да напипам нещо, което знам. Не се отказвам от убавото. А...а, и поздтави за различието в темата ти.  |
| Днес бях на интервю за нова работа и ще ви дам 2 от задачаите, която получих: 1. Дадени са 2 робота A и B поставени върху безкрайни релси на позиции А и B. Могат да се движат наляво N стъпки(Move(-N)) или надясно(+N).Ориентирани са еднакво. Демек, за двата робота "ляво" и "дясно" съвпадат. <- ляво ========A==========B=========== ===-> дясно Разполагате със следните инструкции: 1) Move(N) : ако N>=0, премести се N позиции в дясно ако N<0 -> в ляво 2) IF(A) SKIP пропусни следващата команда, ако се намираш на позиция A 3) IF(B ) SKIP пропусни следващата команда, ако се намираш на позиция B 4) GOTO(N) отиди на стъпка N от програмата 5) NOP (стой на място) Да се програмират роботите A и B да се движат така, че да се сблъскат(евентуално с отделни програми). Ако разстоянието между A и B е "d", след колко стъпки най-късно ще се сблъскат роботите ( една стъпка е една инструкция от програмата) Всяка програма се състои от номерирани инструкции, една стъпка означава всеки робот да изпълни следващата инструкция) Редактирано от - Sta на 29/3/2011 г/ 05:50:10 |
| Втората задача: Дадени са 50 точки в равнината. Да се свържат точките с отсечки по такъв начин, че 1. Между всеки 2 точки да съществува път, който ги свързва 2. Сумата от дължините на всички отсечки да е минимална. Ако се чудите за каква позиция съм кандидатствал, програмист C++/Linux Съвременните тенденции очевидно са връщане към извора(математиката) |
| Понеже не е уточнено дали на пътя, свързващ 2 точки може да се намират и други точки от множеството, задачата се свежда до изчисляване на минималното от 50! възможности. |
| Караваджо, "Минималния" следва да се разбира по следния начин: при зададени точки да се намери минималната сума, а не "точките да се подредят така, че сумата да е минимална". Щом не е дадено, че точките са на една права, значи може да са, а може и да не са. Решението трябва да работи и в двата случая. Освен това вариантите са над 50!. Вярно че на всяка пермутация А1 А2 .. А50. отговаря едно свързване. Следователно броя е поне 50!, но има и още начини. Примерно, свързваме А1 с останалите 49. Или свързваме А1 с 30 и една от тези 30 с останалите 29. И т.н. Математик, за писане на програма която да изброи всички варианти и да намери минималния не става дума. Иначе 50 си се сетил откъде идва, но не исках да замесвам физика, тоци и кабеляк и затуй я дадох в този абстрактен вариант. Редактирано от - Sta на 29/3/2011 г/ 14:38:59 |
| Sta, щом липсва условието за "единствен път" между две точки, по правилата на топологията равнината може да се "разтегне" така, че точките да лежат на права. Възможните начини на подреждане на точките са точно пермутациите на броя им. |
| Математик, Дадените точки се свързват с отсечки без да се добавят нови. Например, ако са дадени 3 точки(триъгълник), свързването на медицентъра с трите върха не е възможно решение. Караваджо - топологичното разтегляне е ок, но изпускаш, че при него някои отсечки може да се наслагват Пример с 4 точки: А поотделно е свързана с B, C и D. това е едно от възможните свързвания. "Разтегляме": А----B----C----D. Сега отсечките са насложени: АB, AC и AD и не отговарят на нито една от пермутациие. Очевидно за разтегления вариант сумата не може да е минималната. поради припокриване на отсечките. Обаче, "разтеглянето" не запазва разтоянията, следователно от факта че "разтегления" вариант не е миниманата сума не може да се напеави извода че оригиналът не е минималната сума. |
| Не виждам защо А трябва да е поотделно свързана с всички останали. Условието е да има път между всеки две точки, и тъй като не е казано, че "по пътя" не може да има други точки, A-B-C-D си е напълно "законно" свързване. |
| Топологичните преобразувания само илюстрират възможността N точки, лежащи на някаква повърхност да бъдат свързани с единствена, непресичаща се крива. В случая, ако се вземе предвид, че окръжността е фигурата с най-добро отношение периметър/повърхност, вероятното решение би изглеждало така: - намират се точките, които ограждат най-голяма свободна повърхност и се свързват последователно - операцията се повтаря с точките извън заградената площ до изчерпването им. |
| . | |
Редактирано: 1 път. Последна промяна от: Математик |
| Момчета, аз от студент не съм гледал подобни неща, ама не става ли въпрос за minimum spanning tree все пак? _______________________ Интеллигент — это тот, у кого ума больше, чем умения, знаний больше, чем ума, сведений больше, чем знаний, а амбиций больше, чем всего перечисленного… Блогът на Манрико |
| Точно за "minimum spanning tree" става въпрос. Топологичните трансформации не запазват разтоянията. Затова не съм съгласен с решението на Караваджо. Също според мен оценката 50! за броя на възможните свързвания е занижена. Обяснение за какво става въпрос: Натиснете тук Едно примерно подсказване: намерете минималното разтояние между 2 точки ( броят на възможните двойки е 50*49/2 да речем АB е минимално), добавете отсечката AB към решението, отстранете точка А и приложете рекурсия за останалите 49 точки. После махнете B и приложете рекурсия. Сравнете двете решения и изберете по-малкото. Разгледайте случая на 2 и повече еднакви минимума. |