попалась задача

[=penelopa=]

Богатый дядюшка подарил своему племяннику в день появления на свет 1 доллар. Каждый следующий день рождения он удваивает имеющуюся у племянника сумму и прибавляет к ней столько долларов, сколько племяннику лет.
Определить сумму капитала племянника, подаренную на n-ый день рождения и всего за n лет.

Предлагаю реализовать решение алгоритмом.

У кого есть похожие, интересные задачи, пожалуйста, поделитесь))

@темы: Головоломки и занимательные задачи, алгоритм

Comments

[Trotil]

здесь был правильный ответ

[=penelopa=]

Trotil
задачка, конечно, не сложная))

[Trotil]

Ага... Пусть другие подумают

[Dagda]

2 в степени н плюс н) подарок)
2 в степени (н+1) минус 1 плюс н(1+н)/2 капиталлец)

[Amicus Plato]

Dagda
Точно?

[Trotil]

Amicus Plato

Правильность ответа легко проверить для начальных n=1,2,3...

У меня был другой ответ.

[Amicus Plato]

Trotil
ну дык... это я так завуалировано спрашиваю... )
У меня тоже другой ответ))

[Dagda]

Trotil Amicus Plato точно, ступил, подумаю) пасипп)

[NadinMart]

О, наша информатичка задала нам именно сию задачку в седьмом классе. Помню, мы еще смеялись над богатым дядюшкой, который дарит доллар. Информатичка тогда ухмыльнулась и предложила решить задачку на Бейсике. Кому удалось, тот завистливо хмыкнул..)

[Amicus Plato]

Да, эта задачка как раз алгоритмически решается элементарно)))
Т.е. здесь гораздо проще написать программу, чем найти решение в общем виде )
(Ну, это мне так кажется (мне по роду деятельности положено))))

[Dagda]

Amicus Plato алгоритмически я вообще проблемы не вижу. запрашиваешь число лет и столько раз запускаешь цикл.

[Amicus Plato]

Dagda
ну, да, так оно и есть))

[Dagda]

Amicus Plato а вот в общем виде я как-то не доберусь подумтаь хорошенько.
поидее это разностные уравнения, но я забыл как решать их((( совсем(((

[Amicus Plato]

Dagda
да нет, это задачка и без разностных уравнений решается
Только надо аккуратно выписать несколько первых лет жизни и поискать закономерность.
А вот программку я не выдержала и написала.
Впечатляет)))
Sl — "слагаемое"
S — сумма.

Задачи на геометрические прогрессии и близкие к ним всегда поражают воображение)))

[Amicus Plato]

=penelopa=, Trotil
кстати, извините за дурной вопрос, суммы сворачиваются в компактную формулу? Типа бинома Ньютона?
Что-то не соображу...

[Trotil]

Конечно
Можно получить явную формулу от n

[Amicus Plato]

Trotil
Я получила явную. Но в ней сигма!

Sl(n)=2ⁿ + Σ(_i=1ⁿ) (i*2^n-i)

Вот это сворачивается?
Или тут ошибка, которую я не вижу? )))

Я в последние дни страшный тормоз (есть на то причины ((( ).
Хотя, это меня не извиняет ))))))))

[Trotil]

У меня S как раз Si

То есть я посчитал, что дядюшка добавляет капитал до 2*a_(n-1) + n по условию

Там сигмы нет

А если еще и сложить... Сейчас попробую без сигмы написать сумму

[Amicus Plato]

Trotil
да нет (((
у меня и Sl без суммы не выходит... (((((((

[Trotil]

Вот это сворачивается?

А то, что ты написала - это геометрическая прогрессия

Нужно написать сумму для геометрической прогрессии, продифференцировать по a обе части и получится справа выражение для нужной суммы

[Amicus Plato]

Trotil
всё! Ни слова больше!
Зачем дифференцировать??? Как ты дискретную величину дифференцируешь? И для чего?
И где геометрическая прогрессия?
Какой у нее знаменатель?
Право слово, доцент тупой...

[Trotil]

Зачем дифференцировать???

Ну есть формула для такой суммы, только без i - это и есть геометрическая прогрессия
Чтобы i вылезла, нужно взять производную

[=penelopa=]

ого)) у Вас тут дискуссия, а я думала с этой понятно, хотела другую из недавно найденных мной предложить))

[Amicus Plato]

пойду спать (((
завтра буду дифференцировать))
Только всё равно не пойму, легитимно ли здесь взятие производной. Деньга же не непрерывно капает...

[Trotil]

Можно без дифференцирования обойтись в принципе

Если начать считать по-другому

[Amicus Plato]

Trotil
БЛИН!
Какой же я осёл!
Мы же кажется с тобой и кажется здесь решали задачу — один в один такую же!
Как только решила, тут же вспомнила ((((( Нет бы наоборот (((
Это просто сумма сумм геометрических прогрессий. Никакого тут не надо дифференцирования.
Формула такая:
2ⁿ⁺¹ + 2ⁿ - (n+2)

[Amicus Plato]

=penelopa=
задач много не бывает)))
выкладывай))

[Trotil]

Общий метод решения реккурентных сумм (на примере этой задачи)

Дано: a_(n+1) = 2*a_n + n

Шаг 1 ) Избавиться от полинома справа

a_(n+1) = 2*a_n + n
a_(n+2) = 2*a_(n+1) + (n+1)

Вычитаем одно из другого:

a_(n+2) - a_(n+1) = 2*a_(n+1) - 2 * a_n + (n+1) - n

a_(n+2) - 3 a_(n+1) + 2 * a_n = 1

Cледующая итерация:

a_(n+2) - 3 a_(n+1) + 2 * a_n = 1
a_(n+3) - 3 a_(n+2) + 2 * a_(n+1) = 1

a_(n+3) - 4 a_(n+2) + 5 * a_(n+1) - 2* a_n = 0

Шаг 2) Решение однородного реккурентного соотношения с линейными коэф.

Характеристическое уравнение: k^3 - 4*k^2 + 5*k - 2 = 0
или (k-1)(k-1)(k-2) = 0

Решение ищем в виде a_n = C1 * 2^n + 1^n (C2*n + C3)

Начальные условия:
a0 = 1
a1 = 3
a2 = 8

C1 + C3 = 1
2*С1 + C2 + С3 = 3
4*С1 + 2*С2 + С3 = 8

Решаем систему, получаем ответ

[Trotil]

Шаг 2 напоминает решение ОДУ, по сути так оно и есть, потому что и там, и здесь решение ищется в виде С1*k1^n + C2*k2^n + ...

[Dagda]

Trotil пасипп) напомни еще плиз, как из корней характеристического уравнения составить общий вид зависимости)