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

Консультация к ЕГЭ

Пара ссылок для подготовки к ЕГЭ. Во-первых, как все уже знают, лучший ресурс для подготовки к ЕГЭ по информатике -- это http://kpolyakov.spb.ru/school/ege.htm

(так же есть видеоразборы заданий https://www.youtube.com/playlist?list=PLWpxuJBIZRlMCvaI96eyES8gsus4QAm44 , которые рекомендует Лёша Вишняков.)

Если кто-то до сих пор не прорешал демонстрационный вариант по информатике, настоятельно рекомендую это сделать. http://4ege.ru/informatika/4175-demoversiya-ege-po-informatike-2014.html

Вот архив с вариантами заданий, которые мы писали в начале весны, и критериями их проверки ( http://programming1189.ru/files/sc2012/EGE_diagnostics_19032014.zip ). Внимательно читаем критерии проверки, особенно к заданию С3. Большинство из вас на диагностике не расписало словами выигрышные стратегии, и не получило полный балл, несмотря на правильный ответ. Внимательно читаем критерии, чтобы понять, что нужно писать в ответах на часть C.

Решаем самостоятельно задания из Яндекс-ЕГЭ http://ege.yandex.ru/informatics/ (к части из вариантов есть эталонные решения, которые можно просмотреть после того, как решите сами).

Так же для тренировки смотрим задания из книжки для подготовки http://programming1189.ru/files/sc2012/EGE-2014-Ushakov.pdf На консультации я буду разбирать решения части C для 2-го и 6-го вариантов из этой книжки, так что крайне желательно их прорешать ещё до консультации, чтобы понять возможные проблемы в своих методах решения.

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

Начало консультации 6 июня (в пятницу) в 15:30.

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

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

Дополнительные занятия проходят во вторник и среду, с 15:30 до 17:30.

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

Самоподготовка к ЕГЭ

Сайт с подробнейшим разбором всех типов заданий:

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

Видеоразборы заданий:

https://www.youtube.com/playlist?list=PLWpxuJBIZRlMCvaI96eyES8gsus4QAm44

Тренировка по ЕГЭ

Решаем этот вариант, сдаём во вторник. Естественно, решают только те, кто будет сдавать.

Задание 42

Написать блог с многими авторами. Использовать cookie. Для авторов должны быть страницы регистрации и входа в блог. Комментаторов можно оставить анонимными.

Пример работы с POST- и GET-запросами Я уже вывешивал его в предыдущем задании, но рекомендую посмотреть ещё раз.

Диагностика ЕГЭ

Результаты (1 и 3 страница)

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

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

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

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

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

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

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

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

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

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

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

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

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

PyQt:

Физика:

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

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

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

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

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

Утилиты:

Сайты:

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

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

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

Задание 38

Написать программу, моделирующую движение планеты и её спутника вокруг звезды. Звезду считаем тяжёлой и неподвижной. Формулы в тетради.

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

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

Комплект материалов по PyQt4

Перевод нескольких уроков по PyQt4: урок 1, урок 2, урок 3 (к сожалению, здесь рассказано про сигналы и слоты старого стиля, а мы проходили новый стиль), урок 4, урок 5.

Задание 37, задача Кеплера

Написать программу для численного вычисления траектории вращения спутника вокруг планеты. Можно считать планету неподвижной. Нужно реализовать два метода решения дифференциальных уравнений: метод Эйлера и метод Эйлера-Кромера. К ним можно (но не обязательно) добавить метод с перешагиванием, который есть в приложении с формулами.

Формулы. Метод с перешагиванием пока подробно не описан, но в ближайшее время там появится.

Траектории можно рисовать без анимации.

Задание 36, простейшая игра с анимацией

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

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

Программа, анимирующая движение шарика по кругу (ссылка исправлена)

Можно выполнить одно из четырёх заданий:

  1. Игра "Жизнь". Есть поле из M*N клеток, M и N на ваше усмотрение. На поле от шелчка мышью появляется клетка, при щелчке по живой клетке она исчезает. При нажатии пробела на экране отображается следующее поколение клеток, построенно по следующим правилам. Если у пустой клетки 3 живых соседа, в ней зарождается жизнь. Если у клетки 2 или 3 живых соседа, она продолжает жить, иначе она погибает от недостатка общения или его переизбытка. Подробнее на вики

  2. Игра "забей грызуна обратно в нору". Что-то типа такого, но с многократно упрощённой графикой. Можно отличать пустую нору от норы с грызуном просто по цвету.

  3. Змейка. Просто змейка.

  4. Тетрис. Просто тетрис.

Задание 35.

Нарисовать простейший фрактал -- снежинку Коха. Рекомендуется переделывать пример №4 или №5 из тех, что есть на сайте и разобраны на уроке.

Процесс рисования снежинки коха.

Примеры работы с PyQt4

Пример 1.

Пример 2.

Пример 3.

Пример 4.

Пример 5.

Примеры взяты с сайта http://zetcode.com/tutorials/pyqt4/ . Там же можно найти больше примеров на другие разделы PyQt4.

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

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

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

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

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

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

Официальный разбор школьного тура олимпиады

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

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

Диагностическая в формате ЕГЭ

Результаты. Подведение итогов и разбор на первом занятии в новой четверти.

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

Задание 34

Написать программу для перемножения матриц и векторов.

Программа должна уметь:

Для сложения, вычитания и умножения следует использовать специальные методы __add__, __sub__, __mul__. Для красивого преобразования в строку с помощью функции str, переопределите метод __str__. Отличать, на что домножается матрица: на число или на вектор, следует с помощью инструкции type(x) == Vector или type(x) == Matrix.

Пример реализации для класса комплексных чисел MyComplex (кстати, комплексные числа уже есть в питоне, это встроенный тип complex).

Задание 33, шахматы

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

Сделать по классу для каждого типа фигуры (пешка, слон, конь, ладья, король, ферзь). Каждая из фигур в объекте-экземпляре класса должна содержать текущие координаты фигуры и её цвет. У каждого класса должны быть метод, который будет проверять, может ли фигура перейти на клетку с введёнными пользователем координатами.

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

Задача 32, обработка ошибок

Дописать программу с записной книжкой таким образом, чтобы она:

Конструция перехвата нескольких классов исключений выглядит так:

try:
    x = 1 / int(input())
except (ValueError, ZeroDivisionError):
    print('Danger!')

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

Задание 31, знакомимся со словарями

Часть 1.

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

Часть 2.

Написать калькулятор для вычисления выражений в польской нотации Например, математическому выражению 1 + (4 * 6) соответствует следующее выражение в польской нотации:

1 4 6 * +

Сначала программа положит на стек числа 1, 4, 6, затем, при поступлении на вход операции '*' она возьмёт два числа, 4 и 6, со стека и перемножит их, положив на стек результат. Таким образом, на стеке будут лежать числа 1 и 24. Потом программа обработает знак +, взяв со стека 1 и 24 и положив обратно 25. Это число и будет результатом вычислений.

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

a = 1 4 6 * +
You saved 25 into variable 'a'
beta = 3 4 + 5 *
You saved 35 into variable 'beta'
a beta +
Result = 70

Для хранения значений переменных использовать словарь.

Задание 30, Рекурсия в судоку

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

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

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

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

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

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

Написать записную книжку из задания 16 на питоне. Для хранения пользователей использовать питоновские списки. Загрузку и сохрание из файлов реализовывать не нужно.

Результаты контрольной

Все, кто написал на 3, должны переписать.

Результаты

Задание 27, чтение из файла

Пользователь вводит имя файла, программа открывает этот файл и выводит:

Задание 26, подсчёт символов и слов в строке

Пользователь вводит строку на ввод.

Вывести:

Задание 25, факториалы и интегралы

Нужно написать на Питоне две программы. Одна должна быть аналогом задания 3 (вывод в цикле факториала, двойного факториала, чётности и делителей), другая аналогом задания 15, но реализовывать нужно только методы трапеций и прямоугольников, без метода Симпсона. Формулы смотрите в соответствующих заданиях прошлого года.

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

Написать на питоне программу для вычисления функции exp(x). Программа должна считывать введённое значение x и выводить значение экспоненты. Формулу для exp(x) смотрите в прошлогоднем задании на Си.

Критерий годовых оценок

Оценка "5" -- 21 сданное задание.

Оценка "4" -- 17 сданных заданий.

Оценка "3" -- 12 сданных заданий.

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

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

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

57420361

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

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

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

Пример

./proga edcode 57420361 secret_data.txt encoded_secret_data.txt

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

Задание 22, подсчёт числа Пи

Подсчитать радиус единичного метода методом Монте-Карло. Для расчёта с точностью два знака после запятой досточно 10000 итераций.

Задание 21, расстановка ферзей

Программа принимает как аргумент командной строки или считывает при помощи scanf целое число N. Необходимо вывести на экран такие варианты расстановки ферзей на шахматной доске N*N клеток, при которых ферзи не бьют друг друга.

Пример (для доски 4*4):

./queens 4
--X-
X---
---X
-X--

-X--
---X
X---
--X-

2 positions total.

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

Учтите, что на доске 2*2 можно поставить максимум одного ферзя, на 3*3 -- максимум двух. Во всех остальных случаях на доске N*N возможно поставить N ферзей. Для случая 2*2 и 3*3 можно не запускать рекурсивный перебор, а вывести готовый результат.

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

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

Реализация стека через связный список

Задача 19, подсчёт кратностей слов

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

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

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

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

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

5 6 3 - * 2 +

равен 17.

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

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

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

Задание 17, длинная арифметика

Написать программу, которая будет производить операции над целыми числами произвольного размера. Программа должна быть разделена на файлы bignum.h с определением структуры для больших чисел и сигнатурами функций для работы с ними, bignum.c для определения функций для работы с большими числами. main.c и находящаяся в нём функция main должны работать с большими числами только с помощью функций, прототипы которых указаны в bignum.h (это означает, что залезать руками внутрь структуры в main нельзя, все необходимые операции должны делать соответствующие функции).

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

Ахтунг! файлы обновлены, написано больше коментариев и исправлен злобный баг с неправильным выделением памяти под внутренний массив с разрядами числа (не было домножения на sizeof(int)). Кто уже начал писать программу, исправьте у себя эту ошибку.

Шпаргалка по языку C. На английском, но думаю, что всё равно будет очень полезна. Рекомендую распечатать.

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

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

Пункты меню.

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

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

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

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

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

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

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

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

  9. «Выход».

Программа должна быть написана с использованием структур (у структуры должно быть два поля: массивы символов для хранения имени и номера телефона) и разделена на три файла: book.h, book.c и main.c

book.h
Файл с определением структуры и прототипами функций для выполнения пунктов меню из book.c
book.c
Файл с определениями функций для выполнения пунктов меню. Подключает book.h через #include.
main.c
Файл с функцией main. Подключает book.h через #include.

Задание 15

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

Формулы:

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

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

$$ 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^3}{12} $$

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

$$ 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^3}{24} $$

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

