Задания для 10 класса, 2008-2009 учебный год

24.04.2009, задача 23: numbersort

Требуется написать программу, которая считывает со стандартного ввода некоторое количество чисел и сортирует их согласно пользовательскому выбору метода и направления сортировки.

При запуске программы пользователь вводит несколько целых чисел. Точное их число заранее неизвестно, ввод заканчивается когда пользователь вводит что-то, не являющееся целым числом.

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

17.04.2009, задача 22: nbook #2

Та же записная книга, что и в предыдущей задаче, но внутренняя структура для хранения записей во время работы программы — односвязный список.

10.04.2009, задача 21: nbook #1

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

Программа интерактивная, ее меню выглядит следующим образом.

  1. Показать все записи. При выборе данного пункта показываются все записи с их порядковыми номерами.
  2. Создать новую запись. При выборе данного пункта программа запрашивает в какое место записной книжки нужно вставить новую запись, после чего получает с клавиатуры данные записи и добавляет эту запись к уже существующим. Если в книжке нет свободных мест, программа должна попытаться увеличить размер массива. Если это невозможно, то программа выводит сообщение об ошибке, но продолжает работать; при этом существующее содержание книжки теряться не должно.
  3. Удалить запись. При выборе данного пункта программа запрашивает номер записи для удаления и удаляет указанную запись, если она существует.
  4. Сохранить книгу в файл. Имя файла вводится пользователем.
  5. Загрузить книгу из файла. Имя файла вводится пользователем. При ошибке загрузки текущее содержимое книги теряться не должно. Если загрузка успешна, то текущее содержимое книги замещается новым.
  6. Выход.

03.04.2009, задача 20: w/l/s count

Требуется написать программу, которая подсчитывает количество слов, строк и предложений в файле. Слова отделяются друг от друга одним или несколькими пробельными символами (пробелами, табуляциями и символами перехода на новую строку). Строки отделяются друг от друга одним символом перехода на новую строку. Предложения оканчиваются на символ «точка», далее идет несколько пробельных символов, а следующее предложение начинается с заглавной буквы.

Режим подсчета строк выбирается ключом «-l», подсчета предложений — ключом «-s», если ни одного ключа нет, то подсчитываются слова.

Обычный формат выдачи программы — по одному числу на каждый входной файл, без имен файлов или чего-то еще. Однако, если программе передан флаг «-n» то перед каждым числом она печатает имя соответствующего файла. Обратите внимание, что порядок флагов (если их несколько) может быть произвольным.

03.04.2009, задача 19: copy

Требуется написать программу, копирующую один файл в другой. Есть два обязательных аргумента, имя исходного файла и имя файла-получателя данных. Если программе передан необязательный флаг «-a», то программа дописывает содержимое исходного файла к уже существующему файлу-приемнику; в противном случае последний файл уничтожается и его содержимое должно совпадать с содержимым исходного файла.

13.03.2009, задача 18: filesize

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

06.03.2009, задача 17: progname

Необходимо реализовать программу progname, которая работает по-разному, в зависимости от имени своего исполняемого файла.

Если исполняемый файл называется «strlen», то программа печатает длины всех своих аргументов, рассматриваемых как строки. Например,

$ ./strlen abc defg
abc; 3
defg: 4

Если исполняемый файл называется «strsearch», то программа ищет во втором и последующих аргументах вхождение первого из аргументов и распечатывает те аргументы, в которых вхождение было найдено. Например,

$ ./strsearch est Test hello beast i see your breast beest
Test
beast
beest
Если аргументов менее двух, то программа предупреждать пользователя, что нужно ввести два или более параметров.

Если исполняемый файл называется «strreplace», то программа заменяет во всех своих аргументах, начиная с третьего, все вхождения первого аргумента на второй аргумент. Например,

$ ./strreplace wow go wowwowwow oh yes wowl dowowowq
gogogo
oh
yes
gol
dogoowq
Если аргументов менее трех, то программа предупреждать пользователя, что нужно ввести три или более параметров.

27.02.2009, задача 16: revecho

Необходимо реализовать программу revecho, которая распечатывает список своих аргументов в порядке, обратном нормальному: последний аргумент печатается первым. Сами аргументы при этом тоже «выворачиваются наизнанку»: последний символ аргумента печатается первым, а первый — последним.

