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

test1.pdf: Задачи контрольной 2006 года (последнее обновление 2006.11.22)

Теоретические вопросы

Содержание

Теоретические вопросы

Основы работы с файлами и с компилятором

Файлы. Работа с файлами: создание, удаление, редактирование.
Сборка программ из исходных файлов.
- Представление о препроцессинге, компиляции и компоновке.
- Статическое подключение библиотек.
Тем, кто работает под Linux
- команды pwd, ls, mkdir, cd, cat.
- Перенаправление потоков ввода вывода (команды > < |)

Язык Си

Понятие функции, переменой, типа.
Представление о типах
- int, long, float, double, char,
- unsigned int, unsigned char, unsigned long.
Глобальные и локальные переменные. Области видимости переменных.
Операторы структурного программирования
- for (..) { .. }
- if (..) { .. } else { .. }
- while ( .. ) { .. }
- do { .. } while ( .. )
- switch( .. ) { case C1: ...; case C2: ... ; default: ...; }
Бинарные и унарные операторы, тренарный оператор
- Арифметика: + - * / %
- Логические: && || !
- Сравнения: == != < > <= >=
- Присваивания: = += -= .= %= /=
- Тетнарный оператор: (A) ? B : C
Функции
- Объявление, определение и вызов функций. Понятие прототипа функции.
- Рекурсия
Статические массивы.
Указатели. Разименования указателей. Арифметику указателей знать не требуется.
Динамическое выделение памяти: malloc, free.
Массивы указателей. Указатели на указатели.
Явное и неявное приведение типов — базовых и указательных.
Стандартные функции:
- printf, scanf
  - Простейшие варианты использования функций, форматы %u %d %lf %c %s.
- getchar, putchar
- rand, srand (stdlib.h)
- exit
- atoi, atof
- isspace (ctype.h)
- qsort (на 5+)
struct, typedef, sizeof
Директивы
- #define
- #include

Общие замечания

Здесь приведён примерный список тем задач. Каждую задачу можно оформить в нескольких вариантах, с указанием (по возможности)

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

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

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

Как растет время работы программы с ростом размера входных данных?
Каковы предельные значения входных данных (каковы ограничения на входные данные), при которых ваша программа работает верно?
Создайте набор тестовых входных данных (сохраните их в файлах с именами in00.txt in01.txt ... in10.txt) и убедитесь, что для них программа работает верно.

Ответы на теоретические вопросы должны быть даны в комментариях в начале текстов программ.

Список задач на acm.mipt.ru/judge

Максимум PROB:001
Скобочки PROB:008
Пересечение множеств PROB:002
Лишнее число PROB:027
Три квадрата PROB:006
Турнирная таблица PROB:003
Перевернутая башня PROB:051
Числа Фибоначчи (с длинной арифметикой) PROB:009
Сложные скобочки PROB:011
Количество решений уравнения PROB:201

Другие задачи

Задачи на технику

Инвертирование строки.

Вход: строка из символов 0 и 1.
Выход: строка, в которой 0 заменён на 1, а 1 — на 0.

Архимедовы тройки. Найдите все тройки натуральных чисел (a, b, c), такие что $0 < a \le b \le c \le N$ и a^2+b^2=c^2 .

Вход: N, (0 < N < 60).
Выход: Количество троек M, а затем M строчек, в каждой строчке три числа a, b и c, разделённые пробелом.

Перевёртывание строки.

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

Выведите все четырёхзначные числа, сумма цифр которых равна заданному числу N.

Вход: N.
Выход: Искомые четырёхзначные числа — каждое число в отдельной строчке.

Таблица умножения. Напишите программу, которая считывает N и выводит таблицу умножения N x N.

Вход: N.
Выход: N строчек по N чисел в каждой, отформатированных так, что на каждое число отводится 6 мест.

Пересечение множеств. Напишите программу, которая находит пересечение двух введенных множеств целых чисел.

Вход: Две строчки. В каждой строчке дан набор целых чисел по модулю меньше 2^31 разделенных пробелом. В каждой строке могут быть повторения.
Выход: Одна строчка, содержащая числа (без повторений), которые содержаться и в первой и во второй строке. Если пересечение пусто, но выведите слово "Empty".

Сумма квадратов. Напишите программу, которая находит сумму квадратов первых N натуральных чисел.

Вход: N.
Выход: Сумма квадратов чисел 1, 2, ..., N.

Напишите программу, которая находит частичную сумму ряда a_n = 1/n^2 .

Вход: N.
Выход: $S_N=\sum_{i=1}^{N} a_i$ . Выведите также число $\sqrt{S_N\cdot 6}$ .

Напишите программу, которая выводит все бинарные слова длины N.

Вход: N, 1 <= N <= 50.
Выход: слова, в каждой строчке по слову.

