Задача № 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;
Код :
| 1. program FibonacciNumbersSum; 2. 3. var 4. fib0, fib1, fib, sum: integer; 5. i, n: byte; 6. 7. begin 8. readln(n); 9. fib0 := 0; 10. fib1 := 1; 11. if n = 0 then sum := 0 else sum := 1; 12. for i := 2 to n do begin 13. fib := fib1 + fib0; 14. sum := sum + fib; 15. fib0 := fib1; 16. fib1 := fib 17. end; 18. writeln(sum) 19. end. |
Задача № 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;
Так как мы выводим все результаты в самом цикле, на этом программа заканчивается.
Код :
| 1. program FirstNFibonacciNums; 2. 3. var 4. fib0, fib1, fib: integer; 5. i, n: byte; 6. 7. begin 8. readln(n); 9. fib0 := 0; 10. fib1 := 1; 11. write(fib0, ' '); 12. if n <> 0 then write(fib1, ' '); 13. for i := 2 to n do begin 14. fib := fib1 + fib0; 15. write(fib, ' '); 16. fib0 := fib1; 17. fib1 := fib 18. end 19. 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);
Код :
Дата добавления: 2018-10-25; просмотров: 488; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!