Пример вызова программы и ее выдачи:

$ ./revecho This is a test
tset a si sihT

20.02.2009, задача 15: malloc

Нужно модифицировать программу из задания 11 (любой из двух вариантов) для использования динамического распределения памяти. Теперь программа должна запрашивать у пользователя размерности двумерного массива и самостоятельно распределять область памяти нужного размера. Функцию malloc разрешается вызывать только один раз.

20.02.2009, задача 14: sizeof

Требуется распечатать размеры в байтах, требующиеся для хранения переменных всех встроенных типов, их unsigned вариантов и указателей на переменные данных типов. После получения результатов следует задуматься о связи различных чисел, выдаваемых вашей программой.

13.02.2009, задача 13: сортировка пушек

Нужно реализовать сортировку четырех пар начальных скоростей снаряда, летящего в поле тяжести и не испытывающего сопротивления воздуха. Критерии сортировки такие:

  1. по возрастанию максимальной высоты подъема снаряда;
  2. по возрастанию дальности полета снаряда.
Значения скоростей должны быть заданы в программе, но также должен присутствовать пункт меню, позволяющий изменить значения всех скоростей.

Сами пары скоростей снарядов должны храниться в отдельных переменных. Массивы использовать не разрешается. Функция сортировки sort4 должна принимать восемь указателей на отдельные координаты и параметр, определяющий тип сортировки. При этом sort4 должна только сортировать, выводом получившихся точек на экран должна заниматься либо отдельная функция, либо функция main.

В качестве результата любой из сортировок должны выводиться 4 строчки, в каждой из которых указаны два составляющих скорости, дальность полета и максимальная высота подъема снаряда для данной начальной скорости.

23.01.2009, задача 12: strXXX

Необходимо написать программу, которая запрашивает у пользователя строку и затем входит в интерактивный диалог, показывает меню, которое состоит из следующих пунктов:

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

В самой программе нужно реализовать функции strren(), strupper() и strlower(). Две последние функции нужно реализовать через процедуры преобразования отдельных символов toupper() и tolower().

Пользоваться библиотечными процедурами нельзя.

19.12.2008, задача 11: массивы возвращаются

Заполнить двумерный массив размерности MxN (M может быть неравно N) последовательными целыми числами от единицы до M*N следующими способами.

  1. Волнами: начиная от верхней левой точки идём «углом» сверху-вниз и справа-налево каждый раз расширяя «угол». После того, как закончится свобода движения сверху-вниз или справа-налево, заполняем оставшуюся часть «угла».
  2. В этом (и только в этом) варианте предполагается, что M и N — четные числа. Массив заполняется по обычной схеме — заполняем строку слева-направо, переходим на следующую строку — но единицами заполнения являются не клетки, а квадраты 2x2. Внутри каждого квадрата заполнение подчиняется одной из 24 возможных схем заполнения четырех клеток четырьмя последовательными числами; во всех квадратах схема заполнения одинакова. На рисунке изображена одна из возможных схем заполнения.

Для лучшего понимания происходящего можно пользоваться рисунком из предыдущей задачи (варианты «d» и «e»).

12.12.2008, задача 10: заполнение массивов

Заполнить двумерный массив размерности MxN (M может быть неравно N) последовательными целыми числами от единицы до M*N следующими способами.

  1. По горизонтали, изменяя направление движения на каждой строке.
  2. По диагонали, начиная с верхнего левого угла и двигаясь вдоль диагональных направлений «отскакивая от стенок массива».
  3. По спирали, закручивающейся вовнутрь массива.

Ниже приведен рисунок, который призван помочь понять всё вышесказанное.

Без картинки придется думать:
может включить отображение картинок?

05.12.2008, задача 9: spaghetti

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

Далее пользователь вводит неотрицательное число N (то есть, пользователь может ввести все что угодно, но программа должна чутко следить за входными данными и пресекать попытки ее подломить). Это число используется следующим образом: исходный массив разделяется на N подмассивов, образованных элементами, идущими с шагом N. Для N = 3 это выглядит примерно так:

$ @ # $ @ # $ @ # $ @ # $ @ # $ @ # $ @ # $ @ # $ @
Значками «$», «@» и «#» и цветом обозначены различные подмассивы.

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

