Логические задачи.

sto2299 · 13.04.2013

В принципе все кто писал догадались как решить эту задачу. Некоторые объяснения я правда не понял. Сейчас и я попытаюсь объяснить решение этой задачи. Не знаю получится у меня объяснить доходчиво или нет.........

Итак:

Берём 5 групп по 16 бочек - каждый раб выпьет по 16 бочек.

Далее берём ещё 10 групп по 8 бочек и рабы выпьют в следующей последовательности:
1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5

Потом 10 групп по 4 бочки, рабы:
1-2-3, 1-2-4, 1-2-5, 1-3-4, 1-3-5, 1-4-5, 2-3-4, 2-3-5, 2-4-5, 3-4-5

Потом берём 5 групп по 2 бочки, рабы:
1-2-3-4, 1-2-3-5, 1-2-4-5, 1-3-4-5, 2-3-4-5

И последняя группа - это 1 группа из одной бочки из которой выпьют все пять рабов: 1-2-3-4-5.

Подсчитаем бочки: 16*5 + 8*10 + 4*10 + 2*5 + 1 = 211

В первый день будет продегустировано 211 бочек.

Теперь далее:

Умерли все - имеем бочку из которой выпили все, значит она с ядом.

Остался в живых один - имеем две бочки из которых он не пил. На следующий день он пьёт из одной из этих двух бочек, если остался жив то вторая с ядом, если умер то эта.

Остались в живых два - имеем 4 бочки из которых они не пили. На следующий день пьют следующим образом.
Из одной не пьют вообще, далее один пьёт из второй, второй из третьей, вдвоём пьют из четвёртой.
Соответственно исходя из того кто умер будет ясно какая бочка с ядом.

Потом остались в живых 3 - 8 бочек.
Имеем следующие комбинации (как и прежде комбинации применяются к каждой бочке). 0 - это бочка из которой никто не пьёт. Получаем:
0, 1, 2, 3, 1-2, 1-3, 2-3, 1-2-3

Осталось в живых 4 раба - это 16 бочек, следующие комбинации:
0, 1, 2, 3, 4, 1-2, 1-3, 1-4, 2-3, 2-4, 3-4, 1-2-3, 1-2-4, 1-3-4, 2-3-4, 1-2-3-4

Остались в живых все, тогда на следующий день берём оставшиеся 240 - 211 = 29, но на самом деле можно проверить 32 бочки, то есть на самом деле можно за два дня проверить 243 бочки.

Итак 32 бочки:

0, 1, 2, 3, 4, 5, 1-2, 1-3, 1-4, 1-5, 2-3, 2-4, 2-5, 3-4, 3-5, 4-5, 1-2-3, 1-2-4, 1-2-5, 1-3-4, 1-3-5, 1-4-5, 2-3-4, 2-3-5, 2-4-5, 3-4-5, 1-2-3-4, 1-2-3-5, 1-2-4-5, 1-3-4-5, 2-3-4-5, 1-2-3-4-5

Вот собственно и всё не знаю понятно объяснил или нет.

Очень понравилось решение:

JAZZ сказав(ла):
вопрос - а что мешает пичкать одного раба каждые 5 минут из новой бочки? И после его смерти отсчитать назад время и указать бочку?
если пичкать каждые 5 минут, то 240 дегустаций закончатся через 20 часов, т.е. даже если последняя была с ядом, то за 4 часа до пира он умрет, указав на последнюю бочку.

Конечно это задача вряд ли имеет реальное воплощение, но если в условии указать что умирает после 24 часов то решение предложенное JAZZ вполне подходит.

По поводу задачи ранее - вот это объяснение не понял.

Achenar сказав(ла):
0. Дано множество A, в котором 100 целых чисел в пределах от 1 до 100.

1. Создаем множество B на 51 элемент, в нем все нули. Первый элемент B[0].

2. Проходим по множеству A и увеличиваем соответствующее значение в B на 1. Таким образом мы будем знать, сколько каких чисел у нас есть. Значения 52 и выше опускаем.

4. Если B[25] > 1, то у нас не меньше 2 чисел 26 и давай до свидания.

5. Перебираем 25 пар B[0] + B[50], B[1] + B[49]... B[24] + B[26], если в обоих числах пары не нули, то мы нашли ответ.

Можно еще ускорить за счет дополнительной информации в B (если увеличили B[40], тут же выставить в B[10] "я очень жду сюда число" и когда будет увеличено B[10], сразу выдать ответ). Но спорно, все-таки дополнительные операции.

