Как стать автором
Обновить

Комментарии 125

Задачи:
1. Есть 8 монет. Одна из них фальшивая, она весит меньше, чем настоящие. Есть аптекарские весы. Каково минимальное количество взвешиваний, чтобы определить фальшивую монету?

2. Есть 8 монет. Одна из них фальшивая, она отличается по весу от настоящих. Есть аптекарские весы. Каково за минимальное количество взвешиваний, чтобы определить фальшивую монету?

3. Есть три закрытых ящика, в которых соответственно лежать апельсины, лимоны и смесь апельсинов и лимонов. На ящиках таблички с надписями, но они перепутаны, и надпись на ящике не соответствует содержимому. Какой(ие) ящик(и) надо открыть и сколько фруктов вытащить, чтобы смочь перевесить надписи правильно?

4. Жили-были пять братьев. Отец их умер и оставил им в наследство 100 монет. Придумали братья, как эти монеты делить. Первым предлагает схему, как разделить, старший. Если он предложит схему, за которую проголосует большинство, что она приемлема, деление состоялось. Если же нет, его убивают и делит следующий по старшинству. Братья жадны, кровожадны и хотят жить. Они очень расчетливы и просчитывают исход вперед. Как старший разделит деньги, чтобы остаться в живых и получить как можно больше монет?
3. 1 ящик, 1 фрукт вроде бы.
НЛО прилетело и опубликовало эту надпись здесь
это была, так скажем, проверка логического мышления соискателя. Задачи на php были потом. Могу запостить и их. Попросили обойти двоичное дерево без рекурсии, написать функцию решения квадратного уравнения и переставить слова в строке без explode и разбивки на символы.
НЛО прилетело и опубликовало эту надпись здесь
Вопрос спорный. Что сейчас знает кодер о кодерстве может даже менее важно, чем наличие у него впринципе мозга.
НЛО прилетело и опубликовало эту надпись здесь
молодца! понизил программиста до дворника ))
НЛО прилетело и опубликовало эту надпись здесь
ну если не до дворника, то до робота точно )) учите, дети, синтаксис, а ваша смекалка/творческие способности/стрессоустойчивость/элементарная сообразительность нам ни к чему. дворник должен тупо мести улицу, а кодер должен тупо кодить! вот и вся твоя "логика".
НЛО прилетело и опубликовало эту надпись здесь
Имхо первые три задачки решит слету любой средний школьник за пол часа максимум. По крайней мере у меня в школе такое решали в 6-ом классе на математике.
бывают разные задачи, если брать человека на копание ямы - одно. а часто нужен человек с системным мышлением и нормальным характером, это певичнее, чем то какое кодинг-стайлы он предпочитает в настоящий момент времени, я верю :)
НЛО прилетело и опубликовало эту надпись здесь
Задачи боянистые.
достаточно у кого-то кто проходил собеседование спросить их.
так я их решила, я не спрашиваю, я приглашаю тех, кто их не знает, "размять мозги" :-) Кроме того, вдруг кто ищет работу и с этим столкнется - их же не на дом задают, спросить будет не у кого.
Зачем собеседование? Про шарики — школьная задача на логику с элементами физики :)
Ой, то есть про монеты ;) мне просто привычнее чуть-чуть другая формулировка
НЛО прилетело и опубликовало эту надпись здесь
ОЧЕНЬ ВАЖНОЕ ДОБАВЛЕНИЕ К ЧЕТВЕРТОЙ ЗАДАЧЕ: тот, кто делит, тоже голосует, понятное дело, за
1 и 2 легкий вариант с 12 монетами:
У Вас есть 12 монет, одна из которых фальшивая и она либо легче, либо тяжелее настоящей. Как с помощью трёх взвешиваний балансировочных весах (которые показывают больше-меньше) определить фальшивую монету и то,легче она или тяжелей настоящей?
А еще пришла идея собирать здесь подобные задачи. Так и время приятно провести можно и друг другу помочь.
Купите книги Мартина Гарднера, там много интересного.
спасибо, куплю. Сынок подрастет - будем тренировать логику!
Еще очень интересные книги по этой теме у Рэймонда Смаллиана. Веселее и увлекательнее, что ли :)
Согласен. Но, судя по всему, лучше это делать в отдельном блоге
Не 2 :-)
да, правильно!
Двух достаточно
НЛО прилетело и опубликовало эту надпись здесь
правильно
3. Ну вначале достать из любого. Там где лемон - там не апельсин и нааборот.
по очереди из каждого вынуть. Там где 2 одинаковых - в одном из них перемешанный ящик.
можно проще решить. Если нарисовать, то все станет понятно
Так как на каждом ящике надписе НЕ те (?), то там где лимон (апельсин) там - микс. Итого 3 фрукта надо вынуть.
:-) Даже 2, если надписи НЕ правильные.
а если там смесь?
Уверен, что из любого?
Вот достаёшь ты из "Апельсин" и там лимон. И нельзя понять, там "Лимон" или "Лимон-Апельсин" на самом деле.

