Программирование на языке Pascal

Формулировка. Дано натуральное n (которое также может быть равно 0). Вывести на экран n-ное число Фибоначчи.

Примечание: последовательность чисел Фибоначчи задается следующей рекуррентной формулой:

То есть, нулевой член последовательности - это число 0, 1-й член - число 1, а любой другой член, начиная со 2-го, является суммой двух предыдущих. Например, F₂ = F₁ + F₀ = 1 + 0 = 1, F₃ = F₂ + F₁ = 1 + 1 = 2 и т. д.

Решение. Найдем несколько первых чисел Фибоначчи:

F₂ = F₁ + F₀ = 1 + 0 = 1;

F₃ = F₂ + F₁ = 1 + 1 = 2;

F₄ = F₃ + F₂ = 2 + 1 = 3;

F₅ = F₄ + F₃ = 3 + 2 = 5;

Легко заметить, что при их последовательном вычислении нам не нужно «расписывать» слагаемые по определению, и чтобы получить очередной член последовательности, достаточно на каждом шаге складывать два предыдущих полученных результата.

Так как нулевой и первый члены последовательности не вычисляются и даются как часть определения, будем полагать их заранее известными. Обозначим их идентификаторами fib0 и fib1. По примеру нахождения первых членов последовательности посчитаем количество операций, необходимое для вычисления каждого члена (считая, что предыдущие члены неизвестны). Легко увидеть, что для вычисления 2-го члена (при известном 1-ом и нулевом членах) необходима одна операция сложения, 3-го - две операции сложения и т. д. Видно, что по этим же правилам для вычисления n-ного члена необходимо выполнить (n - 1) операций.

Теперь можно начать писать программу. Сначала нам необходимо ввести значение n и выполнить инициализацию значений нулевого и первого чисел Фибоначчи, так как мы считаем их заранее известными:

readln(n);

fib0 := 0;

fib1 := 1;

Далее нам необходимо организовать цикл, в котором на каждом шаге переменные fib0 и fib1 будут получать следующие значения в последовательности чисел Фибоначчи. То есть, например, если в fib0 и fib1 будут находиться значения, соответственно, (n - 2)-го и (n - 1)-го членов последовательности Фибоначчи, то после одного шага цикла они будут содержать значения (n - 1)-го и n-го членов. Для этого можно создать некую вспомогательную переменную fib, в которую поместить результат сложения fib0 и fib1, после чего в fib0 у нас будет значение (n - 2)-го члена, в fib1 - (n - 1)-го, а в fib - n-го. Теперь нужно только скопировать значение fib1 в fib0 и fib в fib1, после чего значение переменной fib на этом шаге уже не имеет значения. С учетом того, что мы уже посчитали необходимое количество повторений для получения необходимого результата, цикл будет выглядеть так:

for i := 1 to n - 1 do begin

fib := fib1 + fib0;

fib0 := fib1;

fib1 := fib

end;

Такой метод решения общей задачи, основанный на использовании в ней решений задач с меньшей размерностью исходных данных (в данном случае под размерностью понимается величина n), называется динамическим программированием.

Если говорить конкретнее, то мы применили метод восходящего динамического программирования, основывающийся на решении задач сначала минимальной размерности с постепенным получением решений более обширных задач. Этот метод наиболее оптимален в плане реализации, быстродействия и используемой памяти.

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

Другой пример нисходящего динамического программирования - вычисление факториала (задача 28). Чтобы вычислить n!, необходим вычисленный (n - 1)! и т. д.

Итак, вернемся к текущей задаче. Ранее было сказано, что по исчерпании n - 1 шагов цикла в переменной fib1, которая пойдет на вывод в программе, будет храниться значение F_n. Проверим корректность обработки граничных значений (в частности, когда n = 0, 1, 2):

1) При n = 0 границы цикла будут в отрезке [1, 0 - 1]. При этом значение правой границы зависит от типа переменной i, так как компилятор, дабы избежать ошибок, при вычислении «расширяет» тип выражений, означающих границы цикла.

