Задания Оценки Ведомость Материалы

Ведомость и материалы для обучения

Все памятки, материалы и ссылки отныне находятся в разделе "материалы".

Почта преподавателя: valeriy.fedotov [...] gmail.com

Дополнительные занятия проходят по понедельникам с 15:15 до 17:00 и по четвергам с 14:15 по 17:00.

Лекции по мере записи выкладываются здесь.

Варианты прошедшей диагностики

Некоторые из вас просили меня выложить варианты, чтобы просто порешать вторую часть дома.

Вариант 1

Вариант 2

Результаты диагностик

Мартовская: http://programming1189.ru/files/sc2013/Forma_IN11_27022015.pdf

Апрельская: http://programming1189.ru/files/sc2013/Forma_IN11_01042015.pdf

Задание 44, системы логических уравнений

http://kpolyakov.spb.ru/download/ege23.doc Нужно прочитать первые 6 страниц этого пособия и решить задания 52, 53, 61, 65, 74. Задания находятся в конце документа.

Экзаменационные задания

Внимание. Можно предлагать мне задания, которые были бы вам интересны, если я соглашусь (это зависит от многих факторов), будете делать его.

Список в процессе наполнения, обновление от 27 марта:

PyQt, работа с графикой:

PyQt:

Физика:

Игры (PyQt и графика):

Текстовые игры:

Работа с сетью:

Прикладные библиотеки:

Интерпретаторы:

Утилиты:

Сайты:

Для энтузиастов:

Задание 43, метод наименьших квадратов

Задание 42, миниблог

Написать простейший блог. В блоге должно быть две страницы:

Cсылка на архив c проектом сайта в формате zip

Cсылка на архив c проектом сайта в формате .tar.gz (с сохранением атрибутов исполняемых файлов для UNIX).

Тот же самый сайт с примером обработки GET-запросов.

Задание 41, простейший скрипт CGI

Простейшая страница, написанная на уроке, с запускалкой вёб-сервера

После запуска вёб-сервера надо открыть ссылку http://localhost:8000/cgi-bin/script.py

Задание заключается в том, чтобы страница, аналогичная той, что сделана в предыдущем задании, генерировалась CGI-скриптом и отдавалась через сервер. То есть надо немного переписать скрипт.

Задание 40, генерация страницы блога

HTML-код документа, данного на уроке

А так этот пример отображается в браузере

http://htmlbook.ru/samhtml/vvedenie-v-html -- краткий самоучитель по html, который можно освоить за пару вечеров.

Задание заключается в том, что нужно написать скрипт, генерирующий .html-файл со страницей блога по набору текстовых файлов.

Сначала программа открывает файл info.txt для того, чтобы узнать имена текстовых файлов, по которым будет генерироваться html-страница.

Пример содержания info.txt

1.txt
2.txt
44.txt

Соответственно, для такого содержания info.txt html-страница будет генерироваться по трём этим файлам.

Файлы могут быть двух типов: с текстом и с таблицей. Если на первой строчке вашего файла написано слово text, то на следующей идёт название записи в блоге, а на всех остальных текст записи. Если на первой строке идёт слово table, то на второй идёт название таблицы, а на всех остальных строчках идут значения полей таблицы, разделённые запятыми.

Пример:

text
Заголовок
Много текста 1.
Много текста 2.
Много текста 3.

Ещё пример:

table
Мегатаблица.
Колонка 1,Колонка 2
1,2
3,4
5,6

Подготовка к ЕГЭ

Мы посвятим подготовке к ЕГЭ четвёртую четверть, но, если не терпится поботать, то самые лучшие материалы для ЕГЭ по информатике лежат на сайте

http://kpolyakov.spb.ru/school/ege.htm

Задание 39

Написать простую игру с использованием PyQt4. Варианты:

Результаты пробника ЕГЭ

Я просто оставлю здесь ссылку без дальнейших комментариев.

Критерии проверки третьей части.

Задание 38, планета и спутник

Написать программу, рисующую движение спутника вокруг планеты. Расчёт выполнить двумя методами: Эйлера и Эйлера-Кромера.

Формулы для расчётов можно посмотреть здесь (пока в тетради, в понедельник вечером будет ссылка).

Дополнительно к простому рисованию траектории, можно реализовать анимацию движения спутника, например, с помощью небольшого движущегося кружка (см. пример).

Пример программы, которая печатает события мышки и клавиатуры.

Пример анимации гармонического осциллятора

Формулы и пояснения к заданию.

Задание 37, множество Мандельброта

Нарисовать множество Мандельброта.

Создать окно размером 300 на 200 пикселей, в нём нём сопоставить каждому пикселю точку \(c = x + i y\), где \(x \in [-2, 1]\), \(y \in [-1, 1]\).

