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

19.04.2007, задача 26: раздельная компиляция

Требуется разделить программу «Сортировки-2» на два исходных файла: main.c и lib.c. В main.c будет содержаться функция main(), которая должна осуществлять диалог с пользователем и вызывать функции сортировки, которые содержатся в файле lib.c. Прототипы функций, содержащихся в файлу lib.c должны быть объявлены в main.c.

lib.c дожен экспортировать наружу только необходимые функции. Если, например, внутри него есть вспомогательная функция swap(), которая используется только внутри этого файла, то она должна быть объявлена таким образом, чтобы её было невозможно вызвать из какого-то другого файла (в нашем случае — из main.c).

12.04.2007, задача 25: XOR-шифрование

Требуется написать программу, шифрующую/расшифровывающую файл, используя битовые операции. Файл представляется как поток битов некоторой длины (кратной восьми). Также существует пароль, из которого получается другой поток битов такой же длины, как и файл. Делается это "приставлением" пароля к самому себе некоторое количество раз, пока длина получившегося потока не станет большей либо равной длине файлового потока. Зашифрование производится применением операции XOR к паре битовых потоков. Операцию расшифрования нужно придумать самому.

Небольшая иллюстрация метода получения второго потока из пароля: пусть содержимое файла равняется «This is a test» и пользователь ввел пароль «secret». Тогда пара битовых потоков будет выглядеть так:

Поток 1: This is a test
Поток 2: secretsecretse

Программа принимает три аргумента командной строки:

строку «crypt», что означает режим шифрования, или строку «decrypt», что означает режим расшифрования;
имя исходного файла;
имя выходного файла, в который будет записываться результат операции.

Приглашение ко вводу пароля выводится программой после ее запуска и пользователь вводит свой пароль с клавиатуры.

12.04.2007, задача 24: сортировки-2

В программу «Сортировки» требуется добавить метод сортировки вставкой.

05.04.2007, задача 23: телефонная книга #2 с сортировкой

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

05.04.2007, задача 22: сортировки

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

22.03.2007, задача 21: телефонная книга #2

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

Пункты меню.

«Создать новую книгу». Программа освобождает все ресурсы, связанные с текущей телефонной книгой и создает новую, девственно чистую книгу.
«Просмотреть содержимое». Программа выводит содержимое всех непустых записей и их полное количество. Каждая запись должна иметь свой уникальный номер по которому ее можно распознать.
«Добавить запись». Программа спрашивает пользователя о имени и телефоне объекта, а также о номере записи, после которой нужно вставить создаваемую запись. Если все параметры хороши, то делается попытка создания новой записи.
«Удалить запись». Программа требует ввода номера записи, которая будет удалена, и проводит процедуру удаления записи.
«Поиск по имени». Пользователь вводит имя объекта, а программа в ответ выводит все записи, у которых имена объектов совпадают с введенным пользователем.
«Поиск по номеру телефона». То же, что и предыдущий пункт, только сритерием поиска является телефон объекта.
«Сохранить книгу в файл». Программа запрашивает у пользователя имя файла и сохраняет текущее содержимое телефонной книги в указанный файл.
«Восстановить книгу из файла». Программа запрашивает у пользователя имя файла и восстанавливает содержимое ранее сохраненной книги. Если восстановление успешно, то все ресурсы, связанные с предыдущей книгой освобождаются. При неудачном восстановлении текущая телефонная книга не уничтожается.
«Выход». Угадайте сами…

15.03.2007, задача 20: телефонная книга #1

Пункты меню.

«Создать новую книгу». Программа освобождает все ресурсы, связанные с текущей телефонной книгой, запрашивает у пользователя значение максимального числа записей и создает новую, девственно чистую книгу.
«Просмотреть содержимое». Программа выводит содержимое всех непустых записей и их полное количество. Каждая запись должна иметь свой уникальный номер по которому ее можно распознать.
«Добавить запись». Программа спрашивает пользователя о имени и телефоне объекта и создает новую запись, если это возможно.
«Удалить запись». Программа требует ввода номера записи, которая будет удалена, и проводит процедуру удаления записи.
«Поиск по имени». Пользователь вводит имя объекта, а программа в ответ выводит все записи, у которых имена объектов совпадают с введенным пользователем.
«Поиск по номеру телефона». То же, что и предыдущий пункт, только сритерием поиска является телефон объекта.
«Сохранить книгу в файл». Программа запрашивает у пользователя имя файла и сохраняет текущее содержимое телефонной книги в указанный файл.
«Восстановить книгу из файла». Программа запрашивает у пользователя имя файла и восстанавливает содержимое ранее сохраненной книги. Если восстановление успешно, то все ресурсы, связанные с предыдущей книгой освобождаются. При неудачном восстановлении текущая телефонная книга не уничтожается.
«Выход». Угадайте сами…

01.03.2007, задача 19: подсчет слов или строк

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