Напишите программу, которая выводит все бинарные слова длины N, в которых ровно K единиц

Вход: N, K, 3 <= N <= 50, 0 <= K <= N.
Выход: бинарные слова, в каждой строчке по слову.

Напишите программу, которая считывает N натуральных чисел, и выводит их в том же порядке, исключив нечётные числа.

Напишите программу, которая считывает N натуральных чисел, и выводит их в том же порядке, исключив числа, которые являются степенями тройки. В программе определите функцию int is_power_of_three(int), которая возвращает 1, если аргумент является степенью тройки.

Напишите программу, которая считывает из стандартного потока символы, и печатает их на стандартный поток вывода, и при этом

а) пропускет знаки препинания
б) последовательности подряд идущих пробельных символов (' ', '\t', '\n') заменяет на один пробел
в) большие латниские буквы преобразует в маленькие.
г) пропускает все цифры

Программа должна заканчивать свою работу при достижении конца потока (EOF).

Напишите программу, которая считывает символы из стандартного потока ввода и при достижении конца потока печатает число встретившихся

а) цифр (символы '0', '1', ..., '0'; напишите сами функцию int isdigit(char c), которая возвращает 1, если символ с является цифрой, и 0 — иначе. ;
б) пробельных символов (символы ' ', '\n', '\t'); используйте функцию isspace, объявленную в файле ctype.h.
в) знаков препинания (символы ',', ':', ';', '.', '!', '?');
г) латинских букв (символы 'A', ... 'Z', 'a', ... 'z').

Напишите функцию int word_to_int(char *s), которая строку символов пытается интерпретировать как целое число и возвращает значение этого целого числа. Если запись целого числа некорректна, то функция должна возвращать 0. Функции scanf и atoi изпользовать нельзя.

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

Напишите программу, которая считывает символы из станларного потока ввода и при достижении конца ввода (EOF) выводит количество встретившихся символов '\n'.

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

Вход: набор символов до EOF
Выход: Множество строчек, в каждой из которых указана пара (символ, его частота).

НОД, НОК, делимость

НОД. Напишите функцию НОД: long gcd(long, long).

НОК. Напишите функцию НОК: long lcd(long, long).

Делители. Напишите программу, которая выводит все делители введённого числа.

Вход: N, (1 < N < 2^31)
Выход: M a1 a2 a3 ... aM — число делителей и делители числа N (включая 1 и N).

Функция Эйлера. Для данного числа N найдите число f(N) взаимопростых с ним чисел из множества {1, ..., n-1}.

Вход: N, 0 <= N <= 2^31.
Выход: f(N).

Простое число. На вход поступает натуральное число менее 2^31. Выведите ДА или НЕТ, в зависимости от того, простое оно или нет.

Решето Эратосфена. На вход поступает натуральное число N менее 2^31. Выведите все простые числа от 1 до N. Используйте для этого алгоритм Эратосфена, описанный в учебнике в первом семинаре.

Задачи на вычисление последовательностей и треугольников

Числа Фибоначчи 1. Напишите реализацию итеративного алгоритма вычисления чисел Фибоначчи.

Вход: N
Выход: f(N)

Числа Фибоначчи 2. Напишите реализацию рекурсивного алгоритма вычисления чисел Фибоначчи.

Вход: N
Выход: f(N)

Числа Фибоначчи 3. Найдите последнее число Фибоначчи, представимое типом long. Напишите для этого программу.

Числа Фибоначчи 4 (сложная). Напишите программу, вычисляющую все числа Фибоначчи от f(0) до f(1000).

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

                 1
               1   1
             1   2   1
           1   3   3   1
         1   4   6   4   1
       1   5   10  10   5  1
              ..    ..

Напишите программу, которая вычисляет N-ю строчку треугольника Паскаля.

Вход: N — номер строки треугольника Паскаля. Самая верхняя строка имеет номер 0.
Выход: (N+1) натуральных чисел, разделённых пробелом.

Треугольник Паскаля 2. Обозначим числа в треугольника Паскаля как C(n,k), где n - номер строки, k - номер числа слева. Нумерация n и k начинается с 0. Напишите рекурсивный алгоритм вычисления чисел C(n,k). Оцените как растет время вычисления C(2n,n) с ростом n.

(дополнение 1) Сделайте так, чтобы программа выводила число рекурсивных вызовов, которые произошли во время вычисления C(n,k).
(дополнение 2) Добавьте в программу глобальный массив, в котором будут хранится вычисленные значения. Исправьте рекурсивную функцию так, чтобы она а) сохраняла вычисленные значения в этом глобальном массиве, б) не осуществляла рекурсивный взов, если необходимое значение уже вычислено.

Степень. Напишите рекурсивную функцию double power(double x, int n), которая вычисляет f(x,n)=x^n согласно рекуррентной формуле: x^n=

