Назад   Содержание   Вперед

1. Простые задачи.

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

Проверить, поместится ли на диске компьютера музыкальная композиция, которая длится m минут и n секунд, если свободное дисковое пространство 6 мегабайт, а для записи одной секунды звука необходимо 16 килобайт.
Решение

Координаты двух полей шахматной доски заданы в виде двух пар чисел x₁ , y₁ и x₂ , y₂. На первом поле стоит ферзь, на втором - конь. Определить, бьет ферзь коня, конь - ферзя, или фигуры не угрожают друг другу.
Решение

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

По данным статистического исследования, производительность птицефермы такова, что каждые полторы курицы за полтора дня сносят полтора яйца. Написать программу, которая позволяет рассчитать, сколько яиц (без десятых долей) снесут N кур за d дней (N и d - целые числа).
Подсказка

Показать, что любую сумму, большую 7 копеек, можно выплатить, используя только 3-х и 5-ти копеечные монеты. (То есть, для любого целого N>7 найти такие целые числа x и y, что 3x+5y=N ).
Подсказка

Написать программу, которая переводит величину, заданную в метрах и сантиметрах, в футы и дюймы. 1 фут = 30,48 см; 1 дюйм = 2,54 см. Если величина не переводится нацело, округлить число дюймов до ближайшего целого. Учесть, что 1 фут равен 12 дюймам.

Диаметр колеса автомобиля 80 см. Колесо потребует замены через 200 000 оборотов. Определить, доедет ли колесо от города Саратова до города N-ска, если расстояние между ними x километров.

Количество цветов, которые может воспроизводить видеоадаптер, определяется количеством бит, отводимых в видеопамяти ПК для описания одной точки. Например, 2 бита позволяют воспроизводить 4 цвета, 4 бита - 16 цветов и т.д. Видеопамять содержит информацию о цвете каждой точки экрана. Определить, может ли картинка на экране монитора с разрешающей способностью видеоадаптера 800x600 содержать 2048 цвета, если видеопамять ПК - 4 мегабайта.

Известна цена монитора Samsung SyncMaster в январе 2000 г. и январе 2001 г. Ответьте на вопрос: "Произошло ли удешевление или нет? На сколько процентов изменилась цена изделия?"

В совпадающих по типу переменных a и b хранятся некоторые числовые значения. Поменять местами значения этих переменных, не используя третьей дополнительной переменной.
Подсказка

Назад   Содержание   Вперед

2. Задачи на использование циклов и стандартных алгоритмов.

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

Для любого целого числа N>7 найти все такие пары целых чисел x и y, что 3x+5y=N.
Решение

Для заданного числа x распечатать числовую последовательность:
sin(x), sin(sin(x)), sin(sin(sin(x))), …
Вычисления прекратить, когда очередной элемент последовательности станет по модулю меньше, чем 10^-2.

Подсчитать количество сочетаний из N элементов по M (N>M). Для подсчета количества сочетаний используется формула:
,
Подсказка

Задан числовой массив А(50). Определить, каких элементов больше в этом массиве: положительных или отрицательных.
Подсказка

Информация о температуре воздуха и о количестве осадков в течение месяца задана в виде двух одномерных массивов. Определить, сколько выпало осадков в виде снега и сколько - в виде дождя. (Для определенности предполагается, что при 0 градусов идет дождь).

В расписании движения поездов указано время отправления 12 пригородных поездов со станции г. Урюпинска. Определить количество поездов, отправляющихся со станции в период времени с 16.00 до 19.30. (Время отправления поездов задается одномерным массивом.)

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

Из одного порта в другой необходимо перевезти 15 различных грузов. Грузоподъемность судна, на котором будет проходить перевозка, 50 тонн. Грузы пронумерованы, и информация о массах грузов хранится в массиве М(15). Определить, сколько рейсов необходимо сделать судну, если грузы неделимы и могут перевозиться только подряд в порядке их нумерации. (Предполагается, что масса отдельного груза не превышает 50 тонн).
Решение

