Pascaler
О проекте Теоретический материал Тестирование Архив задач
Войти в личный кабинет



О проекте


Преподавателям


Тема: Решение задач.

  1. Определите члены последовательность Фибоначчи.


  2. Найдите максимальный элемент в одномерном массиве.


  3. Составьте алгоритм вычисления суммы
    .
    Указание. Обозначьте и используйте соотношения


  4. Вычислите


  5. Определите n-й член последовательности, в которой каждый следующий член равен сумме обратных величин всех предыдущих.


  6. Определите n-й член последовательности, в которой каждый следующий член равен сумме квадратов всех предыдущих.


  7. При положительном а решением уравнения х=х/2+а/(2х) служит х=√a. Рекуррентное соотношение
    можно использовать для быстрого вычисления √a. Определите корень квадратный числа а.


  8. Составьте алгоритм для вычисления 3a, используя соотношение


  9. Составьте алгоритм, вычисляющий n-й член последовательности, заданной соотношениями:


  10. Составить рекурсивную программу ввода с клавиатуры последовательности чисел (окончание ввода - 0) и вывода ее на экран в обратном порядке.

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

Для любознательных

Ханойские башни. Задача о разрезании прямоугольника

Ханойские башни - это древняя игра. Заключается она в следующем. Имеются три стержня, на одном из них (например, на правом) насажены диски разных размеров, причем диски располагаются так, чтобы стержень с дисками напоминал башню, т.е. внизу располагаются самые большие диски, а вверху - маленькие. Цель игры - перенести башню с правого стержня на левый, причем за один раз можно переносить только один диск и при этом можно насаживать только диск с меньшим диаметром на диск с большим диаметром. Средний стержень является вспомогательным для временного хранения дисков.

В программе применяются вложенность подпрограмм и рекурсивный вызов подпрограмм.

Пронумеруем стержни слева направо и договоримся переносить диски с правого (3) стержня на левый(1).

Program Tower;
Type
  Position = (Left, Centre, Right);
Var
  N : integer;

Procedure MoveDisk (From, Tol : Position);
Procedure writePos (P : Position);
Begin
  case P of
    Left : write ('1');
    Centre : write ('2');
    Right : write ('3');
  end;
End;
Begin
  writePos (From);
  write('->');
  writePos (Tol);
  writeln
End;

Procedure MoveTower(Hight : integer; From, Tol, Work : Position);
Begin
  if Hight>0
    then
      begin
        MoveTower(Hight-1, From, Work, Tol);
        MoveDisk (From, Tol);
        MoveTower(Hight-1, Work, Tol, From);
      end;
End;

Begin
  writeln('Введите количество колец ');
  readln(N);
  MoveTower(N, Right, Left, Centre);
End.

Задание. Изучите текст программы. Введите текст программы, запишите файл на диск и откомпилируйте его. после того, как компиляция выполнится успешно, задайте для просмотра в окне отладчика переменные Hight, From, Tol, Work. Установите видимыми одновременно окно редактора с текстом программы и окно просмотра. Исполните программу в пошаговом режиме с заходом в процедуры и пронаблюдайте за рекурсивным вызовом процедуры MoveTower. Дополните программу операторами графического режима, чтобы наглядно можно было представить перенос дисков со стержня на стержень. Дополните текст программы комментариями.

Рассмотрим задачу о разрезании прямоугольника.

Задача. Дан прямоугольник со сторонами А и В, где А, В - натуральные числа. Начинаем отсекать от него квадраты. Сколько таких квадратов можно отсечь, если каждый раз отсекается самый большой квадрат?

Для решения этой задачи нам нужны будут функции Max и Min для переопределения длины и ширины прямоугольника. А также введем вспомогательные переменные Х и У (У>=Х), соответствующие уменьшающимся сторонам прямоугольника, и вспомогательную переменную D, которая определяет уменьшение размеров прямоугольника после очередного отсечения наибольшего квадрата, сторона которого находится как Х:=Min(D, X) и продолжаем цикл.

В программе нам нужно организовать цикл, в котором сторона У уменьшается каждый раз на Min(D, X) до тех пор, пока не останется последний квадрат или У не станет меньше Х. В последнем случае переименовываем стороны оставшегося прямоугольника как Y := Max(D, X) и X := Min(D, Х) и продолжаем цикл.

Program OtsehKvadr;
Var
  A, B, D, K, X, Y : integer;

Function Min(I,J : integer) : integer;
Begin
  If I<J
    Then
      Min := I
    Else
      Min := J;
End;

Function Max(I,J : integer) : integer;
Begin
  if I>J
    then
      Max := I
    else
      Max := J;
End;

Begin
  repeat
    writeln ('Введите два натуральных числа ');
    readln(A,B);
  until (A>0) and (B>0);
  K := 1;
  X := Min(A, B);
  Y := Max(A, B);
  while X<>Y do
    begin
      K := K+1;
      D := Y-X;
      Y := Max(D, X);
      X := Min(D, X);
    end;
  writeln('Искомое число квадратов : ',K);
End.

Задание. Наберите текст программы. Проверьте ее работоспособность. Дополните программу комментариями. Если у Вас возникло желание, то усовершенствуйте эту программу своими дополнениями. Результат покажите учителю для оценки.

Анализ рекурсивных алгоритмов

При изучении темы "Рекурсия" полезно проанализировать рекурсивные алгоритмы с точки зрения последовательности их выполнения. Под последовательностью выполненного рекурсивного алгоритма будем понимать последовательность вызовов алгоритма с различными значениями аргументов и очередью определения результатов.

Рассмотрим сначала функцию расчетов факториала числа (см. выше)