Точка c из этой области считается принадлежащей множеству Мандельброта, если ограничена последовательность \[ z_{n+1} = z^{2}_{n} + c, \quad z_0 = 0. \] Грубо можно считать такую последовательность ограниченной, если вычислить, допустим, 15-ую точку, и посмотреть, что она не очень далеко отошла от начала координат. То есть, если \(\|z_{15}\| < 2\), точка \(с\) принадлежит фракталу.

При достижении чего-то похожего на правильный рисунок, можно увеличивать размер окна и номер члена последовательности, по которому определяется принадлежность точки множеству Мандельброта.

Интересующиеся могут прочитать про похожий фрактал, множество Жюлиа.

P.S. Комплексные числа используйте стандартные, то есть complex(x, y), где x -- действительная часть, а y -- мнимая. Они работают намного быстрее ваших собственных из задания 36.

Информация по PyQt4

Пример 1.

Пример 2.

Пример 3.

Пример 4.

Пример 5.

Пример c циферблатом.

Все примеры, кроме примера с циферблатом, взяты с сайта http://zetcode.com/tutorials/pyqt4/ . Перевод введения в PyQt4, написанного на этом сайте, выполнен энтузиастами здесь , так что если что-то непонятно в лекциях, читайте этот перевод.

Ссылки для скачивания PyQt4:

Задание 36

Написать собственный класс, реализующий комплексное число.

В классе должны быть определены конструктор и арифметические методы __add__, __sub__, __mul__, __div__, __abs__, методы для перевода в строку __str__ и __repr__.

Небольшое напоминание о том, как работают специальные методы. Положим, вы написали класс ComplexNum и его метод __init__ помимо self принимает ещё два аргумента, комплексную и мнимую часть числа:

a = ComplexNum(1, 2)
b = ComplexNum(5, 7)
c = ComplexNum(10, 15)

При наличии в классе специальных методов __add__ и __mul__ арифметическое выражение

x = (a + b) * c

интерпретатор переведёт в форму

x = (a.__add__(b)).__mul__(c)

А при печати результата с помощью

print(x)

функция print заметит наличие спецметода __str__, и распечатает не x, а x.__str__()

P.S. Те кто хочет, могут реализовать возведение в целую степень с помощью метода __pow__ и формулы Муавра.

P.P.S. В питоне есть встроенный тип данных complex, который всё это уже умеет, но его использовать нельзя.

Задание 35, записная книжка не сдаётся

Написать записную книжку с использованием классов. В программе должно быть два класса:

В функции main должен быть только код, реализующий вывод меню и выбор соответствующего метода объекта записной книги для каждого пункта меню.

Задача 34, записная книжка наносит ответный удар

Следует переписать записную книжку таким образом, чтобы пользователь ни при каком неправильном вводе данных не мог вызвать аварийное завершение программы или потерю данных без завершения программы. Дополнительно к этому надо сделать защиту от негативных внешних условий, например от нехватки места на диске, чтобы программа не завершалась в этом случае с потерей данных а продолжала работать и позволяла пересохранить данные в другое место.

Задание 33, словари

  1. Пользователь вводит имя текстового файла, программа считает, сколько раз каждое слово встречается в тексте, потом выводит результат: в алфавитном порядке

  2. Вывести 10 самых разговорчивых персонажей из пьесы hamlet.txt Допускается некоторая погрешность в работе программы, т.к. формат реплик не везде строго соблюдён. Дополнительно можно посчитать величину словарного запаса каждого персонажа.

Задание 32, рекурсивная решалка судоку

Написать программу для решения судоку в случае, когда простым вычёркиванием получить финальное решение не получается.

Пример такого судоку:

38.6.7.95
.........
7..3...8.
..7.35..6
..5...3..
4..86.5..
.9...6..7
.........
65.7.8.21

Псевдокод рекурсивной функции записан в тетради.

Задание 31, решалка судоку

Реализовать решалку судоку на питоне. Считать, что поданное на вход судоку решается вычёркиванием недопустимых вариантов (без перебора гипотез).

Пользователь должен вводить имя текстового файла с судоку, программа должна считывать его и выводить решение. В качестве входного формата можно выбрать запись точек в пустых клетках:

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

Пример судоку, решающегося вычёркиванием вариантов: http://upload.wikimedia.org/wikipedia/commons/f/ff/Sudoku-by-L2G-20050714.svg

Задание 30, работа с файлами

Переписать программу №28 (с записной книжкой) и добавить в неё сохранение и загрузку записной книги из файла.

Переписать программу №27 (работа со строками) так, чтобы программа считывала текст, который она анализирует, из файла и записывала результат анализа так же в файл.

Шпаргалка

Закончил перевод шпаргалки по Python3. Скачать без СМС и регистрации.

Задание 29

Написать программу для перевода выражений в инфиксной (математической) нотации в обратную польскую (постфиксную) нотацию.

Описание алгоритма "сортировочной станции" дано на википедии, если что-либо непонятно, пишите на почту. Алгоритм достаточно прост.

