Лабораторная работа 8. Рекурсия и сортировка данных

Краткая теория

К сегодняшнему занятию Вами изучены следующие элементы управления

• 1. Edit

  2. Label

  3. Button

  4. RadioButton

  5. CheckBox

  6. SpinEdit (на вкладке Misc)

  7. ListBox (на вкладке Standard)

  8. Memo (на вкладке Standard)

  9. ShowMessage

Компонент TStringGrid в Lazarus

Компонент TStringGrid - на вкладке компонентов Additional. Настройка таблицы StringGrid1

в окне Инспектор объектов

• 1. Убрать заголовки строк

  2. FixedCols = 0

  3. Убрать заголовки колонок

  4. FixedRows = 0

  5. Установить количество колонок

  6. ColCount = 5

  7. Установить количество строк

  8. RowCount = 1

  9. Установить ширину всех колонок

  10. DefaultColWidth = 30

  11. Установить высоту всех строк

  12. DefaultRowHeight = 30

  13. Разрешить редактирование ячеек

  14. Options/goEditing = True

Об отметках

Основные упражнения не отмечены никакими специальными знаками, их выполнения достаточно для удовлетворительной оценки. Дополнительные упражнения отмечены "звездочками", их выполнение необходимо для получения повышенной оценки.

• • "5" - в отчете выполнены все основные упражнения, дополнительно выполнены упражнения с одной и двумя "звездочками".

  • "4" - в отчете выполнены все основные упражнения, дополнительно выполнены упражнения с одной "звездочкой".

  • "3" - в отчете выполнены все основные упражнения.

Упражнения

• 1. Рекурсия. Вычислить факториал заданного числа двумя способами: итерационным методом и рекурсивным методом. Число задается в компоненте SpinEdit1, способ выбирается с помощью RadioButton1 и RadioButton2.

  2. Требования к выполнению. Использовать компоненты TLabel, TButton, TRadioButton, TSpinEdit.

  3. Пример интерфейса

• 1. Пример программы

     1.  TForm1 = class(TForm)

     2. //...

     3. // Добавить эти 2 строки в описание класса TForm1.

     4.    function iter_f(a_n : Byte) : Integer;

     5.    function recur_f(a_n : Byte) : Integer;

     6.  private

     7.    { private declarations }

     8.  public

     9.    { public declarations }

     10.  end;

     11. // В разделе implementation - 2 функции и процедура.

     12. function TForm1.iter_f(a_n : Byte) : Integer;

     13. var

     14.    x : Integer;

     15.    k : Byte;

     16. begin

     17.    x := 1;

     18.    for k := 2 to a_n do begin

     19.        x := x * k;

     20.    end;

     21.    iter_f := x;

     22. end;

     23. function TForm1.recur_f(a_n : Byte) : Integer;

     24. begin

     25.    if a_n = 0 then recur_f := 1

     26.    else recur_f := a_n * recur_f(a_n - 1);

     27. end;

     28. procedure TForm1.Button1Click(Sender: TObject);

     29. var

     30.    n : Integer;

     31. begin

     32.    n := SpinEdit1.Value;

     33.    Label2.Caption := IntToStr(n);

     34.    if RadioButton1.Checked then Label2.Caption := IntToStr(iter_f(n));;

     35.    if RadioButton2.Checked then Label2.Caption := IntToStr(recur_f(n));;

     36. end;

  2. Уникальные числа. Заполнить одномерный массив целыми случайными числами без повторений.

  3. Требования к выполнению. Использовать компоненты TLabel, TButton, TSpinEdit, TListBox, TStringGrid.

  4. Пример интерфейса

