Книга содержит 145 страниц. На каждой странице 37 строк. В каждой строке 57 символов (включая пробелы). Найти информационный объём текста, считая, что каждый символ кодируется одним байтом
Представим, что мы знаем ответ на вопрос "чему равна сумма всех выписанных чисел при выполнении вызова F(n)" для всех n < k. Попробуем понять, как найти ответ для n = k.
Что делает F(n)? Читаем текст программы: сначала выводит n, а потом (если n > 0) запускает F(n - 1) и F(n - 3). Обозначим S(n) - сумму всех чисел после вызова F(n), тогда (при n > 0) S(n) = n + S(n - 1) + S(n - 3)
Для неположительных n получаем, что S(n) = n (т.к. F(n) просто выводит n и завершает работу, не запуская никаких других F).
При исследовании рекурсивных алгоритмов бывает полезно понять, сколько вызовов функций делает программа (например, если рисовать дерево вызовов, это будет показывать количество "стрелочек" на этом дереве). Представим себе, что мы стали выполнять алгоритм на бумаге, попробуем понять, сколько чисел придется выписывать. Если #(N) - число вызовов процедуры F при наивном вычислении F(N). Понятно, что #(N) = #(N - 1) + #(N - 3) (при N <= 0 #(N) = 1). Не задаваясь целью получить точную формулу для #(N), получим только оценку (на самом деле, весьма показательную). Очевидно, что #(N - 1) >= #(N - 3), тогда #(N) >= 2 * #(N - 3). Так как #(0) = 1, то #(3) >= 2 * #(0) = 2, #(6) >= 2 * #(3) >= 2^2, #(9) >= 2 * #(6) >= 2^3, и вообще #(3N) >= 2^N Отсюда можно предположить, что #(N) растет не медленнее, чем 2^(N/3) >= 1.25^N. Если 1,25^N кажется медленно растущей функцией - это вовсе не так, для N = 100 (это немного, наверно?) получим число, большее миллиарда. Так что если не запоминать промежуточные результаты, результат будет считаться ооочень долго. S(N) также растет быстро, но это уже другая проблема.
// PascalABC.Net 3.0, сборка 1064 // "Классическое" решение const nn=20;
type SqMatrix=array[1..nn,1..nn] of integer;
function AvgRow(row,cols:integer; a:SqMatrix):double; var j,s:integer; begin s:=0; for j:=1 to cols do s:=s+a[row,j]; AvgRow:=s/cols end;
var i,j,n,k:integer; cavg:double; M:SqMatrix;
begin Write('Количество строк (столбцов) в матрице: '); Read(n); Write('Ограничение для среднего арифметического: '); Read(cavg); Randomize; // Инициализация и вывод исходной матрицы Writeln('*** Сгенерированная матрица ***'); for i:=1 to n do begin for j:=1 to n do begin M[i,j]:=Random(51)-20; Write(M[i,j]:4) end; Writeln end; // Собственно, решение задачи k:=0; for i:=1 to n do if AvgRow(i,n,M)<cavg then Inc(k); Writeln('Количество отобранных строк равно ',k) end.
Второе решение дано для демонстрации возможностей современного Паскаля. Оно не подходит в качестве ответа в той части, что не использует отдельную функцию для нахождения среднего. По лаконичности записи оно вполне может соперничать с постепенно набирающим популярность языком, как Python
// PascalABC.Net 3.0, сборка 1064 // Решение, использующее возможности версии 3.0
var n: integer; cavg: double; M: array of array of integer;
begin Write('Количество строк (столбцов) в матрице: '); Read(n); Write('Ограничение для среднего арифметического: '); Read(cavg); // Инициализация и вывод исходной матрицы Writeln('*** Сгенерированная матрица ***'); SetLength(M, n); for var i := 0 to n - 1 do begin M[i] := ArrRandom(n, -25, 25); M[i].Println end; // Собственно, решение задачи var k:=M.Select(x->x.Average < cavg).Count(x->x=True); Writeln('Количество отобранных строк равно ', k) end.
1)Количество символов в книге:
142х32х56=254 464 символов
2)Так как один символ весит 1 байт, информационный объем книги равен
254 464 байт
3)Переведем в более крупные единицы:
254 464:1024=248,5 Кб или 248,5:1024=0,24 Мб
Объяснение