ИМХО, надо доставать надо только из "Лимон-Апельсин". Если вынул апельсин => в этом ящике апельсины. Остаётся ящик "Лимон" и "Апельсин". Т.к. надписи не соответвуют действительности, то в "Апельсин" лежат лимоны, а в "Лимон" смесь.
Хотя может я торможу.
да, все правильно!
:-) Даже 1, действительно.
а если вынул лимон?
Тогда симметрично.
Если лимон, то в этом ящике лимоны.
Остаются ящики "апельсины" и "лимоны", в которых как-то расположены апельсины и смесь. Т.к. надпись не соответствует действительности, в "лимоны" лежат апельсины, а в "апельсины" - смесь.
1. Если остальные 7 весят одинаково, то 2 раза :)
Первые две - школьная олимпиада, 5 класс. Легко. Последняя, вроде бы, решается как игра, но должно быть более простое решение. Кто как решил последнюю?
первые три, я хотел сказать ))
поддерживаю. Это просто "опыт собеседования", а не головоломки для крутых программеров :-)
предлагайте решения для четвертой:-)
Младший имеет лучшие условия :-) Или нет?
подумайте. Начинайте с младшего, правда. Попробуйте определить, сколько по максимуму может получить каждый.
Младший всё :-)
Отдать все двум младшим, или трём?
не торопитесь. Если он все отдаст младшему - все будут против и его убьют. А его задача остаться в живых. Если отдавать все трём младшим, то будет не выполнена задача получить самому как можно больше. А это возможно.
Если старший что то сибе оставит то трем младшим выгодно его убить в любом случае (варвары :-)
они руководствуются чистой логикой, поэтому для решения нужно четко определиться, кто и сколько максимально может получить. Они просчитывают и знают. Т.е. если старший отдаст им их максимальную - именно по расчету - долю, то они голосуют за.
правильно, что в доле будут старший и двое самых младших
Дяя, сложно мне :-)
я решала час. Мне мешало, что я филолог по образованию, и я все примешивала чувства, эмоции этих людей - типа как в литературной ситуации. А тут чистая логика и расчет.
НЛО прилетело и опубликовало эту надпись здесь
Попробуйте предположить, что вот всех перебили, осталось их двое, младших - как тогда развернется ситуация?
Нуу, самый младший все захапает. Я не понял, тот кто предлагает - тоже голосует?
да, тоже
:-) Ступор, большинства быть не можеь их же двое. И тот и другой хотят всё. Как же тут? :-)
тут значит, что все захапает младший. Т.е. предыдущий по-любому ничего не получит. Т.е. ему будет достаточно дать одну монету. Один больше, чем ничего. Это ясно? Теперь что будет, если останется трое младших, как тогда все повернется?
Ага, логику просек :-)
Если их 3, то старший может взять 99 а второй 1 :-) типерь 4... Кстати так?
Так, главное, что последний-то точно не получит ничего. Т.е. ему достаточно тоже дать одну монетку. Ну и все, решили: 98 старшему, 1 самому младшему и 1 тому, что перед ним. Поздравляю!
Интересненько :-)
Хотя спорно, второму с конца не важно ведь от кого одну монету получить. Хотяя, пожалуй да - 98,0,0,1,1.

Я бы сам наверное не решил бы :-) Вы молодец
а чем плохи варианты:

98 0 1 0 1 и 98 0 1 1 0

если сравнивать с предыдущим шагом (98 0 1 1), то и в этих двух случаях будет по 3 голоса за. Или я что-то путаю?
Не будет. Потому что четвертый может надеяться на 1, а третий может получить все )
А я логику не понял. Если остается два брата и старший предлагает все 100 оставить ему, тогда он голосует за, а младший против. Где большинство?
большинства нет, и по условию, если нет большинства "за" старшего убивают.