• 1. Пример программы

     1. var

     2.  Form1: TForm1;

     3. // Глобальные константы.

     4. const

     5.    N_MAX = 15;

     6.    INDEX_COL = 0;

     7.    FIRST_COL = 1;

     8. procedure TForm1.Button1Click(Sender: TObject);

     9. var

     10.    a, b, t   : ShortInt;

     11.    i         : Byte;

     12.    z         : array [1..N_MAX] of ShortInt;

     13.    set_array : set of Byte;

     14. begin

     15.    ListBox1.Clear;

     16.    a := SpinEdit1.Value;

     17.    b := SpinEdit2.Value;

     18.    // проверка b - a > N_MAX

     19.    set_array := [];

     20.    i := 1;

     21.    while i <= N_MAX do begin

     22.        ListBox1.Items.Add('Поиск... => ' + IntToStr(i) + '-го');

     23.        repeat

     24.            t := Random(b - a + 1) + a;

     25.            ListBox1.Items.Add(IntToStr(t));

     26.        until not(t in set_array);

     27.        set_array := set_array + [t];

     28.        z[i] := t;

     29.        StringGrid1.Cells[INDEX_COL, i - 1] := IntToStr(i);

     30.        StringGrid1.Cells[FIRST_COL, i - 1] := IntToStr(z[i]);

     31.        Inc(i);

     32.    end;

     33. end;

  2. Сортировка методом "пузырька". Заполнить одномерный массив целыми числами с помощью компонента StringGrid1. Отсортировать элементы массива по возрастанию и вывести в компонент StringGrid2.

  3. Рекомендация к выполнению. Настройка таблицы StringGrid1: в окне Инспектор объектов разрешить редактирование ячеек

  4. Options/goEditing = True

  5. Пример интерфейса

• 1. Пример программы

     1. var

     2.  Form1: TForm1;

     3. // Глобальные константы.

     4. const

     5.    N_MAX     = 5;

     6.    FIRST_ROW = 1;

     7.    INDEX_ROW = 0;

     8. // Глобальные переменные.

     9. var

     10.    z : array [0..N_MAX - 1] of Integer;

     11. procedure TForm1.FormCreate(Sender: TObject);

     12. var

     13.    i : 0..N_MAX - 1;

     14. begin

     15.    for i := 0 to N_MAX - 1 do begin

     16.        StringGrid1.Cells[i, INDEX_ROW] := IntToStr(i);

     17.        StringGrid2.Cells[i, INDEX_ROW] := IntToStr(i);

     18.    end;

     19. end;

     20. procedure TForm1.Button1Click(Sender: TObject);

     21. var

     22.    i, j, i_min : 0..N_MAX - 1;

     23.    min, x      : Integer;

     24. begin

     25.    for i := 0 to N_MAX - 1 do begin

     26.        z[i] := StrToInt(StringGrid1.Cells[i, FIRST_ROW]);

     27.    end;

     28.    for i := 0 to N_MAX - 2 do begin

     29.        min := z[i];

     30.        i_min := i;

     31.        for j := i + 1 to N_MAX - 1 do begin

     32.            if min > z[j] then begin

     33.                min   := z[j];

     34.                i_min := j;

     35.            end;

     36.        end;

     37.        x        := z[i];

     38.        z[i]     := z[i_min];

     39.        z[i_min] := x;

     40.    end;

     41.    for i := 0 to N_MAX - 1 do begin

     42.        StringGrid2.Cells[i, FIRST_ROW] := IntToStr(z[i]);

     43.    end;

     44. end;

  2. *Пошаговая сортировка. Заполнить одномерный целочисленный массив с помощью таблицы StringGrid1. Щелкая по кнопке Button1, вносят исходный массив в первую строку таблицы StringGrid2. Требуется при каждом щелчке по кнопке Button2 выводить в следующую свободную строку таблицы StringGrid2 очередной шаг, или итерацию, сортировки массива по возрастанию. На каждом шаге выводить на форму номер минимального элемента в неотсортированной части массива, его значение и номер шага.

  3. Пример интерфейса

Домашнее задание

• 1. Сортировка методом "пузырька" 2. В программе к задаче "Сортировка методом "пузырька" вычислить суммы строк двумерного массива и записать их соответственно в FixedRow, а затем расположить строки в порядке возрастания суммы.

  2. Требования к выполнению. Исходный массив следует заполнить целыми случайными числами и вывести в StringGrid1, а отсортированный массив - в StringGrid2.