Задача 1.1
Проверить,
поместится ли на диске компьютера музыкальная композиция, которая длится m минут и n секунд, если свободное дисковое
пространство 6 мегабайт, а для записи одной секунды звука необходимо 16
килобайт.
Решение:
Для решения этой задачи необходимо знать, что 1 мегабайт=1024
килобайт, поэтому 6 мегабайт=6x1024=6144 килобайт. Обозначим t - время звучания
композиции в секундах, v - объём файла композиции в килобайтах, тогда:
t=60*m+n, v=16*t.
Программа на Паскале будет иметь вид:
var m,n,t,v:integer;
begin
writeln('Введите m и n');
readln(m,n);
t:=60*m+n;
v:=16*t;
if v<=6144 then writeln('Композиция
поместится')
else writeln('Не
хватает ',v-6144,' килобайт');
end.
Задача 1.2
Координаты двух полей шахматной доски заданы в виде двух пар чисел x1 , y1 и x2 , y2.
На первом поле стоит ферзь, на втором - конь. Определить, бьет ферзь коня, конь
- ферзя, или фигуры не угрожают друг другу.
Рассмотрим, как ходят фигуры: ферзь бьёт те поля (с координатами
x, y ), которые находятся с ним на одной вертикали (x=x1), на одной горизонтали
(y=y1), или на любой из диагоналей
(|x - x1| = (|y - y1|). Конь за один ход
переходит на два поля по одной координате и на одно поле по другой координате,
то есть поля, которые он бьёт, определяются по правилу: либо |x - x2| = 2
и |y - y2|=1, либо |x - x2| = 1 и
|y - y2| = 2. При решении нужно учитывать, что фигуры не
могут угрожать друг другу одновременно, и может быть ситуация, когда фигуры
вообще не угрожают друг другу.
Основная часть программы для данной задачи будет иметь следующий вид:
if (x1=x2)or(y1=y2)or(abs(x1-x2)=abs(y1-y2)) then
writeln('Ферзь
бьёт коня')
else if (abs(x1-x2)=2)and(abs(y1-y2)=1)or
(abs(x1-x2)=1)and(abs(y1-y2)=2) then
writeln('Конь
бьёт ферзя')
else writeln('Фигуры
не угрожают
друг другу');
Задача 1.3
Для нормального разведения золотых рыбок необходимо, чтобы на
каждую рыбку в аквариуме приходилось не менее 3-х литров воды. По известным
объему аквариума и количеству рыбок, в нем содержащихся, определить, является
ли аквариум "перенаселенным" или нет, и указать количество рыбок,
которых в случае перенаселенности необходимо поместить в другой аквариум.
Подсказка
При решении
учтите, что число рыбок должно быть целым числом. Например, в аквариуме объёмом
20,5 литров может жить 6 рыбок (а не 6,83333...). Функция выделения целой части
числа x в Паскале - trunc(x).
Задача 1.4
По данным статистического исследования, производительность
птицефермы такова, что каждые полторы курицы за полтора дня сносят полтора
яйца. Написать программу, которая позволяет рассчитать, сколько яиц (без
десятых долей) снесут N кур за d дней (N и d - целые числа).
Подсказк
При решении
учтите, что если полторы курицы за полтора дня сносят полтора яйца, то одна
курица за тот же срок (полтора дня) снесет одно яйцо. Например: 6 кур за 6 дней
снесут 24 яйца.
Задача 1.5
Показать, что любую сумму, большую 7 копеек, можно выплатить,
используя только 3-х и 5-ти копеечные монеты. (То есть, для любого целого N>7 найти такие целые числа x и y,
что 3x+5y=N ).
Подсказка
Для решения этой
задачи можно разделить число нацело N на 3 и рассмотреть остаток от деления.
Существует три варианта: если остаток 0, то сумма выплачивается трехкопеечными
монетами; если остаток 1 (наименьшее такое число 10), то необходимо убрать 3
монеты по 3 копейки и добавить 2 монеты по 5 копеек; если остаток от деления 2,
то необходимо убрать 1 трёхкопеечную монету и добавить 1 монету достоинством 5
копеек. В Паскале операция деления нацело - div, операция вычисления остатка
при делении целых чисел - mod.
Задачи
на использование циклов и стандартных алгоритмов
Задача 2.1
Для любого целого числа N>7 найти все такие пары целых чисел x и y,
что 3x+5y=N.
Разделим N нацело на 5 и получим k - максимальное значение для y
(т.е. 0<=y<=k). Организуем цикл по переменной y , и будем рассматривать значения
разности N-5y. Если это число делится нацело на 3, то полученное частное и есть
соответствующее значение x.
Соответствующая программа будет иметь вид:
var x,y,n,k:integer;
begin
writeln('Введите N');
readln(n);
k:=n div 5;
for y:=0 to k do
if (N-5*y) mod 3=0 then
begin
x:=(N-5*y) div 3;
writeln('x=',x,' y=',y);
end;
end.
Задача 2.3
Подсчитать количество сочетаний из N элементов по M (N>M). Для подсчета
количества сочетаний используется формула:
, 
Подсказка
Для решения этой задачи необходимо вычислять функцию n! (читается
n - факториал), которая представляет собой произведение натуральных чисел от 1
до n. Программа вычисления n! будет иметь вид:
var n,i:integer;
p: real;
begin
readln(n);
p:=1;
for i:=1 to n do p:=p*i;
writeln(n,'!=',p:1:0);
end.
Значение факториала накапливается в этой программе в переменной p.
Особенность оператора цикла for i:=1 to n do … в том, что если n меньше
начального значения i (в данном случае 1), то тело цикла не выполнится ни разу.
Поэтому проверять условие, что n>0 не имеет смысла, так как значение p в
этом случае останется равным 1. Для переменной p выбран вещественный тип real,
так как функция факториал очень быстро растет (формат печати :1:0 означает, что
будет печататься только целая часть числа). На основе этой программы легко
написать программу, вычисляющую 
. Вычисление
факториала удобно при этом офрмить в виде подпрограммы.
Задача 2.8
Из одного порта в другой необходимо перевезти 15 различных грузов.
Грузоподъемность судна, на котором будет проходить перевозка, 50 тонн. Грузы
пронумерованы, и информация о массах грузов хранится в массиве М(15).
Определить, сколько рейсов необходимо сделать судну, если грузы неделимы и
могут перевозиться только подряд в порядке их нумерации. (Предполагается, что
масса отдельного груза не превышает 50 тонн).
Обозначим: k - номер рейса судна, i - номер очередного груза, s -
масса груза на судне в k-том рейсе. Решать задачу будем так: если на судно в
k-том рейсе можно поместить ещё один груз, то мы грузим его и берём следующий,
если груз не может быть размещен, то перевозим его следующим рейсом
(увеличиваем k).
Основная часть соответствующей программы будет иметь вид:
k:=1;
i:=1;
s:=0;
repeat if s+m[i]<=50 then
begin
s:=s+m[i];
i:=i+1;
end
else begin k:=k+1;
s:=0;
end;
until i>15;
writeln('Всего
потребовалось', k,' рейсов');
Задача 2.10
Вычислить значение арифметического выражения:
Вычисление непрерывных радикалов производится в цикле, начиная от
внутреннего радикала. В данной задаче начальное значение 
. Каждое
следующее значение радикала будет вычисляться через предыдущее значение
радикала по формуле 
, число
изменяется от начального значения 5 до конечного значения 98 с шагом 3.
Программа для вычисления R будет иметь вид:
var r,a:real;
begin
r:=sqrt(2);
a:=5;
while a<=98 do
begin
r:=sqrt(a+r);
a:=a+3;
end;
writeln('R=',r);
end.
Вычисленное по данной программе значение 
.
Задача 2.18
Напечатать все натуральные четырехзначные числа, в десятичной
записи которых нет одинаковых цифр, и разность двух натуральных двузначных
чисел, составленных из двух последовательных первых цифр и двух
последовательных последних цифр числа, равна сумме всех цифр числа.
Решение
Любое целое четырехзначное число можно представить в виде:
(a, b, c, d
- цифры числа, причем a
0).
Например: 1742=1*1000+7*100+4*10+2.
То, что цифры числа не должны совпадать, можно записать на Паскале в виде
условия:
(a<>b)and(a<>c)and(a<>d)and(b<>c)and(b<>d)and(c<>d).
Условие на разность чисел, составленных из цифр числа:
a*10+b-(c*10+d)=a+b+c+d.
Тогда выполняемая часть программы будет иметь вид:
for a:=1 to 9 do for b:=0 to 9 do for c:=0 to 9 do for d:=0 to 9
do if
(a<>b)and(a<>c)and(a<>d)and(b<>c)and(b<>d)and(c<>d)and
(a*10+b-(c*10+d)=a+b+c+d) then writeln(a*1000+b*100+c*10+d);
Задача
2.20
Выпуклый
многоугольник задан последовательностью координат своих вершин в порядке
обхода: (x1, y1),
(x2, y2),
(x3, y3),
. . . , (xn, yn).
Вычислить площадь многоугольника.
Стандартный способ вычисления площади выпуклого многоугольника -
разбиение исходного многоугольника на отдельные треугольники (рис.) с
последующим вычислением площадей полученных треугольников и их суммированием.
Площадь отдельного треугольника можно вычислить, например, по формуле Герона,
но в данном случае более удобной будет формула расчета площади треугольника по
координатам его вершин:
Пусть n - число вершин, X(n), Y(n) - массивы, содержащие координаты вершин,
тогда основная часть программы для вычисления площади многоугольника будет
иметь вид:
s:=0;
for i:=3 to n do
s:=s+0.5*abs((x[i-1]-x[1])*(y[i]-y[1])-
(x[i]-x[1])*(y[i-1]-y[1]));
writeln('Площадь многоугольника s=',s);
Задача 4.14
На шахматной доске размером 4x4 клетки расставить 4 ладьи так,
чтобы они не угрожали друг другу. Определить все такие расстановки (всего их
будет 24).
Как и в предыдущей задаче, будем считать, что на каждой вертикали
стоит по ладье, и для каждой из них необходимо найти координату по горизонтали
(причем не совпадающую с соответствующими координатами остальных ладей). Таким
образом, исходная задача сводится к нахождению всех возможных перестановок из 4
элементов. Известно, что число перестановок из n элементов равно n!=1*2*3*…*n.
Например, из 3 элементов можно получить 3!= 1*2*3=6 перестановок:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Так как алгоритмы перестановок часто используются в олимпиадных задачах,
рассмотрим их подробнее.
Наиболее коротким и простым для запоминания является рекурсивный алгоритм
получения перестановок. Пусть X[n] - массив, элементы которого числа от 1 до n.
Для упрощения программы будем использовать процедуру printm, печатающую массив
X, и процедуру swap(a,b), меняющую местами значения переменных a и b. Тогда
программа рекурсивного получения перестановок (при n=4) будет иметь вид:
const n=4;
var x:array [1..n] of
integer;
i:integer;
procedure printm;
var i:integer;
begin
for i:=1 to n do
write(x[i],' ');
writeln;
end;
procedure swap(var
a,b:integer);
var v:integer;
begin
v:=a; a:=b; b:=v
end;
procedure perest(k:integer);
var i:integer;
begin
if k=n-1 then printm
else
for i:=k+1 to n do
begin
swap(x[k+1],x[i]);
perest(k+1);
swap(x[k+1],x[i]);
end;
end;
begin
for i:=1 to n do
x[i]:=i;
perest(0);
end.
Эта программа работает по следующему принципу: первоначально
процедура perest будет рекурсивно вызываться до тех пор, пока не будет
распечатан исходный массив X (без перестановки элементов):
1 2 3 4
Потом произойдет отход на шаг назад, перестановка двух последних элементов, и
при очередном вызове печать получившегося массива:
1 2 4 3
после чего массив вернется в первоначальное состояние.
Потом произойдет еще один отход назад и перестановка последнего и третьего с
конца элементов, после чего процедура будет снова рекурсивно вызываться, пока
не будет распечатан массив X:
1 4 3 2
Далее опять будут переставлены два последних элемента:
1 4 2 3
и т.д.
Особенность данного алгоритма в том, что после окончания он оставляет исходный
массив X без изменений.
Из программ, которые не используют рекурсию, рассмотрим следующую:
const n=4;
label 10,20,30;
var x,c:array[1..n] of
integer;
i,j:integer;
…
{описание
процедур swap и printm}
…
begin
for
i:=1 to n do x[i]:=i;
printm;
for
i:=2 to n do c[i]:=1;
20: for i:=2 to n do
begin
if c[i]<>i then goto 10;
for j:=2 to i do c[j]:=1;
end;
goto 30;
10: for j:=1 to trunc(i/2)
do swap(x[j],x[i+1-j]);
printm;
c[i]:=c[i]+1; goto 20;
30:
end.
Массив X(n) в этой программе - массив
номеров, массив C(n) - служебный массив, который используется для отслеживания
числа сделанных перестановок.
Как и в предыдущей задаче, будем считать, что на каждой вертикали
стоит по ладье, и для каждой из них необходимо найти координату по горизонтали
(причем не совпадающую с соответствующими координатами остальных ладей). Таким
образом, исходная задача сводится к нахождению всех возможных перестановок из 4
элементов. Известно, что число перестановок из n элементов равно n!=1*2*3*…*n.
Например, из 3 элементов можно получить 3!= 1*2*3=6 перестановок:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Так как алгоритмы перестановок часто используются в олимпиадных задачах,
рассмотрим их подробнее.
Наиболее коротким и простым для запоминания является рекурсивный алгоритм
получения перестановок. Пусть X[n] - массив, элементы которого числа от 1 до n.
Для упрощения программы будем использовать процедуру printm, печатающую массив
X, и процедуру swap(a,b), меняющую местами значения переменных a и b. Тогда
программа рекурсивного получения перестановок (при n=4) будет иметь вид:
const n=4;
var x:array [1..n] of
integer;
i:integer;
procedure printm;
var i:integer;
begin
for i:=1 to n do
write(x[i],' ');
writeln;
end;
procedure swap(var
a,b:integer);
var v:integer;
begin
v:=a; a:=b; b:=v
end;
procedure perest(k:integer);
var i:integer;
begin
if k=n-1 then printm
else
for i:=k+1 to n do
begin
swap(x[k+1],x[i]);
perest(k+1);
swap(x[k+1],x[i]);
end;
end;
begin
for i:=1 to n do
x[i]:=i;
perest(0);
end.
Эта программа работает по следующему принципу: первоначально
процедура perest будет рекурсивно вызываться до тех пор, пока не будет
распечатан исходный массив X (без перестановки элементов):
1 2 3 4
Потом произойдет отход на шаг назад, перестановка двух последних элементов, и
при очередном вызове печать получившегося массива:
1 2 4 3
после чего массив вернется в первоначальное состояние.
Потом произойдет еще один отход назад и перестановка последнего и третьего с
конца элементов, после чего процедура будет снова рекурсивно вызываться, пока
не будет распечатан массив X:
1 4 3 2
Далее опять будут переставлены два последних элемента:
1 4 2 3
и т.д.
Особенность данного алгоритма в том, что после окончания он оставляет исходный
массив X без изменений.
Из программ, которые не используют рекурсию, рассмотрим следующую:
const n=4;
label 10,20,30;
var x,c:array[1..n] of
integer;
i,j:integer;
…
{описание
процедур swap и printm}
…
begin
for
i:=1 to n do x[i]:=i;
printm;
for
i:=2 to n do c[i]:=1;
20: for i:=2 to n do
begin
if c[i]<>i then goto 10;
for j:=2 to i do c[j]:=1;
end;
goto 30;
10: for j:=1 to trunc(i/2)
do swap(x[j],x[i+1-j]);
printm;
c[i]:=c[i]+1; goto 20;
30:
end.
Массив X(n) в этой программе - массив
номеров, массив C(n) - служебный массив, который используется для отслеживания
числа сделанных перестановок.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.