Turbo Pascal

NiCketT

Member
Ответ: Turbo Pascal

Есть рекурсивная процедура, которая лазит по дереву и выводит его содержимое. Нужно переделать ее с рекурсивной на итерационную. Что это значит?
Вот код процедуры:
Код:
 Procedure P2(pos1:dbl; var f:text); {обход дерева рекурсивно}
 var pos:dbl; {текущая позиция этого елемента}
 begin
   pos:=pos1;
   if pos<>nil then begin

    Write(f, 'Количество сотрудников с возрастом ');
    write(pos^.key); write(' равно '); writeln(pos^.count);

    P2(pos^.left, f); {левая ветка}
    P2(pos^.Right,f); {правая ветка}

   end;
 end;
 

quant

yeah
Відповідь: Ответ: Turbo Pascal

Есть рекурсивная процедура, которая лазит по дереву и выводит его содержимое. Нужно переделать ее с рекурсивной на итерационную. Что это значит?
итерация - это повторение, проход в цикле
эта реализация рекурсивная, а тебе нужно сделать её без рекурсии используя циклы
это можно реализовать используя стек
кстати прикольная рекурсивная функция
она оставит в файле строку 'Количество сотрудников с возрастом ' столько раз, сколько вершин у дерева, но не выдаст его содержимого
 
Останнє редагування:

NiCketT

Member
Ответ: Відповідь: Ответ: Turbo Pascal

кстати прикольная рекурсивная функция
она оставит в файле строку 'Количество сотрудников с возрастом ' столько раз, сколько вершин у дерева, но не выдаст его содержимого
это и есть содержимое дерева
 

Rostyslav

New Member
Ответ: Turbo Pascal

Народ помогите написать програмку, плізз, очень нужно. :idea:

Є монети з різними фіксованими номіналами, вираженими у копійках (наприклад, 2 і 5) у достатній кількості. Написати програму, COINS.*, яка визначає чи можна представити задану суму S (виражену у копійках), використовуючи задані номінали. Якщо це можливо, то представити цю суму за допомогою мінімальної кількості монет.
Вхідні дані: Вхідний файл COINS.DAT містить у першій стрічці суму S(0 < S < 1000000000), у другій стрічці – N – кількість різних номіналів (0 < S < 20), а в наступних N стрічках – A1 …An – номінали (в порядку зростання), які можна використовувати (0 < A1 < A2 < … < An < 1000000000).
Вихідні дані: Вихідний файл COINS.SOL повинен містити у першій стрічці знак “+”, якщо задану суму S можна представити, і знак “-”, якщо не можна. Якщо представлена сума існує, то наступні N стрічок повинні містити кількості монет кожного номіналу, які необхідні для представлення суми S за допомогою мінімальної кількості монет.
 

quant

yeah
Відповідь: Turbo Pascal

Rostyslav это в школах такую задачу задают ? нехило
жадный алгоритм ломается на тесте
Код:
8
1 4 5
потому здесь динамическое программирование
составь таблицу d от 1 до S, каждый элемент d которой будет содержать наименьшее количество монет для получения суммы i
для этого в элементах a1, a2, ... ставь единицы
и проходя i все элементы массива если d ненулевой ищи наименьшее значение из d[i - a1], d[i - a2], d[i - a3] ... записывай его, увеличенное на 1, в d
так получиш наименьшее количество монет, если не получиш - значит набрать эту сумму не возможно
а потом ищи по монетам значения на 1 меньше d и так постепенно находи путь
ну я старался понятно объяснить :) спрашивай если не ясно
 

Micle Owen

New Member
Ответ: Turbo Pascal



Задача один в один. Разбор.
 

dreamer

Member
Ответ: Turbo Pascal

Да уж, интересно зачем тебе олимпиадная задачка? ;)
 

Rostyslav

New Member
Спасибо quant . Ето мне очень помогло. Уж как нибудь разберусь.

quant я то понял твою идейку, но ты не мог бы написать ету задачу на паскале. ПЛІІЗЗ, очень прошу. Я тебе поставлю ящик уявного пива.
 

quant

yeah
Відповідь: Turbo Pascal

так как задача сложновата так и быть вспомню паскаль, только пиво я и в реале не пью - с тебя рисунок 4-мерного массива =)
Код:
const lim = 10;
var d, a: array[1..lim] of integer;
    s, ap, i, j, min: integer;

procedure reading; begin
    assign (input, 'coins.dat');
    reset (input);
    ap := 0;
    readln (input, s);
    while not eof(input) do begin
        inc(ap);
        read(input, a[ap]);
    end;
    close (input);
end;

function access (pos: integer) : integer; begin
    access := 0;
    if pos > 0 then begin
        access := d[pos];
    end;
end;

procedure building; begin
    for j := 1 to ap do begin
        d[a[j]] := 1;
    end;
    for i := 1 to s do begin
        if d[i] = 0 then begin
            min := s + 1;
            for j := 1 to ap do begin
                if (access(i - a[j]) <> 0) and (access(i - a[j]) < min) then begin
                    min := access(i - a[j]);
                end;
            end;
            if min <= s then begin
                d[i] := min + 1;
            end;
        end;
    end;
end;

procedure reverse; begin
    i := s;
    while i <> 0 do begin
        for j := 1 to ap do begin
            if access(i - a[j]) = d[i] - 1 then begin
                write (output, a[j], ' ');
                i := i - a[j];
                break;
            end;
        end;
    end;
end;

begin
    reading;
    building;
    assign (output, 'coins.sol');
    rewrite (output);
    if d[s] = 0 then begin
        writeln (output, 'it''s impossible');
        close (output);
        halt;
    end;
    reverse;
    close (output);
end.
 
Останнє редагування:
Зверху