Если i будет объявлено типа byte, то выражение 0 - 1 даст в результате 255 (так как все числовые типы в языке Pascal большинство компиляторов считает кольцевыми), что вызовет длинную цепочку вычислений, а это неверно. Конечно, можно объявить i типа integer, и тогда границы цикла будут в отрезке [1, -1] и вход не будет осуществлен, но мы поступим иначе, стараясь сохранить память для переменных.

Так как при вычислении важно лишь количество повторений, мы можем сдвинуть отрезок [1, n - 1] на одну позицию правее на числовой прямой, и тогда цикл будет проходить от 2 до n, что поможет отсеять вход в цикл при вводе 0 в качестве n, так как невозможен цикл по всем i от 2 до 0.

Однако тогда мы столкнемся с другой проблемой: при вводе 0 будет выведено значение fib1, которой было присвоено число 1 при инициализации. Справиться с проблемой можно, присвоив fib1 значение 0, если n = 0:

if n = 0 then fib1 := 0;

2) При n = 1 (с учетом принятых в предыдущем пункте изменений) входа в цикл не будет, и на экран выведется неизменное значение fib1, равное 1;

3) При n = 2 произойдет вход в цикл, где i будет изменяться от 2 до 2 (то есть, в этом случае будет выполнен единственный шаг), в котором будет вычислено значение fib = fib1 + fib0 = 1 + 0 = 1, которое будет скопировано в fib1 и выведено на экран. Нетрудно понять, что дальнейшая подстановка значений не требуется, так как корректность циклической конструкции мы уже доказали.

Верхние значения мы не проверяем, так как не существует наибольшего номера в последовательности чисел Фибоначчи (хотя понятно, что корректность вычислений ограничена «вместимостью» типа integer, и при его превышении в вычислениях числа уже будут неправильными).

Код:

Задача № 47. Вывести на экран сумму чисел Фибоначчи до n-ного включительно

Формулировка. Дано натуральное n (которое также может быть равно 0). Вывести на экран сумму чисел Фибоначчи до n-ного включительно. Например, при n = 3 нам необходимо получить сумму 0-го, 1-го, 2-го и 3-го членов последовательности.

Решение. Задача основана на предыдущей, так как здесь нам тоже необходимо найти каждое число Фибоначчи до n включительно, однако теперь мы должны прибавлять найденные числа к некоторой переменной суммы (sum), которая потом будет выведена на экран.

Используем код предыдущей задачи:

readln(n);

fib0 := 0;

fib1 := 1;

for i := 2 to n do begin

fib := fib1 + fib0;

fib0 := fib1;

fib1 := fib

end;

if n = 0 then fib1 := 0;

writeln(fib1);

Чтобы переделать этот код по текущему назначению, мы должны добавить в цикл прибавление найденного числа Фибоначчи к переменной sum. Например, так:

for i := 2 to n do begin

fib := fib1 + fib0;

sum := sum + fib;

fib0 := fib1;

fib1 := fib

end;

Кроме того, следует исправить вывод ответа, так как нам необходимо вывести не последнее найденное число Фибоначчи, а сумму найденных чисел:

writeln(sum);

Очевидно, что вход в цикл не происходит при n = 0 и n = 1. Следовательно, правильную обработку этих случаев мы должны обеспечить инициализацией значений переменной sum, как мы это делали в предыдущей задаче.

Так как сумма нулевого и 1-го чисел Фибоначчи равна 1, то sum можно инициализировать значением 1. При входе в цикл первые два числа уже обработаны, поэтому при вводе n >= 2 накопление суммы также будет верным. Но очевидно, что в случае n = 0 необходимо инициализировать переменную sum значением 0. Реализовать эти два варианта можно так:

if n = 0 then sum := 0 else sum := 1;

Код:

Задача № 48. Вывести на экран все числа Фибоначчи до n-ного включительно

Формулировка. Дано натуральное n (которое также может быть равно 0). Вывести на экран все числа Фибоначчи до n-ного включительно.

Решение. Задача основана на задаче 46. В данном случае нам необходимо лишь выводить каждое найденное число Фибоначчи на экран. Мы можем легко получить решение этой задачи из задачи 46 или задачи 47.

