Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте fAX, Вы писали:

fAX>>Здравствуйте KonstantinA, Вы писали:

KA>>>Предположим, что стратегия есть и мы придерживаемся такой схемы:

KA>>>Проводим взвешивание. По его результатам определяем, что делать дальше.
KA>>>Тогда
KA>>>количество_вариантов_после_взвешивания( 1 ) = #(<,>,=) = 3 // больше, меньше, равно
KA>>>количество_вариантов_после_взвешивания( 2 ) = количество_вариантов_после_взвешивания(1) * #(<,>,=) = 9
KA>>>количество_вариантов_после_взвешивания( 3 ) = количество_вариантов_после_взвешивания(2) * #(<,>,=) = 27

KA>>>Пусть есть стратегия:
KA>>>На первом шаге делим на кучки a, a, b.
KA>>>a и а --- на весах. b откладываем.
KA>>>Тогда после взвешивания мы узнаем, что
KA>>>"неправильный" шарик либо в кучке, где b шариков (=), либо в одной, где а шариков ( <, > ).
KA>>>1. Утверждается, что b <= 9
KA>>>Пусть выпало =. Тогда шарик в кучке b
KA>>>Если b > 9, то задача неразрешима, т.к. за 2 взвешивания возможно 9 вариантов показаний весов, а самих вариантов = b > 9.
KA>>>2. Утверждается a + a <= 9
fAX>>Это неверно.

KA>Да? А почему?
KA>Шарик может быть любым из a+a, а комбинаций <<, <=, <>, ><, >=, >>, =<, ==, => всего 9.

Потому что опять надо на три кучки делить и учитывать не только количество комбинаций показаний весов, но и какие кучки на весы попали. Так как кучек два типа — с дефекным шариком или без него, то комбинаций 18.

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

По-моему, 27 — это ты загнул. Я попытаюсь продолжить начинание KonstantinA и доказать, что это невозможно.

Мы разделили все шарики на три кучки взвешиваем две из них и (о чудо) они одинаковые, значит фальшивый шарик в третьей, назовём её куча_2.

Теперь проделываем тоже самое с кучей_2, и опять весы уравновесились, фальшивый шарик в куче_3.

Итак, у нас куча_3 в ней X шариков, которые мы ни разу не взвешивали, одно взвешивание и куча шариков, про которые известно, что они нормальные.

Попытаемся оценить максимальное Х, которое нам подходит. Поскольку всё шарики в куче_3 одинаковы, для определения нужного за одно взвешивания нужно разделить их по одному (взвешивать в одной чашке два шарика не имеет смысла). Т.к. у нас всего три таких места (две чашки и место вне весов), то Х не более чем 3 (у меня не вышло даже с 3-мя, но предположим за вас играет интуиция).

Теперь предположим, что предпоследнее взвешивание закончилось не так удачно. Т.е. у нас есть две кучки по У шариков, которые мы взвешивали один раз, одна "легкая", другая "тяжёлая", одно взвешивание и куча нормальных шариков.

Попытаемся оценить У. Здесь ситуация аналогична предидущей. Складывать в одну чашку два подозрительных шарика не имеет сысла (не совсем так, но в данном случае это не спасает), т.к. будет непонятно, какой из них фальшивый. Складывать два подозрительных шарика рядом с весами тем более не имеет смысла. Итого, Y должно быть 1,5. Но, так и быть, с учётом интуиции, пусть Y 2.

Итак, в куче_2 должно быть не более 7-ми шариков, иначе нам не хватит на неё двух взвешиваний. Значит за первое взвешивание мы должны отбросить 20 шариков => в кучках, которые мы с начала кладём на весы их по 10.

А теперь предположим, что одна из кучек в 10 шариков перевесила. И пусть интуиция подсказывает вам, что фальшивый шарик тяжелее, т.е. "легкую" кучку вы с чистой совестью можете выбросить. Итак, вы имеете два взвешивания, десять шариков, информацию о том, что фальшивый тяжелее и ни одного шанса решить задачу.

А если интуиция вам не поможет, всё закончится ещё печальнее...

Единственная возможность — не делить на кучки, а использовать принципиально другой подход. Какой?

Здравствуйте fAX, Вы писали:

fAX>Тут — продолжение чересчур длинной темы.

А задачи с толстыми подвохами принимаются? Если да, то у меня есть одна.

Дан ряд цифр 0123456789. Нужно используя только знаки деления получить из этого 45.
(с) Мой гениальный папа.

Ниже идут подсказки. Без них врядли что-то получится.
.
.
.
.
.
.
.
.
1. Это задачка для тех, кто не умеет считать.
.
.
.
.
.
.
.
.
.
2. Знак деления — '/', а не ':'.

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте Nikto, Вы писали:

