Tramvision
Всякая всячина => Головомойки и задачки => Тема начата: Почта сайта от 08 Июнь 2008, 23:53:57
-
Имеется очень большая колония бактерий, в которую внедряется вирус. Каждую секунду он пожирает одну бактерию и после пожирания мгновенно делится на два себе подобных. Также каждую секунду популяция бактерий увеличивается в два раза.
Уничтожит ли этот вирус все бактерии?
-
Уничтожит всех бактерий, т.к. сколько-бы их не было, вируса становится всё больше...Я даже на бумажке прикинул-на примере колонии из десяти бактерий: такая колония умрёт на 5-й секунде...А колония из 5-ти бактерий-на 3й секунде)
-
Это принцип "два шага вперед и один назад".
Думаю - нет.
-
Уничтожит всех бактерий, т.к. сколько-бы их не было, вируса становится всё больше...Я даже на бумажке прикинул-на примере колонии из десяти бактерий: такая колония умрёт на 5-й секунде...А колония из 5-ти бактерий-на 3й секунде)
Если из 10, то на пятой секунде будет 32 против 160. Проверьте вычисления :)
ЗЫ. Пока не хочу палить ответ
-
Если изначально бактерий N, то колония умрет на N секунде.
Количество вирусов на k секунде 2^k
На 0 секунде бактерий N. После первого шага бактерий становится b1 = 2*(N-1) = 2*N - 2
после 2 шага становится b2 = 4*N-8 итд.
bk = 2^k*N-ck
c0 = 0
c1 = 2
c2 = 8
ck = 2*c(k-1) + 2^k = 4*c(k-2) + 2*2^(k-1) + 2^k = 4*c(k-2) + 2 * 2^k = 8 * c(k-3) + 3*2^k. Пусть k = 3 и c(k-3) = 0.
видим, что ck = k*2^k
итого bk = 2^k*N - 2^k*k = 2^k*(N-k).
bN = 0
-
Вот, смотрите, в первой колдонке - кол-во бактелий (начальное, к примеру, 5). Вторая - кол-во вирусов. Третья - колво уничтоценных на данном шаге бактерий. Первая таблица - алгоритм, вторая - пример его осуществеления. Видим, что бактерии заканчиваются на (N-1)м шаге, если N-колво бактерий изначально.