На этом сайте выкладывается информация для студентов группы 603Б Высшего колледжа информатики НГУ по предмету «методы программирования». В рамках курса студентам читаются лекции (1 пара в неделю), проводятся семинары (1 пара раз в две недели) и практические занятия в терминальном класса (1 пара в неделю). В конце семестра студенты сдают зачёт по результатам выполнения практических заданий и экзамен по теории. Данный сайт призван помочь им в этом непростом деле.
Посещаемость и результаты «пятиминуток»: html
Вопросы к экзамену: doc.
Текущие результаты: html
Вы можете ознакомиться с предварительным списком практических заданий. Сроки сдачи и формулировки будут уточняться в течение семестра.
Задание 1а. Простые числа. Необходимо вывести на экран все простые
числа в интервале от 2 до 100.
Срок сдачи на 5: 15-17 февраля.
Задание 1б. Решето Эратосфена. То же самое, но необходимо реализовать
«решето Эратосфена» при помощи массива.
Срок сдачи на 5: 22-24 февраля.
Задание 2. Треугольник Паскаля. Вывести на экран первые N строк треугольника Паскаля, каждый элемент которого равен сумме числа, стоящего над ним, и числа, стоящего над его левым соседом (при этом считается, что вся плоскость вне треугольника заполнена нулями). Программа должна использовать только один одномерный массив длины N. Вывод программы должен выглядеть примерно так:
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
Для вывода чисел с фиксированной длиной (например, 2 цифры) можно использовать %2d в
функции printf.
Срок сдачи на 5: 1-3 марта.
Задание 3. Строки. Дана строка, состоящая из цифр, точек и прочих символов,
например, "ab134def43.5gh7". Вычислить сумму чисел строки
(т. е. в данном случае ответ 184.5). Считать, что числа заданы корректно, т. е. не встречается,
например, последовательности "13.4.6".
Срок сдачи на 5: 15-17 марта.
Задание 4. Системы счисления. Задание состоит из трёх частей.
float from_b(char *number, int b);
вычисляющую значение вещественного числа по его b-ичной записи в строке number,
т. е. переводящую число number из b-ичной в 10-ю систему счисления.void to_b(float number, int b, char *result);
вычисляющую запись вещественного числа number в b-ичной системе счисления
(целая часть и несколько первых цифр после запятой).Задание 5. Перестановки. Необходимо вывести все перестановки множества {1, ..., N} в файл output.txt
двумя способами.
Задание 6. Бинарный поиск. Дан упорядоченный по возрастанию массив чисел длины N.
Определить, встречается ли в нём число k.
Срок сдачи на 5: 26-28 апреля.
Задание 7. Алгоритм Бойера-Мура. Даны строки s и t. Определить, встречается ли t
в строке s, при помощи алгоритма Бойера-Мура.
Срок сдачи на 5: 10-12 мая.
Задание 8. Сортировки. Задание состоит из двух частей.
Посещаемость и сданные домашние задания: html
Все домашние задания, данные на семинарах, необходимо сдавать на следующем семинаре на листочках.
Список тем проведённых семинаров и домашних заданий:
(информация о семинаре появляется после того, как он прошёл в обеих подгруппах)
Семинар 1 (10, 17 февраля): итеративные и рекурсивные алгоритмы. Факториал, решение
уравнения f(x) = 0 на [a, b] с возрастающей функцией f, чтение натурального числа при помощи
getchar(), рекурсивный «разворот» ввода.
Домашнее задание: написать программу, выводящую N-е число Фибоначчи, двумя способами:
при помощи цикла и рекурсивно.
Семинар 2 (24 февраля, 3 марта): передача одномерных массивов в функцию и работа со строками.
Основная идея: функция не может определить размер фактически переданного ей массива, поэтому его необходимо
также передавать. Функции, принимающие строки, не требуют размер, т. к. конец строки можно определить,
найдя в ней завершающий нуль.
Домашнее задание: реализовать функцию strrev, принимающую строку и «разворачивающую»
её. Заголовок функции: void strrev(char *s).
Семинар 3 (10, 17 марта): ветвящаяся рекурсия. Разбор задач первой контрольной работы,
задача на работу с массивами (поиск количества максимумов), а затем ветвящаяся рекурсия:
размен данной суммы монетами заданного достоинства.
Домашнее задание: придумать алгоритм вывода всех возможных разложений числа на множители.
Семинар 4 (24, 31 марта): системы счисления. Разбор различных задач на системы счисления.
Домашнее задание: выписать таблицу сложения и таблицу умножения для 4-й системы счисления, решить два примера
(сложение и умножение любых четырёхзначых чиселв 4-й системе, ответ также дать в 4-й системе).
Семинар 5 (7, 14 апреля): перестановки. Разбор алгоритмов генерации перестановок.
Домашнее задание: написать функцию генерации таблицы инверсий по данной перестановке.
Александр Геннадьевич Фенстер
fenster@fenster.name