Пример.

A = [1, 45, 67, 22, 55, 89, 7, 26, 13, 17, 58]

B[0] = B[44] = B[21] = B[6] = B[25] = B[12] = B[16] = 1

B[25] меньше двух, не получилось

B[0] и B[50] не устраивают.
B[1] и B[49] не устраивают.
....
B[6] > 0 и B[44] > 0. Ура, товарищи, есть числа 7 и 45, они - ответ.

Achenar если можешь объясни более подробней.

avbua · 13.04.2013

sto2299 сказав(ла):
Сейчас и я попытаюсь объяснить решение этой задачи. Не знаю получится у меня объяснить доходчиво или нет.........

то же самое, но для тех кто не знает двоичной системы счисления.

sto2299 сказав(ла):
Achenar если можешь объясни более подробней.

Почитай мой ответ в 121 сообщении, там то же самое написано, может понятнее будет

sto2299 · 13.04.2013

Твоё то же не понял.

avbua · 13.04.2013

sto2299 сказав(ла):
Твоё то же не понял.

Код:

main()
 {
 int Source[100]= {...}, //Массив со входными данными
     My[101]= { 0, 0, 0, ....}, // Мой временный массив для подсчёта количества каждого числа
     Res1= 0, // сюда мы занесём результат
     Res2= 0,
     i;
 for( i= 0; i<100; i++) // делаем один проход по массиву с данными
  My[Source[i]]++; // Увеличиваем на 1 счётчик текущего числа. Т. е. если нашли 43, то My[43] увеличиваем на 1

 for( i= 1; i<26; i++) // делаем проход по всем 25 парам чисел, которые в сумме могут дать 52, т. е. 1 и 51, 2 и 50, 3 и 49, ...
  if( My[i] && My[52-i]) // если представители текущей пары присутствуют, то счётчики их будут не нулевыми
   {
   Res1= My[i]; // сохраняем результат
   Res2= My[52-i];
   break;  прерываем цикл, ответ найден
  }

 if( !Res1) // если ответ ещё не найден
  if( My[26]>1) // проверяем есть ли два и более числа 26
   Res1= Res2 = 26; // если есть сохраняем результат
 
 printf( "Rezult: %lu and %lu", Res1, Res2); // печатаем результат
 }

Achenar · 14.04.2013

80-й уровень.

Доказать или опровергнуть, что n рабов за m попыток могут "отдегустировать" (m+1)^n бочек, среди которых ровно одна отравлена. Для четкости - рабы пьют, их постигает участь, участь считается окончательной, только после этого следующая проба.

Это так, в качестве развлекухи для тех, кому надоело ходить на северо-запад и двигать гору Фудзи.

belanga · 14.04.2013

Решение с двоичной алгеброй и комбинаторикой конечно работает, но каким, проститите, ФИГОМ, это относится к ЛОГИЧЕСКИМ задачам?

avbua сказав(ла):
Конкретно, что не правильно и как должно быть?

Всё таки правильно. Ссори. Объяснено не оченнь хорошо просто.

Кстати про рабов-камикадзе есть более неточные но болне простые методы, которые позволяют отделить, скажем, не 1 бочку, а 30 или 20. То есть можно поварьировать скоростью решения в ущерб точности определения. Что, кстати, чаще всего, именно таки, и является обоснованным веским критерием в условиях реального мира.

Achenar · 15.04.2013

Achenar сказав(ла):
n рабов за m попыток могут "отдегустировать" (m+1)^n бочек

Не дадим теме заглохнуть, теорема таки верна и вечером выкладываю доказательство.

Achenar · 15.04.2013

Здесь не слишком удобно формулы рисовать, поэтому немножко обозначений.

C(k;n) - число сочетаний из n по k.

Z+ - множество неотрицательных целых чисел.

Итак, дано n рабов, которые должны сделать m попыток (отпить из бочки), после того, как все рабы отпили, падает шлагбаум, наступает счастье, выжившие продолжают.

Теорема утверждает, что при таких условиях можно найти 1 отравленную бочку, которая находится среди (m+1)^n

Теорема тривиально верна, если (m = 0, n = Z+) (сколько бы не было рабов, если они ничего не делают, то единственный случай, когда они могут определить отравленную бочку - эта бочка единственная перед ними и стоит; по условию 1 отравленная бочка всегда есть)

Она также тривиально верна для ( n = 0, m = Z+ ) потому что сколько попыток не закажи, если их некому исполнять, то все это опять же имеет смысл только для 1 бочки.

