Задачи контрольной по технике программирования на языке Си. Требования к знаниям языка Си - базовый уровень.
- 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+)
- printf, scanf
- 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), такие что


- Вход: 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.
Напишите программу, которая находит частичную сумму ряда

- Вход: N.
- Выход:
. Выведите также число
.
Напишите программу, которая выводит все бинарные слова длины 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)
, которая вычисляет 

-
, если
нечётное число;
-
, если
чётное число.
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 в случайном порядке.
Напишите генератор случайных точек из круга

- Вход: 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: |