$x\cdot x^{n-1}$ , если — нечётное число;
$(x\cdot x)^{n/2}$ , если — чётное число.

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

и число вызовов функции power, которые были сделаны во время вычислений. Программа должна завершать свою работу, если пользователь введёт что-нибудь отличное от пары чисел, соответствующих форматам "%lf" и "%d" функции scanf.

Задачи на системы счисления

B2_to_B10. Напишите программу, которая переводит числа из двоичной системы в десятичную

Вход: слово из алфавита B={0,1} длины менее 32 — двоичная запись числа N.
Выход: десятичная запись числа N.

B10_to_B2. Напишите программу, которая переводит числа из десятичной в двоичную.

Вход: натуральное число менее 2^31.
Выход: двоичное представление числа — слово в алфавите B={0,1}.

Число единиц. Напишите программу, которая определяет число единиц в двоичной записи введенного числа

Вход: Натуральное число N (десятичная запись), 0 <= N <= 2^31.
Выход: Число единиц в двоичной записи.

Сумма степеней двойки. Напишите программу, которая для данного натурального числа N предъявляет его разложение на сумму неповторяющихся степеней двойки.

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

B16_to_B8. Напишите программу, которая для данного 16-чного представления натурального числа выводит его 8-чное представление.

Вход: слово в алфавите B={0,..9, a,b,c,d,e,f}. Длина слова менее 100 букв.
Вход: слово в алфавите B={0,..7}.

B8_to_B16. Напишите программу, которая для данного 8-чного представления натурального числа выводит его 16-чное представление.

Вход: слово в алфавите B={0, .., 7}. Длина слова менее 100 букв.
Вход: слово в алфавите B={0, .., 9, a, b, c, d, e, f}.

B2_to_B16. Напишите программу, которая для данного 2-чного представления натурального числа выводит его 16-чное представление.

Вход: слово в алфавите B={0, 1}. Длина слова менее 100 букв.
Вход: слово в алфавите B={0, .., 9, a, b, c, d, e, f}.

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

Вход: две строки содержащие двоичные слова дины менее 100 — двоичные представления чисел A и B.
Выход: двоичная запись числа A+B.

Задачи на генерацию случайных чисел

Сгенерируйте N случайных натуральных чисел из диапазона [A,B].

Вход: числа N, A, B.
Выход: В первой строке число N, а во втрой строке — N чисел, разделённых пробелом.

Сгенерируйте случайную N перестановку первых N натуральных чисел.

Вход: N, (1 < N < 100).
Выход: Одна строка, в которой через пробел перечислены числа 1, 2, 3, ..., N в случайном порядке.

Напишите генератор случайных точек из круга X^2+Y^2<1 .

Вход: N, (1 < N < 100).
Выход: N строчек, в каждой из которых дана пара действительных чисел X и Y, разделённых пробелом.

Задачи на типы языка Си

Предъявите внутреннее представление числа 0.00175 типом double. Напишите для этого программу, которая выводит биты переменной double x=0.00175L.

Предъявите внутреннее представление числа -177 типом int. Напишите для этого программу, которая выводит биты переменной int x=-177.

Напишите программу, при выполнении которой происходит переполнение при операции над типом а) double; б) int.

Найдите самую большую степень тройки, представимую типом long. Напишите программу, которая находит это число, и по коду которой можно судить о правильности ответа.

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

Выведите символы, у которых ASCII коды равны 50, 51, ...., 127.

Неотклассифицированные задачи

Напишите программу, которая решает квадратное уравнение.

Вход: действительные числа a, b, c, разделённые пробелом.
Выход: Слово "None" или или два действительных числа (возможно одинаковых), которые являются корнями уравнения . Корни должны быть выведены с точностью до 10-го знака.

На вход поступает сначала число N, а затем N целых чисел менее 2000000.

а) Выведите введённые N чисел в порядке возрастания
б) Выведите введённые N чисел в порядке возрастания, удалив при этом дубликаты.

Форматы входа и выхода:

Вход: В первой строчке число N. Во второй строчке — N чисел, разделённых пробелом.
Выход: Одна строка, содержащая N чисел, разделенных пробелом.

Напишите программу, которая определяет правильность введённой скобочной структуры (PROB:008). При решении задачи нельзя использовать массивы.

Вход: Одна строка, содержащая символы '(' и ')'.
Выход: YES или NO.

Info.CommonWebForm
Type:	Другое
Stuff:	Other
Date:
ID:
Importance:	Medium
Author:	Ворожцов Артем
Summary:

Attachment	Action	Size	Date	Who	Comment
solutions.zip	manage	12.5 K	22 Nov 2006 - 20:34	ArtemVoroztsov	Решения задач контрольной
test1.pdf	manage	194.2 K	22 Nov 2006 - 20:48	ArtemVoroztsov	Задачи контрольной