$$ 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} $$

Задание 14, решаем уравнения

Написать программу для решения уравнения cos(x) = 0. Функция cos(x) и её производная должны быть заданы в коде как фукнции языка C, чтобы для изменения уравнения нужно было изменить только эти две фукнции. Писать расчёт cos(x) не обязательно, лучше просто воспользоваться функцией double cos(double x) из математической библиотеки (заголовочный файл math.h).

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

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

Метод хорд

Уравнение хорды

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

Решаем уравнение для y = 0, получаем точку пересения касательнос с осью X. Она и является следующим приближеним метода хорд:

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

Метод Ньютона

Уравнение касательной:

$$ y=f(x_{0})+f'(x_{0})(x-x_{0}) $$

Следующее приближение метода Ньютона:

$$ x_{1}=x_{0}-\frac{f(x_{0})}{f'(x_{0})} $$

Задание 13, самые длинные строки

Найти в каждом из заданных файлов стоки наименьшей и наибольшей длины.

Имена файлов задаются через аргументы командной строки.

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

Олимпиада "Курчатов"

Традиционная курчатовская олимпиада проходит в этом году в два этапа: интернет-отбор и очный тур.

Цитата с сайта олимпиады ( http://olimpiadakurchatov.ru/internet_etap ):

Интернет-этап олимпиады «Курчатов» в 2012/2013 учебном году будет проводиться в декабре 2012–январе 2013 года и будет включать в себя конкурсы по математике, физике, информатике, химии и биологии, а также межпредметный конкурс и конкурс по истории науки. К участию допускаются ученики всех классов. Для участия необходимо зарегистрироваться на портале Единой системы регистрации http://reg.olimpiada.ru/.

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

Интернет-этап будет проводиться с декабря 2012 года по январь 2013 года. Победители будут приглашены к участию в очных турах. Победители интернет-этапа в выпускных классах по решению Оргкомитетов могут быть приглашены на финальные туры олимпиад, входящих в Перечень (иными словами, олимпиад, по результатам которых ВУЗы предоставляют льготы при поступлении).

Те, кому интересно, могут поучаствовать. Задания в отборочном туре занятные.

Олимпиада продлена до 23:59 9 января

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

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

  1. Поиск подстрок. Если указан аргумент --search и идущая после него строка для поиска, программа должна проводить поиск данной подстроки во всех оставшихся строках, и выводить только те строки, в которых она найдена.

    Пример:

    ./proga12 --search abc abcdef zabc abdc ababcbc
    abc
    abcdef
    zabc
    ababcbc
    
  2. Разбиение по шаблону. Если указан аргумент --split, то следующий аргумент после него считается текстовым шаблоном, по которому нужно разбить все остальные аргументы. Если в аргументе не встречается шаблон, он должен быть распечатан как есть. Если шаблон содержится в аргументе, то нужно распечатать куски аргумента между вхождениями шаблона, разделив их запятыми.

    Пример:

    ./proga12 --splist abc xabcz aabcababababcd xabcabcz
    x z
    a ababab d
    x z
    

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

  3. Сортировка аргументов по алфавиту.

    ./proga12 --sort xyz def abc
    abc
    def
    xyz
    
  4. Расчёт среднего. Если задан аргумент --average, то идущие за ним аргументы должны быть преобразованы в числа и должны быть рассчитаны следующие величины:

    • среднее: $$ \bar{a} = \frac{1}{N} \sum{a_{i}} $$

    • стандартное отклонение (мера того, насколько последовательность отклоняется от среднего): $$ \sigma = \sqrt{\frac{1}{N} \sum_i^N {(a_{i} - \bar{a})^2}} $$

    • стандартное отклонение среднего (именно эта величина определяет то, насколько точно значение \(\bar{a}\)): $$ \sigma_{\bar{a}} = \sqrt{\frac{1}{N(N-1)}\sum_i^N{(a_i - \bar{a})^2}} $$

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

    double atoi(char *nptr);
    

    Функция принимает строку и преобразует её в соответствующее число с плавающей точкой.

Задание 11, указатели наступают

Переписать программу №7 таким образом, чтобы функции внутри неё работали с помощью указателей, а не массивов.

Пример для strlen:

size_t mystrlen(char *s) {
    size_t length = 0;
    for (; *s != '\0'; s++) {
        length++;
    }
    return length;
}

Сигнатуры функций и описания того, что они должны делать:

char *strcpy(char *dest, char *src);
char *strncpy(char *dest, char *src, size_t n);

Описание функций

char *strcat(char *dest, char *src);
char *strncat(char *dest, char *src, size_t n);

Описание функций

int strcmp(char *s1, char *s2);
int strncmp(char *s1, char *s2, size_t n);

Описание функций

void *memcpy(void *dest, const void *src, size_t n);

Описание функции

void *memset(void *s, int c, size_t n);

Описание функции

На странице man.opennet.ru, на который даны ссылки, можно найти не только документацию по функциям стандартной библиотеки языка Си, но и по командам в командной строке Unix (мы работаем с ней через Putty).

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

Задание 10, обход двумерного массива

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

  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

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

Окружная олимпиада

В воскресенье 2 декабря состоится окружная олимпиада по информатике. Потренироваться на задачах 2009, 2010, 2011 года можно тут: http://olympiads.ru/moscow/2012-13/okrug/training.shtml

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

Задание 9

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

  1. по возрастанию максимальной высоты подъема снаряда;

  2. по возрастанию дальности полета снаряда.

После сортировки, например, по возрастанию дальности полёта, первая пара скоростей (вектор vx,vy) должна иметь наименьшую дальность, вторая — большую, чем первая, третья — большую чем вторая и последняя — наибольшую дальность.

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

sort4(int sort_type,
      double *vx1, double *vy1, double *vx2, double *vy2,
      double *vx3, double *vy3, double *vx4, double *vy4)
{
    //...
}

Сами пары скоростей снарядов должны храниться в отдельных переменных. Массивы использовать не разрешается. Функция сортировки sort4 должна принимать восемь указателей на отдельные координаты и параметр, определяющий тип сортировки. При этом sort4 должна только сортировать, выводом получившихся точек на экран должна заниматься либо отдельная функция, либо функция main.

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

Программа с функцией swap

Задача 8, посдсчёт слов в файле

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

  1. число символов в файле,

  2. число строк,

  3. число слов (слова отделяются друг от друга одним или несколькими пробелами),

  4. число слов, начинающихся с заглавной буквы,

  5. число слов, целиком состоящих из заглавных букв,

  6. число английских согласных в тексте.

Результат программа должна выводить на экран и в файл results.txt (c помощью fprintf).

Не забывайте проверять ошибки при открытии файлов и закрывать файлы.

Программа, написанная на уроке, дополнена примером вызова fprintf.

Задание 7, строковые функции

Реализовать следующие функции:

// Скопировать строку 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 символов.
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);

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

Ещё раз напоминаю, что ваши функции не должны носить те же имена, что и указанные выше, иначе это приведёт к конфликту имён.

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

Задание 6, функции, функции, много функций

Необходимо написать функции mypow, fact, myexp, mysin, mycos. Ну и, конечно, функцию main, которая будет запускать функции для расчёта экспоненты, синуса и косинуса.

Прототипы функций должны быть следующими:

double myexp(double x, int N, double delta); double mysin(double x, int N, double delta); double mycos(double x, int N, double delta);

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

Если функции передаётся отрицательное N, то она должна выполнять суммирование ряда не ориентируясь ни на какое заранее заданное количество членов ряда, а до тех пор, пока текущий член ряда по модулю меньше delta.

Если N положительно, надо просуммировать ряд вплоть до N-го члена.

Прим. Не называйте свои фукнции pow, exp, sin, cos. В математической библиотеке языка Си уже есть функции с такими именами, и, если математическая библиотека подключается при компиляции, случится конфликт имён.

Задание 5, сдвиги в массиве

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

Меню:

  1. Распечатать элемент массива.

  2. Изменить i-ый элемент массива.

  3. Вставить элемент в массив по индексу i. При этом элемент, ранее находившийся на позиции i и все следующие за ним (кроме последнего), будут сдвинуты на одну позицую вправо. Последний элемент при этом будет потерян, так как для того, чтобы сдвинуть его, уже нет места.

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

  5. Поиск элемента. Для введенного пользователем значения найти его индекс. Если такого значения в массиве нет, то следует сообщить об этом пользователю.

  6. Удаление чётных элементов со сдвигом. При удалении каждого числа используется метод из пункта 5.

  7. Удаление нечётных элементов со сдвигом.

Вместе с меню нужно печатать содержание массива, чтобы понимать, что собственно происходит.

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

Текущее содержание массива: 0 0 0 0 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 2 Введите индекс: 0 Введите новое значение: 10 Текущее
содержание массива: 10 0 0 0 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 2 Введите индекс: 2 Введите новое значение: 7 Текущее
содержание массива: 10 0 7 0 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 2 Введите индекс: 3 Введите новое значение: 8 Текущее
содержание массива: 10 0 7 8 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 1 Введите индекс: 0 a[0] = 10 Текущее содержание массива: 10
0 7 8 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 3 Введите индекс для вставки: 2 Введите значение для вставки:
16 Текущее содержание массива: 10 0 16 7 8
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 4 Введите индекс удаляемого элемента: 1 Текущее содержание
массива: 10 16 7 8 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 5 Введите значение элемента для поиска: 7 Элемент найден по
индексу 2.  Текущее содержание массива: 10 16 7 8 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 6 Чётные элементы массива удалены.  Текущее содержание
массива: 7 0 0 0 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход 7 Нечётные элементы массива удалены.  Текущее содержание
массива: 0 0 0 0 0
1. Чтение по индексу
2. Запись по индексу
3. Вставка элемента со сдвигом
4. Удаление элемента со сдвигом
5. Поиск элемента
6. Удаление чётных со сдвигом
7. Удаление нечётных со сдвигом
8. Выход
8
Пока!

Задание 4, ряды для exp, sin, cos

Программа должна вычислять приближённое значение exp(x), sin(x), cos(x), суммируя N первых членов соответствующего бесконечного ряда. Формулы для вычисления:

\[\exp(x) = \sum_{i=0}^{N} \frac{x^{i}}{i!} \] \[\sin(x) = \sum_{i=0}^{N} \frac{(-1)^{i} x^{2i+1}} {(2i + 1)!} \] \[\cos(x) = \sum_{i=0}^{N} \frac{(-1)^{i} x^{2i}} {(2i)!} \]

Пользователь вводит x, N (число членов ряда, чем оно выше, тем точнее сумма (см. прим. 1)), delta (точность, чем число ниже, тем точнее значение суммы). Программа должна суммировать N членов соответствующего ряда, при этом, если i-ый член ряда становится по модулю меньше delta, суммирование можно прервать.

Примечание 1. Число N не стоит делать слишком большим, так как из-за ограничений машинной точности может переполниться значение фактриала. Приемлемым значением N является 4 или 5.

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

Задание 3

Программа должна в цикле считывать значения целого числа n и выводить: 1) Чётное число или нечётное 2) n! 3) n!! 4) Все делители числа n. Когда пользователь введёт отрицательное число, цикл должен завершиться. Программа печатает "Пока!" и завершается.

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