Опишем основные фрагменты программы. Так как нулевой член последовательности выводится при любом возможном n, то его можно вывести на экран сразу после ввода n (или до, что не имеет значения). Затем, если n отлично от нуля, выводим на экран 1-ый член (так как вывод в цикле остальных членов происходит при n >= 2):

readln(n);

fib0 := 0;

fib1 := 1;

write(fib0, ' ');

if n <> 0 then write(fib1, ' ');

Далее необходимо добавить вывод текущего найденного члена в цикл:

for i := 2 to n do begin

fib := fib1 + fib0;

write(fib, ' ');

fib0 := fib1;

fib1 := fib

end;

Так как мы выводим все результаты в самом цикле, на этом программа заканчивается.

Код:

Задача № 49. Проверить баланс круглых скобок в символьном выражении

Формулировка. Дана последовательность символов длины n (n >= 1). Проверить баланс круглых скобок в этом выражении. Например, при вводе выражения (())() программа должна сообщить о правильности расстановки скобок, а при вводе выражения ((()) - о неправильности.

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

Так как мы вводим последовательность произвольных символов, в которой учитываются только круглые скобки, то между знаками скобок может находиться любая символьная информация, в силу чего корректная программа может проверять баланс скобок в арифметических выражениях, тексте и т. д. Например, выражение (7y + 1)(17 - (x + 3)) - правильное, а (146x + 18(y + 9) - неправильное, что сможет распознать программа.

Решение. Представим себе посимвольный ввод скобочного выражения с клавиатуры (когда уже введено некоторое количество символов) и подумаем, какие выводы можно сделать на данном этапе (для простоты восприятия будем рассматривать выражения, состоящие только из скобок):

1) ((()

Сейчас «как бы» мы видим начало скобочного выражения и не знаем, какие символы следуют далее. Какие выводы можно сделать на этом этапе? Имеющееся выражение содержит лишние открывающие скобки и его можно как сбалансировать, если дописать две закрывающие скобки, так и нарушить, если оставить в том же виде или применить множество других комбинаций. Вывод: если имеются лишние открывающие скобки, то выражение еще может быть сбалансировано.

2) (()))

Это выражение содержит явное нарушение баланса скобок, которое уже не может быть скомпенсировано добавлением любых скобочных комбинаций справа, так как не всем закрывающим скобкам соответствует по одной открывающей скобке левее. Отсюда вывод: если в выражении появилась хотя бы одна лишняя закрывающая скобка, то выражение «неправильное» и дальнейшая проверка бессмысленна.

Приступим к реализации этих рассуждений. Заведем счетчик count для подсчета открывающих и закрывающих скобок: при вводе открывающей скобки будем увеличивать его на 1, а при вводе закрывающей - уменьшать на 1.

Нам нужно создать переменную c символьного типа char, в которую мы будем последовательно вводить все символы нашего выражения. Стоит отметить, что в тип char также входит пробел, что влияет на значение длины вводимой последовательности. Например, длина n вводимого выражения (7y + 1)(17 - (x + 3)) равна 22 (пробелы выделены красным цветом).

После ввода n мы входим в цикл из n повторений, в котором вводим в c очередной символ. Полагаясь на предыдущие рассуждения, мы увеличиваем count на 1, если c = '(' и уменьшаем на 1, если c = ')':

readln(n);

count := 0;

for i := 1 to n do begin

read(c);

if c = '(' then inc(count);

if c = ')' then dec(count)

end;

Примечание: функция dec(x) уменьшает значение переменной x числового типа на 1.

Кстати, так как любой любая переменная не может иметь сразу два каких-либо значения, мы можем поместить второй условной оператор цикла в else-блок первого, что будет выглядеть логичнее, но мы не будем этого делать, чтобы повысить читаемость кода.

Отметим, что ввод n осуществляется с помощью readln(), так как он требует ввод enter'а в качестве ограничителя. При вводе n через read() далее следующий пробел или enter будет включен непосредственно во вводимую последовательность, что повлечет ошибку. Кроме того, нельзя разделять лишними пробелами или enter'ами символы последовательности при вводе, так как они не игнорируются при вводе в переменные типа char и должны быть включены в последовательность (при этом каждый пробел добавляет к длине 1, а каждый enter - 2).

Вернемся к разбору. Как же быть, если некоторый начальный фрагмент вводимого выражения станет заведомо неправильным, то есть, если в нем появятся лишние закрывающие скобки? Но тогда при появлении лишней («некомпенсируемой») закрывающей скобки переменная count станет равна -1, что можно оформить как условие выхода из цикла и поместить после первых двух операторов сравнения:

if count = -1 then break;

Какие результаты мы получим по завершении цикла?

1) Цикл прошел по всем символам, но были найдены лишние открывающие скобки (то есть, count > 0), компенсирования которых мы ожидали, однако они так и не были скомпенсированы и скобочная последовательность неправильная;