Послесловие:
Тут нету житейской логики, тут просто логока, формальная так сказать.
По условию младший все возьмет (если нет, убивают).
1-ю задачку решили - 2 раза достаточно.
2-ю тоже - 3 раза.
На третью тоже правильный ответ видела - 1 ящик (только какой?), 1 фрукт
1. 3
2. 6
3. 1 из 1-го
4. хз :)
шесть взвешиваний во второй задаче - зачем?
если делать бинарный поиск то мы изначально не знаем что ищем, условие может быть либо , поэтому приходится на каждой итерации делать шаг назад грубо говоря.

вопрос: каким образом в 1-ой задачи можно в две итерации найти манету?
условие либо « , либо »
Взвесить 2 и 2.
А потом или или...
не понял. подробнее если можно.
Если 2 и 2 одинаковые, то в тех 3-х фальшивая. Если одна из двух не одинаковая то следующем взвешиванием это и определим. По етой же логике с 3-мя.
bell2007, опечатался - из оставшихся 4-х. Если первые две по весу одинаковые, то взвешиваем оставшиеся 4 опять по две, таким образом обнаруживаем иную по весу пару. Потом одну из монет из выделенной пары сравниваем с любой из остальных. Таким образом либо она, либо вторая монета фальшивая. Три взвешивания.
Ой ссори, 3 и 3 :-)
Их же 8.
Хотя можно и 2 и 2, так как вы сказали.
ага, несколько решений есть.

$arr = array(23,23,23,23,23,21,23,23);
while(count($arr)>1)
{
$ar1 = array_slice($arr, 0, count($arr)/2, true);
$ar2 = array_slice($arr, count($arr)/2, count($arr)/2, true);
$arr = (array_sum($ar1) > array_sum($ar2))?$ar2:$ar1;
}
list($idx) = array_flip($arr);
для этой задачи не требовался php :-)
Оно то понятно. Да тут просто некоторые начинают противоречить здравому смыслу...
3. из смешанного 1 фрукт
3. - да, правильно
4.
1 - 34
2 - 0
3 - 0
4 - 33
5 - 33
Нее, троя младших будут против, мне кажется :-)
тогда так
1 - 34
2 - 33
3 - 33
4 - 0
5 - 0

2 и 3 будут понимать, что младшие всегда будут голосовать против, т.к. они самые последние в очереди.
zipo, мы с bell2007 решили ее-таки, посмотри выше
Кто б мне типерь помог д.з. по физике сделать :-)))
неее.... Я гуманитарий, я физику не помню нифига :-)
Вчера тут было :-)
Не имеет решения. Это кстати говоря модифицированная задача про мосты в парке. Уже не помню кто ее решил ну и соответственно доказал невозможность.
Пронтрягин с Куратовским :)
Тут все кричат, что задачи легкие только вот что-то я не вижу ответа на 2-ую.
Я насчитал 6 сравнений.
stix, простите, мы Вас запутали.
Первая задача: взвешиваем по три. В той кучке, что легче взвешиваем любые две монеты и так отыскиваем более легкую. Если же кучки по три одинакового веса, то из двух оставшихся мы уж подавно более легкую обнаружим. Т.о. два взвешивания.
А типерь 3-я щас :-)
Всеравно 3 получается, как не крути.
Сори, торможу, 2 взвешивания
Делим на две кучи.

Сравниваем половинки первой. Если равны - фальшивая в другой куче. За 1 взвешивание переполовинили.

Делим 4 пополам, сравниваем монеты в первой половине. Если равны - фальшивая в другой паре.

Третье взвешивание: любую монету из найденной пары сравнить с заведомо настоящей.

Аллес.
ага, пока я набирала, уже написали решение второй задачи.
О, как вы хорошо свои мысли излогаете :-) Есть еще одно решение, но мне его не сформулировать так быстро (пора уже уходить ;-).
Есть более красивый способ, который также определит, легче или тяжелее фальшивая монета.
За три взвешивания? Приведите, пожалуйста.
привожу.

обозначим монеты 1, 2, ..., 8

1. взвешиваем 1, 2, 3 - 4, 5, 6.
При равенстве - взвешиваем оставшиеся две(7, 8) по очереди с одной из нормальных (1-6).
Очевидно, что мы определим и какая монета фальшивая, и в какую сторону она отличается по весу.
При неравенстве - переобозначим монеты.
Три монеты из более легкой группы обозначим 1л, 2л, 3л (л - легкий).
Три монеты из более тяжелой группы обозначим 1т, 2т, 3т (т - тяжелый).
Две оставшихся - 1н, 2н (н - нормальный).

