Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Цель работы: Сформировать навыки по решению задач с использованием циклических алгоритмов средствами изучаемого языка программирования
Основные разновидности циклов
Унифицированная структура цикл обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла.
Цикл с постусловием
Данный вид циклов реализуется оператором цикла REPEAT, который организует выполнение цикла, состоящего из любого числа операторов, с неизвестным заранее числом повторений. Тело цикла выполняется хотя бы один раз. Выход из цикла осуществляется при истинности некоторого логического выражения, поэтому иногда его называют ЦИКЛ - ДО. Структура этого оператора следующая:
repeat
instruction1;
instruction2;
. . .
instructionN
until S;
В этой структуре:
Instruction1, Instruction2, ..., InstructionN - выполняемые операторы, составляющие тело цикла;
S - логическое выражение, истинность которого проверяется в конце каждой итерации.
Так как слова repeat и until являются своеобразными операторными скобками, точку с запятой перед словом until ставить не обязательно.
Цикл с предусловием
Данный вид циклов реализуется оператором цикла WHILE, который организует выполнение одного оператора неизвестное заранее число раз. Выход из цикла осуществляется, если некоторое логическое выражение окажется ложным, поэтому данный вид циклов имеет второе название ЦИКЛ - ПОКА. Так как истинность логического выражения проверяется в начале каждой итерации, тело цикла может не выполняться ни разу. Структура оператора цикла имеет вид:
While S do Instruction;
В этой структуре:
S - логическое выражение, истинность которого проверяется в начале каждой итерации;
Instruction - выполняемый оператор цикла (единственный).
Важно: для циклов repeat и while необходимо, чтобы в теле цикла изменялась переменная, влияющая на условие выхода из цикла, либо предусмотрен альтернативный выход, в противном случае цикл будет бесконечным.
Цикл с параметром
Данный вид циклов реализуется при помощи оператора FOR, который организует выполнение одного оператора заранее известное число раз. Существует два варианта оператора:
for Param:=Start to Finish do Instruction;
for Param:=Start downto Finish do Instruction;
В этих операторах:
Param - параметр цикла, являющийся переменной порядкового типа;
Start - выражение, определяющее начальное значение параметра цикла;
Finish - выражение, определяющее конечное значение параметра цикла;
Instruction - выполняемый оператор.
Start и Finish должны быть совместимы для присваивания с параметром цикла .
Цикл действует следующим образом. Первоначально вычисляются и запоминаются начальное - Start и конечное - Finish значения параметра цикла, после чего параметру цикла Param присваивается начальное значение Start. Затем значение параметра цикла сравнивается с конечным значением Finish. Далее, пока параметр цикла меньше или равен конечному значению (в первом варианте оператора) или больше или равен конечному значению (во втором варианте), выполняется очередная итерация цикла; в противном случае происходит выход из цикла. Выполнение очередной итерации включает в себя сначала выполнение оператора Instruction, a затем присваивание параметру цикла следующего большего значения (в первом варианте оператора) или следующего меньшего значения (во втором варианте).
Естественно, что, если в первом варианте значение Start больше Finish или во втором варианте меньше Finish, оператор не выполняется ни разу.
Важно: после выхода из цикла параметр цикла принимает значение Finish (для Turbo Pascal) либо Finish + 1 или Finish – 1 (для консольного приложения Delphi), за исключением случая, когда выход из цикла был осуществлен с помощью оператора Goto или стандартной процедуры Break.
Пример 1.1 Посчитать сумму целых чисел от Xнач до Xкон с шагом 1
Таблица 1.1 Система тестов
|
Номер теста |
Данные |
Результат |
|
|
|
1 |
9 |
45 |
|
|
1 |
10 |
55 |
|
|
10 |
12 |
33 |
Решим эту задачу, используя все виды циклов. Следует отметить, что использование цикла с параметром для данной задачи возможно только при шаге равном 1. Если задача будет перефразирована например к виду: посчитать сумму чисел от Xнач до Xкон с каким-либо вещественным шагом, тогда цикл с параметром для этой цели не подойдет. Фрагменты блок-схем для каждого цикла приведены на рис. 1.1. Реализация алгоритма показана в таблице 1.2.
Рис. 1.1 Фрагменты блок-схем для примера 1.1
Таблица 1.2
|
Цикл While |
Цикл Repeat |
Цикл For |
||||||||
|
sum:=0; while xn<=xk do begin sum:=sum+xn; inc(xn); end; |
sum:=0; repeat sum:=sum+xn; inc(xn); until xn>xk; |
sum:=0; for k:=xn to xk sum:=sum+k; |
||||||||
|
Исполнение алгоритмов при xn=10 и xk=12 (все значения приведены после соответсвующего шага) |
||||||||||
|
шаг |
xn |
xk |
sum |
шаг |
xn |
xk |
sum |
шаг |
k |
sum |
|
1 |
11 |
12 |
10 |
1 |
11 |
12 |
10 |
1 |
10 |
10 |
|
2 |
12 |
12 |
21 |
2 |
12 |
12 |
21 |
2 |
11 |
21 |
|
3 |
13 |
12 |
33 |
3 |
13 |
12 |
33 |
3 |
12 |
33 |
Программное прерывание выполнения циклов
В циклах REPEAT, WHILE и FOR можно использовать две стандартные процедуры: Break и Continue. Процедура Break позволяет досрочно выйти из цикла, не дожидаясь выполнения условия выхода рис. 1.2.a. Процедура Continue позволяет начать новую итерацию цикла, даже если предыдущая не завершена; однако при этом проверяется вначале, существует ли новая итерация (анализируется условие выхода из цикла) рис. 1.2.b.
Для демонстрации применения инструкции Continue приведен пример 6.3.
Пример 1.2 Посчитать сумму целых чисел от Xнач до Xкон с шагом 1, причем вычисления прекратить если значения суммы превысит 100.
sum:=0;
while xn<xk do
begin
sum:=sum+xn;
inc(xn);
if sum>100 then break;
end;
Пример 1.3 Вывести на экран значения функции f(x)=1/x для целых x, изменяющихся от -10 до 10 с шагом 1.
x:=-10;
dec(x);
repeat
inc(x);
if x=0 then
begin
writeln('f(',x,') не существует');
continue;
end;
f:=1/x;
writeln('f(',x,')=',f:0:3);
until x>=10;
В данном примере оператор continue используется для обработки деления на нуль.
Рис. 1.2 Фрагменты блок-схем примеров 1.2 и 1.3
Проверка корректности введенных данных
Циклы зачастую используются для обеспечения корректного ввода данных пользователем, например листинг 1.1 демонстрирует проверку на корректность ввода числовой переменной x.
Листинг 1.1
Var strTmp:string;
code:integer;
x:real;
begin
repeat
write('x='); readln(strTmp);//Ввод в строковую переменную
val(strTmp,x,code); //Преобразование строки в число
if code<>0 then writeln('Error');
until code=0;
. . . //Здесь может быть размещена расчетная часть программы
end.
Для проверки корректности ввода целой переменной x можно модифицировать листинг 1.1 так как показано в листинге 1.2. Для этого случая разработаем систему тестов, а затем покажем исполнение алгоритма.
Таблица 1.3 Система тестов Таблица 1.4 Исполнение алгоритма
|
Номер теста |
Данные |
Результат |
Номер теста |
strTmp |
realTmp |
code |
x |
|
|
x |
||||||||
|
1 |
A |
Неверно |
1 |
‘A’ |
0 |
code<>0 |
неопред. |
|
|
2 |
12.5 |
Неверно |
2 |
’12.5’ |
12.5 |
code<>0 |
неопред. |
|
|
3 |
12 |
Верно |
3 |
‘12’ |
12 |
0 |
12 |
Листинг 1.2
Var strTmp:string;
code:integer;
realTmp:real;
x:integer;
begin
repeat
write( 'x='); readln(strTmp);//Ввод в строковую переменную
val(strTmp,realTmp,code); //Преобразование строки в число
if (code=0) and (realTmp=int(realTmp)) then
begin
x:=trunc(realTmp); //Приведение вещест. числа к целому
break;
end
else writeln('Error')
until false;
. . . //Здесь может быть размещена расчетная часть программы
end.
Решение задач с использованием диапазонов чисел
Пример 1.4 Подсчитать сумму всех n-значных чисел кратных 7
Все n-значные числа находятся в диапазоне от 10 n-1 до 10 n-1. Для вычисления границ диапазона можно использовать ли6о формулу 3.1 ли6о функцию power, преобразовав результат вычисления к целому типу, либо можно написать свою функцию вычисления степени целого числа (листинг 1.3).
Листинг 1.3
//Объявление функции
Function intpow(n:byte):longint;
Var i:byte; result:longint;
begin
result:=1;
for i:=1 to n do
result:=result*10;
intpow:=result;
end;
//Основная программа
Var
i, sum, a, b:longint; n:byte;
begin
write('n='); readln(n);
sum:=0;
a:= intpow(n-1);
b:=a*10-1;
for i:=a to b do
if i mod 7 = 0 then sum:=sum+i;
. . . //Здесь может быть размещен вывод результатов
end.
Решение задач полным перебором
Большинство приведенных в этой лабораторной работе задач решается при помощи полного перебора всех возможных сочетаний, однако для части задач возможно провести некоторую оптимизацию, что можно продемонстрировать на примере 6.5.
Пример 1.5 У гусей и кроликов вместе 64 лапы. Сколько может быть кроликов и гусей (указать все сочетания)?
Здесь достаточно проблематично построить систему тестов, т.к существует 17 различных вариантов (64 / 4 +1), однако некоторые из них приведем:
|
Таблица 1.5 Система тестов |
Таблица 1.6 Исполнение алгоритма для варианта 2 |
||||
|
Номер варианта |
гуси |
кролики |
k |
результат |
|
|
1 |
0 |
16 |
16 |
кроликов=16, гусей=0 |
|
|
2 |
2 |
15 |
15 |
кроликов=15, гусей=2 |
|
|
… |
… |
||||
|
17 |
32 |
0 |
0 |
кроликов=0, гусей=32 |
Вариант решения 1 (полный перебор)
For g:=0 to 64 div 2 do
For k:=64 div 4 downto 0 do
If k*4+g*2=64 then writeln(‘кроликов=’,k,’гусей=’,g)
Вариант решения 2 (оптимизированный)
For k:=64 div 4 downto 0 do
writeln(‘кроликов=’,k,’гусей=’,(64-k*4) div 2)
Пояснения к задачам 18, 23, 24, 25:
Пример 1.6 Заменить буквы цифрами так, чтобы соотношение оказалось верным (одинаковым буквам соответствуют одинаковые цифры, разным — разные): ХРУСТ*ГРОХОТ = РРРРРРРРРРР.
Систему тестов здесь составить опять таки проблематично, но после решения и проверки корректности полученного результата мы можем привести решение: 21649 * 513239 = 11111111111
Перед написанием программы следует отметить, что во время решения данной задачи может возникнуть переполнение, поэтому каждую букву заменяем переменной целого типа и определяем для нее ограничения, так h, g, r могут принимать значения из диапазона 1 .. 9, т.к. с них начинаются числа, а остальные переменные o, t, s, u находятся в диапазоне 0 .. 9.
Слова сопоставляем с переменными a, b, c, которым присваиваем тип comp, который позволяет хранить целые 11-тиразрядные числа.
Листинг 1.4 (Turbo Pascal 7.0)
{$N+} //Включение математического сопроцессора
var
h,r,u,s,t,g,o:integer;
a,b,c:comp;
begin
for r:=1 to 9 do
begin
c:=r*exp(10*ln(10))+r*1000000000+r*100000000+r*10000000+
r*1000000+r*100000+r*10000+r*1000+r*100+r*10+r;
for h:=1 to 9 do
for u:=0 to 9 do
for s:=0 to 9 do
for t:=1 to 9 do
for g:=1 to 9 do
for o:=0 to 9 do
begin
a:=h*10000+r*1000+u*100+s*10+t;
b:=g*100000+r*10000+o*1000+h*100+o*10+t;
if c=a*b then
begin
writeln(h,r,u,s,t,'*',g,r,o,h,o,t,
'=',r,r,r,r,r,r,r,r,r,r,r);
readln;
halt;
end;
end;
end;
end.
1. Имеется серия измерений элементов треугольника. Группы элементов пронумерованы. В серии в произвольном порядке могут встречаться такие группы элементов треугольника:
1)основание и высота;
2) две стороны и угол между ними (угол задан в радианах);
3) три стороны.
Разработать программу, которая запрашивает номер группы элементов, вводит соответствующие элементы и вычисляет площадь треугольника. Вычисления прекратить, если в качестве номера группы введен 0.
2. Начав тренировки, спортсмен в первый день пробежал 10 км. Каждый день он увеличивал дневную норму на 10% нормы предыдущего дня. Какой суммарный путь пробежит спортсмен за 7 дней?
3. Одноклеточная амеба каждые 3 часа делится на 2 клетки. Определить, сколько амеб будет через 3, 6, 9, 12, ..., 24 часа.
4. Около стены наклонно стоит палка длиной х м. Один ее конец находится на расстоянии у м от стены. Определить значение угла а между палкой и полом для значений х = k м и у, изменяющегося от 2 до 3 м с шагом h м.
5. На мебельной фабрике выпускают табуреты с тремя и четырьмя ногами (заготовки одинаковые). В наличии имеется 101 заготовка. Выбрать наилучшие сочетания (все варианты) изготовления табуретов, т.е. количество оставшихся ног должно стремиться к минимуму.
6. Составить алгоритм решения задачи: сколько можно купить быков, коров и телят, платя за быка 10 руб., за корову — 5 руб., а за теленка — 0,5 руб., если на 100 руб. надо купить 100 голов скота?
7. Доказать (путем перебора возможных значений), что для любых величин А, В, С типа Boolean следующие пары логических выражений имеют одинаковые значения (эквивалентны):
А) A OR В И В OR А;
Б) A AND В И В AND A;
В) (A OR В) OR С И A OR С;
Г) (A AND В) AND С И A AND (В AND С) ;
8. Составить программу для проверки утверждения: «Результатами вычислений по формуле х2 +х+ 17 при 0≤х≤ 15 являются простые числа». Все результаты вывести на экран.
9. Составить программу для проверки утверждения: «Результатами вычислений по формуле x2+x+41 при 0≤х≤40 являются простые числа». Все результаты вывести на экран.
10. Составить программу-генератор простых чисел, в основу положить формулу 2х2 + 29 при 0 ≤ х ≤ 28.
11. Составить программу-генератор простых чисел, в основу
положить формулу при 1≤ x ≤ 36
12. Составить программу-генератор чисел Пифагора а, b, с (с2 = а2 + b2). В основу положить формулы: a= m2—n2, b=2mn, с = m2 + n2 (m, n — натуральные, 1 < m < k, 1 < n < k, k — данное число). Результат вывести на экран в виде таблицы из пяти столбцов: m, n, а, b, с.
13. Составить программу, которая печатает таблицу умножения и сложения натуральных чисел в десятичной системе счисления.
14. Составить программу, которая печатает таблицу умножения и сложения натуральных чисел в шестнадцатеричной системе счисления.
15. Найти сумму всех n-значных чисел (1 ≤n ≤ 4).
16. Найти сумму всех n-значных чисел, кратных k (1 ≤ n ≤ 4).
17. Показать, что для всех n = 1, 2, 3, N
(15 + 25 + ... + n5) + (17 + 27 + ... + n7) = 2(1 + 2 + ... + n)4.
18. Составить алгоритм решения ребуса КОТ + КОТ = ТОК (различные буквы обозначают различные цифры, старшая — не 0).
19. Составить программу, которая находит наибольшее значение отношения трехзначного числа к сумме его цифр.
20. Вычислить сумму кодов всех символов, которые в цикле вводятся с клавиатуры до нажатия на клавишу Esc.
21. Вычислить количество точек с целочисленными координатами, находящихся в круге радиуса R (R>0).
22. Напечатать в возрастающем порядке все трехзначные числа, в десятичной записи которых нет одинаковых цифр (операции деления и нахождения остатка от деления не использовать).
23. Составить алгоритм решения ребуса РАДАР = (Р + А + Д)4 (различные буквы обозначают различные цифры, старшая — не 0).
24. Составить алгоритм решения ребуса МУХА + МУХА + + МУХА = СЛОН (различные буквы обозначают различные цифры, старшая - не 0).
25. Составить алгоритм решения ребуса ДРУГ — ГУРД = 2727 (различные буквы обозначают различные цифры, старшая — не 0).
26. Покупатель должен заплатить в кассу S руб. У него имеются купюры по 1, 5, 10, 50, 100, 500, 1000 и 10000 руб. Сколько купюр разного достоинства отдаст покупатель, если он начинает платить с самых крупных купюр?
27. Ежемесячная стипендия студента составляет N руб., а расходы на проживание превышают стипендию и составляют В руб. в месяц. Рост цен ежемесячно увеличивает расходы на 3%. Составьте программу расчета суммы денег, которую необходимо единовременно попросить у родителей, чтобы можно было прожить учебный год (10 месяцев), используя только эти деньги и стипендию.
28. Составить программу, которая запрашивает пароль (например, четырехзначное число) до тех пор, пока он не будет правильно введен.
29. Найдите любое трёхзначные число, кратное заданному Р и не равное ему.
30. Известен начальный вклад клиента в банк и процент годового дохода. Определите, через сколько лет вклад превысит заданный размер и каков при этом будет размер вклада.