А вот кому работать сегодня the padlo -

[captain_solo]

можно мозги приятно поразмять - задачка, я ея в 8-м классе решал.

На столе лежат 99 одинаковых монет, из них 50 фальшивых

Comments

[tassadar_ha]

Откладываем определяемую монету в сторону, остальные разделяем на две одинаковые кучи и кладем на весы. Получаем какую-нибудь разницу. Далее шось одно із двух:

1. На весах осталось 50 фальшивых монет. Каждая отличается от другой на 1 грамм. Значит, разница между чашами будет составлять 0 или четное число (2, 4, 6...). Следовательно, наша монета настоящая.

2. На весах осталось 49 фальшивых монет. Значит, разница между чашами будет составлять нечетное число (1, 3, 5...). Следовательно, наша монета фальшивая.

[captain_solo]

молодец

сам придумал или знал раньше

[tassadar_ha]

Тоже когда-то давным-давно решал :-)

[captain_solo]

молодость - комсомол

[tassadar_ha]

Моя - она слегка позже Комсомола была (есть?), конечно. Но в остальном - таки да, молодость... :-)

[captain_solo]

ето пословица

вот ещьо поразила меня в свойо время задача про кнопки Ctr+F : оказьіваєтся чтоб проверить наличие слова длины n в тексте длины N достаточно N операций а не Nxn

[tassadar_ha]

Ищем первую букву, если находим, проверяем вторую, третью и так далее?

[captain_solo]

нудануда - вот и получается в худшем случае Nxn

а можно за N

[tassadar_ha]

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

А какой алгоритм поиска за Н шагов?

всьо просто

[captain_solo]

пусть слово длины n будет \альфа\ а \Сигма\ - весь алфавит

построить автомат с n состояниями допускающий язык \Сигма\^* \альфа\ \Сигма\^* и за N тактов проверить - допускает ли он слово - текст длины N