http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C#.D0.9F.D1.80.D0.B5.D0.BE.D0.B1.D1.80.D0.B0.D0.B7.D0.BE.D0.B2.D0.B0.D0.BD.D0.B8.D0.B5_.D0.B8.D0.B7_.D0.B8.D0.BD.D1.84.D0.B8.D0.BA.D1.81.D0.BD.D0.BE.D0.B9_.D0.BD.D0.BE.D1.82.D0.B0.D1.86.D0.B8.D0.B8

Отдельные личности могут дополнительно реализовать упрощение выражений. Как это сделать, написано тут:

http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C#.D0.9E.D0.BF.D1.82.D0.B8.D0.BC.D0.B8.D0.B7.D0.B0.D1.86.D0.B8.D1.8F_.D0.B2.D1.8B.D1.80.D0.B0.D0.B6.D0.B5.D0.BD.D0.B8.D0.B9

Те, кому жизнь кажется пресной, могут прикрутить к этой программе дифференцирование выражений. )

P.S. Ошибся на уроке, запись называется обратной польской нотацией.

Задание 28, записная книжка возвращается

Написать записную книжку на списках. Книжка должна уметь делать то же самое, что и в прошлом году, но без загрузки и сохранения в файл, то есть:

Так же как и раньше, программа должна выводить меню доступных действий и спрашивать пользователя, какое действие ему нужно выполнить, выполнять его, и ждать следующего выбора пользователя.

Задание 27, работа со строками

Программа должна считывать со стандартного ввода строку с помощью функции input() и выводить:

Задание 26, решение уравнений

Решить уравнение \( f(x) = 0 \) методом деления отрезка пополам (пользователь вводит границы отрезка и точность) и методом Ньютона (пользователь вводит начальную точку и точность).

Формула следующего приближения в методе Ньютона выглядит как

$$ x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} $$

Функцию f выбираем произвольно.

Задание 25, экспонента

Вычислить экспоненту в с помощью выражения

$$ \exp(x) = \sum_0^{+\infty} \frac{x^n}{n!} \approx \sum_0^{N_{max}} \frac{x^n}{n!}. $$

\(N_{max}\) можно выбрать равным 10.

Задание 24, калькулятор

Написать калькулятор для вычисления выражений в постфиксной записи.

Результат выражения

5 6 3 - * 2 +

равен 17.

Этапы вычисления:

стек ввод
  5
5 6
5,6 3
5,6,3 '-'
5,3 '*'
15 2
15,2 '+'
17  

Если пользователь правильно ввёл выражение, то в стеке должно остаться одно число, которое и будет ответом.

Задание 23, шифрование

Задание состоит в реализации шифрования одним из двух способов.

Способ 1, перестановка бит

Написать программу для шифрования файлов с помощью перестановки бит. Перестановка для каждого байта одинаковая и задаётся из командной строки. Перестановка вида

57420361

означает, что значение 0-го бита перейдёт в первый бит, 1-го -- в 6-ой, 2-го в 3-ий, 4-го в 0-ой и т.д. Считать, что младший бит имеет индекс 0, а старший индекс 7.

Программа должна принимать данные от пользователя через аргументы командной строки и иметь следующий формат аргументов:

./proga <MODE> <CYPHER> <IN> <OUT>
   <MODE> -- режим работы, encode для шифрования, decode для расшифровки.
   <CYPHER> -- перестановка
   <IN> -- имя входного файла
   <OUT> -- имя выходного (зашифрованного или расшифрованного) файла.

Пример

./proga encode 57420361 secret_data.txt encoded_secret_data.txt

Программа обязательно должна проверять на правильность вводимую пользователем перестановку. В перестановке должны быть только цифры от 0 до 7 включительно, каждая по одному разу, и только они. Если перестановка задана неправильно, то данные будет невозможно расшифровать. Поэтому ваша программа в случае таких некорректных перестановок должна завершаться с ошибкой.

Способ 2, наложение случайной последовательности

Более простой способ. Заключается в генерации случайной последовательности с помощью функции rand() и наложении каждого байта этой последовательности на байты входного файла с помощью исключающего побитового или. Каждый байт результата при этом записывается в выходной файл.

Программа должна принимать в виде аргументов командной строки ключ шифрования, входной файл и выходной файл. Ключом шифрования для данного алгоритма является число для инициализации генератора псевдослучайных чисел.

./proga <KEY> <IN> <OUT>

Пример:

./proga 456 secret_data.txt encoded_secret_data.txt

В данном случае обратного режима для раскодирования быть не должно, так как повторное применение того же алгоритма с тем же ключом должно давать раскодированную информацию. Данный факт следует из тождества

x ^ y ^ y == x

Задание 22, интегралы

Написать программу для численного вычисления определённых интегралов методами Симпсона, средних прямоугольников и левых прямоугольников. Написать программу для подсчёта числа \(\pi\) методом Монте-Карло.