Теорема доказывается очевидным способом, если ( n = 1, m = Z+). Один раб за m попыток сможет найти 1 отравленную бочку среди m+1.

Наконец, если ( m = 1, n = Z+ ), то это самый простой вариант этой задачи, когда нужно пронумеровать бочки в двоичной системе и напоить рабов в соответствии с поднятыми битами. Кто погибнет - это поднятые биты, дают число. Количество бочек тогда 2^n

Доказуемость и верность теоремы в начальных точках дает серьезное основание для индукции.

Итак, предположим, что теорема верна для n1<=n рабов и m-1 попыток.

В таком случае мы можем посчитать, сколько бочек может быть для n рабов и m попыток.

Как мы уже знаем, n рабов обеспечивают 2^n дегустационных групп. Пронумеруем их от 0 до 2^n-1 и представим номера в двоичной системе.

В нулевой группе должно быть столько бочек, чтобы все выжившие рабы разобрались с ней за m-1 попыток. То есть m^n, поскольку мы предположили, что теорема верна. Такая группа может быть только одна, это, кстати C(0;n) = 1

В первой группе, второй, четвертой, восьмой... (поднят 1 бит) должно быть столько бочек, чтобы выжившие n-1 рабов разобрались за m-1 попыток. То есть m^(n-1), так как теорема предположительно верна. Важно также знать, сколько таких групп. Но мы это знаем - это C(1;n) = n

И вообще, если мы берем группу, в которой поднято 0<=k<=n бит, то таких групп C(k;n) и в каждой группе m^(n-k) бочек.

Следовательно, всего бочек может быть:

C(0;n)*m^n + C(1;n)*m^(n-1) + C(2;n)*m^(n-2)+...+C(n-1;n)*m + C(n;n)

Написанное смутно напоминает бином Ньютона, формула из Википедии.

И это в самом деле он, a = m, b = 1. Значит, наша сумма равна (m+1)^n - количество бочек, которые могут проверить n рабов за m попыток.

Поскольку из верности теоремы для (n1<=n;m-1) следует верность теоремы для (n;m) и теорема верна в начальных точках - она верна для любых неотрицательных n и m.

:пляж:

sto2299 · 15.04.2013

avbua сказав(ла):
Res1= My; // сохраняем результат
Res2= My[52-i];

Разобрался - да крутое решение, решение задачи получается в 125 действий, но есть не большая ошибочка:

надо вот так наверное:

Код:

Res1= i; // сохраняем результат Res2= (52-i);

Achenar по последней задачи то же круто всё написал.

Сейчас напишу новою задачу.....

Имеется два одинаковых стеклянных шарика и N этажный дом. Необходимо предложить алгоритм, который за наименьшее количество бросаний определяет, с какого максимального этажа этот данный шарик не разобьётся.
Следует отметить, что предложенный алгоритм минимизирует кол-во испытаний в наихудшем случае. Т.е. тогда, когда нужный этаж находится в последний момент.

avbua · 15.04.2013

sto2299 сказав(ла):
надо вот так наверное:

Код:

Res1= i; // сохраняем результат Res2= (52-i);

да, надо так, поспешил я.

sto2299 · 15.04.2013

Вот ещё одна интересная задача:

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?

burning_LEGION · 16.04.2013

sto2299 сказав(ла):
В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?

все просто =)
всего заключенных: 10
начальное положение переключателей выкл/выкл
заходит 00 заключенный, переключатели ставит выкл/вкл
заходит 01 заключенный, переключатели ставит вкл/выкл
заходит 10 заключенный, переключатели ставит вкл/вкл

urban1ze · 16.04.2013

Попрошу уточнить: первоначальное положение выключателя известно или нет? С известным положение задачка довольно простая (могу написать подробно, как отдельно выбранный заключенный переключает в OFF после посещений отдельных заключенных), а без него всё довольно плохо, поскольку невозможно определить, заходит ли отдельно выбранный зек в комнату с переключателем в ON первым или же после того, как другой зек переключил в положение ON.

avbua · 16.04.2013

burning_LEGION сказав(ла):
все просто =)
всего заключенных: 10
начальное положение переключателей выкл/выкл
заходит 00 заключенный, переключатели ставит выкл/вкл
заходит 01 заключенный, переключатели ставит вкл/выкл
заходит 10 заключенный, переключатели ставит вкл/вкл

А где ты взял второй выключатель?
Почему заключённых в твоём решении трое?

sto2299 сказав(ла):
Вот ещё одна интересная задача:

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?