Обратите внимание: исходный текст программы един. Важно то, как называется исполняемый файл программы.

22.02.2007, задача 18: размер файлов

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

08.02.2007, задача 17: вояж коня

Требуется написать рекурсивную программу поиска всех возможных вариантов обхода конем шахматной доски размером MxN клеток. Конь начинает с произвольной, но фиксированной точки и должен побывать в каждой точке доски один и только один раз. Программа должна выводить все варианты и их количество на экран. Будет очень хорошо, если числа M и N будут задаваться с клавиатуры.

08.02.2007, задача 16: ферзиное гнездо

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

01.02.2007, задача 15: числа Фибоначчи

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

25.01.2007, задача 14: подарок от Романа Игоревича

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

int multidim(int *array, int *dimensions, int *indices, int ndim);

Первый аргумент — это указатель на кусок памяти, который будет рассматриваться как многомерный массив с «ndim» индексами. Массив «dimensions» содержит размерности каждого из индексов, а массив «indices» — индексы произвольного элемента.

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

18.01.2007, задача 13: точки на плоскости

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

по возрастанию x-координаты,
по убыванию x-координаты,
по возрастанию y-координаты,
по убыванию y-координаты,
по возрастанию расстояния от произвольной точки плоскости,
по убыванию расстояния от произвольной точки плоскости.

В последних двух вариантах координаты произвольной точки вводятся каждый раз заново.

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

14.12.2006, задача 12: строковые функции

Нужно реализовать пять стандартных функций для работами с символами и ASCIIZ-строками: strlen(), strcpy(), strncpy(), tolower(), toupper(). Функции должны корректно обрабатывать символы из первой половины таблицы ASCII. Сама программа должна содержать меню, в котором можно выбирать демонстрацию одной из пяти функций или завершение работы.

14.12.2006, задача 11: наименьшее общее кратное

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

07.12.2006, задача 10: операции со строками

Требуется написать программу, которая в цикле читает вводимую с клавиатуры строку. Если строка совпадает со строкой «exit» (регистр букв не учитывается), то программа завершается. В противном случае, программа

печатает на экран длину введенной строки,
копирует содержимое строки в другой массив,
распечатывает содержимое «другого» массива,
переходит на следующую итерацию цикла.

Разрешено использовать следующие стандартные функции: printf(), scanf(), strlen() и strncpy().

30.11.2006, задача 9: существительные после числительных

Как известно, в русском языке некоторые существительные, употребляемые после числительных, изменяют свою словарную форму. Сравните, например, «одно яблоко» и «пятнадцать яблок».

Требуется написать программу, которая принимает к клавиатуры целое число и печатает на экран результат склонения избранного автором программы существительного. После этого программа завершается. Существительное должно быть склоняемым.

23.11.2006, задача 8: заполнение массивов

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

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

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

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

23.11.2006, задача 7: размеры встроеных типов

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

16.11.2006, задача 6: обращение массива

Обратить порядок следования чисел в одномерном массиве, не пользуясь никакими дополнительными массивами. Размерность массива задается глобальной константой. Массив инициализируется пользователем с клавиатуры поэлементно.

09.11.2006, задача 5: простой калькулятор

Реализовать простой калькулятор: на ввод программы в цикле подаются строки типа «число[пробел]{+,−,*,/}[пробел]число». Квадратные скобки означают необязательность содержащегося в них объекта, фигурные скобки — выбор одного из вариантов, перечисленных через запятую. После ввода строки калькулятор должен вывести результат или сообщение об ошибке. В случае неправильного ввода программа не должна завершаться. Выход из программы производится при вводе выражения «0[пробел]+[пробел]0».

26.10.2006, задача 4: ряд Тейлора для экспоненты

Оценка сходимости ряда для экспоненты. Необходимо при заданных значениях x и точности «эпсилон» найти первое N, при котором выполняется неравенство

$|Sum_{k=0}^N x^k/k! - exp(x)| < epsilon$

Сумма в неравенстве называется рядом Тейлора для экспоненты в окрестности точки x = 0. Поэкспериментируйте с различными значениями входных параметров, но не берите x слишком большим по-сравнению с единицей.

26.10.2006, задача 3: вычисление факториала

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

26.10.2006, задача 2: нахождение x^k

Необходимо возвести все целые числа от единицы до N в степень k и вывести результаты в виде таблицы. Параметры N и k задаются при компиляции.

28.09.2006, задача 1: стороны треугольника

Даны три произвольных рациональных числа. Необходимо выяснить, могут ли они являться сторонами треугольника и при ответе «Да, да, конечно могут!» классифицировать треугольник как остро-, прямо- или тупоугольный.

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

Первая группа

Для чего нужен центральный процессор?

Вторая группа

Для чего нужны шины и контроллеры?

Третья группа

Чта такое разрядность шины памяти и как преодолеть предел в 4 Gb физической памяти для 32-х битной архитектуры процессора?