Шереметев Информатика. Сборник домашних заданий 2009
.pdfСто двадцать восемь прибавить одиннадцать
будет сто тридцать девять
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и наглядную форму диалога.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Осуществить расширение этой задачи для чисел не более 10000.
Задача 1.14. "ИЗ АРАБОВ В РИМЛЯНЕ". Написать про-
грамму, осуществляющую преобразование числа в его запись римскими цифрами. Вводится арабскими цифрами число N (N < 2000). Программа выполняет преобразование этого числа в запись римскими цифрами и выводит результат на экран. При этом используются следующие обозначения: 1 = I, 5 = V, 10 = X, 50 = L, 100 = C,
500 = D, 1000 = M.
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и наглядную форму диалога. Сначала попытайтесь найти алгоритм решения этой задачи для чисел не более 10, а затем расширьте его.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Осуществить расширение этой задачи для чисел не более 10000.
Задача 1.15. "ИЗ РИМЛЯН В АРАБЫ". Написать про-
грамму, осуществляющую преобразование числа, записанного римскими цифрами, в его запись арабскими цифрами. Вводится римскими цифрами число N (N < МММ). Программа выполняет преобразование этого числа в запись арабскими цифрами и выводит результат на экран. При этом используются следующие обо-
значения: 1 = I, 5 = V, 10 = X, 50 = L, 100 = C, 500 = D, 1000 = M.
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и наглядную форму диалога. Сначала попытайтесь найти
11
алгоритм решения этой задачи для чисел не более 10, а затем расширьте его.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Осуществить расширение этой задачи для чисел не более 10000.
Задача 1.16. "ШИФРОВАНИЕ ПО АЛФАВИТУ-
КЛЮЧУ". Вводится строка символов не длиннее 64 символов - алфавит допустимых символов. Затем вводится другая строка символов - алфавит-ключ, состоящий из допустимых символов, переставленных в произвольном порядке. Каждый символ в любом из алфавитов должен встречаться не более одного раза. Потом вводится текст для шифрования - последовательность строк символов не длиннее 72 символов. Окончание входного потока - ввод строки, начинающейся с символа ".". Максимальное количество строк равно 10. Шифрование состоит в том, что каждый символ каждой входной строки заменяется символом алфавита-ключа, стоящим в той же позиции, что и в алфавите допустимых символов. Формируется также статистическая информация. Примерный вид выходной информации:
Исходный алфавит: (строка)
Алфавит-ключ: (строка)
Входной текст:
(последовательность входных строк)
Введено К строк, N символов, макс. длина строки М символов.
Получен шифрованный текст:
(последовательность обработанных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
12
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод исходного алфавита, алфавита-ключа, числовых и символьных констант из текстовых файлов.
Задача 1.17. "ШИФРОВАНИЕ СИММЕТРИЧНОЙ ПЕ-
РЕСТАНОВКОЙ СИМВОЛОВ". Вводится последовательность строк символов не длиннее 50 символов. Допустимые символы в строке - русские буквы, цифры и пробел. Окончание входного потока - ввод строки, начинающейся с символа "/". Максимальное количество строк равно 12. Шифрование состоит в том, что в каждой входной строке символ обменивается местом с символом, симметричным ему относительно середины строки. При нечетном количестве символов в строке центральный символ не изменяется. Формируется также статистическая информация. Примерный вид выходной информации:
Входной текст:
(последовательность входных строк)
Введено К строк, всего N символов,
макс. четная длина строки М1 символов, макс. НЕчетная длина строки М2 символов.
Получен шифрованный текст:
(последовательность обработанных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант. Обратите внимание, что алгоритм шифрования симметричен - для дешифрования нужно применить его же.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод допустимых символов, символа-признака окончания входного потока, числовых констант из текстового файла.
13
Задача 1.18. "ШИФРОВАНИЕ ОБРАТНОЙ ПЕРЕСТА-
НОВКОЙ БИТОВ". Вводится последовательность строк символов не длиннее 46 символов. Допустимые символы в строке - латинские буквы, цифры, знаки препинания и пробел. Окончание входного потока - ввод строки, начинающейся с символа "?". Максимальное количество строк равно 7. Шифрование состоит в том, что в двоичном коде каждого символа (байте) биты переставляются в обратном порядке, а затем бит 7 устанавливается в 0/1 при не/четном количестве 1-битов в байте, формируя код зашифрованного символа. Формируется также статистическая информация. Примерный вид выходной информации:
Входной текст:
(последовательность входных строк)
Введено К строк, всего N символов,
минимальная длина строки М1 символов.
максимальная длина строки М2 символов. Получен шифрованный текст:
(последовательность обработанных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод допустимых символов и символа-признака окончания входного потока, числовых констант из текстового файла.
3.Разработать обобщенные алгоритмы шифрования/дешифрования перестановкой битов и реализовать их в программе. Произвольная перестановка битов в байте может задаваться ключевой строкой. Например, для частного случая алгоритма этой задачи такая строка выглядит как "01234567".
Задача 1.19. "ШИФРОВАНИЕ ПЕРЕСТАНОВКОЙ ПО-
ЛУБАЙТОВ". Вводится последовательность не более 11 строк длиной не более 26 символов. Допустимые символы в строке - русские буквы и пробел. Окончание входного потока - ввод строки, начинающейся символом ";". Шифрование состоит в том, что в
14
двоичном коде каждого символа (байте) переставляются местами его старшая и младшая тетрады, то есть бит 0 меняется с битом 4, бит 1 с битом 5 и т.д. Формируется также статистическая информация. Примерный вид выходной информации:
Входной текст :
(последовательность входных строк)
Введено N1 строк , N2 символов.
Минимальная длина строки N3 символов,
Максимальная длина строки N4 символов.
Шифрованный текст :
(последовательность обработанных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант. Обратите внимание, что алгоритм шифрования симметричен - для дешифрования нужно применить его же.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод допустимых символов и символа-признака окончания входного потока, числовых констант из текстового файла.
3.Разработать обобщенные алгоритмы шифрования/дешифрования перестановкой битов и реализовать их в программе. Произвольная перестановка битов в байте может задаваться ключевой строкой. Например, для частного случая алгоритма этой задачи такая строка выглядит как "32107654".
Задача 1.20. "ШИФРОВАНИЕ СУММИРОВАНИЕМ СОСЕДНИХ БАЙТОВ". Вводится последовательность не более 6 строк длиной не более 53 символов. Допустимые символы в строке - латинские буквы, цифры, пробел и знаки препинания. Окончание входного потока - ввод строки, начинающейся символом ":". Алгоритм шифрования (формирования очередного байта выходной строки):
b[i] = a[i] + a[i+1],
b[k] = a[0] + a[k], i = 0, 1, 2, ...,
где a[0] - значение начального байта входной строки, а[k] - значение ее последнего байта, аналогично b[0], b[k] - для выходной
15
строки. Формируется также статистическая информация. Примерный вид выходной информации:
Входной текст:
(последовательность входных строк)
Введено N1 строк, всего N2 символов,
Минимальная длина строки N3 символов,
Максимальная длина строки N4 символов.
Получен шифрованный текст:
(последовательность обработанных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод допустимых символов и символа-признака окончания входного потока, числовых констант из текстового файла.
3.Разработать алгоритм дешифрования и реализовать его в программе.
Задача 1.21. "ШИФРОВАНИЕ ПО ПРЕДЫДУЩЕМУ
БИТУ ". Вводится последовательность не более 7 строк длиной не более 45 символов. Допустимые символы в строке - „0‟ и „1‟. Окончание входного потока - ввод строки, начинающейся символом "/". Алгоритм шифрования (формирования очередного байта выходной строки):
b[0] = a[0],
b[k] = „1‟, если a[k] = a[k-1], иначе „0‟; k = 0, 1, 2, ...,
где a[0] - значение начального байта входной строки, а[k] - значение ее очередного байта, аналогично b[0], b[k] - для выходной строки. Формируется также статистическая информация. Примерный вид выходной информации:
(c) <имя автора, версия и название задачи> Входной текст:
(последовательность входных строк)
Введено N1 строк, всего N2 символов,
16
Минимальная длина строки N3 символов, Максимальная длина строки N4 символов.
Получен шифрованный текст:
(последовательность обработанных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Разработать алгоритм дешифрования и реализовать его в программе.
3.Расширить задачу п. 2 для шифрования/дешифрования обычного текста, используя битовое представление символов и реализовать в программе.
Задача 1.22. "ШИФРОВАНИЕ ПОВТОРЕНИЕМ БИ-
ТОВ". При передаче цифровых сообщений через каналы связи с помехами для повышения надежности можно повторять каждый бит, например 3 раза. При этом при передаче последовательность 1, 0, 1 заменяется на 1, 1, 1, 0, 0, 0, 1, 1, 1. При приеме и дешифровке такой последовательности три последовательные цифры (бита) заменяются значением той цифры (бита), которая встретилась в этой тройке по крайней мере дважды. Написать программу шифрования и дешифрования. Вводится последовательность не более 5 строк длиной не более 23 символов. Допустимые символы в строке - „0‟ и „1‟. Окончание входного потока - ввод строки, начинающейся символом "*". Формируется также статистическая информация. Примерный вид выходной информации:
(c) <имя автора, версия и название задачи> Входной текст:
(последовательность входных строк)
Введено N1 строк, всего N2 символов, Минимальная длина строки N3 символов,
Максимальная длина строки N4 символов. Получен шифрованный текст:
(последовательность обработанных строк для передачи)
Принятое сообщение:
(последовательность дешифрованных строк после приема)
17
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Расширить задачу п.1 для шифрования/дешифрования обычного текста, используя битовое представление символов и реализовать в программе.
Задача 1.23. "ОПРЕДЕЛЕНИЕ БИТОВЫХ ПЕРЕХО-
ДОВ". Вводится последовательность не более 10 строк символов не длиннее 37 символов. Допустимые символы в строке: "0", "1" и "." - разделитель битовой группы. Окончание входного потока - ввод строки, начинающейся с символа "!". Максимальное количество строк равно 8. Для каждой входной строки нужно выделить битовую группу, а для каждой битовой группы определить ее длину и количество переходов "0" -> "1" и "1" -> "0". Cформировать также статистическую информацию. Примерный вид выходной информации:
Входной текст:
(входные строки без лишних разделителей) Введено К строк, всего N символов,
минимальная длина строки М1 символов, максимальная длина строки М2 символов.
Для строки номер 1:
Битовая группа Номер 1: (последовательность "0" и "1")
длина = С1
переходов "0" -> "1" = N1
переходов "1" -> "0" = N2
...
Битовая группа Номер 10: (последовательность "0" и "1")
длина = С10
переходов "0" -> "1" = N10
переходов "1" -> "0" = N20 Всего 10 групп,
минимальная длина группы М11 символов.
максимальная длина группы М12 символов. Для строки номер К:
(вывод аналогичен приведенному выше)
18
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод допустимых символов и символа-признака окончания входного потока, числовых констант из текстового файла.
Задача 1.24. "ПОИСК БИТОВОГО ОБРАЗА". Вводится последовательность строк символов не длиннее 16 символов. Каждая строка считается числом (кодом) в двоичной системе и после ввода преобразуется в unsigned int. Допустимые символы в строке: "0", "1". Первая строка длиной не более 5 символов (битов) задает битовый образ для поиска в последующих строках. Окончание входного потока - ввод строки, начинающейся с символа "+". Максимальное количество строк равно 8. Для каждой входной строки, начиная со 2-й, попытаться найти битовый образ, задаваемый 1-й строкой (а не подстроку в строке символов), и подсчитать количество вхождений образа в 16-битовое слово (unsigned int). Cформировать также статистическую информацию. Примерный вид выходной информации:
Поиск битового образа:
01100 (1-я строка)
в битовых строках:
(последовательность остальных входных строк)
Всего введено К строк, N символов,
минимальная длина строки М1 символов, максимальная длина строки М2 символов.
Двоичный код строки 2: (последовательность из 16-ти "0" и
"1")
Обнаружено С2 вхождений образа, начало 1-го в бите N1
...
Двоичный код строки 8: (последовательность из 16-ти "0" и
"1")
НЕТ ВХОЖДЕНИЙ ОБРАЗА
Максимальное количество вхождений К1 в строке К2.
19
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
2.Предусмотреть ввод допустимых символов и символа-признака окончания входного потока, числовых констант из текстового файла.
Задача 1.25. "ОПРЕДЕЛЕНИЕ БИТОВЫХ ИМПУЛЬ-
СОВ". Вводится последовательность не более 3 строк символов не длиннее 75 символов. Допустимые символы в строке: "0" , "1". Окончание входного потока - ввод строки, начинающейся с символа "+". Для каждой входной строки нужно определить минимальную и максимальную длительности битовых импульсов - длину последовательности идущих подряд “0” (0-импульс) и “1” (1- импульс). Cформировать также статистическую информацию. Примерный вид выходной информации:
(c) <имя автора, версия и название задачи>
Входной текст:
(входные строки без лишних разделителей)
Введено К строк, всего N символов, минимальная длина строки М1 символов, максимальная длина строки М2 символов.
Для строки номер 1:
мин. длительность 0-импульса = 99, начало в бите номер = 99
макс. длительность 0-импульса= 99, начало в бите номер = 99
мин. длительность 1-импульса = 99, начало в бите номер = 99 макс. длительность 1-импульса= 99, начало в бите номер = 99 (аналогично для остальных строк)
УКАЗАНИЯ: Предусмотреть обработку ошибочных ситуаций и легкую замену в тексте программы числовых и символьных констант.
РАЗВИТИЕ:
1.Предусмотреть режимы ввода/вывода: только экран и клавиатура, ввод из текстового файла и вывод в текстовый файл с отображением диалога на экране.
20