N>>Здравствуйте fAX, Вы писали:

fAX>>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...

fAX>>>Удачи.

N>>ИМХО задачка на много проще чем если бы было 2 демона...
N>>Так вопрос такой: Это нужная арка?
N>>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ

fAX>Пояснение: Задаётся один вопрос произвольному демону.

Понятно. Тогда она решается так же как если бы демона было два...

Здравствуйте fAX, Вы писали:

fAX>Здравствуйте Аноним, Вы писали:

А>>А что понимается под взвешиванием?
fAX>Взвешивание на "чашечных" весах.

Я не очень сильно разбираюсь в весах, поэтому, может быть, мой вопрос не к месту. Но все-таки.
Знаю два типа весов с двумя "чашами". Один тип просто показывает, груз на какой из чаш тяжелее. А второй (тот, который в магазинах стоит, например) показывает еще и разницу в весе.
Какой тип используется (т.е. знаем ли мы разницу в весе?)

Здравствуйте fAX, Вы писали:

fAX>Тут — продолжение чересчур длинной темы.

Имеется последовательность x_1, ..., x_n.
Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

Задача:
По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

..и с учетом подсказок, вероятно, решение такое — повычеркивать все цифры кроме 4 и 5, используя знак / для зачеркивания

Здравствуйте KonstantinA, Вы писали:

KA>Имеется последовательность x_1, ..., x_n.
KA>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

KA>Задача:
KA>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

Легко. Хотя и не очень понятно, что такое просто монотонной. Я решил это понимать, как невозрастающую или неубывающую.

Работающий пример

Код: (ногами не пинать =))

<?
if (!isset($chain)){
  ?>
  <form action=chain.php method=post>
  Введите последовательность:<br>
  <input type=text size=50 name=chain> <br><br>
  <input type=submit value=Отправить>
  </form>
  <?
  exit;
}

if(ereg("[^0-9]",$chain)) {
  print "введена неверная (нечисловая) последовательность <a href=chain.php>попробовать еще раз</a>";
  exit;
}

print "Введена последовательность <i>$chain</i><br><br>";
$subch = array();
// 0 - невозрастающая
// 1 - неубывающая
for ($i=0;$i<strlen($chain);$i++){
  $dig = $chain{$i};
  $subch[] = array($dig,$dig);
  for ($j=0;$j<(count($subch)-1);$j++){
    $asc  = $subch[$j][1]; // неубывающая
    $desc = $subch[$j][0]; // невозрастающая
    if ($asc{strlen($asc)-1} <= $dig)   $subch[$j][1] .= $dig;
    if ($desc{strlen($desc)-1} >= $dig) $subch[$j][0] .= $dig;
  }
}

$max = 0;
for ($i=0;$i<count($subch);$i++){
 $max = (strlen($subch[$i][0])>$max)?strlen($subch[$i][0]):$max;
 $max = (strlen($subch[$i][1])>$max)?strlen($subch[$i][1]):$max;
}

print "Максимальная длина подпоследовательности <b>$max</b>";
print "<br>Такую длину имеют следующие подпоследовательности:<br><br>";

for ($i=0;$i<count($subch);$i++){
 if (strlen($subch[$i][0]) == $max) print "Невозрастающая: <i>".$subch[$i][0]."</i><br>"; 
 if (strlen($subch[$i][1]) == $max) print "Неубывающая: <i>".$subch[$i][1]."</i><br>"; 
}

print "<br><a href=chain.php>попробовать еще раз</a>";

?>

Добавьте php подсветку!!!!!!!!!!!!

R>Легко. Хотя и не очень понятно, что такое просто монотонной. Я решил это понимать, как невозрастающую или неубывающую.

Виноват, ошибся. Продолжаю думать.

Здравствуйте Rumata, Вы писали:

R>Здравствуйте KonstantinA, Вы писали:

KA>>Имеется последовательность x_1, ..., x_n.
KA>>Подпоследовательность --- это последовательность x_{k1}, x_{k2}, ..., x_{k_p} не обязательно идущих подряд членов последовательности (но с сохранением их порядка). Например последовательность 1, 2, 3, 4, 5, тогда {1,3,5}, {2,4} --- ее подпоследовательности.

KA>>Задача:
KA>>По имеющейся последовательности найти длину ее самой длинной монотонно возрастающей (убывающей/просто монотонной) подпоследовательности.

R>Легко. Хотя и не очень понятно, что такое просто монотонной. Я решил это понимать, как невозрастающую или неубывающую.

