Методы программирования

Общая информация

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

Задание 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