Хорошая логическая задачка

[kashperuk]

Цитата:

Сообщение от Milk

Вернемся к шляпам - если второй озвучил свой вариант, а первый все еще молчит, это сигнал для третьего , что его шляпа отличается от шляпы второго. Так что в ситуации, приведенной на картинке, он тоже догадается.

5 баллов. Всем коллективом ржали. )

[Silent]

1 и 4 так и останутся в неведении, бедолаги..

[Косых Артём]

вот задачка, тоже про шапки
Поймал дракон 100 гномов. Сказал что утром всех их выстроит в ряд. На каждого наденет либо белую шапку, либо черную. Первый в ряду видит шапки всех остальных, второй видит шапки всех, кроме первого (он к нему спиной стоит), третий шапки всех, кроме первого и второго, и так далее. Оглядываться низя
Дракон начнет спрашивать начиная с первого "Какого цвета у тебя шапка?" и если гном угадает, то дракон его отпустит. Гномы покумекали и к утру придумали способ, когда дракону достается на завтрак только один гном (и то, если не повезет).

UPDATE: что за способ придумали гномы?
UPDATE: у гномов хороший слух, так что они слышат ответ каждого гнома.

[kashperuk]

Возможно, пожертвуют только первым, и то, только в случае, если шапка его будет другого цвета, чем у второго.
То есть гномы будут называть шапки впередистоящего.

1 минуту спустя:
Не, не получается.

Кол-во шапок черного и белоге цвета не известно?

[Atar]

Цитата:

вот задачка, тоже про шапки

А задачка в чем?
Чтобы придумать как дракону съесть всех гномов?

[Косых Артём]

Цитата:

Сообщение от kashperuk

Возможно, пожертвуют только первым, и то, только в случае, если шапка его будет другого цвета, чем у второго.
То есть гномы будут называть шапки впередистоящего.

Не, не получается.

надел дракон на первого белую, на второго черную, на третьего белую, на четвертого черную - по такой схеме всем гномам кердык гномы же не знают ни сколько шапок белых, сколько черных, ни в какой последовательности на них дракон шапки наденет.

[Sada]

чёт все ето похоже на пятничный расслабон

[Zabr]

Цитата:

Сообщение от kashperuk

Возможно, пожертвуют только первым, и то, только в случае, если шапка его будет другого цвета, чем у второго.
То есть гномы будут называть шапки впередистоящего.

1 минуту спустя:
Не, не получается.

Получится, если в ответе гном будет называть свой цвет, но при этом кодировать и цвт впередистоящего. Например, порядком слов. Например, первый гном смотрит на шапку второго и говорит: "шапка белая". Первого отпускают или съедают. Второй знает теперь что его шапка белая, и говорит либо "шапка белая" (если у впередистоящего она тоже белая) либо "белая шапка" (если у впередистоящего она черная). В задаче же не сказано, какими именно словами гном должен сообщать о цвете своей шапки. Тогда вроде все сходится.

[Косых Артём]

Цитата:

Сообщение от Zabr

Получится, если в ответе гном будет называть свой цвет, но при этом кодировать и цвт впередистоящего. Например, порядком слов. Например, первый гном смотрит на шапку второго и говорит: "шапка белая". Первого отпускают или съедают. Второй знает теперь что его шапка белая, и говорит либо "шапка белая" (если у впередистоящего она тоже белая) либо "белая шапка" (если у впередистоящего она черная). В задаче же не сказано, какими именно словами гном должен сообщать о цвете своей шапки. Тогда вроде все сходится.

хитро Ну а если на выходе функции "сказатьЦветСвоейШапки" класса "Гном" значение перечислимого типа "ЦветШапкиГнома", которое соответсвенно может быть либо "Черный", либо "Белый"??? то тогда как?

[Recoilme]

Цитата:

Сообщение от Zabr

Получится, если в ответе гном будет называть свой цвет, но при этом кодировать и цвт впередистоящего. Например, порядком слов. Например, первый гном смотрит на шапку второго и говорит: "шапка белая". Первого отпускают или съедают. Второй знает теперь что его шапка белая, и говорит либо "шапка белая" (если у впередистоящего она тоже белая) либо "белая шапка" (если у впередистоящего она черная). В задаче же не сказано, какими именно словами гном должен сообщать о цвете своей шапки. Тогда вроде все сходится.

Не.. не получается..
Потому что на практике первый назло назовет неверный цвет второму чтоб его съели))
А дракон ещё и поразвлекается в процессе питания

[oip]

Цитата:

Сообщение от Косых Артём

вот задачка, тоже про шапки
Поймал дракон 100 гномов. Сказал что утром всех их выстроит в ряд. На каждого наденет либо белую шапку, либо черную. Первый в ряду видит шапки всех остальных, второй видит шапки всех, кроме первого (он к нему спиной стоит), третий шапки всех, кроме первого и второго, и так далее. Оглядываться низя
Дракон начнет спрашивать начиная с первого "Какого цвета у тебя шапка?" и если гном угадает, то дракон его отпустит. Гномы покумекали и к утру придумали способ, когда дракону достается на завтрак только один гном (и то, если не повезет).