И нужно вывести на экран (в два столбца) значения соответственных элементов исходного и результирующего массивов.

05.12.2008, задача 8: чет/нечет

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

Далее пользователя запрашивают, какие числа из массива нужно вывести, четные или нечетные. И программа таки выводит все четные или нечетные элементы исходного массива в порядке их следования.

28.11.2008, задача 7: экспонента

Математике известно следующее разложение для экспоненты x меньших единицы:

Ряд Тейлора для экспоненты

В нем есть два параметра: количество членов (N) и точность (эпсилон). Вам необходимо написать программу, которая будет определять по заданной точности минимальное количество членов в сумме и по заданному количеству членов в сумме — точность вычисления. Что именно вычислять выбирает пользователь. Также пользователь с самого начала работы программы вводит значение «x».

Диалог с пользователем должен быть интерактивными: «Что вы хотите вычислить? Эпсилон? Тогда введите количество членов ряда. Что хочется теперь? Количество членов ряда? Тогда мне нужно задать точность…»

21.11.2008, задача 6: разложение на множители

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

Программа должна разлагать числа на множители, используя функцию get_smallest_divisor(), которая принимает один аргумент — целое число, а возвращает наименьший делитель данного числа, больший единицы. Функцию get_smallest_divisor() необходимо реализовать самостоятельно.

14.11.2008, задача 5: пушка

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

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

Обратите внимание: в режиме пристрелки по углу не каждое расстояние достижимо. Однако средневековые канониры знают, что максимальная дальность полета снаряда при фиксированной начальной скорости достигается при угле наклона ствола в 45 градусов. Поэтому ваша программа тоже может пользоваться этим фактом для оповещения пользователя о невозможности дострелить до точки назначения при данной начальной скорости.

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

14.11.2008, задача 4: отрицание условий

Требуется (на листочке бумаги) доказать, что оператор отрицания действует на составные условия следующим образом:

Также нужно показать, что это утверждение верно и для случая «ленивого» вычисления условий, принятого в языке C (и, кстати говоря, не только в нем).

07.11.2008, задача 3: «Официант, двойной факториал!»

Необходимо написать программу, вычисляющую двойной факториал введенного пользователем числа.

07.11.2008, тест 2: тестик ;))

Разминка от Романа Игоревича.
  1. Перечислите целые типы данных.
  2. Перечислите нецелые типы данных.
  3. Какая функция выводит данные на экран?
  4. Какая функция интерпретирует вводимые пользователем данные?
  5. Какие циклы вы знаете и как они устроены?

24.10.2008, задача 2: все экстремумы

Для заданной функции на данном отрезке необходимо найти все ее экстремумы. Алгоритм поиска должен работать для произвольной достаточно гладкой функции.

17.10.2008, задача 1: правые экстремумы

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

03.10.2008, тест 1: проверка внимательности

Первый вариант теста

  1. Ширина шины — 7 бит, частота — 12 KHz. Сколько данных такая шина способна пропустить через себя за одну минуту?
  2. В чем отличия текстового и графического режимов работы видеокарты?
  3. Почему в качестве основных цветов триады флоуресцента были выбраны красный, зеленый и синий?
  4. Каковы функции CPU и FPU?
  5. Для чего нужны шины?
  6. Перечислите типы интерфейсов контроллеров жестких дисков, их сходства и различия.
  7. Чем выделена оперативная память среди устройств PC?

Второй вариант теста

  1. Почему ЭЛТ-трубки отличаются по размеру от ЖКИ-мониторов?
  2. Текстовой режим 25x40, матрица символа — 8x8, количество различных цветов фона и символа  128, в шрифте 256 символов. Каково минимальное количество видеопамяти, нужное для работы такого видеорежима?
  3. Условия как в предыдущем вопросе. Можете ли вы предложить какой-то другой способ организации видеобуфера, отличный от дающего минимальный размер видеопамяти? Будет ли этот способ лучше или хуже?
  4. Каковы функции контроллеров?
  5. Чем (с точки зрения хранения информации, а не с точки зрения внутренней организации) отличаются ОЗУ и жесткие диски?
  6. Чем параллельное подключение отличается от подключения типа «точка-точка»?
  7. Какие способы визуализации трехмерного мира на двумерном экране вы знаете?