Первый вариант: Если 10 это в двоичной системе и известно первоначальное положение переключателя, то первый включает его, а второй выключает и делает заявление.

Второй вариант: Если известно первоначальное положение переключателя, то 9 человек должны его включить по разу, десятый девять раз выключить и после этого сделать заявление.

burning_LEGION · 16.04.2013

avbua сказав(ла):
Почему заключённых в твоём решении трое?

There are 10 types of peoples: those who understand binary, and those who don't.

avbua сказав(ла):
А где ты взял второй выключатель?

вчера я ясно видел их два, сча перечитал - один

funfte.zirkel · 16.04.2013

sto2299 сказав(ла):
Вот ещё одна интересная задача:

В тюрьме сидят 10 заключенных, каждый — в одиночной камере. Общаться между собой они не могут. В один прекрасный день начальник тюрьмы объявил им, что предоставляет всем шанс выйти на свободу, и предложил следующие условия: «В подвале тюрьмы есть комната с переключателем, имеющим два состояния: ON/OFF (верх/низ). Вас будут в произвольном порядке по одному приводить в эту комнату и через несколько минут уводить. Находясь в комнате, каждый из вас может либо изменить положение переключателя, либо ничего с ним не делать. Персонал тюрьмы трогать этот переключатель не будет. В какой-то момент один из вас (любой) должен сказать, что в комнате побывали все заключенные. Если он окажется прав — всех отпустят, если ошибется — вы навсегда останетесь в тюрьме. Я обещаю, что в комнате побывают все заключенные и что каждого из вас будут приводить туда снова и снова неограниченное число раз». После этого заключенным разрешили собраться и обсудить стратегию, потом развели по камерам. Что им нужно делать, чтобы гарантированно выйти на свободу?

одного заключенного могут завести несколько раз, а другого еще ни разу?

avbua · 16.04.2013

funfte.zirkel сказав(ла):
одного заключенного могут завести несколько раз, а другого еще ни разу?

да

burning_LEGION сказав(ла):
There are 10 types of peoples: those who understand binary, and those who don't.

Я прекрасно понимаю двоичный код и 10 в двоичном - это 2 в десятичном. Откуда взялся третий, всё равно не понятно.

Achenar · 16.04.2013

sto2299 сказав(ла):
Имеется два одинаковых стеклянных шарика и N этажный дом. Необходимо предложить алгоритм, который за наименьшее количество бросаний определяет, с какого максимального этажа этот данный шарик не разобьётся.
Следует отметить, что предложенный алгоритм минимизирует кол-во испытаний в наихудшем случае. Т.е. тогда, когда нужный этаж находится в последний момент.

Первый шарик испытывает этажи 1, 1+a, 1+2a и т.д., пока не разобьется на 1 + na < N. Второй шарик испытывает этажи 2 + na, 3+na, пока не разобьется.

Таким образом первый шарик побывает на N/a этажах (максимум), второй на a этажах (тоже максимум).

Минимум суммы N/a +a при a = N^0.5. То есть надо найти корень из N, понятно, что он не целый скорее всего, найти сумму [N/a] + a для двух ближайших к корню из N а и выбрать a, при котором сумма меньше.

Оценка количества испытаний для данного алгоритма - 2N^0.5.

Oleg_Viktorovich · 16.04.2013

Achenar сказав(ла):
Первый шарик испытывает этажи 1, 1+a, 1+2a и т.д., пока не разобьется на 1 + na < N. Второй шарик испытывает этажи 2 + na, 3+na, пока не разобьется.

Таким образом первый шарик побывает на N/a этажах (максимум), второй на a этажах (тоже максимум).

Минимум суммы N/a +a при a = N^0.5. То есть надо найти корень из N, понятно, что он не целый скорее всего, найти сумму [N/a] + a для двух ближайших к корню из N а и выбрать a, при котором сумма меньше.

Оценка количества испытаний для данного алгоритма - 2N^0.5.

если 100-эт. дом, то 20 попыток?
(100/N)+(N-1) = 19 попыток. Если бросать через каждые 10 этажей, потом бросать с 1 по 9й.
К чему я, на собеседовании у меня было такое задание...сказали, что есть меньше, чем 19 попыток...я погуглил и нашел 14 попыток, но там 4 строчки интегралов

Может кто-то ещё знает какие-нибудь простые решения для 100 этажного дома?

Achenar · 16.04.2013

Oleg_Viktorovich сказав(ла):
я погуглил и нашел 14 попыток

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

Логические задачи.

Привіт!