This shows you the differences between two versions of the page.
courses:programming:extra_tasks [2021/09/27 11:07] pro100kot |
courses:programming:extra_tasks [2022/12/10 09:08] |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== Дополнительные задачи по программированию ====== | ||
- | |||
- | ===== Легенда ===== | ||
- | |||
- | * <color green>3</color> -- простые задачи | ||
- | * <color blue>4</color> -- задачи средней сложности | ||
- | * <color red>5</color> -- более сложные задачи | ||
- | |||
- | ===== Задачи ===== | ||
- | |||
- | * <color green>3</color> Написать программу, которая выводит строку "HELLO WORLD!" на консоль. | ||
- | * На вход подаются два целых числа | ||
- | * если первое больше второго, вывести их сумму | ||
- | * если они равны, вывести 0 | ||
- | * если второе больше первого, вывести их произведение. | ||
- | * <color green>3</color> Найти и вывести максимальное число из трех целых чисел (числа вводятся с консоли). | ||
- | * <color green>3</color> Заполнить значениями, введенными с клавиатуры, одномерный массив целых чисел длиной 15 и вывести эти значения на консоль. | ||
- | * <color green>3</color> Заполнить значениями, введенными с клавиатуры, одномерный массив целых чисел длиной 15 и вывести эти значения на консоль в обратном порядке. | ||
- | * <color green>3</color> Найти и вывести максимальное число из 15 целых чисел (числа вводятся с консоли). | ||
- | * <color green>3</color> Найти и вывести первое отрицательное число из 3 введенных целых чисел. | ||
- | * <color green>3</color> Найти и вывести первое отрицательное число из 15 введенных целых чисел. | ||
- | * <color green>3</color> Найти и вывести последнее отрицательное число из 15 введенных целых чисел. | ||
- | * <color green>3</color> Найти и вывести среднее арифметическое 3 введенных целых чисел. | ||
- | * <color green>3</color> Найти и вывести среднее арифметическое 15 введенных целых чисел. | ||
- | * <color green>3</color> Найти и вывести индекс первого символа пробела из 3 введенных символов (пробел вводится обязательно). | ||
- | * <color green>3</color> Найти и вывести индекс первого символа пробела из 15 введенных символов (пробел вводится обязательно). | ||
- | * <color green>3</color> Посчитать и вывести количество пробелов в 15 введенных символах. | ||
- | * <color green>3</color> Посчитать и вывести количество пробелов и восклицательных знаков в 15 введенных символах | ||
- | * <color green>3</color> Вывести индексы пробелов в 15 введенных символах, если пробелов в символах не было, вывести символ “-”. | ||
- | * <color green>3</color> Используйте оператор switch. На вход программе подается один из трех символов: -, +, * и два целых числа. Выведите результат операции для первого и второго числа. (Например, на вход поступило '-', 30, 10. Программа должна вывести 20.) | ||
- | * <color green>3</color> На вход программе подается сначала число n, а после - n целых чисел. Требуется определить, упорядоченны ли числа по неубыванию. Вывести "Yes" или "No". Числа для обработки сохранить в массив. | ||
- | * <color green>3</color> На вход программе подается строка, представляющая собой одно слово из латинских букв. Требуется определить, является ли слово палиндромом (одинаково читающееся в обоих направлениях (anna)). Вывести "Yes" или "No". | ||
- | * <color green>3</color> Используйте оператор switch. На вход программе подается целое число меньше 10. Программа должна вывести слово "корова" в правильном падеже. | ||
- | * <color green>3</color> Заполнить двумерный массив нулями и вывести его на консоль. | ||
- | * размера 10x10 | ||
- | * размера 5x10 | ||
- | * размера 10x5 | ||
- | |||
- | |||
- | Задачи на массивы (в задачах следует полагать, что на вход программе сначала подается количество элементов N<=100, а после - N чисел. Массив создавать статически.) | ||
- | * <color green>3</color> Найти разницу между максимальным и минимальным числом в этом массиве. | ||
- | * <color green>3</color> Найти сумму элементов массива, расположенных до минимального элемента | ||
- | * <color green>3</color> Найти сумму элементов массива, расположенных после последнего элемента, равного нулю | ||
- | * <color green>3</color> Найти сумму модулей элементов массива, расположенных после максимального о модулю элемента | ||
- | * <color green>3</color> Найти сумму модулей элементов массива, расположенных после первого элемента, равного нулю | ||
- | * <color green>3</color> Найти произведение элементов массива, расположенных между первым и вторых нулевыми элементами | ||
- | * <color green>3</color> Найти сумму элементов массива, расположенных между первым и последним отрицательными элементами | ||
- | * <color green>3</color> Найти произведение элементов массива, расположенных между максимальным по модулю и минимальным по модулю элементами | ||
- | |||
- | Строки: | ||
- | * <color green>3</color> Определить длину строки, введенной пользователем. | ||
- | * <color blue>4</color> Найти разницу между числом строчных и прописных (заглавных) букв в строке. | ||
- | * <color blue>4</color> Дана строка состоящая из букв и цифр (считается, что больше одной цифры подряд идти не может). Требуется посчитать сумму этих цифр. | ||
- | * <color blue>4</color> Дана строка состоящая из букв и цифр Требуется сформировать и вывести новую строку, состоящую только из этих цифр, разделенных пробелами. | ||
- | * <color blue>4</color> Поменять местами слова в строке, состоящей из двух слов. | ||
- | * <color blue>4</color> На вход программе подается строка, представляющая собой последовательность латинских букв. Требуется определить, является ли строка палиндромом (одинаково читающееся в обоих направлениях (A roza upala na lapu Azora)). Вывести "Yes" или "No". | ||
- | * <color blue>4</color> Добавить в строку пробелы после знаков препинания, если они там отсутствуют. | ||
- | * <color blue>4</color> Требуется в произвольной строке удалить последнее слово, т.е. все символы после последнего пробела в строке. | ||
- | * <color blue>4</color> Найти слово, стоящее в тексте под определенным номером, и вывести его первую букву. | ||
- | * <color blue>4</color> Подсчитать количество слов во введенной пользователем строке. Для упрощения задачи считать, что слова разделяются исключительно одним пробелом, а первый и последний символы строки не являются пробелами. | ||
- | * <color blue>4</color> Во введенной строке удалить все символы между первым и вторым вопросительным знаком. Сами знаки в троке оставить | ||
- | * <color blue>4</color> Дана строка. Определите процентное отношение строчных и прописных букв к общему числу символов в ней. | ||
- | * <color blue>4</color> Написать функцию int mystrlen(char *); вычисляющую длину переданной ей строки | ||
- | |||
- | |||
- | * <color blue>4</color> На вход программе подается число n, х, а после - n целых чисел, являющиеся коэффициентами многочлена степени n. Коэффициенты заданы по убыванию степеней. Треуется вычислить и вывести на экран значение многочлена в точке х. | ||
- | |||
- | **<color red>5</color> Встреча с Римлянами** | ||
- | |||
- | Попав в 500 год до нашей эры, вы столкнулись с необходимостью перевести число, записанное арабскими цифрами в число, записанное [[https://ru.wikipedia.org/wiki/%D0%A0%D0%B8%D0%BC%D1%81%D0%BA%D0%B8%D0%B5_%D1%86%D0%B8%D1%84%D1%80%D1%8B|римскими цифрами]] | ||
- | |||
- | Напишите программу, которая переводит число (<=3000) из арабской записи в римскую. | ||
- | |||
- | Примеры: | ||
- | |||
- | 1994 -> MCMXCIV | ||
- | |||
- | 123 -> CXXIII | ||
- | |||
- | |||
- | |||
- | **<color red>5</color> Часы** | ||
- | |||
- | Представьте обычные цифровые часы, время на которых отображается на 7-ми сегментных индикаторах с учетом ведущего нуля. Например, 9:30 на таких часах отображается так: | ||
- | {{courses:programming:screenshot_from_2017-03-07_11-03-10.png?150|}} | ||
- | |||
- | Числа отображатся следующим образом: | ||
- | |||
- | {{courses:programming:screenshot_from_2017-03-07_11-03-22.png?400|}} | ||
- | |||
- | Требуется написать программу, на вход которой подается целое число n, обозначающее количество зажженных сегментов в отображении некого времени. Програма должна по этому числу востановить время, которое отображается на часах. Время должно быть корректным (подразумевается 24 формат представления времени). Если это невозможно, программа должна вывести "Impossible". Если может быть несколько вариантов корректного времени, вывести любой. | ||
- | |||
- | Примеры: | ||
- | |||
- | Вход: 23 | ||
- | |||
- | Выход: 09:30 | ||
- | |||
- | Вход: 28 | ||
- | |||
- | Выход: Impossible | ||
- | |||
- | Вход: 2 | ||
- | |||
- | Выход: Impossible | ||
- | |||
- | **<color red>5</color> Могила** | ||
- | |||
- | Территория некоторого кладбища имеет ровную прямоугольную форму. На нем (не выходя за его границы) расположена прямоугольная церковь. Требуется определить, хватит ли на кладбище места для прямоугольной могилы? могила может касаться границы кладбища и/или церкви, но не должна перекрывать их. | ||
- | |||
- | На вход программе подаются 10 чисел: | ||
- | |||
- | сначала **x1**, **y1**, **x2**, **y2** - координаты левого нижнего и правого верхнего углов гладбища | ||
- | |||
- | после **x1**, **y1**, **x2**, **y2** - координаты левого нижнего и правого верхнего углов церкви | ||
- | |||
- | а потом **w** и **h** - ширина и высота могилы. Сторона длины **w** должна располагаться вдоль оси OX, а сторона длины **h** - вдоль оси OY | ||
- | |||
- | Программа должна вывести "Yes", если место имеется и "No" в проиивном случае. | ||
- | |||
- | Пример: | ||
- | |||
- | {{courses:programming:screenshot_from_2017-03-07_11-37-39.png?400|}} | ||
- | |||
- | Вход: | ||
- | |||
- | 1 1 11 8 | ||
- | |||
- | 2 3 8 6 | ||
- | |||
- | 3 2 | ||
- | |||
- | Выход: | ||
- | |||
- | Yes | ||
- | |||
- | Вход: | ||
- | |||
- | 1 1 11 8 | ||
- | |||
- | 2 3 8 6 | ||
- | |||
- | 4 3 | ||
- | |||
- | Выход: | ||
- | |||
- | No | ||
- | |||
- | **<color red>5</color> Углы углы углы** | ||
- | |||
- | Даны **n** попарно различных точек на плоскости с целыми координатами до 10^6 по абсолютной величине. Требуется найти среди этих точек две точки **A** и **B** такие, что угол **AOB** минимальный. **O** – центр координат. | ||
- | |||
- | **<color red>5</color> Делим пространство** | ||
- | |||
- | Дан набор прямых линий на плоскости (прямая может задаваться уравнением прямой или с помощью двух точек - на ваш выбор), которые могут пересекаться. Найти количество областей, на которые они разбивают плоскость. | ||
- | |||
- | **<color red>4</color> Задачи на структуры** | ||
- | В задачах подразумевается, что хранения связных данных (данных об одном логическом объекте) будет осуществляться с помощью типа struct. | ||
- | * На вход программе подается число n, а после - n пар <Название журнала> <цена>. Следует полагать, что название не содержит пробельные символы. Требуется сохранить данные в массив и вывести информацию о журналах с ценой выше 100. | ||
- | * На вход программе подается число n, а после - n пар <Название журнала> <цена>. Следует полагать, что название не содержит пробельные символы. Требуется создать и заполнить еще один массив теми журналами, стоимость которых меньше 30 | ||
- | |||
- | |||
- | ===== Линейный односвязный список ===== | ||
- | |||
- | **Структуры: ** | ||
- | Способ представления данных инкапсулирующий в себя данные различных типов. Кратко можно почитать [[https://en.wikipedia.org/wiki/Struct_(C_programming_language)|тут]] либо в какой-нибудь книге в духе "Руководство для начинающих (Шилдт)". Важно понимать, что данные-поля структуры в памяти представляются подряд, в порядке их объявления. | ||
- | |||
- | **Идея:** | ||
- | Идеологически - линейный односвязный список это структура данных, представляющая собой список узлов, каждый их которого хранит какие-то данные и указатель на следующий элемент. Это некая альтернатива массиву, но куда более гибкая: порядок элементов в списке не связан с их расположением в памяти. Это порождает, например, то, что такие операции как поиск и удаление не связаны со сдвигами остальных элементов, однако все операции со списком являются исключительно последовательными - прямой доступ к элементам списка невозможен. Кратко можно почитать [[https://en.wikipedia.org/wiki/Linked_list|тут]]. Либо в какой-нибудь книге по структурам данных. | ||
- | |||
- | **Реализация** | ||
- | Каждый узел линейного односвязного списка хранит в себе данные (которые подразумеваются под фразой "хранится в списке") и указатель на следующий элемент списка. Таким образом, узел списка может иметь вид: | ||
- | <code c node.h> | ||
- | struct node | ||
- | { | ||
- | int data; //полезные данные | ||
- | struct node *next; //указатель на следующий элемент | ||
- | }; | ||
- | </code> | ||
- | Из этого следует то, что для всех операций со списком (в том числе и хранения его) достаточно знать только указатель на его первый элемент. | ||
- | |||
- | **Функции: ** | ||
- | вам предлагается реализовать список и следующий набор функций (не обязательно все) для работы со списком (в списке хранятся целые числа). Не забывайте, что качество превыше количества, поэтому если сложно, то реализовать сколько сможете. Функции приведены в порядке возрастания сложности. В этом же порядке и реализовывать : | ||
- | * Добавление элемента в конец списка (void addTail(struct node *root, int data);) | ||
- | * Посчитать длину списка (int length(struct node *root);) | ||
- | * Получить n-й элемент списка (int getN(struct node *root, int n);) | ||
- | * Добавление элемента после n-го элемента списка (элементы нумеровать с нуля) (int addN(struct node *root, int n, int data); функция должна возвращать номер вставленного элемента и отрицательное число в случае ошибки) | ||
- | * Добавление элемента в начало списка (void addHead(struct node *root, int data);) (сложнее, чем вам кажется) | ||
- | * Подумать как можно реализовать удаление n-го элемента списка. (int remove(struct node *root, int n);) | ||
- | |||
- | ===== Бинарное дерево поиска ===== | ||
- | |||
- | Подробнее, например, [[https://en.wikipedia.org/wiki/Binary_search_tree|тут]] | ||
- | |||
- | <code c treeNode.h> | ||
- | struct node | ||
- | { | ||
- | int data; //полезные данные | ||
- | struct node *left; //указатель на левого потомка | ||
- | struct node *right; //указатель на правого потомка | ||
- | }; | ||
- | </code> | ||
- | |||
- | |||
- | |||
- | **Функции: ** | ||
- | |||
- | Реализуйте следующие функции: | ||
- | * Вставка элемента в дерево | ||
- | * Поиск элемента в дереве | ||
- | * Определение высоты дерева | ||
- | * Вывод элементов дерева в порядке их возрастания (ЛКП обход дерева) | ||
- | * Вывод элементов дерева с отображением структуры. Например: <code>((5)10(15))20((25)30(35))</code> | ||
- | * Удаление всех элементов дерева | ||
- | * Удаление заданного элемента - рекомендую подумать и попробовать реализовать самостоятельно | ||
- | |||
- | Для удобства, рекомендуется использовать отдельную функцию для создания узла: | ||
- | <code c createNode.h> | ||
- | struct node* createNode(int n, struct node *left, struct node *right) | ||
- | { | ||
- | struct node *cur = malloc(sizeof(struct node)); | ||
- | cur->left = left; | ||
- | cur->right = right; | ||
- | cur->data = n; | ||
- | return cur; | ||
- | } | ||
- | </code> | ||
- | |||
- | ===== Пример на обзор txt файлов во вложенных папках ===== | ||
- | |||
- | |||
- | <code c dir-list.c> | ||
- | #include <stdio.h> | ||
- | #include <string.h> | ||
- | |||
- | #include <sys/types.h> | ||
- | #include <dirent.h> | ||
- | |||
- | void printFile(const char *path, const int lvl); | ||
- | |||
- | void dirTraveler(const char *startDir, const int lvl); | ||
- | |||
- | int main() | ||
- | { | ||
- | dirTraveler(".",0); | ||
- | return 0; | ||
- | } | ||
- | |||
- | void dirTraveler(const char *startDir, const int lvl) | ||
- | { | ||
- | char path[1000]; | ||
- | strcpy(path, startDir); | ||
- | |||
- | DIR *dir=opendir(path); | ||
- | if(dir) | ||
- | { | ||
- | struct dirent *de = readdir(dir); | ||
- | while(de) | ||
- | { | ||
- | if(de->d_type == DT_REG && strstr(de->d_name,".txt")) | ||
- | { | ||
- | int path_len = strlen(path); | ||
- | strcat(path, "/"); | ||
- | strcat(path, de->d_name); | ||
- | printFile(path, lvl); | ||
- | path[path_len] = '\0'; | ||
- | } | ||
- | if(de->d_type == DT_DIR && 0!=strcmp(".", de->d_name) && 0!=strcmp("..", de->d_name)) | ||
- | { | ||
- | int path_len = strlen(path); | ||
- | strcat(path, "/"); | ||
- | strcat(path, de->d_name); | ||
- | dirTraveler(path, lvl+1); | ||
- | path[path_len] = '\0'; | ||
- | } | ||
- | de = readdir(dir); | ||
- | } | ||
- | } | ||
- | closedir(dir); | ||
- | } | ||
- | |||
- | void printFile(const char *path, const int lvl) | ||
- | { | ||
- | int i; | ||
- | char s[100]; | ||
- | for(i=0;i<lvl;i++) | ||
- | printf("\t"); | ||
- | printf("%s[\n", path); | ||
- | |||
- | FILE *f = fopen(path, "r"); | ||
- | if(f) | ||
- | { | ||
- | while(fgets(s,sizeof(s)/sizeof(char),f)) | ||
- | { | ||
- | for(i=0;i<lvl+1;i++) | ||
- | printf("\t"); | ||
- | printf("%s",s); | ||
- | } | ||
- | fclose(f); | ||
- | } | ||
- | |||
- | for(i=0;i<lvl;i++) | ||
- | printf("\t"); | ||
- | printf("]\n"); | ||
- | } | ||
- | </code> | ||
- | |||