Для алгоритма определения 5-го члена ряда Фибоначчи схема нахождения изображена на рисунке:

Чтобы определить значение 5-го элемента Фибоначчи, для этого необходимо определить значения fib(2), fib (1), fib (3), fib (2). Из схемы видно также , что в рассматриваемом случае значения fib (1), fib (3), fib (2) определяются дважды. При нахождении члена последовательности с большим номером число повторных вычислений значительно увеличивается. В результате при определения значения fib (17) компьютер выполнит свыше 1000, значения fib (31) свыше 1000000, значения fib (45) свыше 1000000000 операций сложения. В тоже время при использовании не рекурсивного алгоритма для вычисления 45-го члена потребуется всего 43 операции сложения.

Это позволяет сделать вывод о неэффективности использования рекурсии для решения рассматриваемой задачи. Аналогичный вывод можно сделать для решения других задач.

Особенности отладки и компиляции программ, содержащих процедуры и функции

При пошаговой отладке программ, содержащих процедуры и функции, при нажатии клавиши F7 в строке, которая содержит вызов подпрограммы, мы переходим в начало (на слово begin) данной подпрограммы. При завершении работы подпрограммы - если подсвечена конечная строка end или exit. При следующем нажатии F7 мы возвращаемся в ту строку основной программы, с которой попали в подпрограмму. Постоянный заход в подпрограммы часто бывает не нужен. Для пошагового исполнения основной программы без захода в подпрограммы используйте клавишу F8.

В меню Debug предусмотрено специальное окно для просмотра последовательности вызываемых функций и процедур. Это окно открывается клавишами Ctrl+F4 или через пункт меню Debug/Call stack. В этом окне прослеживается текущее, то есть изменяющееся при пошаговой отладке, состояние стека вызова подпрограмм. В верхней строке - исполняемая в данный момент подпрограмма, в нижней - основная программа, в промежутке между ними - последовательность вызовов подпрограмм от основной программы до текущей программы.

При выходе из подпрограммы стек программы освобождается от ее вызова, и верхняя строка в окне стека убирается. Это окно следует применять при сложной иерархии взаимных вызовов подпрограмм, когда не очевидно, каким путем выполнение алгоритма привело к данной подпрограмме.

При разработке программных проектов, содержащих несколько модулей, удобно использовать многооконный интерфейс среды, позволяющий одновременно работать со всеми файлами данного проекта.

Пункты этого меню позволяют выбрать расположение окон на экране, переключаться между окнами, закрывать окна. Пункт Tile разделяет экран на отдельные кусочки, в каждом из которых находится свое окно. Такой способ разбиения имеет смысл применить, если открыто 2-4 окна. Пункт Cascade накладывает окна одно на другое таким образом, что край нижних окон виден из-под верхних. При таком раскладе окон каждое из них имеет достаточно большой размер и легко может быть активизировано.

Переключение между окнами производится нажатием клавиш, указанными в меню. Для изменения размера и положения окна нужно нажатием клавиш Ctrl+F5 вызвать пункт Size/Move. Размеры окна изменяются клавишами перемещения курсора. Когда требуемый размер установлен, нужно нажать Enter для фиксации положения окна. Если Вы забудете нажать Enter, все действия будут блокированы. Для перемещения окна при нажатии клавиш управления курсором надо держать нажатой клавишу Shift.

При компиляции проектов, использующих модули, можно использовать различные режимы компиляции.

По нажатию клавиш Alt+F9 компилируется программа или модуль, находившиеся в активном окне. Используемые этой программой модули должны быть предварительно откомпилированы.

Компиляцию проектов, состоящих из нескольких модулей, удобно производить, установив основной файл - это, как правило, файл с основной программой. Для этого выбирается пункт Primary file и вводится имя файла. Уничтожение этой записи производится путем выбора пункта Clear primary file. Если начальный файл установлен, компиляция или компиляция с исполнением происходит всегда так, как будто активным окном являлось окно основной программы. Это позволяет вносить изменения в отдельных модулях и сразу запускать компиляцию и исполнение всего проекта, не переключаясь специально к основной программе.

Для подключения к основной программе модулей компилятор ищет их прежде всего в рабочем каталоге, а затем в каталогах, указанных в строке Units окна настройки, которое появляется при выборе пункта меню Options/Directories.

При нажатии клавиши F9 (Make) прежде всего происходит компиляция начального файла, заданного в строке Primary file. Если эта строка пуста, компиляция начинается с активного окна. когда в процессе компиляции программы или модуля встречаются ссылки на другие модули, проверяется необходимость перекомпиляции подключаемых модулей. Проверка заключается в сверке изменений файла с текстом модуля на Паскале и откомпилированного модуля (по времени внесения последних изменений в файл). Если в текст были внесены изменения, данный модуль компилируется вновь. Если файл модуля с текстом не найден , берется откомпилированный файл без проверки. Эта опция компилятора оптимальна по затратам времени на компиляцию, так как компилируется только то, что нужно. Компиляция и запуск на исполнение, вызываемые клавишами Ctrl+F9, производит компиляцию по данной логике.

В ряде случаев нам необходима обязательная перекомпиляция всех файлов (Build). В частности, это необходимо, если мы изменили опции компиляции в меню Options/Compiler. Изменение опций компиляции через окно не прослеживается далее автоматически, то есть среда не определяет, откомпилирован файл с новыми или старыми опциями, и не производит автоматически перекомпиляцию. Для полной компиляции всех файлов вызывается пункт Build.

Пункт Target устанавливает, для какой платформы - реального режима, защищенного режима или Windows - должны компилироваться файлы.

Вернуться назад
2003—2012 © Группа «Vimedia»
Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.