Монотонная это либо убывающая, либо возрастающая. Но это неважно. Если надется решение для возрастающих, то остальное просто...

Здравствуйте Linuxoid, Вы писали:

L>..и с учетом подсказок, вероятно, решение такое — повычеркивать все цифры кроме 4 и 5, используя знак / для зачеркивания

Правильно

Здравствуйте fAX, Вы писали:

fAX>Тут — продолжение чересчур длинной темы.

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

Есть комунальная квартира. В ней живут 3 хозяйки, которые решают приготовить обед. Поскольку газовой плиты в квартире нет, обед готовиться в печи на дровах. Обед они готвят вместе, на одном огне, одинаково долго и т.д., т.е. каждая из них тратит одинаковое количество ресурсов. Первая хозяйка принесла 3 полена, вторая — 5 поленьев, у третьей хозяйки поленьев не оказалось и она принесла 8 рублей (коммунистические цены) и отдала их первым двум.
Вопрос: как должны поделить между собой эти деньги первые две хозяйки?

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

Всё очень просто, надо только немного подумать.
I. делим на три кучки по 9 шаров, взвешиваем 2 кучи, если есть равновесие, то выкидываем обе если нет, то оставляем более тяжёлую, а остальные две выкидываем (осталось 9 шаров)
II. делим на три кучи по 3 шара, проводим ту же манипуляцию что и при I осталось 3 шара.
III. Взвешиваем 2 шара ........

Здравствуйте fAX, Вы писали:

fAX>1. Есть 27 шариков.
fAX>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>Удачи.

Пронумеруем шарики от 1 до 27.
Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1.
Определение Алгоритм --- следующая последовательность действий
(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( l_1, ..., l_a ), где все k_i, l_j попарно различны и лежат в интервале [1,27].
(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( l_1, ..., l_a ), смотрим результат взвешивания
(шаг 2).
a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( l_1, ..., l_a ). Идем на (шаг 1).
a) Если шаг 1 выполнялся 3 раза, то выход.

Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2).
Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2).
Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)

Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27
Доказательство
Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.

Обозначение (n,*) = (n,+) + (n,-)
Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число
--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1)
--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2)
Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.

Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто.
Доказательство
k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)

Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это
либо {(n,+), если n из A1},
либо {(n,-), если n из A1},
либо {(n,*), если n из A2}.
Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.

Скомбинируем теорему 1, теорему 2, теорему 3 и все

Здравствуйте YuriS, Вы писали:

YS>Здравствуйте fAX, Вы писали:

fAX>>1. Есть 27 шариков.
fAX>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>Удачи.

YS>Всё очень просто, надо только немного подумать.
YS>I. делим на три кучки по 9 шаров, взвешиваем 2 кучи, если есть равновесие, то выкидываем обе если нет, то оставляем более тяжёлую, а остальные две выкидываем (осталось 9 шаров)

А кто сказал, что неправильный шарик тяжелее?

YS>II. делим на три кучи по 3 шара, проводим ту же манипуляцию что и при I осталось 3 шара.
YS>III. Взвешиваем 2 шара ........

Здравствуйте Serge, Вы писали:

S>Здравствуйте fAX, Вы писали:

fAX>>Тут — продолжение чересчур длинной темы.

S>Вот еще одна жутко простая задачка (приведена в учебнике по математике для 6-го класса), однако большинство народу с первого раза дает неправильный ответ...

S>Есть комунальная квартира. В ней живут 3 хозяйки, которые решают приготовить обед. Поскольку газовой плиты в квартире нет, обед готовиться в печи на дровах. Обед они готвят вместе, на одном огне, одинаково долго и т.д., т.е. каждая из них тратит одинаковое количество ресурсов. Первая хозяйка принесла 3 полена, вторая — 5 поленьев, у третьей хозяйки поленьев не оказалось и она принесла 8 рублей (коммунистические цены) и отдала их первым двум.
S>Вопрос: как должны поделить между собой эти деньги первые две хозяйки?

1 и 7

( 3 — 8 / 3 ) = 1 / 3 (от первой)
( 5 — 8 / 3 ) = 7 / 3 (от второй)

Решается простой рекурсией. (Если я опять не ошибся =))))

Решение. Исходник.

Здравствуйте Rumata, Вы писали:

R>Решается простой рекурсией. (Если я опять не ошибся =))))

R>Решение. Исходник.

R> :user:

Возможно работает все правильно, но это далеко не оптимально.
Уточню задачу:
найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!

P.S. А вообще спасибо за ответ...

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте Rumata, Вы писали:

R>>Решается простой рекурсией. (Если я опять не ошибся =))))

R>>Решение. Исходник.

