Дан рекурсивный алгоритм: procedure f(n: integer ); begin writeln ('*'); if n> 0 then begin f (n-3); f ( n div 2); end end; сколько символов "звездочка" будет напечатано на экране при выполнении вызова f (7)?
Пусть K(n) - количество звездочек, напечатанных при вызове F(n) Тогда K(n) = 1 { writeln('*') } + K(n-2) {вызов F(n-2) -> печатается еще K(n-2) звездочек} + K(n div 2) {F(n div 2)} при n > 0 и K(n) = 1 при n <= 0
Пусть а - число правильных ответов, с - число неправильных ответов. тогда число вопросов, на которые ответы даны не были - 25-а-с 5*а-9*с=40 с у нас больше либо равно 1, тогда делаем методом подстановки, не забывая, что а - обязательно целое число. с=1 5а-9=40, 5а=49, а - число не целое, значит, не подходит. с=2 5а-18=40, 5а=58, а - число не целое, значит, не подходит. с=3 5а-27=40, 5а=67, а - число не целое, значит, не подходит. с=4 5а-36=40, 5а=76, а - число не целое, значит, не подходит. с=5 5а-45=40, 5а=85, откуда а =17. ответ: 17.
Тогда
K(n) = 1 { writeln('*') } + K(n-2) {вызов F(n-2) -> печатается еще K(n-2) звездочек} + K(n div 2) {F(n div 2)} при n > 0
и K(n) = 1 при n <= 0
Требуется найти K(7)
K(7) = 1 + K(5) + K(3)
K(5) = 1 + K(3) + K(2)
K(3) = 1 + K(1) + K(1)
K(2) = 1 + K(0) + K(1)
K(1) = 1 + K(-1) + K(0)
K(0) = K(-1) = 1 {0, -1 <= 0}
K(1) = 1 + 1 + 1 = 3
K(2) = 1 + 1 + 3 = 5
K(3) = 1 + 3 + 3 = 7
K(5) = 1 + 7 + 5 = 13
K(7) = 1 + 13 + 7 = 21
ответ: 21