IІ обласна олімпіада учнів 8-10 класів з інформатики Хмельницький, 1988 рік Вариант 1 1. Составить алгоритм, подсчитывающий количество всех простых чисел, не превосходящих данного числа М. 2. Написать алгоритм вычисления количества натуральных чисел, не превосходящих М и удовлетворяющих равенству: I - J =(K + L ). 3. Фрагменты таблицы X[1:N] представляют собой последовательность ее элементов X[k], X[k+1], X[k+2], ..., X[l-1], X[l], расположенных последовательно в таблице Х, при 1 k l N. Составить алгоритм, определяющий начальный и конечный номера самого длинного монотонного фрагмента таблица Х. Монотонным фрагментом назовем такой фрагмент, в котором значения Х монотонно возрастают с ростом индекса или монотонно убывают или равны между собой. 4. Поселок состоит из N домов, расположенных вдоль прямой дороги с одной стороны на равных расстояниях. В поселке проводят телефонную связь. В таблице Т указано, сколько телефонных аппаратов надо установить в каждом доме. Написать алгоритм, определяющий, в каком доме нужно установить АТС, чтобы суммарное расстояние от АТС до всех телефонных аппаратов было минимальным. Каждый телефон связан с АТС отдельным проводом. 5. Стены некоторого упрощенного лабиринта могут быть либо параллельными, либо перпендикулярными, а длины целочисленными (например, лабиринт нарисован на листе в клетку). Кольцевые коридоры в лабиринте отсутствуют и из любой его точки существует выход. Автомат, находящийся в лабиринте, может выполнять только команды: 1. Продвинуться вперед на 1. 2. Повернуть направо на 9O градусов. 3. Повернуть налево на 9O градусов. Автомат может также проверять условия: 1. Впереди стена? 2. Вышел из лабиринта? Составить алгоритм управления автоматом, выводящий его из лабиринта. Вариант 2 1. Обувная фабрика ежегодно увеличивает производство обуви на p%. Составить программу, по которой можно рассчитать через сколько лет производство обуви удвоится. Решить задачу для p=7%, 13%, 19%. 2. Цепь состоит из двух сопротивлений R1 и R2. Эти сопротивления соединены последовательно, если n=1 и параллельно, если n=2. Определить общее сопротивление цепи. Решить задачу для R1=15 Ом и R2=21 Ом и n=1, n=2. 3. Вершины ломаной имеют координаты (X,Y), где Y=1+X /2, X= О,1,2,3,4,5. Составить программу вычисления площади фигуры, ограниченной ломаной линией, осью абсцисс и прямыми X=О, X=5. 4. Задано число а. Найти наименьшее n, удовлетворяющее условию n! a, (n!=1*G2*G3*...*Gn). Решить задачу для a=145, a=731. 5. Составить программу, по которой можно рассчитать значение функции Y=ax +bx +cx+d, не закладывая x в регистры памяти. Решить задачу для а=5, b=3, c=4, d=1 и x=1,75, x=2,5. Т е о р е т и ч е с к и й т у р 1. Даны таблицы Х[1:1ОО] и Y[1:1ОО]. Записать алгоритм, меняющий последовательно местами значения элементов X[k] и Y[k] этих таблиц для k=1, ... , 1ОО по следующему правилу: X[k] принимает значение меньшего из X[k], Y[k], а Y[k] принимает значение большего из этих элементов. 2. Составить алгоритм, подсчитывающий число тех слов в фразе, в которых во второй позиции находится заданная буква. Слова разделены одним или несколькими пробелами, других знаков препинания нет. 3. Составить алгоритм, выбирающий все четырехзначные числа, в записи которых нет цифр 1 и 9. 4. Предположим, что фигура "снежинка" образуется так: из центра вырастает 6 кристалликов-отрезков длины L под углом 6О градусов и на каждом свободном конце отрезка вырастает по 5 новых отрезков, длиной в k раз меньше L, образующих углы в 6О градусов между свободными от резками. Аналогично, из свободных концов полученных отрезков вырастает по 5 новых отрезков, длина которых в k раз меньше длины кристаллика на предыдущем уровне. Написать алгоритм, рисующий "снежинку" для любых L, k, N. 5. В некотором городе все улицы проходят с севера на юг и с запада на восток. На некоторых перекрестках установлены телефоны-автоматы. Для каждого такого перекрестка заданы его координаты X[i], Y[i] и количество автоматов на нем Т[i], i=1, ... ,N. Написать алгоритм, определяющий координаты АТС, при которых сумма длин проводов, идущих от АТС к каждому автомату минимальна. Провода разрешается прокладывать только вдоль улиц (то есть, с севера на юг или с запада на восток). П р а к т и ч е с к и й т у р Вариант 1 1. Среди целых чисел n, n+1, ... , 2n найти все такие, которые можно представить как сумму квадратов двух целых чисел. 2. Дана целочисленная таблица А. Необходимо переставить в начало таблицы все отрицательные элементы, не нарушая порядок их следования в исходной таблице. 3. Среди целых чисел n, n+1, ... , 2n, найти все простые числа, разность между которыми равна двум. 4. Написать программу вывода всех совершенных чисел от M до N, где Mf(x-h) и f(x)>f(x+h). Функция f(х)=sinx + x /1О, a=-2, b=5, h=О.2.