Заполнить квадратную матрицу размера n на n натуральными числами от 1 до n² в указанном порядке:
      Например:

Вычислить значение арифметического выражения:

Решение

Вычислить значение дроби:

Подсказка

Распечатать числовую последовательность, которая задается по следующим правилам:
- первое число последовательности - произвольное нечетное число от 3 до 99;
- каждый следующий элемент последовательности определяется через предыдущий элемент р, и равен

Например:
7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
Вычисления прекратить, когда очередной элемент последовательности станет равен 1. (Известно, что в любой такой последовательности рано или поздно встречается 1.)

Распечатать числовую последовательность, которая задается по следующим правилам:
- первое число последовательности - натуральное число, кратное 3 (входной параметр задачи);
- каждый последующий элемент равен сумме кубов цифр предыдущего.
Например:
33
3³+3³=54
5³+4³=189
1³+8³+9³=1242
1³+2³+4³+2³=81
8³+1³=513
5³+1³+3³=153
Вычисления прекратить, когда очередной элемент последовательности станет равен 153. (Известно, что любая такая последовательность рано или поздно приводит к 153).
Подсказка

Для заданного натурального числа определить, образуют ли его цифры арифметическую прогрессию. Предполагается, что в числе не менее трёх цифр.
Например: 1357, 963.

В трехзначном числе зачеркнули старшую цифру. Когда полученное число умножили на 7, то получили исходное число. Найти это число.

Получить все числа, не превышающие заданного числа N, которые делятся без остатка на все свои цифры.

Задано натуральное число. Записать его в обратном порядке. Например, 12345 должно превратиться в 54321.

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

В электронных часах время показывается на табло в виде последовательности цифр, указывающих часы (от 0 до 23), минуты и секунды.
Например:

Каждая отдельная цифра на табло отображается в виде светящихся сегментов (отрезков) следующим образом:

Часы потребляют тем больше энергии, чем больше сегментов используется в записи времени. Написать программу, которая определяет время (чч.мм.сс) наибольшего и наименьшего потребления энергии часами.

Выпуклый многоугольник задан последовательностью координат своих вершин в порядке обхода: (x₁, y₁), (x₂, y₂), (x₃, y₃),  . . .  , (x_n, y_n). Вычислить площадь многоугольника.
Решение

Задана точка с координатами (x, y) и треугольник с координатами вершин (x₁, y₁), (x₂, y₂), (x₃, y₃). Определить, лежит ли точка внутри или вне треугольника.
Подсказка

Написать программу, которая по заданной дате (числу d и месяцу m) определяет число дней, прошедших от начала года, если известно, что год - не високосный.
Подсказка

Написать программу, которая по заданному числу дней, прошедших от начала года, определяет дату: число d и месяц m, если известно, что год - не високосный.

В журнале метеостанции записаны ежедневные температуры воздуха в г. Смоленске. Определить самый холодный будний день октября 1997 г., если известно, что 1 октября 1997 г. - среда. (Будними считаются все дни недели, за исключением субботы и воскресенья.)
Подсказка

Компьютерный вирус "Пятница, 13" может повредить информацию только в те дни, когда 13 число попадает на пятницу. Определить все месяцы 2000 года, в которых 13 число было пятницей. Учесть, что 2000 год - високосный и 1 января 2000 года - суббота. В качестве ответа распечатать номера месяцев.

Назад   Содержание   Вперед

Подсказки и решения.

Для решения этой задачи необходимо знать, что 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.

