Задачи для Вероники
Текст задачи — ссылка на страницу задачи в тестирующей системе. Под ним — мой комментарий. Файлы .cpp можно отправлять мне на почту max@sinyakov.com. Теперь мы храним домашние задания на гитхабе.
Какой вообще план. Разберем вузовскую программу: асимптотика (бинарный поиск, сортировки), структуры (список, бинарное дерево), классы (стек, свой вектор), шаблоны, стандартные контейнеры (итераторы, лямбды). Напишем утилиты командной строки: умножение произвольных матриц и сжатие методом Хаффмана.
Задание на 26.08.17
Требуется определить, является ли данный год високосным. (Напомним, что год является високосным, если его номер кратен 4, но не кратен 100, а также если он кратен 400.)
Простая задача на условие, чтобы разобраться с тестирующей системой.
Наименьшее общее кратное (НОК) двух натуральных чисел – это наименьшее число, которое делится нацело на оба исходных числа. Напишите программу, которая вычисляет НОК двух чисел. Используйте функцию.
Чтобы найти НОК, нужно сначала найти НОД, а потом использовать формулу, которая их связывает.
Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких последних цифр, тоже является простым. Например, число 733 -– гиперпростое, так как и оно само, и числа 73 и 7 -– простые. Напишите программу, которая находит все гиперпростые числа в заданном диапазоне. Используйте функции.
Написать две функции: является ли число простым и является ли число гиперпростым.
Дан массив, состоящий из целых чисел. Напишите программу, которая подсчитывает количество положительных чисел среди элементов массива.
Напишите программу, которая находит в массиве самую длинную цепочку одинаковых элементов. Программа должна вывести значение элемента, который встречается наибольшее число раз подряд, и длину этой цепочки. Если в массиве есть несколько цепочек максимальной длины, нужно вывести данные по первой из них.
Напишите программу, которая выбирает из массива все простые числа в другой массив. Если в исходном массиве нет простых чисел, программа должна вывести число 0.
Тут используются динамические массивы. Также можно использовать функцию определения простого числа из предыдущей задачи.
Задание на 02.09.17
Решение некоторых задач с занятия: таблица умножения, НОД и НОК, гиперпростые числа.
Напишите программу, которая переставляет элементы массива в обратном порядке без использования дополнительного массива. Программа должна считать массив, поменять порядок его элементов, затем вывести результат (просто вывести элементы массива в обратном порядке – недостаточно!)
Попробуйте также решить без с помощью арифметики указателей (не используя []). И *(a+i) тоже не используя (т.к. мы обсудили, что это одно и то же).
Напишите функцию order(x, y, z); - меняет значения в x, y, z так, чтобы они шли по возрастанию, x <= y <= z. Например: int a=5, b=1; c=3; order(a, b, c); ... теперь a==1, b==3, c==5
Этой задачи нет на сайте, но тут и проверять особо нечего.
Дана последовательность из N (1 ≤ N ≤ 100000) целых чисел и число K (|K| ≤ 100000). Сдвинуть всю последовательность (сдвиг - циклический) на |K| элементов вправо, если K – положительное и влево, если отрицательное.
Проверьте, является ли двумерный массив симметричным относительно главной диагонали. Главная диагональ — та, которая идёт из левого верхнего угла двумерного массива в правый нижний.
Дано число n. Создайте массив A[2*n+1][2*n+1] и заполните его по спирали, начиная с числа 0 в центральной клетке A[n+1][n+1]. Спираль выходит вверх, далее закручивается против часовой стрелки.
Если застрянете на этой задаче, то можно пропустить. Но вообще, ничего сверхсложного. Это задача из тех, что дают на собеседованиях написать маркером на доске, на понимание алгоритмов.
Требуется отсортировать массив по неубыванию методом "выбор максимума".
Видимо, имеется в виду эта сортировка (только у нас сортировка по невозрастанию вместо неубывания). Там простой алгоритм и даже есть примеры реализации. Функцию swap напишите, пожалуйста, отдельно.
Задание на 09.09.17
Решение некоторых задач с занятия: реверс массива через указатели, сортирова массива из структур (точек). Про рекурсию и время работы программы добавлю чуть позже.
Среди исходных точек найдите три, образующие треугольник максимальной площади. Выведите данную площадь. Создайте структуру Point и сохраните исходные данные в массиве структур Point.
Нужно написать дополнительные функции: расстояние между двумя точками, площадь треугольника по трем сторонам.
Требуется отсортировать массив по неубыванию методом "пузырька".
Это еще одна простая сортировка, в википедии есть алгоритм и пример работы.
Напишите программу, которая сортирует натуральные числа в массиве по убыванию суммы цифр десятичной записи числа. При равенстве сумм цифр числа должны сохранить исходный порядок.
Можно использовать стандартную сортировку или написать свою.
Тут была задача про бинарный поиск.
Задание на 16.09.17
Реализовать класс List с такими методами (для начала).