Введите n:
5
нечётное
120
15
1 5
Введите n:
4
чётное
24
8
1 2 4 8
Введите n:
6
чётное
720
48
1 2 3 6
Введите n:
-1
Пока!

Примеры, показанные на уроке

Задание 2, промежутки знакопостоянства

Написать программу, которая находит промежутки знакопостоянства функции cos(x) на отрезке [a, b] и количество этих промежутков. Пользователь вводит границы отрезка a, b и количество шагов N, на которые будет разбит отрезок.

Промежутком знакопостоянства является промежуток, на котором функция имеет один и тот же знак. Необходимо двигаться по отрезку с шагом h = (b - a) / N. Если известно, что на некотором шаге функция меняет знак, делать промежуточные шаги между этими двумя точками не нужно, достаточно включить левую точку в одит промежуток и правую в другой. Чтобы определить, что функция меняет знак, удобно проверять знак произведения значений функции в двух точках: если произведение положительно, знак одинаков, если отрицательно, различен.

Пример работы программы для входных данных a = 0, b = 5, N = 1000:

+ promezutok, start at 0.000000, end at 1.570000
- promezutok, start at 1.575000, end at 4.710000
+ promezutok, start at 4.715000, end at 5.000000

Код программы, показанной на уроке (выводит значения функции cos(x) в промежуточных точках):

#include <stdio.h>
#include <math.h>

int main()
{
    double a, b, h;
    int N;
    printf("a =\n");
    scanf("%lf", &a);
    printf("b =\n");
    scanf("%lf", &b);
    printf("N =\n");
    scanf("%d", &N);
    h = (b - a) / N;
    double x;
    for(x = a; x <= b; x+= h) {
        printf("cos(%lf) = %lf\n", x, cos(x));
    }
    return 0;
}

Задание 1, цельсии и фаренгейты

В учебнике Кернигана и Ритчи есть программа, печатающая таблицу для перевода фаренгейтов в градусы Цельсия. Перепишите её так, чтобы она переводила градусы цельсия в фаренгейты и выводила аналогичную таблицу.