Каждый метод должен быть оформлен как функция, принимающая параметры, которые обрабатывает метод (scanf'ы внутри функций запрещены, так как в этом случае вы не сможете их использовать в более сложной программе, где параметры будут получаться в результате других вычислений, а не в результате ввода).

Формулы:

Шаг \( h = (b - a) / n \)

Метод левых прямоугольников:

$$ S_{mr} = h \left( \sum_{i=0}^{N-1}f(a+ih) \right) $$

Ошибка метода левых прямоугольников:

$$ \left| E \right| \le max_{x \in [a,b]} \left|f'(x)\right| \frac{(b-a)h}{2} \sim h $$

Метод трапеций:

$$ S_{tr} = h \left( f(a) / 2 + \sum_{i=1}^{N-1}f(a+ih) + f(b) / 2 \right) $$

Ошибка метода трапеций:

$$ \left| E \right| \le max_{x \in [a,b]} \left|f''(x)\right| \frac{(b-a)h^2}{12} \sim h^2 $$

Метод средних прямоугольников:

$$ S_{mr} = h \left( \sum_{i=0}^{N-1}f(a+(i+\frac{1}{2})h) \right) $$

Ошибка метода средних прямоугольников:

$$ \left| E \right| \le max_{x \in [a,b]} \left|f''(x)\right| \frac{(b-a)h^2}{24} \sim h^2 $$

Метод Симпсона:

$$ S_{Simpson} = \frac{h}{6} \left( f(a) + 2 \sum_{i=1}^{N-1}f(a+ih) + 4 \sum_{i=0}^{N-1}f(a+(i + \frac{1}{2})h) + f(b) \right) $$

Ошибка метода Симпсона:

$$ \left| E \right| \le max_{x \in [a,b]} \left|f^{(4)}(x)\right| \frac{(b-a)h^4}{2880} \sim h^4 $$

Кроме того, нужно написать программу для вычисления площади единичного круга (то есть, числа \(\pi\) методом Монте-Карло. Формула для вычисления двумерной площади двумерной фигуры методом Монте-Карло:

$$ S_{figure} = S_{region} \frac{N_{hits}}{N_{tries}} $$

\(S_{figure}\) и \(S_{region}\) -- площадь фигуры и площадь области, в которой выбрасываются случайные числа. \(N_{hits}\) и \(N_{tries}\) -- число попаданий и общее число сгенерированных случайных чисел.

Ошибка метода Монте-Карло даётся формулой

$$ \left| E_{MC} \right| \sim \frac{1}{\sqrt{N_{tries}}} $$

Примечание. Желательно (но не обязательно) передавать подынтегральную (математическую) функцию с помощью указателя на (сишную) функцию.

Примечание 2. Ошибки считать не нужно, т.к. их оценка требует некоторых дополнительных знаний, о которых на уроке рассказано не было. Но тем не менее, о наличии неизбежных ошибок у численных методов и об их свойствах надо знать.

Задание 21, записная книжка возвращается

Переписать задание 20 так, чтобы записная книжка превратилась в абстрактный тип данных, то есть, чтобы вся работа с ней шла через функции.

Тип данных и функции для работы с ним должны располагаться в отдельной паре .h и .c-файлов.

Кроме того, нужно написать программу для подcчёта кратностей слов в файле с помощью бинарных деревьев. Такая программа уже разобрана в одной из глав Кернигана и Ритчи.

Задание 20, записная книжка

Требуется написать программу, которая будет вести телефонную книгу. При запуске программа входит в интерактивный режим работы, предоставляя пользователю меню. Пользователь выбирает интересующее его действие, программа это действие выполняет и снова выводит меню. Внутренние структуры данных записной книжки реализуются с помощью массива структур.

Пункты меню.

  1. «Создать новую книгу». Программа освобождает все ресурсы, связанные с текущей телефонной книгой, запрашивает у пользователя значение максимального числа записей и создает новую, пустую книгу.

  2. «Просмотреть содержимое». Программа выводит содержимое всех непустых записей и их полное количество. Каждая запись должна иметь свой уникальный номер по которому ее можно распознать.

  3. «Добавить запись». Программа спрашивает пользователя о имени и телефоне объекта и создает новую запись, если это возможно.

  4. «Удалить запись». Программа требует ввода номера записи, которая будет удалена, и проводит процедуру удаления записи.

  5. «Поиск по имени». Пользователь вводит имя объекта, а программа в ответ выводит все записи, у которых имена объектов совпадают с введенным пользователем.

  6. «Поиск по номеру телефона». То же, что и предыдущий пункт, только критерием поиска является телефон объекта.

  7. «Сохранить книгу в файл». Программа запрашивает у пользователя имя файла и сохраняет текущее содержимое телефонной книги в указанный файл.

  8. «Восстановить книгу из файла». Программа запрашивает у пользователя имя файла и восстанавливает содержимое ранее сохраненной книги. Если восстановление успешно, то все ресурсы, связанные с предыдущей книгой освобождаются. При неудачном восстановлении текущая телефонная книга не уничтожается.

  9. «Выход».

Программа должна быть написана с использованием структур.

Задание 19, раздельная компиляция

Написать программу для решения уравнений методом деления отрезка пополам, методом хорд, методом Ньютона.

Все функции, решающие уравнения, должны находиться в отдельной паре .h- и .c-файлов. Эти функции решения должны принимать указатель на функцию, корень которой они будут искать. Метод хорд и метод деления отрезка пополам принимают по одному указателю, метод Ньютона -- два, на функцию и её производную.

Программа 18, ход конём

Рекурсивный обход доски конём. Конь обходит доску n * n, начиная из клетки (x0, y0). n, x0, y0 вводятся с клавиатуры. Конь должен обойти все клетки доски, побывав в каждой из них только по одному разу.

У вашей рекурсивной функции скорее всего будет две терминальные ветви:

и одна рекурсивная ветвь:

Возможно написать функцию в двух вариантах:

void horses(int n, int k, int *board);

, где n -- размер доски, k -- количество уже заполненных (в данном узле рекурсивного дерева) клеток доски, board -- массив размера n * n, в элементе board[y * n + x] хранится номер хода, на котором конь пришёл в клетку (x, y), или -1, если конь не заходил в эту клетку.

void horses(int n, int k, int *x, int *y);

, где n -- размер доски, k -- количество уже заполненных (в данном узле рекурсивного дерева) клеток доски, x -- массив размера n, в элементе x[i] хранится x-координата i-го хода конём, в элементе y[i] -- хранится y-координата i-го хода конём.

Задание 17

Написать программу для решения уравнений методом деления отрезка пополам и методом хорд.

При решении методом деления отрезка пополам пользователь вводит края отрезка и параметр точности eps, программа выдаёт ответ.

При решении методом хорд пользователь вводит две начальные точки и параметр точности eps. Формулы для метода в тетради, основная формула

$$ c=a-\frac{f(a)(b-a)}{f(b)-f(a)} $$

получена из уравнения хорды

$$ y=f(a)+\frac{f(b)-f(a)}{b-a}(x-a) $$

Задание 16, динамическое выделение памяти

Функция realloc (reallocate memory, перераспределить память), о которой я рассказал на уроке, имеет следующий прототип:

void *realloc(void *old_ptr, size_t new_size);

ptr -- это либо NULL, либо указатель на область памяти, выделенную ранее с помощью функции malloc, calloc или realloc.

new_size -- новый размер куска памяти.

Функция realloc, в зависимости от своих аргументов, может демонстрировать несколько вариантов работы:

  1. Если NULL == old_ptr, то результат аналогичен результату вызова malloc(new_size).

  2. Если new_size меньше текущего размера куска памяти, на который указывает old_ptr, то лишнее место в конце куска памяти будет помечено как свободное. Потом это освобождённое место в памяти может быть выделено при другом вызове одной из функций malloc/calloc/realloc. Функция вернёт old_ptr.

  3. Если new_size равен текущему размеру куска памяти, ничего не произойдёт, и функция вернёт old_ptr.

  4. Если new_size больше текущего размера куска памяти, на который указывает old_ptr, то, если сразу за этим куском памяти есть свободное место, оно будет помечено как выделенное и добавлено к уже имеющейся области памяти. Если такого места нет, будет найден (либо, если нужно, затребован у операционной системы) кусок памяти требуемого размера, и в его начало будет скопировано содержимое старого куска. Вернёт указатель на кусок памяти, в котором можно использовать new_size байт.

Функция realloc во всех случаях возвращает NULL, если ей не удалось выделить память. Если перераспределение памяти произошло успешно, она возвращает указатель на тот кусок памяти, в котором теперь находятся данные (в случае 4 адрес этого куска может изменится). Поэтому обычно эту функцию используют следующим образом:

ptr = realloc(ptr, new_size);
if (NULL == ptr) {
    printf("Can not reallocate memory!\n");
    exit(1);
}

Задание Переписать программу №14 (сортировка слов в файле по алфавиту) так, чтобы она не имела ограничений на размер файла и количество слов в нём.

Задание 15, аргументы командной строки

Написать программу, которая работает с аргументами командной строки. Программа должна принимать следующие ключи и аргументы:

./proga --search pattern str1 ... strN
./proga --split pattern str1 ... strN
./proga --subst pattern substitution str1 ... strN

При передаче ключа --search программа ищет текстовый шаблон pattern в строках str1 ... strN и выводит те из них, в которых шаблон встречается:

./proga --search abc 12abc3 abd abc jabcdef ababab
12abc3
abc
jabcdef

При передаче ключа --split программа "разбивает" строки по шаблону pattern, заменяя его пробелом. При этом, если шаблон встречается в начале или конце строки, его надо просто удалить без замены на пробел.

./proga --split pattern bc abc bcadef abcdef bcabcbbccbc
a
adef
a def
a b c

При передаче ключа --subst программа должна заменять pattern на substitution в каждой из строк.

./proga --subst x AB xyz x abcxxz
AByz
AB
abcABABz

Рекомендуется написать функции, которая будет применять соответствующие операции (поиск, разбиение, замена) к одной из обрабатываемых строк и вызывать их в цикле.

Задание 14, массив указателей

Написать программу, которая спрашивает у пользователя имя файла, открывает его, считывает его в строку в памяти, затем разбивает его на отдельные слова и сортирует их по алфавиту.

Для простоты примем, что:

  1. В файле не более 10000 символов и не более 5000 слов. Таким образом, можно обойтись массивами фиксированной длины. Как увеличивать размер выделенного участка памяти, мы пройдём подзнее.

  2. Сравнение по алфавиту задаётся лексикографическим порядком по номеру символа в кодовой таблице. Именно так сравнивает строки функция strcmp, можно воспользоваться ей.

При выполнении задания лучше заменить символы-разделители (' ', '\t', '\n') на символ конца строки '\0', и тем самым разбить текст файла на самостоятельные строки-слова, сохранив каждую непустую строку в массив строк. Потом надо отсортировать этот массив и вывести результат.

VIII открытая олимпиада школьников по программированию (2013/14)

Началась открытая олимпиада школьников. Кому интересно, можете поучаствовать, чтобы поднять свой уровень владения программированием. Кроме того, это дополнительная возможность потренироваться для тех кто участвует в окружном туре очной олимпиады.

Страница заочной олимпиады

Для тех, кто прошёл на окружной тур очной олимпиады: олимпиада состоится в воскресенье, 1-го декабря.

Официальный разбор школьного тура олимпиады Разбор на питоне, уровень вложенности показывается отступами, а не скобками {}, как в C.

Перед олимпиадами всегда хорошо почитать информацию о динамическом программировании. Общая информация. Более детальный разбор различных аспектов.

Кроме того, желательно посмотреть и порешать олимпиады прошлых лет.

Задание 13, снова указатели

Написать фукнции strcpy, strncpy, strcat, strcmp, memcpy, memset с помощью указателей (вместо массивов).

Фукнция для автоматического тестирования программы, чтобы удостовериться в корректности своих функций и чтобы не нужно было каждый раз вводить тестовые строки с клавиатуры.

Автотестирование написано из расчёта, что ваши функции написаны с префиксом my: mystrcpy, mystrncpy и так далее. Если убрать отовсюду префиксы и протестировать программу со стандартными функциями библиотеки Си, получим на выходе

strcpy test passed
strncpy test #1 passed
strncpy test #2 passed
strcat test passed
strcmp test #1 passed
strcmp test #2 passed
strcmp test #3 passed
strcmp test #3 passed
memcpy test passed
memset test passed

Ваша программа должна работать так же. То есть, не завалить ни один тест.

Чтобы скачать файл для автоматического тестирования в свою домашнюю директорию на сервере, надо выполнить команду

wget http://programming1189.ru/files/sc2013/str_autotest.c

после чего в текущей папке появится файл str_autotest.c

Задание 12, указатели в атаке

Написать программу, которая будет предлагать пользователю на выбор сделать две операции:

  1. Выполнить сортировку трёх пушек по высоте или длине (критерий сортировки выбирает пользователь).

  2. Ввести несколько чисел, но не более некоторого наперёд заданного числа, например, не более 20 штук. И затем вывести среднее арифметическое этих чисел, дисперсию, минимальное и максимальное из них.

Для реализации пункта 1 необходимо написать функцию

void mysort(int sort_type, double *vx1, double *vy1,
            double *vx2, double *vy2,
            double *vx3, double *vy3);

Эта функция должна понимать вектора v1, v2, v3, как вектора снарядов, выпущенных из пушек. Если критерий сортировки sort_type равен 1, надо отсортировать вектора по возрастанию дальности полёта снаряда, если равен 2, то по возрастанию максимальной высоты полёта снаряда. К примеру, после сортировки по дальности, в ячейках памяти, на которые указывают vx1 и vy1, должны лежать компоненты вектора с минимальной дальностью.

Для реализации пункта 2 надо организовать возврат нескольких значений из функции, это можно сделать с помощью указателей следующим образом:

void statistics(int n, double arr[],
                double *average, double *sigma,
                double *minval, double *maxval);

При написании функций обратите внимание на примеры в тетради.

Задание 11, двумерные массивы

Написать программу (или программы) для заполнения массива

  1. Змейкой:

 0  1  2  3  4  5
11 10  9  8  7  6
12 13 14 15 16 17
23 22 21 20 19 18
24 25 26 27 28 29
35 34 33 32 31 30
36 37 38 39 40 41
  1. По спирали:

 0  1  2  3  4  5
21 22 23 24 25  6
20 35 36 37 26  7
19 34 41 38 27  8
18 33 40 39 28  9
17 32 31 30 29 10
16 15 14 13 12 11
  1. Зигзагом:

 0  1  5  6 14 15
 2  4  7 13 16 26
 3  8 12 17 25 27
 9 11 18 24 28 35
10 19 23 29 34 36
20 22 30 33 37 40
21 31 32 38 39 41

Программа для заполнения массива в обычном порядке

Видео про среду разработки Code::Blocks

Здесь будет видео про то, как работать в Code::Blocks. Как только я его запишу...

Задание 10, файловый ввод-вывод

Переписать задачу №5 таким образом, чтобы входной текст брался из файла (его имя вводит пользователь), а результат выводился в другой файл (имя которого также вводит пользователь).

В выходной файл вывести:

Считать что слово -- это последовательность непробельных символов, окружённая одним или несколькими пробельными символами.

Задание 9, работа со строками

Написать следующие функции:

// Скопировать строку src в dest.
void strcpy(char dest[], char src[]);

// Скопировать строку src в dest. В dest будет записано не более
// n байт, даже если src длиннее. Строка-результат в dest в 
// любом случае будет содержать '\0' на конце.
void strncpy(char dest[], char src[], int n);

// Cкопирует содержание строки src в конец строки dest.
// Забота о том, чтобы в dest было достаточно места, лежит на том,
// кто вызывает функцию.
void strcat(char dest[], char src[]);

// То же, что и strcat, но в строке dest будет записано не более
// n символов. n -- число символов, которое будет дописано в конец
// dest, если строка src длиннее n, будет записано (n-1) символов
// и символ конца строки. 
void strncat(char dest[], char src[], int n);

// Сравнивает s1 и s2. Вернёт отрицательное число (любое), если 
// s1 в словаре стоит раньше, чем s2, 0, если содержание s1 и s2
// одинаково, и положительное число, если s2 стояло бы в словаре
// позже, чем s2.
int strcmp(char s1[], char s2[]);

// Аналогично strcmp, но сравнит не более n символов.
int strncmp(char s1[], char s2[], int n);

// Скопирует n байт из src в dest. Не остановится, если встретит
// конец строки.
void memcpy(char dest[], char src[], int n);

// Запишет байт c в n первых байт dest.
void memset(char dest[], char c, int n);

Внимание В описание поведения функции strncat на уроке вкралась весьма досадная неточность, функция ведёт себя так, как указано в тексте выше.

Примечание Не забывайте, что такие функции уже есть в стандартной библиотеке и, чтобы не вызвать конфликт, свои функции надо писать с каким-нибудь префиксом, например, my.

Примечание2 Программа не будет принята без кода, тестирующего функции и выводящего результаты их работы. Его можно написать в main.

Кроме указанных выше функций нужно написать безопасный вариант функции strcat и функцию lower

void strappend(char dest[], char src[], size_t n);

Она должна понимать n как размер массива dest и вести себя так, чтобы никогда не выходить за его пределы и всегда добавлять в конец строки '\0', даже если она усечена.

void lower(char s[]);

Функция должна переводить буквы в верхнем регистры в нижний и оставлять все остальные символы без изменения.

Задание 8, плотная работа с массивом

Программа должна в цикле выводить меню, в котором предлагать следующие действия:

  1. Заполнить все элементы массива новыми значениями, которые введёт пользователь.

  2. Задать новое значение элемента массива. Индекс и новое значение вводит пользователь.

  3. Вывести все элементы массива.

  4. Вывести все элементы массива с чётными индексами.

  5. Вывести все элементы массива с нечётными индексами.

  6. Вывести все чётные элементы массива.

  7. Вывести все нечётные элементы массива.

  8. Найти число в массиве. Пользователь вводит число, программа выводит индекс, по которому такое число хранится. Если такого числа в массиве нет, нужно вывести "Такого числа нет". Если искомых чисел в массиве несколько, вывести меньший из их индексов.

  9. Найти минимум в массиве. Вывести индекс и значение минимума. Если элементов с минимальным значением несколько, вывести самый меньший из их индексов.

  10. Найти максимум в массиве. Вывести индекс и значение максимума. Если элементов с максимальным значением несколько, вывести самый меньший из их индексов.

  11. Отсортировать массив. Использовать сортировку пузырьком или сортировку выбором.

  12. Вставить элемент в массив. Пользователь вводит индекс и значение для вставки. Если до вставки, например, имелся массив из четырёх элементов со значениями

    3 10 43 5
    

    по после вставки элемента 100 по индексу 1 массив должен выглядеть так:

    3 100 10 43
    

    То есть, элементы с индексами 1 и 2 были сдвинуты вправо, а последний элемент при этом был потерян.

  13. Удалить элемент из массива. Пользователь вводит индекс удаляемого элемента. При удалении элемента элементы, идущие после него следует сдвинуть влево, а в последний элемент записать 0. В качестве примера, рассмотрим массив

    3 10 43 5
    

    Если пользователь захочет удалить из него элемент с индексом 1, то должен получиться массив

    3 43 5 0
    
    
  14. При выборе этого пункта меню программа должна завершать свою работу.

Все пункты меню, кроме пункта 14, должны быть оформлены как отдельные функции. Никакая из функций, кроме функции для пункта 1 и функции main, не должна использовать scanf для ввода от пользователя. Весь ввод должна взять на себя функция main, и передавать введённые данные функциям через аргументы. Вывод c помощью printf (или любых других функций) можно делать только в функциях, реализующих пункты 2, 3, 4, 5, 6, 7.

Так как программа разделена на функции, каждую из которых написать легко, она проста, несмотря на большой объём. Как обычно, рекомендую дописывать программу маленькими кусочками по принципу "написал кусок программы, заставил его компилироваться и работать, написал кусок, заставил его компилироваться и работать, и так далее".

И не забудьте, что размер массив должен быть аргументом функции, а иначе получится что функции смогут работать только с массивом одного размера и потеряют универсальность.

Задание 7, ряды функций возращаются

Написать программу для расчёта функций экспонетны, синуса и косинуса с использованием разложения в ряд Тейлора в 0. Использовать формулы из задания 4.

Каждая математическая функция должна быть оформлена в виде функции языка Си и иметь следующую сигнатуру (типы аргументов и тип возвращаемого значения):

double mysin(double x, int N, double eps)
{
  ...
}

Функция должна считать сумму ряда следующим образом:

Задание 6, массив

Пользователь вводит массив из 10 чисел (константу нужно сделать через #define), затем программа выводит

его наоборот), затем выводит его элементы в обычном порядке.

Как обычно, быстрее и проще писать и отлаживать пункты один за другим, чем пытаться написать всё сразу.

Задание 5

Пользователь вводит текст, программа должна подсчитать в нём

Считать словом любую последовательность непробельных символов, разделённую пробельными символами.

Чтобы завершить ввод текста и послать программе EOF, нужно нажать Ctrl+d.

Задание 4, экспонента, синус, косинус

Пользователь вводит число с плавающей точкой x, программа расчитывает значения функций экспонеты, синуса и косинуса для этого x.

Формулы:

\[ exp(x) = \sum_{n=0}^{n=\infty} \frac{x^n}{n!} \]

\[ cos(x) = \sum_{n=0}^{n=\infty} \frac{(-1)^n x^{2n}}{(2n)!} \]

\[ sin(x) = \sum_{n=0}^{n=\infty} \frac{(-1)^n x^{2n+1}}{(2n+1)!} \]

(На уроке в формулах была допущена ошибка, субфакториала в знаменателе нет, только обычный факториал.)

Рекоммендуемый план написания программы:

В дальнейшем, вы сами будете писать программы по частям, самостоятельно разбивая задачу на подзадачи. Но для этой программы я предлагаю придерживаться этого плана.

P.S. Если не видны формулы, включайте JavaScript.

Задание №3, минимумы, максимумы и корни косинуса

Программа должна считывать у пользователя значения концов отрезка a, b и число шагов на этом отрезке N. Затем, двигаясь по отрезку с шагом $$ h = \frac{b-a}{N} $$ программа должна вывести отрезки, на которых у функции cos(x) есть минимумы, максимумы и корни.

Считать, что у функции есть максимум на отрезке [x-h, x+h], если её значение в точке x больше значений в точках x-h и x+h. Дробить отрезок дальше и находить максимум точнее не требуется.

У функции есть корень на отрезке [x, x+h], если она принимает на концах этого отрезка разные знаки.

Оператор логического "и" обозначается в Си как &&

Главная ветвь этого if-a выполнится только тогда, когда верны оба условия.

if (условие1 && условие2) {
    главная ветвь
}

Не забывайте, что программу надо компилировать с ключом -lm для подключения математической библиотеки, иначе компилятор не найдёт функцию cos(x).

Задание на этот урок получилось достаточно сложным, поэтому стараемся написать как можно больше без посторонней помощи, если не получилось всё написать, приходим на урок, либо на дополнительные, и спрашиваем у меня.

Пример работы программы:

Enter a, b, N: 
-0.1 10 101
max at [-0.100000, 0.100000]
root at [1.500000, 1.600000]
min at [3.000000, 3.200000]
root at [4.700000, 4.800000]
max at [6.200000, 6.400000]
root at [7.800000, 7.900000]
min at [9.300000, 9.500000]

Задание 2, факториал

Программа должна считывать с пользовательского ввода целое число, и считать факториал этого числа.

Примечание. Факториал является очень быстро растущей функцией, и уже 13! не помещается в типе int, так что не удивляйтесь отрицательным значениям при больших числах. Можете подумать, почему значение, выводимое программой, считающей факториал в числе int, станет нулевым, начиная с !34.

Задание 1, квадраты и кубы

Написать программу, выводящую таблицу кубов целых чисел от 0 до 100 включительно, кратных 4.