Задачи районных олимпиад по информатике

[назад]

1.   (5 баллов) Найдите наибольшее значение отношения трехзначного числа к сумме его цифр.

Задача решается методом перебора всех возможных вариантов. Начальное значение переменной первого цикла равно единице, а не нулю т.к. число по условия задачи трехзначное. Соответственно его минимальное значение равно 100.

var

  a,b,c: integer;

  res: real;

begin

  res := 0;

  for a := 1 to 9 do

    for b := 0 to 9 do

      for c := 0 to 9 do

      if (a*100 + b*10 + c) / (a + b + c) > res then

        res:= (a*100 + b*10 + c) / (a + b + c);

   writeln ('Результат равен ', res);

end.

2.   (3 балла) Дана строка, состоящая из символов, каждый из которых является знаком «+» или цифрой, начинающаяся и заканчивающаяся цифрой. Если в строке встречается сочетание «++», то выдать сообщение об ошибке, в противном случае вычислить получившуюся сумму.

Эта задача рассчитана больше на знание языка программирования, чем  на сообразительность. Дело в  том, что в языке Turbo Pascal нет функции преобразования строки в число. Для решения задачи приходиться использовать функцию "ORD", которая позволяет получить порядковый номер любого символа согласно таблице ASCII-кодов. Например, номер сивола '0' - 48, а номер символа '1' - 49. Как вы понимаете, чтобы получить искомую цифру, необходимо отнять от номера символа 48.

const

  str = '2 + 6 + 8 + 9 + 1 + 5';

var

 i,res: integer;

begin

  for i := 1 to length(str) - 1 do

    if (str[i] = '+') and (str[i+1]= '+' ) then

      exit;

  for i := 1 to length(str) do

    if str[i] <> '+' then

     res := res + (ord(str[i]) - 48);

  writeln(res);

end.

3.     (7 баллов) Каждый элемент квадратной матрицы размеренности NxN равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.

При решении задачи используется стандартная процедура обхода 4-связной области. В компьютерной графике 4-связной называется клетчатая область, которую можно обойти ходом ладьи.

const

    n = 7;

  var

    mas: array [1..n, 1..n] of integer;

    i,j,res: integer;

  procedure count(i,j: integer);

    begin

     if mas[i,j] <> 1 then

       exit;

     mas[i,j] :=  0;

     count(i + 1, j);

     count(i - 1, j);

     count(i, j + 1);

     count(i, j - 1);

    end;

   begin

   {Инициализируем таймер случайных чисел, иначе некоторые компиляторы будут выдавать одно и тоже поле}

    randomize;

    res := 0;

  {Заполняем матрицу так, чтобы ее наружные клетки были заполнены нулями  иначе при выполнении процедуры "count" возможен выход за границы массива}

    for i := 2 to n-1 do

      for j := 2 to n-1 do

          mas[i,j]:=random(2);

   {Выводим матрицу на экран}

    for i := 1 to n do

      for j := 1 to n do

          begin

            write(mas[i,j],' ');

            if j = n then

              writeln;

          end;

    for i := 1 to n do

      for j := 1 to n do

        begin

          if mas[i,j] = 1 then

           {Сперва увеличиваем переменную res, а потом уже вызываем процедуру count иначе результат будет равен кол-ву клеток матрицы}

            inc(res);

            count(i,j);

        end;

    writeln(res);

  end.

4.     (8 баллов) В массиве А[1..n], состоящем из целых чисел, найдите самую длинную последовательность идущих подряд нулей. Укажите начало и конец.

Решение. Занесем произвольно в массив m числа. Каждый раз, когда встретится в последовательности 0, устанавливаем флаг flag = 1 и начинаем считать в переменной len сколько нулей идет далее. Когда встречается не ноль, сбрасываем flag = 0 и сравниваем len с max. В переменной max хранится ответ - максимальная длина среди всех длин кусков, состоящих из нулей. Для нахождения начала и конца последовательности заведем четыре переменных: beg и en хранят начало и конец КАЖДОГО просматриваемого куска из нулей, а в _beg и _en хранится наибольший кусок из нулей, который потом и выводим

const

  m:array[1..10] of integer = (1,1,1,2,0,1,1,4,5,5);

var

  i,flag,len,max:integer;

  _beg,beg,_en,en:integer;

begin

  flag := 0; max := 0;

  for i:=1 to 10 do

    if (m[i] = 0) then

      if (flag = 1) then Inc(len) else begin beg := i; len := 1; flag := 1; end

    else begin

           en := i-1;

           if (len > max) then

           begin

             max := len; flag := 0;

             _beg := beg; _en := en;

           end;

         end;

  writeln(max,' ', _beg,' ',_en);

end.

5. (5 баллов) Каждая пара из 17 ученных переписывается по одной из трех тем. Докажите, что найдутся трое ученых, которые попарно переписываются по одной из тем.

Решение. Эта задача на графы. Представьте себе граф с 17 вершинами. Переписка по одной из тем - ребра одного цвета. Например, темы 1,2, 3 будем считать ребра синие, зеленые и красные. По условию сказано, что какую бы пару ученых мы не взяли, они обязательно переписываются по одной из тем, то есть между ними существует хотя бы одно ребро какого-нибудь цвета.  Доказать то, что существуют три ученых, переписывающихся по одной из тем, означает, что в графе существует треугольник со сторонами одного цвета.

Доказательство строится по принципу Дирихле. Упрощенно принцип Дирихле звучит так: "Если в N клеток посадить N+1 кроликов, то в одной из клеток окажется два кролика либо более". На словах все выглядит довольно просто, но как применить принцип Дирихле в нашем случае?

 Рассмотрим одного ученого. Поскольку он переписывается по трем темам с 16 учеными, то существуют 6 ученых (3*5 < 16) с которыми он переписывается по одной теме (например, красной). Если среди этих 6 ученых существуют два, переписывающиеся по красной теме, то доказательство завершается, так как искомая тройка найдена. Иначе эти 6 ученых переписываются между собой только по синим и зеленым темам. Снова выберем одного из этих 6 ученых. По принципу Дирихле существуют 3 ученых, с которыми он переписывается по одной теме, например, синей. Если в этой тройке есть двое, переписывающиеся по синей теме, то задача решена. Если нет - то обязательно в этой тройке переписываются ТОЛЬКО по оставшейся, зеленой теме. То есть мы и в этом случае нашли тройку вершин, соединенных ребрами одного цвета, в нашем случае - зеленого.

[назад]