R>> :user:

KA>Возможно работает все правильно, но это далеко не оптимально.
KA>Уточню задачу:
KA>найти оптимальный алгоритм по затратам времени и памяти (сколько чего тратить на усмотрение решающего). Более оптимальное решение есть!

Да кстати совсем не обязательно находить эту последовательность...

Здравствуйте KonstantinA, Вы писали:

fAX>>1. Есть 27 шариков.
fAX>>2. Среди них — один, отличающийся по весу. (неизвестно, в какую сторону.)
fAX>>3. Требуется за 3 взвешивания определить, какой шарик "неправильный".

fAX>>Удачи.

[/i]День добрый. Мне серьёзно нравится Ваша настойчивость и аргументированнотсь (то, чего мне самому не хватает)[/i] :beer:

Теперь по теме. К сожалению ( :shuffle: ), явной ошибки я пока обнаружить не смог. У меня есть некоторые соображения, но об этом после. Вы не могли бы пояснить Теорему 2 (и, если можно, поменять индексы, а то "1" и "l" очень похожи, отчего плохо воспринимаются. Спасибо.

ЗЫ. Я всё же думаю, что знаю, что и где не так, но хочу дождаться Вашего ответа на этот пост.
ЗЗЫ. Я сейчас лихорадочно вспоминаю решение как самый сильный аргумент :)

fAX

KA>Пронумеруем шарики от 1 до 27.
KA>Определение (n,sign) --- конфигурация, где шарик n неправильный и тяжелее, если sign == +1, и легче, если sign == -1.
KA>Определение Алгоритм --- следующая последовательность действий
KA>(шаг 0). выбираем 0 < a <= 13, ( k_1, ..., k_a ) и ( l_1, ..., l_a ), где все k_i, l_j попарно различны и лежат в интервале [1,27].
KA>(шаг 1). Кладем на весы по а шариков ( k_1, ..., k_a ) и ( l_1, ..., l_a ), смотрим результат взвешивания
KA>(шаг 2).
KA>a) Если шаг 1 выполнялся меньше 3 раз, то по итогам предыдущих результатов взвешивания выбираем a, ( k_1, ..., k_a ) и ( l_1, ..., l_a ). Идем на (шаг 1).
KA>a) Если шаг 1 выполнялся 3 раза, то выход.

KA>Определение Результат работы алгоритма на конфигурации (n,sign) --- это те конфигурации (a_1,sign_1)...(a_k,sign_k), для которых результаты всех взвешиваний в процессе работы такие же как и для (n,sign). Обозначение A(n,sign) = (a_1,sign_1) + ... + (a_2, sign_2).
KA>Утверждение A(n_1,sign_1) == A(n_2,sign_2) либо A(n_1,sign_2) не пересекает A(n_2,sign_2).
KA>Определение Множество эквивалентности для A --- те конфигурации (a_1,sign_1),..., (a_k, sign_k), для которых A(a_1,sign_1) == ... == A(a_k, sign_k) и для любого (a,sign) не из этого множества A(a_i,sign_i) != A(a,sign)

KA>Теорема 1 Для любого алгоритма A число множеств эквивалентности не превосходит 27
KA>Доказательство
KA>Результатов взвешивания 3 * 3 * 3 = 27, а одному результату взвешиваний соответствует не более одного множества эквивалентности.

KA>Обозначение (n,*) = (n,+) + (n,-)
KA>Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
KA>Определение Пусть A решает задачу нахождения неправильного шарика, тогда n число
KA>--- типа 1 для алгоритма A, если A(n,sign) == (n,sign) для любого sign (обозначим такие числа A1)
KA>--- типа 2 для алгоритма A, если A(n,sign) == (n,*) (обозначим такие числа A2)
KA>Замечание Каждое число от 1 до 27 является либо числом типа 1, либо числом типа 2 для данного алгоритма, решающего задачу нахождения шарика.

KA>Теорема 2 Пусть A решает задачу нахождения неправильного шарика, тогда A1 не пусто.
KA>Доказательство
KA>k1 из шага 0 лежит в А1, т.к. мы знаем результаты взвешивания на первом шаге, поэтому A(k1,sign)=(k1,sign)

KA>Теорема 3 Пусть А --- алгоритм решающий задачу нахождения неправильного шарика, тогда каждое множество эквивалентности для A это
KA>либо {(n,+), если n из A1},
KA>либо {(n,-), если n из A1},
KA>либо {(n,*), если n из A2}.
KA>Поэтому количество множеств эквивалентности = 27 + количество чисел типа A1.

KA>Скомбинируем теорему 1, теорему 2, теорему 3 и все :shuffle: