Как сделать ввод с клавиатуры значения числа ключей и относительных частот?
Код:
Код:
{ Размер матриц и векторов - максимальное количество ключей в дереве }
const nMax = 10;
{ Массивы, содержащие исходные данные и результаты работы алгоритма }
type IMatrix = array [1..nMax, 1..nMax] of Integer;
RVector = array [1..nMax] of Real;
{ Процедура OptimalTree строит дерево, оптимальное по среднему времени обращения
к ключам способом динамического программирования. }
procedure OptimalTree(n : Integer; var freq : RVector; var Roots : IMatrix);
type RMatrix = array [1..nMax, 1..nMax] of Real;
var PT : RMatrix; { Матрица оценок деревьев T[i,j] и сумм частот P [i,j] }
{ Индексы и другие вспомогательные переменные: }
i, first, last, root, minRoot, nKeys : Integer;
leftWeight, rightWeight, minT : Real;
begin
{ 1. Инициализация массивов оценок и корней оптимальных деревьев }
for i := 1 to n do begin
Roots [i, i] := i;
PT [i, i] := freq [i]
end;
{ 2. Основной цикл заполнения матриц }
for nKeys := 2 to n do begin
{ nKeys - число ключей в строящемся оптимальном дереве (номер диагонали матрицы) }
for first := 1 to n - nKeys + 1 do begin
last := first + nKeys - 1;
{ Строятся деревья, содержащие ключи с номерами от first до last }
{ Сначала заполняем сумму частот для всех ключей дерева P[first, last] }
PT [last, first] := PT [first, first] + PT [last, first+1];
{ Теперь находим минимальную из оценок оптимальных деревьев }
minRoot := first; { Первый кандидат на корень }
minT := PT [first+1, last]; { Оценка дерева с корнем first }
{ Цикл по другим возможным корням дерева }
for root := first+1 to last do begin
leftWeight := PT [first, root-1];
rightWeight := 0;
if root < last then rightWeight := PT [root+1, last];
if leftWeight + rightWeight < minT then begin
{ Дерево с корнем root пока лучше всех - корректируем минимальную оценку }
minRoot := root;
minT := leftWeight + rightWeight;
end
end;
{ Заносим окончательную оценку и фиксируем корень оптимального дерева с ключами от first до last }
PT [first, last] := minT + PT [last, first];
Roots [first, last] := minRoot
end
end
end;
{ Тестируем работу процедуры на простом дереве из пяти ключей с заданными частотами поиска }
{ Исходные данные задачи - число ключей и заданные относительные частоты их поиска }
const n : Integer = 5; { Число ключей }
freq : RVector = (5, 20, 10, 30, 40,
0, 0, 0, 0, 0); { Относительные частоты }
var Roots : IMatrix; { Результат - матрица корней (структур оптимальных деревьев) }
var i, j : Integer; { Индексы }
begin
{ Вычисление оптимального дерева }
OptimalTree(n, freq, Roots);
{ Распечатка результатов - матрицы корней оптимальных деревьев }
for i := 1 to n do begin
for j := i to n do
write(' ', Roots[i,j]);
writeln
end
end .