|
Страници по тази тема: 1 | 2 | 3 | 4 | 5 | 6 | 7 | (покажи всички)
|
Че ти дивелъпър със здрав мозък виждал ли си?
| |
|
Приликата между шефа и сперматозоида нали я знаеш :) ? Шанс 1:1 000 000 да стане човек от него :)
Задачата е от тест извършван от българска фирма набираща С/С++ програмисти. Няма да й споменавам името, но фирмата се занимава основно с видео обработка. Каква точно е връзката между подобен род задачи и видеообработката, оставям на вашата фантазия
Редактирано от mlee на 07.11.08 14:40.
| |
|
Българска фирма, която се занимава с обработка на изображенията, я да видим ... сещам се за няколко десетки такива ...
Dum loquo hora fugit
| |
|
не на избражения ! за Видео иде реч. Има име на животно в името на фирмата... Няма значение всъщност коя е фирмата.
| |
|
Информацията в условието е недостатъчна, за да се определи стратегия.
>> "маса с произволна /недефинирана/ форма и площ."
Дефинирам диаметър на равнинна фигура с произволна форма така: това е отсечка, съединяваща две възможно най-отдалечени точки, принадлежащи на фигурата. Като не е задълижтелно всички точки от диаметъра да са вътрешни за фигурата. Задължително е единствено краищата на диаметъра да са от фигурата. Има такова твърдение:
"Фигура с крайна дължина на диаметъра си (ако има повече от един - без значение на кой от тях) има крайна площ." Вярно ли е това? :)
Ако диаметърът на масата не е краен, то винаги ще може да се постави още една монета и играта никога няма да завърши, без значение дали площта на масата е крайна или не.
Необходимо условие за съществуване на стратегия, гарантираща винаги печалба на първия играч, е масата да е с краен диаметър.
Редактирано от Пporpaмиcт-дъpвo на 09.11.08 11:51.
| |
|
>> "маса с произволна /недефинирана/ форма и площ."
ок, приемам забележката :) да се чете
>> "маса с произволна /недефинирана/ форма на плота и крайна площ на същия."
Едит: Съотношението на площа на монетата към площа на масата също е неизвестно
Редактирано от mlee на 10.11.08 12:01.
| |
|
Ако сложиш първата монета така, че да раздели масата на 2 полупространства, винаги печелиш.
Написах го още миналата седмица. Защо не го коментира?
Dum loquo hora fugit
| |
|
Защото е частен случай. Въобще не е сигурно, че като сложиш монета остават четен брой ходове.
| |
|
Ще ти дам "математическо" решение, т.е ще ти го сведа до две решавани задачи.
До колкото знам играта с клечките има алгоритъм по който първия винаги да печели. Трябва да погледнем условието за да дефинираме начините по които монетите могат да се сложат - реално това са два начина: легнала, заемаща кръгла форма и на ръб, заемаща правоъгълна форма. Изключително важен е факта, че не само не могат да се слагат една вържу друга, но и не могат да се припокриват - т.е поставена на ръб монетата заема целия правоъгълник на проекцията си.
Тук отново имаме решавана задача (трудна, олимпийска, но решавана) - да се намери максималния брой монети който може да се сложи в една фигура.
И така знаейки максималния брой монети които могат да се съберат ще ги изчисляваме за всяка една отделна фигура на масата (оградена от монета или ръб на масата) и ще сведем задачата до тази с клечките.
Разбира се ще има усложнения, защото играча може не само да маха клечки от една колона, но и може да я раздели на две със същия ход. Да не говорим, че подобно решение е силно теортично и надали ще може да се изпълни на практика ... но като гледам до тук е единственото.
----------------------------------------
Здрав дух, в здрава бутилка!
| |
|
Трябва да водиш играта от самото начало по правила, защото ако го разглеждаш от позицията "дай да позапълним масата, пък като стане удобна за изчисления ще ги правим", то на другия нищо не му пречи да почне със същите изчисления една монета преди теб
----------------------------------------
Здрав дух, в здрава бутилка!
| |
|
Страници по тази тема: 1 | 2 | 3 | 4 | 5 | 6 | 7 | (покажи всички)
|
|
|