2. Взвешиваем 1л, 1т - 2л, 2т
При равенстве - очевидно, что фальшивая монета или 3л, или 3т. Взвешиваем 3л, 3т - 1н, 2н.
Если первая чаша легче - то наша монета 3л, и она легче. Если нет - то 3т, и тяжелее.
При неравенстве - если легче первая чаша, то фальшивая монета или 1л или 2т. Если первая тяжелее - то 1т или 2л. Дальше все аналогично.
Четвертая задача изложена не совсем верно. Даже если учесть дополнения к условию, появившиеся в комментах, а именно:
1. делящий тоже голосует
2. большинство должно быть абсолютныи (т.е. при равном количестве голосов делящий проигрывает),
то остается неопределенным момент, как поступит брат, если независимо от его голоса, т.е. умрет делящий или нет, он может рассчитывать как минимум на столько же?
Обьясняю:
1 2 3 4 5
2 - - - 0 100
3 - - 99 1 0
4 - 98 0 1 1
5 98 0 0 1 1

Это решение задачи, в столбиках братья (1 - старший, 5 - младший), по строкам - количество оставшихся.
Возникает вопрос: а зачем 4ому брату принимать одну монетку, если он может получить ту же монетку, да еще и двух братьев завалить? Братья ведь "кровожадные" :)
Если посмотреть с этой точки зрения, то результат будет такой:
1 2 3 4 5
2 - - - 0 100
3 - - 99 1 0
4 - 97 0 2 1
5 95 0 0 3 2
"Возникает вопрос: а зачем 4ому брату принимать одну монетку, если он может получить ту же монетку, да еще и двух братьев завалить? Братья ведь "кровожадные" :)"

Я тоже об этом подумал, ему без пазницы а так как задача на "формальную" логику то ... ээ... ему без разницы :-)
Я в итоге решил точно также, т.к. в задании не просто так упомянута «кровожадность».
Не пойму теперь, если мы исходим из того, что при 4-ёх боатьях расклад таков:

2 - 97 "+"
3 - 0 "-"
4 - 2 "+"
5 - 1 "+"

Почему при пяти расклад не может быть к примеру таким:

1 - 97 "+"
2 - 0 "-" // т.к. может получить 97
3 - 1 "+" // иначе не получит ничего
4 - 0 "-" // т.к. получит 0 вместо 2-ух
5 - 2 "+" // т.к. получит 2-е вместо 1-ой

или так:

1 - 96 "+"
2 - 0 "-" // т.к. может получить 97
3 - 1 "+" // иначе не получит ничего
4 - 3 "+" // т.к. получит 3 вместо 2-ух
5 - 0 "+" // т.к. получит 0 вместо 1-ой
Короче говоря, с учётом кровожадности, мой ответ был бы таков:

1 - 97
2 - 0
3 - 1
4 - 0
5 - 2
Да, действительно. Но есть еще момент, когда братьев трое - старший может забрать все себе, потому что второй все равно проголосует за него (иначе его в любом случае убьет кровожадный младший). Ответа не меняет, но появляется вариант
1 - 97
2 - 0
3 - 1
4 - 2
5 - 0
Какая «многовариантноответная» задачка =)
ага, специально для собеседования придумана *LOL*
Ура! Я был на этом собеседовании, кажется в марте. Сразу у всех прошу прощения, так как дальше будут одни эмоции, которые у меня остались до сих пор, можете не читать ) просто раз возможность предоставилась )
Вот, что у меня было в голове, когда я решал эти задачи: Логика это конечно хорошо, но как мне помогут эти монеты блин, если к примеру из базы будет лезть всякая абракадабра, вместо нужных буковок...или эти апельсины, если дамп не хочет нормально раз-ся....или там веревочки, были кажется ), если создатели Firefox забабахали DOM со своими особенностями, который не хочет мой JavaScript как Opera и IE...и наконец это двоичное дерево, ну и где вы видели двоичное дерево в PHP, может я не те книги читаю или скриптов не видел, посоветуйте. Такое ощущение, что создатели теста понятия не имеют для чего был создан PHP,
и зачем им вообще нужен php-программист и какими знаниями он должен обладать, я молчу про HTML, CSS, Javascript c DOM-ом, MySQL, SQL, XML, которые уже по умолчанию должны быть зашиты в "биос" пхпграммера..в общем я сидел и думал, что мой фрилансерский опыт и знания, над которыми работал и работаю здесь почему-то не нужны, что-то там немного нарешал, плюнул и ушел.....на следующей неделе взяли меня в одну контору, где пока и работаю, получаю удовольствие от PHP-функций, SQL-операторов и других нужных для /*** PHP-ПРОГРАММИСТА ***/ вещей! Уф, все! Всем спасибо!
Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.