Рассмотрим, как ходят фигуры: ферзь бьёт те поля (с координатами x, y ), которые находятся с ним на одной вертикали (x=x₁), на одной горизонтали (y=y₁), или на любой из диагоналей (|x - x₁| = (|y - y₁|). Конь за один ход переходит на два поля по одной координате и на одно поле по другой координате, то есть поля, которые он бьёт, определяются по правилу: либо |x - x₂| = 2 и |y - y₂|=1, либо |x - x₂| = 1 и |y - y₂| = 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('Фигуры не угрожают друг другу');

При решении учтите, что число рыбок должно быть целым числом. Например, в аквариуме объёмом 20,5 литров может жить 6 рыбок (а не 6,83333...). Функция выделения целой части числа x в Паскале - trunc(x).

При решении учтите, что если полторы курицы за полтора дня сносят полтора яйца, то одна курица за тот же срок (полтора дня) снесет одно яйцо. Например: 6 кур за 6 дней снесут 24 яйца.

Для решения этой задачи можно разделить число нацело N на 3 и рассмотреть остаток от деления. Существует три варианта: если остаток 0, то сумма выплачивается трехкопеечными монетами; если остаток 1 (наименьшее такое число 10), то необходимо убрать 3 монеты по 3 копейки и добавить 2 монеты по 5 копеек; если остаток от деления 2, то необходимо убрать 1 трёхкопеечную монету и добавить 1 монету достоинством 5 копеек. В Паскале операция деления нацело - div, операция вычисления остатка при делении целых чисел - mod.

При решении этой задачи необходимо воспользоваться тем условием, что a и b - числовые переменные, тогда поменять их местами можно, например, следующим образом:
a:=a+b;
b:=a-b;
a:=a-b;

Разделим 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.

Для решения этой задачи необходимо вычислять функцию 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 означает, что будет печататься только целая часть числа). На основе этой программы легко написать программу, вычисляющую . Вычисление факториала удобно при этом офрмить в виде подпрограммы.

При решении учтите, что число 0 не относится ни к отрицательным, ни к положительным числам.

Обозначим: 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,' рейсов');

Вычисление непрерывных радикалов производится в цикле, начиная от внутреннего радикала. В данной задаче начальное значение . Каждое следующее значение радикала будет вычисляться через предыдущее значение радикала по формуле , число изменяется от начального значения 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.

Вычисленное по данной программе значение .

Вычисление непрерывных дробей производится снизу вверх, начиная от последней. Значение Q0.69777.

На каждом шаге данного алгоритма приходится разбивать целое число на отдельные цифры (причем количество цифр в числе неизвестно). Это можно выполнить, используя операции целочисленной арифметики (деления нацело - div и остатка от деления - mod). Процесс вычисления очередного члена последовательности p через предыдущий в рассматриваемой задаче будет иметь следующий вид (s и p1 - рабочие переменные, t - очередная цифра числа):

s:=0; p1:=p;
while p1<>0 do
begin
   t:=p1 mod 10;
   p1:=p1 div 10;
   s:=s+t*t*t;
end;
p:=s;

Любое целое четырехзначное число можно представить в виде:
(a, b, c, d - цифры числа, причем a0).
Например: 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);

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

Площадь отдельного треугольника можно вычислить, например, по формуле Герона, но в данном случае более удобной будет формула расчета площади треугольника по координатам его вершин:

Пусть 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);

Чтобы определить, лежит ли точка внутри треугольника, можно соединить эту точку отрезками с его вершинами и рассчитать площади получившихся треугольников (как в предыдущей задаче). Если сумма вычисленных площадей равна площади исходной фигуры (рис. а), то точка лежит внутри, если нет (рис. б) - снаружи.

Для решения задачи можно создать массив D(12), каждый элемент которого - число дней в соответствующем месяце.

Пусть i - номер дня в октябре месяце. Так как 1 октября среда, то 4 и 5 октября будут соответственно суббота и воскресенье. Соответственно, субботами и воскресеньями будут все те дни, которые отличаются от 4 и 5 на целое число недель. Субботами будут дни с такими номерами i, что остаток от деления на 7 равен 4 (i mod 7 = 4), воскресеньями - дни с номерами i, для которых i mod 7 =5.

Назад   Содержание   Вперед