2) Цикл прошел по всем символам (то есть, не было выхода), причем количество скобок обоих видов равно (то есть, count = 0) и скобочная последовательность, соответственно, правильная;

3) Был осуществлен выход из цикла (то есть, нашли «некомпенсируемую» закрывающую скобку и count = -1) и последовательность неправильная.

Выходит, правильный ответ даст вывод выражения count = 0 (оно истинно во 2-ом случае и ложно в 1-ом и 3-ем):

writeln(count = 0);

Код:

Задача № 50. Вычислить экспоненту с заданной точностью

Формулировка. Дано действительное число x. Вычислить значение экспоненциальной функции (то есть, показательной функции e^x, где e - математическая константа, ) в точке x с заданной точностью eps с помощью ряда Тейлора:

Примечание 1: показательными называются функции вида a^x, где a - некоторое действительное число, x - независимая переменная, являющаяся показателем степени.

Примечание 2: ряд Тейлора - это представление функции в виде суммы (возможно, бесконечной) некоторых других функций по особым правилам (требующим детального математического обоснования, что в данном случае нам не нужно).

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

1) Нам дана некоторая точка на оси Ox, и мы должны вычислить значение функции e^x в этой точке. Допустим, если x = 4, то значение функции в этой точке будет равно ;

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

3) Точность должна составить вещественное число eps, меньшее 1 - это означает, что когда очередное прибавляемое к сумме слагаемое будет меньше eps, то необходимо завершить вычисление и выдать результат на экран. Это условие обязательно выполнится, так как математически доказано, что каждое следующее слагаемое в ряде Тейлора меньше предыдущего, следовательно, бесконечная последовательность слагаемых - это бесконечно убывающая последовательность.

Теперь разберемся с вычислением самого ряда. Очевидно, что любое его слагаемое, начиная со 2-го, можно получить из предыдущего, умножив его на x и разделив на натуральное число, являющееся номером текущего шага при последовательном вычислении (примем во внимание то, что тогда шаги нужно нумеровать с нуля). Значение x нам известно на любом шаге, а вот номер текущего шага (будем хранить его в переменной n) придется фиксировать.

Создадим вещественную переменную expf (от англ. exponential function - экспоненциальная функция) для накопления суммы слагаемых. Будем считать нулевой шаг уже выполненным, так как первое слагаемое в ряду - константа 1, и в связи с этим expf можно заранее проинициализировать числом 1:

expf := 1;

Так как мы начинаем вычисления не с нулевого, а с первого шага, то также нужно инициализировать значения n (числом 1, так как следующий шаг будет первым) и p (в ней будет храниться значение последнего вычисленного слагаемого):

n := 1;

p := 1;

Теперь можно приступить к разработке цикла. С учетом заданной точности eps условием его продолжения будет abs(p) >= eps, где abs(p) - модуль числа p (модуль нужен для того, чтобы не возникло ошибки, если введено отрицательное x).

В цикле необходимо домножить p на x и доделить его на текущий номер шага n, чтобы обеспечить реализацию факториала в знаменателе, после чего прибавить новое слагаемое p к результату expf и увеличить n для следующего шага:

while abs(p) >= eps do begin

p := p * x / n;

expf := expf + p;

inc(n)

end;

После выхода из цикла нужно осуществить форматированный вывод результата expf на экран с некоторым количеством цифр после точки, например, пятью. Отметим, что если при этом введенное eps содержало меньше 5 цифр после точки, то сформированное значение expf будет, соответственно, неточным.

Код:

Размещено на Allbest.ru