| bregalad пишет: |
| анон-анон пишет: bregalad пишет: бывают и интересные задачи. Одну я прочитал в какой-то статье про Андрея Дмитриевича Сахарова. Между стеной и человеком натянута резинка длиной в 1 метр, в ее начале находится жучок. Жучок проползает по резинке 1 см, после чего человек, растягивая резинку, отходит на 1 км. Так повторяется многократно. итерация описана не полностью, через два шага расстояние будет 1000 км или что? Длина резинки последовательно меняется: 1 метр, 1км+1м, 2км+1м, 3 км+1м и т.д. Когда резинка растягивается, жучок на ней тоже перемещается. Можно считать долю общей длины резинки, которую жучок преодолел. В первый момент она равна 1cm/1m =0.01, после отхода на километр и проползания жучком 1см она равна 0.01 + 1см/(1км+1м) = 0.01 + 1/(100000+100), после второго этапа 0.01 + 1/(100000+100) + 1/(200000+100), после третьего 0.01 + 1/(100000+100) + 1/(200000+100) + 1/(300000 + 100) и т.д. Очевидно, что ряд расходится (частичная сумма ограничена снизу величиной 1/100000*(1/2+1/3+1/4+1/5+..., а это расходящийся гармонический ряд). |
Быстренько написал программу на Питоне, подсчитывающую, через сколько шагов жучок доползет до человека:
distanceFraction = 1/100000
time = 0
while distanceFraction < 1:
time += 1
distanceFraction += 1/(time*100000+100)
print("Total time =", time)
Увы, сумма гармонического ряда настолько медленно растет (скорость логарифмическая), что дождаться окончания этой программы невозможно. Ладно, заменим километр на метр (жучок проползает сантиметр, человек отходит на метр):
distanceFraction = 1/100
time = 0
while distanceFraction < 1:
time += 1
distanceFraction += 1/(time*100+1)
print("Total time =", time)
Всё равно дождаться окончания невозможно...
Но вообще-то можно вспомнить, что мы учили математику и что частичная сумма гармонического ряда оценивается как натуральный логарифм и примерно равна
1+1/2+1/3+1/4+1/5+...+1/n ≈ ln(n) + 0.577
Тогда пишем другую программу (для расстояния 1 метр, не километр!), применяя на этот раз математику:
from math import *
# Approximate sum of harmonic series:
# 1+1/2+1/3+1/4+...+1/n == log(n) + 0.577
# Solve the equation:
# 1/100*(1/2+1/3+1/4+1/5+...1/n) = 1
# This is equivalent to:
# 1/100*(harmonicSum(n) - 1) = 1
# harmonicSum(n) = 1 + 100
# log(n) = 1 + 100 - 0.577
# n = exp(1 + 100 - 0.577)
n = exp(1 + 100 - 0.577)
k = int(n)
print("number of steps <=", k)
Запускаем программу с помощью python3 и получаем ответ:
number of steps <= 41035030085576654404824517296440350489968640
Да, жучка придется ждать очень долго (может, я ошибся в выкладках?).