UPDATE: что за способ придумали гномы?
UPDATE: у гномов хороший слух, так что они слышат ответ каждого гнома.

Ну это просто.
Если первый видит четное кол-во белых шапок, он кричит НА МНЕ БЕЛАЯ!!!, а если нечетное - НА МНЕ ЧЕРНАЯ!!! и отправляется в пасть к дракону (если не повезло). Далее все легко последовательно определяют свой цвет.

[kashperuk]

Цитата:

Сообщение от oip

Ну это просто.
Если первый видит четное кол-во белых шапок, он кричит НА МНЕ БЕЛАЯ!!!, а если нечетное - НА МНЕ ЧЕРНАЯ!!! и отправляется в пасть к дракону (если не повезло). Далее все легко последовательно определяют свой цвет.

А кто сказал, что шабок будет одинаковое кол-во? насколько я понял, их может быть хоть все белые.

UPDATE:
В подтверждение моих слов:

Цитата:

Сообщение от Косых Артём

гномы же не знают ни сколько шапок белых, сколько черных, ни в какой последовательности на них дракон шапки наденет.

[oip]

Ну пусть хоть все белые. Гномов сколько? 100. Сколько перед собой белых шапок видит первый? 99. Что он крикнет? "НА МНЕ ЧЕРНАЯ!!!". Сколько перед собой шапок белых видит второй? 98. Но он знает, что белых нечетное кол-во, не считая первого. Значит на нем белая. И.т.д.

[kashperuk]

Цитата:

Сообщение от oip

Ну пусть хоть все белые. Гномов сколько? 100. Сколько перед собой белых шапок видит первый? 99. Что он крикнет? "НА МНЕ ЧЕРНАЯ!!!". Сколько перед собой шапок белых видит второй? 98. Но он знает, что белых нечетное кол-во, не считая первого. Значит на нем белая. И.т.д.

Да, видимо таки, это верное решение.
Хотя долго переваривал, как же это так получилось.

[Косых Артём]

Цитата:

Сообщение от oip

И.т.д.

правильно

[oip]

Да я в общем и не сомневался.

Update: Спасибо за задачку.

[Косых Артём]

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

[kashperuk]

Цитата:

Сообщение от Косых Артём

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

Полным перебором ))

[oip]

Цитата:

Сообщение от TasmanianDevil

Решите лучше такую задачку : есть 8 шаров, одинаковых по размеру, цвету. 1 шар отличается по весу . Как за 2 взвешивания найти этот шар ?

Что-то я не понял... Не получается чего-то. За 3 взвешивания из 12 монет - это научился, а из 8 за 2 - нет.

Даже некое "доказательство" невозможности придумал:
Всего равновероятных состояний у системы из 8 монет - 8 (восьмь возможностей для фальшивой монеты) =>в этом пространстве содержится log(2)8+1 = 4 бита информации (плюс один - т.к. еще неизвестно легче фальшивая или тяжелее).
Каждое взвешивание дает нам log(2)3<2 бита информации (три возможных исхода взвешивания). Т.е. за 2 взвешивания мы 4 бита ну никак не получим.

ЗЫ Если где-то у меня логическая ошибка - сильно не бейте. Тяжелый день был.

ЗЗЫ Тьфу, по привичке про монеты писал. Исправлять не буду, думаю все и так понятно.

[oip]

Цитата:

Сообщение от Косых Артём

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

Не знаю, правильно или нет, но у меня числа Фибоначчи получились.

Теорема: для n ячеек число таких способов равно F(n+1), т.е. n+1-му числу Фибоначчи. Докажем ее.

Для начала докажем лемму: при расположении, удовлетворяющему условиям задачи, число последовательностей, заканчивающихся на 1 равно F(n), а на 0 - F(n-1).

Докажем с помощью метода математической индукции.

Предпосылка: для n=2 имеем 1-1, 1-0 и 0-1, Т.е. на 1 оканчиваются F(2)=2, на 0 - F(1)=1.

Предположим теперь что это верно для n=k и докажем для n=k+1.
Очевидно, что к любому из этих k-значеых "чисел" можно приписать 1 и последовательность по-прежнему будет удовлетворять условию задачи. Т.е. на 1 будут оканчиваться F(k)+F(k-1)=F(k+1).
Ноль можно приписать только к последлвательностям, оканчивающимся на 1, т.е. их будет F(k). Таким образом лемма доказана.

Из доказанной леммы следует доказательство теоремы: число таких n-значных последовательностей равно числу последовательностей, заканчивающихся на 1 плюс заканчивающихся на 0, т.е. F(n)+F(n-1)=F(n+1). Теорема доказана.

P.S. Для n=8, F(n+1)=F(9)=55. Вроде так.