[ Курс «Теория алгоритмов» Задания для СРС к лекции № 4
Второй семестр 2013/2014 учебного года (весна)
1. Простое задание (по вариантам).
Для данных орграфов необходимо выписать матрицу смежности и матрицу
инцидентности в соответствии со своим вариантом.
Номер
Изображение графа
варианта
1, 11, 21
2, 12, 22
3, 13, 23
Курс «Теория алгоритмов» Задания для СРС к лекции № 4 Второй семестр 2013/2014 учебного года (весна) 4, 14, 24 5, 15, 25 6, 16, 26 7, 17, 27 Курс «Теория алгоритмов» Задания для СРС к лекции № 4 Второй семестр 2013/2014 учебного года (весна) 8, 18, 28 9, 19, 10, 20, 2. Простое задание (индивидуальное) Приведите свой пример орграфа с 8-мью вершинами, для которого:
1. существуют две вершины, между которыми нет пути (нельзя из одной вершины попасть в другую), укажите эти вершины;
2. есть две вершины (можно включить те, которые вы выбрали в пункте 1), попасть в которые можно только более чем через 3 вершины (не включая первую и последнюю, то есть всего, суммарно, путь от начальной вершины до конечной вершины проходит через 5 вершин и более, включая начальную и конечную вершины), укажите эти вершины и выпишите вершины, через которые лежит маршрут.
Курс «Теория алгоритмов» Задания для СРС к лекции № Второй семестр 2013/2014 учебного года (весна) 3. Сложное задание (требует кодирования на С++).
Ваша задача - написать программу, которая будет читать текстовый файл и определять для него частоту вхождения символов в тексте. В результате своей работы программа должна вывести на экран число повторений каждого из символов, если символ хотя бы один раз встретился (если символ в тексте не встретился – ничего выводить не надо). Отдельно необходимо вывести число пробелов, даже если их нет.
Например, если в файле написано слово «МОЛОКО», программа должна вывести на экран (в алфавитном порядке):
‘К’ – ‘Л’ – ‘М’ – ‘О’ – Пробелов - Имя входного файла передатся программе в качестве аргументов командной строки (см. FAQ ниже). Гарантируется, что весь текст – 8-битные символы в кодовой странице 1251.
Напишите программу, которая:
1. будет принимать в качестве аргумента имя файла, имя файла гарантированно передатся первым и единственным передаваемым 2. будет читывать и анализировать содержимое файла, считая частоты 3. будет выводить частоты встречи только букв русского и английского алфавитов на экран в виде, как показано в примере выше (то есть точки, запятые, цифры и прочие символы выводить не надо), а также число пробелов, вывод делать на русском языке (см. FAQ ниже)!
4. оценит сво быстродействие и выведет время чтения данных и вывода на Пример работы моей программы.
Второй семестр 2013/2014 учебного года (весна) Подробнее про коды символов в кодировке CP-1251:
http://en.wikipedia.org/wiki/Windows- Я буду свои примеры тестировать на файлах вот отсюда:
http://tululu.org Важно!
Три самых интересных и быстродействующих варианта реализации программы я выберу на оценку «отлично» автоматом по дисциплине «Теория алгоритмов» при условии, что ранее выполнялись и далее будут выполняться варианты заданий СРС и все лабораторные работы за семестр будут сданы в срок.
Важно!
На оценку «отлично» и шоколадку я выберу также две программы наименьшего размера исходного кода (из каждой группы – по одной программе, если такие будут).
У кого будет желание посоревноваться, можете протестировать свой код на тех же компьютерах, на которых тестировал я. Я тестировал в аудитории 4131 – наша лаборатория. Можете приходить и проверять быстродействие в любое время, когда там нет занятий (на скриншоте выше время отличается, так как скриншот сделан на мом компьютере, а не в лаборатории).
Размер моего исходника: 535 байт. Дерзайте!
Ответ можно присылать в электронном виде на адрес [email protected] В заголовке письма прошу указать группу, фамилию. Пример заголовка письма:
«ЭКТ-23, Андрющенко А.А.»
Крайний срок прима ответов для этого задания – 22 апреля. Ответы, присланные позже этого срока, рассматриваться не будут.
Второй семестр 2013/2014 учебного года (весна) FAQ к данному заданию для СРС.
Q1: Как научить программу корректно выводить текст на русском языке?
Для этих целей необходимо корректно указать специальную штуку, называемую «локаль».
Пример кода показан ниже.
Результат работы программы:
Каракули рисуются потому, что в консольных программах используется кодировка, доставшаяся в наследство от MS-DOS - CP-866, а в операционной системе Windows – CP-1251.
Эти кодировки отличаются тем, что в таблице ASCII-символов нужные буквы стоят в разных местах.
Обращаю ваше внимание, что изменение локали таким способом не поможет при вводе текста, это вс работает только при выводе текста на экран. Как с этим бороться более серьзно, можно почитать, например, вот тут: http://cppstudio.com/uchebniki/yazyk-programmirovaniyas/kirillica-v-konsoli/ Q2: Как можно определить число аргументов, передаваемых программе?
Для этого необходимо в качестве аргументов функции main указать две переменные типов int и char ** (или char * []), традиционно они называются argc (переменная типа int, сокращение от arguments count) и argv (переменная типа char **, сокращение от arguments vector).
В первую из них операционная система записывает число аргументов, передаваемых программе, во вторую – массив аргументов, представленных в виде строк. Поскольку обе эти переменные заполняются для наших программ операционной системой, из программы в эти переменные ничего записывать не нужно, в них уже лежат все переданные значения, необходимо их лишь считать. Важно помнить, что операционная система всегда передат как минимум один аргумент – это имя самой запускаемой программы.
Ниже приведн пример программы, которая выводит число своих аргументов и сами аргументы на экран.
Второй семестр 2013/2014 учебного года (весна) Вот что будет выведено на экран в результате работы программы, если явно не передавать аргументы в программу.
А вот что будет написано, если программе передать несколько аргументов.
Q3: Как можно передать аргументы в программу?
Для этого есть много способов, но я покажу один – как это сделать с использованием Visual Studio.
1. В дереве проекта на имени вашего проекта вызовите контекстное меню, выберите самый последний пункт - «Properties»(для русифицированной студии - «Свойства»).
2. В открывшемся диалоге слева в списке выберите «Configuration properties» «Debugging»
(для русифицированной студии – «Конфигурация» «Отладка»).
3. В поле справа введите нужные аргументы в поле «Command Arguments» (в русифицированной студии – «Аргументы»).
4. Если у вас русифицированная студия и ничего найти не можете – удалите е и поставьте нормальную англоязычную версию.
Второй семестр 2013/2014 учебного года (весна)
«