Дан рекурсивный алгоритм: procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
F(n-2);
F(n div 2);
F(n div 2);
end
end;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(5)?

232

498

Посмотреть ответы 1

Ответы на вопрос:

Жания27

Информатика

4,5(51 оценок)

1) 27^4 – 9^5 + 3^8 – 25 (см. рис) все числа к степеням тройки, учитывая, что 25 = 27-2 = 3^3-2∙3^0 27^4 – 9^5 + 3^8 – 25 = (3^3)^4 - (3^2)^5 + 3^8 - 3^3 + 2∙3^0 = (3^12 - 3^10) + (3^8 - 3^3) + 2∙3^0 найдем значение разности в первой скобке, учитывая что 12-ая степени тройки в троичной системе это 1000000000000(3), а 10-ая степень - это 10000000000(3) 1000000000000(3) - 10000000000(3) 220000000000(3) т.е. в троичной записи 12–10 = 2 «двойки» и 10 «нулей». вычислим аналогично вторую скобку: 100000000(3) - 1000(3) 22222000(3) т.е. в троичной записи 8–3 = 5 «двоек» и 3 «нуля». таким образом, общее количество двоек = 2+5+1 = 8 2) 3∙16^8 – 4^5 + 3 (см. рис) все числа к степеням четверки: 3∙16^8 – 4^5 + 3 = 3∙(4^2)^8 – 4^5 + 3∙4^0 = 3∙4^16 – 4^5 + 3∙4^0 найдем значение разности, учитывая что 3∙4^16 в системе счисления с основанием 4 это одна «тройка» и 16 «нулей», а 4^5 - это одна «единица» и 5 «нулей»: 30000000000000000(4) - 100000(4) 23333333333300000(4) (одна «двойка», 11 «троек» и 5 «нулей») таким образом, общее количество троек = 11+1 = 12 3) 4^1024 + 8^1025 – 2^1026 – 140количество значащих нулей равно количеству всех знаков в двоичной записи числа минус количество единиц. все числа к степеням двойки, учитывая, что 140 = 128 + 8 + 44^1024 + 8^1025 – 2^1026 – 140 = (2^2)^1024 + (2^3)^1025 – 2^1026 – (2^7+2^3+2^2) =2^3075 + 2^2048 – 2^1026 – 2^7 - 2^3 - 2^2старшая степень двойки – 3075, двоичная запись этого числа представляет собой единицу и 3075 нулей, то есть, состоит из 3076 знаков; таким образом, остаётся найти количество единиц.представим далее -2^1026 = -2^1027 + 2^1026, получим: 2^3075 + 2^2048 - 2^1027 + 2^1026 – 2^7 - 2^3 - 2^2аналогично – 2^7 = - 2^8 + 2^7, получим: 2^3075 + 2^2048 - 2^1027 + 2^1026 - 2^8 + 2^7 - 2^3 - 2^2и, наконец, - 2^3 = - 2^4 + 2^32^3075 + (2^2048 - 2^1027) + (2^1026 - 2^8) + (2^7 - 2^4) + (2^3 - 2^2)вспомним свойство: число 2^n–2^k при k < n записывается как n–k единиц и k нулей.общее число единиц = 1+(2048-1027)+(1026-8)+(7-4)+(3-2) = 2044таким образом, количество значащих нулей равно 3076-2044 = 1032