Водной стране жил-был волшебный кузнечик, умеющий прыгать на любое расстояние. а ко¬гда он изучил тему «числовые последовательности», то решил прыгать по дороге с нумерованны¬ми клетками по придуманному им правилу: 1 247 11 16 22 29 и так далее, дальше продолжи¬те сами. а другой кузнечик решил подкараулить его в какой-нибудь клетке n, чтобы не дать уска¬кать в бесконечность. ему, предложите алгоритм, проверяющий, попадет ли первый кузнечик в клетку n?

5. “кузнечик” в одной стране жил-был волшебный кузнечик, умеющий прыгать на любое расстояние. а ко- гда он изучил тему «числовые последовательности», то решил прыгать по дороге с нумерованны- ми клетками по придуманному им правилу: 1 2 4 7 11 16 22 29 и так далее, дальше продолжи- те сами. а другой кузнечик решил подкараулить его в какой-нибудь клетке n, чтобы не дать уска- кать в бесконечность. ему, предложите алгоритм, проверяющий, попадет ли первый кузнечик в клетку n? решение: можно догадаться, что каждое n-ное число bn = bn-1 + n – 1, где b1 = 1. можно также догадаться, что каждое число нашей прогрессии bn = 1 + 1 + 2 + 3 + … + n – 1 = 1 + sn , где sn – это сумма арифметической прогрессии с a1=0 и d=1. и по формуле прогрессии получаем: bn = 1 + n(n-1)/2. остается проверить, равно ли введенное n какому-нибудь bn. решаем уравнение: n = 1 + n(n-1)/2, квадратное уравнение: n2 – n + 2 – 2n = 0, d = 1 – 4(2-2n) = 8n – 7, n = (1+sqrt(8n-7))/2 – берем только положительный ответ. получился алгоритм: подставляем n в формулу для n и если n – целое, то кузнечик попадет в клетку с номером n. вопрос только, как проверить, целое ли n. для этого проверяем, достаточно ли мало отклонение его от его округле- ния: если abs( n – round( n ) ) < 0,000000000000001, то n – скорее всего целое. по крайней мере с точностью до 0,000000000000001.

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