Тотальный тренинг по c#

Доступен только на StudyGur

Тема:
Скачиваний: 3
Страниц: 122
Опубликован:
ЧИТАЙТЕ ПОЛНЫЙ ТЕКСТ ДОКУМЕНТА

ПРЕДПРОСМОТР

(мультифкещ
1
Валерий Рубанцев
ТОТАЛЬНЫЙ ТРЕНИНГ
ПО СИ-ШАРПУ
БОЛЬШОЙ ПРАКТИКУМ ПО ПРОГРАММИРОВАНИЮ
НА ЯЗЫКЕ C#
2
3
Это издание представляет собой сокращённый вариант книги Тотальный
тренинг по Си-шарпу. Полная версия книги включает 20 глав (615 страниц).
Вы можете приобрести её (вместе с исходными кодами всех проектов) на
сайте издательства:
RVGames.de/buy2.htm
Все права защищены. Никакая часть этой книги не может быть воспроизведена
в любой форме без письменного разрешения правообладателей.
Автор книги не несёт ответственности за возможный вред от использования
информации, составляющей содержание книги и приложений.
Copyright 2013 Валерий Рубанцев
Лилия Рубанцева
От автора
Ученики никогда не пишут неправильно –
они пишут по-другому.
Немецкая педагогическая мудрость
Многие учебники по программированию для закрепления пройденного
материала обычно предлагают набор довольно скучных упражнений и заданий. Например, такие.
Дано натуральное число n. Получить в порядке возрастания n первых
натуральных чисел, которые не делятся ни на какие простые числа,
кроме 2, 3 и 5.
На мой взгляд, гораздо интереснее и полезнее решить более общую задачу
- о разбиении чисел на простые множители и вспомнить основную теорему арифметики.
В другой книге мы найдём следующее задание.
Напишите определение рекурсивной функции, имеющей следующий
прототип:
int squares(int n);
//Предусловие: n >= 1
//Возвращает сумму квадратов чисел от 1 до n.
Например, squares(3) возвращает значение 14, потому что 12 + 22 + 32
равно 14.
А мы отыщем все числа Армстронга и решим ещё парочку задачек со степенями!
В этой книге вас ждёт множество занимательных проектов, выполняя которые вы не только узнаете много нового, но и сможете в полной мере
оценить все возможности современного языка программирования Сишарп.
Вы узнаете:






о литорее обычной и мудрой;
о тыблоках и яквах, числах-Фениксах и словах-мамах;
о секретах транслитерации;
чем занимается высшая арифметика и комбинаторика;
что такое числа Стирлинга и Белла;
что такое код Грея и диаграммы Феррерса;
4
 как генерировать перестановки, подмножества, мультимножества,
разбиения чисел и другие комбинаторные объекты;
 как придумать и отладить эффективный алгоритм для своего приложения;
 как использовать списки List, массивы Array, ArrayList и BitArray, словари Dictionary, множества HashSet и SortedSet, большие числа BigInteger, а также другие структуры и классы в своих программах.
И научитесь:
 находить десятки тысяч цифр знаменитого числа пи всего за несколько секунд;
 подсчитывать кроликов Фибоначчи;
 просеивать числа через решето Эратосфена;
 расшифровывать тарабарскую грамоту;
 говорить на логопефическом языке;
 зашифровывать свои сообщения кодом Цезаря и Льюиса Кэрролла;
 выбирать правильный пароль;
 исправлять ошибки по методу Левенштейна;
 честно делить пиратские сокровища;
 играть в Супернаборщика и в Города;
 отыскивать палиндромы, палиндромоиды, анаграммы, логогрифы,
метаграммы, шарады, факториалы, простые и суперпростые числа;
 составлять чайнворды;
 разменивать деньги и наклеивать марки;
 играть в домино на шахматной доске;
настилать паркет прямыми полимино;
 надувать и лупасить геометрические пузыри;
 находить близких соседей на плоскости;
 составлять цепочки метаграмм, как учил нас Льюис Кэрролл;
 правильно рассчитываться по методу Иосифа Флавия, чтобы уцелеть;
 решать и составлять числобусы;
 набирать игроков в сборную.
5
Мы решим много «исторических» задач, которые без компьютера давались
людям с большим трудом. Например, всем известна печальная история
Вильяма Шенкса (William Shanks, 1812-1882), который за 15 лет работы
нашёл 707 знаков числа пи. Много лет спустя его вычисления были проверены, и оказалось, что он ошибся на 527-ом знаке. А мы за несколько секунд вычислим десятки тысяч знаков этого бесконечного числа!
А легко ли найти вручную все решения знаменитой головоломки о расстановке знаков между цифрами 1 2 3 4 5 6 7 8 9? Или все числа Армстронга?
Или решить «денежную» головоломку Генри Дьюдени?
На страницах этой книги мы будем решать старинные и современные задачи, проблемы и головоломки на новый лад – не на бумаге, а попрограммистски – на компьютере и на Си-шарпе. Надеюсь, это занятие доставит вам немало удовольствия!
Впрочем, мы постараемся совместить приятное с полезным, ведь наша
главная задача – отработать знания и умения по языку программирования
Си-шарп.
Несмотря на сравнительно небольшой объём книги, она охватывает все
основные элементы языка Си-шарп. В самом её начале вы найдёте Тематический указатель, который поможет вам ориентироваться во всех проектах и легко находить нужный.
Все проекты (а их несколько десятков) условно разделены на четыре
группы – словесные, секретные, числовые и комбинаторные. Лучше и правильнее выполнять их последовательно, хотя это и необязательно. В конце каждой главы имеются упражнения для самостоятельной работы.
Многие проекты представлены в двух вариантах – консольном и графическом (Windows Forms), так что вы можете выбрать тот, который вам больше по душе. А ещё лучше – переделывайте готовые приложения «под себя». Это самый лучший способ изучения языка Си-шарп.
Валерий Рубанцев
6
Условные обозначения, принятые в книге:
Дополнение, примечание
7
Предложение, ненавязчивое требование
Предупреждение
Задание для самостоятельного решения
Папка с исходным кодом приложения
Все исходные коды находятся в папке _Projects.
Пиктограммы элементов управления
Оглавление
ТОТАЛЬНЫЙ ТРЕНИНГ ................................................................................................. 2
От автора........................................................................................................................... 4
Оглавление ...................................................................................................................... 8
Полное оглавление ...................................................................................................... 9
Тематический указатель ............................................................................................ 12
СЛОВЕСНЫЙ ТРЕНИНГ ................................................................................................ 15
Словарный запас .......................................................................................................... 15
Слова и дела в Си-шарпе........................................................................................... 16
Глава #1. Вначале было Слово…............................................................................. 18
Палиндромы, или Слова задом наперёд ......................................................... 19
Проект Палиндромная программа (Palindrome) ............................................ 25
Проект Палиндромы .............................................................................................. 31
Проект Детский лепет (Мама) ............................................................................ 37
Глава #3. Новые приключения неуловимых слов .......................................... 44
Проект Занимательная транслитерация (Словари)....................................... 44
Проект Занимательная латиница (Словари) ................................................... 48
Глава #5. Занимательная логопедия ................................................................... 51
СЕКРЕТНЫЙ ТРЕНИНГ .................................................................................................. 57
Глава #8. Занимательная криптография ............................................................. 57
Проект Простая литорея (Литорея) ................................................................... 57
Литорея мудрая ......................................................................................................... 63
Проект Тарабарская грамота ................................................................................ 65
ЧИСЛОВОЙ ТРЕНИНГ .................................................................................................... 72
Глава #14. Простые числа ....................................................................................... 72
Проект Решето Эратосфена (Numbers) ............................................................. 72
Проект Простые числа (Numbers) ..................................................................... 80
Глава #15. Занимательная математика ................................................................ 86
Проект Числа Фибоначчи (Numbers).................................................................. 86
Проект Наибольший общий делитель, НОД (Numbers) ............................. 93
Проект Наименьшее общее кратное, НОК (Numbers) ................................ 100
КОМБИНАТОРНЫЙ ТРЕНИНГ .................................................................................. 106
Глава #18. Занимательная комбинаторика ....................................................... 106
Проект Генерируем перестановки (Permutation) ......................................... 107
Проект Как собрать Дрим тим? (Subset) .........................................................113
Литература ........................................................................................................................119
8
Полное оглавление
ТОТАЛЬНЫЙ ТРЕНИНГ
От автора
Оглавление
Тематический указатель
2
4
8
11
СЛОВЕСНЫЙ ТРЕНИНГ
Словарный запас
Слова и дела в Си-шарпе
Глава #1. Вначале было Слово…
Палиндромы, или Слова задом наперёд
Проект Палиндромная программа (Palindrome)
Проект Палиндромы
Проект Детский лепет (Мама)
Глава #2. Фракционирование, или Слова мелкого и крупного помола
Проект Fraction
Проект Фракционирование
Кроссворд от Винни-Пуха
Проект Классная библиотека (rv)
Проект Практика – критерий истины (Словари)
Проект Каркас слов (Словари)
Проект Гласность (Словари)
Проект Разнобуквицы (Словари)
Проект Буквопорядок (Словари)
Глава #3. Новые приключения неуловимых слов
Проект Занимательная транслитерация (Словари)
Проект Занимательная латиница (Словари)
Проект Супернаборщик (Словари)
Проект Наборщик (Словари)
Проект Анаграммы (Словари)
Проект Играем в прятки со словами (Словари)
Проект Палиндромоиды (Словари)
Проект Метаграммы (Словари)
Проект Цепочки метаграмм (Словари)
Проект Крутые цепи (ЦепочкиМетаграмм2)
Проект Анатомирование слов, или Шарады (Словарь)
Проект Телефонный номер (Словари)
Красная кнопка
14
14
15
17
18
24
30
36
43
44
47
52
55
63
68
78
81
86
97
97
101
103
106
108
118
123
130
140
151
182
192
204
9
Глава #4. Тыблоки и яквы
Глава #5. Занимательная логопедия
Глава #6. Занимательная география
Проект Компьютерный навигатор (Города)
Проект Рекурсивный навигатор (ГородаРекурс)
Проект Чайнворды (Chainword)
Проект Играем в города (Города2)
Глава #7. Исправляем АШИПКИ и ОЧЕПЯТКИ
Проект Логогрифы
Словесные дистанции
Проект Алгоритм Левенштейна (Логогрифы)
225
229
235
237
244
248
254
261
262
275
276
СЕКРЕТНЫЙ ТРЕНИНГ
Глава #8. Занимательная криптография
Проект Простая литорея (Литорея)
Литорея мудрая
Проект Тарабарская грамота
Проект XORный текст (XOR)
Глава #9. Занимательная тарабарщина
Проект Тарабарский язык
Глава #10. Шифр Льюиса Кэрролла
Проект Компьютерный шифровальщик (Carroll)
Проект Код Цезаря (Caesar)
Глава #11. Взлом паролей
Проект Пароль
Проект Взломщик паролей (Codebreaker)
Глава #12. Числобусы (Alphametics)
Проект Числовые ребусы (Alphametics)
Проект Мани-мани (Alphametics)
285
285
285
291
293
296
306
307
311
313
320
326
327
331
335
335
339
ЧИСЛОВОЙ ТРЕНИНГ
Глава #13. Какие бывают числа
Как это будет по-римски?
Проект Римские числа (Rome)
Проект Шиворот-навыворот (Arabic)
Глава #14. Простые числа
Признаки делимости
Проект Решето Эратосфена (Numbers)
Проект Простые числа (Numbers)
Проект Суперпростые числа (Numbers)
356
356
361
362
366
373
373
376
384
388
10
Проект Разложение числа на простые множители (Numbers)
Глава #15. Занимательная математика
Проект Вычисление числа π (Numbers)
Проект Числа Фибоначчи (Numbers)
Проект Наибольший общий делитель, НОД (Numbers)
Проект Наименьшее общее кратное, НОК (Numbers)
Проект Факториал (Numbers)
Глава #16. Степенные забавы
Проект Высокая степень искусства (Power)
Проект Числа Армстронга (Armstrong)
Глава #17. Компьютерная геометрия
Проект Близкие соседи (MinDist)
Проект Пускаем пузыри (Пузыри)
391
395
395
402
409
416
417
428
428
431
451
451
464
КОМБИНАТОРНЫЙ ТРЕНИНГ
Глава #18. Занимательная комбинаторика
Проект Генерируем перестановки (Permutation)
Проект Как собрать Дрим тим? (Subset)
Проект Разменный пункт (Разбиения)
Проект Разбиения множества (SetPartitions)
Проект Наша марка! (Марки)
Проект Шахматное домино (DominoTiling)
Глава #19. Задача Иосифа Флавия
Семеро смелых
Проект Ударим Си-шарпом по… (Josephus Problem)
По порядку номеров – рассчитайсь!
Глава #20. На все сто!
Проект Плюс-минус сотня (_123456789)
479
479
480
486
492
507
523
529
555
556
560
573
575
576
Ответы
Кроссворд от Винни-Пуха
Кроссворд Слово в слове
Цепочка метаграмм Папа на коне
Факториальные нарциссы
Зигзаг слов
Криптокроссворд
Числовые ребусы
Расставить знаки
Литература
597
597
597
597
598
598
599
600
600
601
11
Тематический указатель
Элементы языка C#
Идентификаторы
Выражения
Проекты
*
*
Комментарии //, ///
*
Директива using
Палиндромная программа, Классная библиотека, Практика – критерий истины, Высокая
степень искусства, Ударим Си-шарпом по…
Пространство имен
namespace
Классная библиотека, Практика – критерий
истины
Логический тип bool
Палиндромная программа . . .
Символьный тип
char/Char
Палиндромы . . .
Целый тип int, Int32
*
Целый тип Int64 , long
Мани-мани, Разложение чисел на простые
множители, НОД, НОК
Вещественный тип double Вычисление числа пи, Близкие соседи, Пускаем
пузыри, Ударим Си-шарпом по…
Массивы []
Палиндромная программа . . .
Константы const
Fraction, Каркас слов, Гласность, Тарабарский
язык, Пароль, Близкие соседи. . .
Переменные
Локальные переменные
*
Ссылочные и значимые
типы данных
Операторы и операции
присваивания
= =+ =- *= /= %=
Операции отношения
< > == != <= >=
Логические операции
&&, || и !
Арифметические операции
Факториал, Шахматное домино. . .
*
*
*
*
12
+-*/%
++ -Условный оператор if
Вложенные
условные
операторы
Условная операция ? :
Оператор множественного выбора switch/case
Цикл for
Цикл while
Цикл do-while
*
Алгоритм Левенштейна
Шиворот-навыворот, Пускаем пузыри
Цикл foreach
Вложенные циклы
Оператор break
Оператор continue
Структуры struct
Палиндромная программа . . .
Палиндромная программа . . .
Пускаем пузыри, Мани-мани, Простые числа,
Решето Эратосфена, Разложение чисел на
простые множители
Палиндромы. . .
Простые числа. . .
Палиндромная программа . . .
Детский лепет, Цепочки метаграмм . . .
Близкие соседи, Пускаем пузыри
Классы
rv, rvGrid, Близкие соседи
Поля
Методы
Свойства
rv, rvGrid, Близкие соседи, Шахматное домино.
Ключевое слово void
*
Ключевое слово return
*
Шрифты Font FontStyle
Ударим Си-шарпом по…
Структура Point
Близкие соседи, Пускаем пузыри
Класс Array
Палиндромная программа, Анаграммы
Класс ArrayList
Палиндромы, Фракционирование, Классная
библиотека, Практика - критерий истины,
Мани-мани, Близкие соседи
Класс BitArray
Решето Эратосфена
Класс Console
Все консольные приложения
Класс Dictionary
Крутые цепи, Мани-мани, Римские числа
Класс HashSet
Каркас слов, Разнобуквицы, Палиндромоиды,
Шарады
Класс List
Анаграммы, Метаграммы, Цепочки мета-
13
грамм, Мани-мани, Близкие соседи, Пускаем
пузыри
Класс Math
Логогрифы, Простые числа, Близкие соседи,
Пускаем пузыри
Класс Random
Чайнворды, Тарабарская грамота, Пароль,
Близкие соседи, Пускаем пузыри
Класс SortableDictionary
Анаграммы
Класс SortedSet
Буквопорядок, Мани-мани
Класс string/String
Палиндромная программа . . .
Класс StringBuilder
Палиндромная программа, Палиндромоиды,
Компьютерный шифровальщик
Если после название проекта стоит многоточие . . ., значит, элемент многократно используется и в следующих проектах.
14
СЛОВЕСНЫЙ ТРЕНИНГ
Если вы интересуетесь головоломками, задачками и прочими пазлами, то,
конечно, знаете, что большинство из них прочно связано со словами. Тут
тебе и кроссворды всех мастей и национальностей, и чайнворды, и метаграммы, и логогрифы, и шарады, и ребусы, и даже игра Виселица! И как теперь не веселиться при таком богатстве выбора?
Словарный запас
Словарный запас за язык не тянет.
Компьютерная поговорка
В любых словесных играх преимущество имеет тот игрок, чей словарный
запас больше. Это и понятно – есть из чего выбирать! С другой стороны,
всех слов не знает никто, да и знать их ни к чему. В наших проектах мы будем придерживаться этой позиции.
В качестве основы мы примем Толковый словарь русского языка Ожегова и
Шведовой [ОШ].
В папке _СЛОВАРИ вы найдёте ещё два дополнительных словаря.
Попробуйте воспользоваться ими, если вам придётся разгадывать
трудные, редкие слова.
В словаре makarov_frc.txt буква Ё везде заменена буквой Е, имейте
это в виду.
В русской головоломной литературе традиционно используются имена
существительные, нарицательные, в единственном числе (или во множественном, если единственное число отсутствует, - штаны, ножницы, шахматы), в именительном падеже. Специальные термины, ненормативная
лексика и тому подобные слова, как правило, не употребляются.
В некоторых словесных играх и головоломках вместо отдельных слов
можно брать какие-либо фразы, пословицы, названия книг, фильмов и так
далее. А в кроссвордах, например, допускаются и слова из названий или
фраз, которые не являются существительными. Также широко употребляются имена собственные.
Мы по возможности будем ограничивать свой познавательный пыл существительными из словаря Ожегова и Шведовой.
15
Слова и дела в Си-шарпе
Как бы ни был хорош словарь Ожегова и Шведовой, но в компьютер, даже
самый современный, его не засунешь – тут нужен список слов в текстовом
формате TXT. Не пугайтесь, добрые люди в лице автора этой книги уже извлекли все нужные слова и бережно сохранили их в файле OSH-W97.txt, то
есть вам остаётся только писать замечательные словесные проекты!
Впрочем, компьютер ни рожна не понимает в простых человеческих словах, поэтому нам придётся переводить все наши желания в программы на
языке C#. А в нём для работы со словами нам пригодятся такие типы данных:
char – структура для хранения одного символа Юникода; в нашем случае –
буквы русского языка.
string – класс, объекты которого могут хранить очень длинные последовательности символов Юникода. Например, отдельные слова или целые
предложения вместе со знаками препинания.
StringBuilder– класс для конструирования строк из отдельных символов
или слов.
Вопрос: в каком из этих типов данных мы будем хранить наш список слов?
– В принципе, можно загнать весь словарь в одну строку, но тогда пользоваться им будет крайне неудобно. Более того, если мы посмотрим, как слова располагаются в самом текстовом файле
АБАЖУР
АБАЗИНЕЦ
АБАЗИНКА
АББАТ
АББАТИСА
АББАТСТВО
АББРЕВИАТУРА
АБЕРРАЦИЯ,
то их последовательность живо напомнит нам одномерный массив строк
string[] list;
Для удобства его можно заменить экземпляром класса Array:
Array list;
16
Не менее остроумно представить список слов – в виде списка слов:
List<string> list;
Но, как мы знаем из в классической литературы, Агафья Тихоновна в подобном случае размышляла так:
Если бы губы Никанора Ивановича да приставить к носу Ивана
Кузьмича, да взять сколько-нибудь развязности, какая у Балтазара Балтазарыча, да, пожалуй, прибавить к этому ещё дородности
Ивана Павловича - я бы тогда тотчас же решилась.
Мы последуем её благим намерениям и воспользуемся для хранения слов
классом ArrayList, который весьма удачно сочетает достоинства массивов и
списков, но иногда мы будем принимать и более сильнодействующие
структуры данных – словари типа Dictionary и SortableDictionary.
17
Глава #1. Вначале было Слово…
Как только люди научились писать буквами (а это радостное для нас событие произошло не сразу, а немного погодя, ведь сначала люди употребляли рисунки-пиктограммы, а затем иероглифы), они тут же начали подмечать в словах странности, особенности и закономерности. Например,
маленькие дети лепечут слова, состоящие из двух одинаковых половинок:
мама, папа, дядя, ням-ням (Рис. 1.1)… А некоторые «взрослые» слова читаются одинаково в обе стороны. Так давайте же начнём наше компьютерное знакомство со словами именно с них!
Рис. 1.1. Ням-ням
18
Палиндромы, или Слова задом наперёд
Смотри вперёд,
хоть пятишься назад!
Рачье кредо
19
Палиндромное дело в Пенькове
Слова, фразы, числа и вообще любые последовательности символов, которые читаются одинаково слева направо и наоборот, называются палиндромами. Это слово составлено из двух греческий корней - palin (πάλιν снова) и dromos (δρóμος - путь, направление) и буквально значит бегущий
назад.
Первые палиндромы и появились в Древней Греции, более двух тысяч лет
тому назад. Ими украшали амфоры, чаши, вазы и другие предметы округлой формы. Такие палиндромные надписи можно было читать в обе стороны, поворачивая сосуд в руках.
А самый известный из древних палиндромов придумали римляне, которые упаковали его в словесный магический квадрат:
Sator
Arepo
Tenet
Opera
Rotas
Появление этого палиндрома датируется 79 годом нашей эры, а переводится он так: Сеятель Арепо держит колёса в деле.
Палиндром одинаково читается не только по горизонтали, но и по вертикали. Необыкновенные свойства квадратного палиндрома так поразили
людей того времени, что они считали его магическим и наносили на стены
жилищ и монастырей, писали на амулетах.
Много тысячелетий спустя он послужил образцом для самой популярной
современной головоломки со словами - кроссворда.
20
Особенно популярны стали палиндромы в средние века, из коих и дошли
до нас такие палиндромные фразы:
Signa, te signa, temere me tangis, et agnis Roma tibi subito montibus ibit amor.
(Говорят, что её произнес Сатана)
Otto tenet mappam, madidam mappam tenet Otto.
Отто держит карту, мокрый Отто держит карту.
В России палиндромы появились не ранее 17-го века, а палиндромные
стихи тогда называли рачьими – по аналогии с ретроградными членистоногими.
В истории человечества мы легко отыщем примеры и несловесных
палиндромов (Рис. 1.2). Обратите внимание: они не всегда симметричные, но обязательно равносмыленные с обоих концов.
Российский герб
Двуликий Янус
21
Рис. 1.2. Сказочная зверушка тяни-толкай
Кто мешает тебе выдумать
порох непромокаемый?
Козьма Прутков
Впервые мы знакомимся с палиндромами в замечательной сказке Алексея
Толстого Золотой ключик, или Приключения Буратино. Помните, как
Мальвина диктует своему дубовому ученику Буратино (Рис. 1.3) предложение А роза упала на лапу Азора? Она называет эту фразу волшебной, потому что она читается точно так же и в обратную сторону. А придумал её
русский поэт Афанасий Фет!
Рис. 1.3. О-о-пс!
Другой известный исторический палиндром принадлежит перу Г.
Державина: Я иду с мечем судия.
В литературе вы найдёте множество примеров фраз-палиндромов (или более патриотично – перевёртышей, перевертней), порой очень забавных
и даже ненормативных.
Словарь русского языка Т.Ф.Ефремова даёт вот такое курьёзное
толкование этому слову. ПЕРЕВЕРТЕНЬ - м. местн. Тот, кто изменил
своим убеждениям.
Но – придумывание таких афоризмов – настоящее искусство, которое совершенно не поддаётся алгоритмизации, поэтому мы поставим перед собой чисто техническую задачу – отыскать слова, которые не изменяются
при чтении наоборот. Их тоже называют палиндромами, и вы наверняка
знаете немало таких слов. Например, РОТОР, ШАЛАШ, КАБАК. Чтобы найти
все такие слова, достаточно внимательно просмотреть словарь русского
языка, но мы делегируем это пагубное занятие компьютеру.
Палиндромы можно найти во многих языках мира. Например, в английском:
CIVIC, RADAR, LEVEL, ROTOR, KAYAK, REVIVER, RACECAR, REDDER.
Но самым длинным английским словом-палиндромом считается
TATTARRATTAT, которое зафиксировано в Оксфордском словаре. В
книге рекордов Гиннесса приводятся и другие рекордсмены:
DETARTRATED, ROTAVATOR (название фирмы), REDIVIDER,
MALAYALAM (язык индийского племени малаяли).
Несколько слов-палиндромов из немецкого языка: nun, stets,
neben, Elle, Ebbe, Ehe и Reliefpfeiler.
А самым длинным в мире палиндромом признано финское слово
SAIPPUAKIVIKAUPPIAS (поставщик мыльного камня), которое используется и по сей день. Еще длиннее производные от него слова
SAIPPUAKALASALAKAUPPIAS и SAIPPUAKUPPINIPPUKAUPPIAS. Эстонское слово KUULILENNUTEETUNNELILUUK также претендует на этот
титул, но в этом качестве нигде не отмечено.
В голландском издании книги Гиннесса присутствует слово
KOORTSMEETSYSTEEMSTROOK (термометр). Голландское же слово
POTSTALMELKKOORTSPILSTAALPLAATSLIPSTROOKKLEMLATSTOP и того
больше, но оно просто составлено из других слов и собственного
значения не имеет.
22
Конечно, более интересны палиндромные фразы:
Was it a rat I saw?
A nut for a jar of tuna.
Ma is as selfless as i am.
Dammit, I'm mad!
Rats live on no evil star.
Английский язык
ΝΙΨΟΝ ΑΝΟΜΗΜΑΤΑ ΜΗ ΜΟΝΑΝ ΟΨΙΝ
Греческий язык
Ein Neger mit Gazelle zagt im Regen nie.
Ade, liebe Ella, red' nie in der Allee bei Leda!
Grasmitte, da kniet ein Kadett im Sarg.
Немецкий язык
В них пунктуация и пробелы между словами не учитываются.
Может быть, вам попадались на глаза известные английские выражения-палиндромы:
Able was I ere I saw Elba Noting the first exile of Napoleon to Elba.
(Я был силён, пока не увидел Эльбу. Это, якобы, сетования Наполеона.)
A man, a plan, a canal, Panama.
(Палиндром, составленный по горячим следам аферы с Панамским
каналом)
Madam, I'm Adam или Madam in Eden, I'm Adam.
(Мадам, я – Адам. Райское первознакомство)
Нам, естественно, более интересны русские высказывания:
Водовозу - руку кукурузоводов.
Лезу на санузел.
Лису кум укусил.
Маловаты пока копыта волам.
Манит рак к картинам.
Лёша на полке клопа нашёл.
Нажал кабан на баклажан.
Случаются палиндромные имена:
23
ADA, ANNA, BOB, EVE, HANNAH, OTTO, АННА, АЛЛА, НАТАН, ТИТ.
и фамилии:
Нилин, Аникина.
А вот палиндромные имена-фамилии:
Лон Нол (1913–1985) - бывший премьер-министр Камбоджи.
Нисио Исин (Nisio Isin, NisiOisin, настоящее имя Nishio Ishin) – японский писатель и автор манга-книг.
Как мы видим, некоторые личности намеренно берут себе палиндромные псевдонимы. К Нисио Исину можно добавить актёра Роберта Требора (Robert Trebor), урожденного Роберта Шенкмана
(Robert Schenkman). Другим такое богатство обеспечивают родители. Например, американскому филологу Revilo P. Oliver и американскому автору сам не знаю чего Mike Kim. Особенно этим похвальным качеством отличаются финские родители: Olavi Valo, Emma
Lamme, Sanna Rannas, Anni Linna, Asko Oksa.
Stanley Yelnats – имя одного из героев рассказа Луиса Закара (Louis
Sachar) Holes (1998) , экранизированного в 2003 году.
Некоторые литературные деятели умудряются писать палиндромные стихи и рассказы. В этой связи хорошо известны два рассказа
на английском языке - Dr Awkward & Olson in Oslo (Доктор Оквард и
Олсон в Осло), который Л.Левин (Lawrence Levin) написал в 1986
году, состоит из 31 954 слов, и Veritas (1980), принадлежащий перу
Дэвида Стивенса (David Stephens), - 58795 слов. На французском
языке написан рассказ Grand Palindrome (1969), в котором 5556
букв. Есть и другие, менее «значительные» произведения в этом
жанре.
В 1912 году Велимир Хлебников написал первое палиндромное
стихотворение на русском языке, которое так и называется Перевертень:
Кони, топот, инок.
Но не речь, а чёрен он.
24
Идем, молод, долом меди.
Чин зван мечем навзничь.
Голод, чем меч долог?
Пал, а норов худ и дух ворона лап.
А что? Я лов? Воля отча!
Яд, яд, дядя!
Иди, иди!
Мороз в узел, лезу взором.
Солов зов, воз волос.
Колесо. Жалко поклаж. Оселок.
Сани, плот и воз, зов и толп и нас.
Горд дох, ход дрог.
И лежу. Ужели?
Зол, гол лог лоз.
И к вам и трем с Смерти-Мавки.
25
Отдали
должное
подобным
стихотворениям
И.Сельвинский, С.Кирсанов, А.Вознесенский.
В.Брюсов,
Проект Палиндромная программа (Palindrome)
Говори прямо!
Кузьма Протков
Теперь, когда мы знаем о палиндромах достаточно много, давайте напишем приложение Palindrome для их поиска. Задача для нас очень простая,
но над алгоритмом программы необходимо немного подумать.
Сравним обычное слово и палиндром:
ПИРАТ ПОТОП
1. Переписываем слова справа налево и сравниваем между собой каждую пару. Для первого слова получаем: ПИРАТ  ТАРИП, для второго: ПОТОП  ПОТОП. Очевидно, что слово тогда и только тогда является палиндромом, когда слова в паре совпадают. Отсюда вытекает
первый способ опознавания палиндромов:
char[] s = word.ToCharArray();
Array.Reverse(s);
if(word == new string(s))
Console.WriteLine(word);
Тот же самый способ можно реализовать и более привычно, то есть
сформировать пару к исходному слову, переписав его в обратном
направлении (Рис. 1.4):
StringBuilder sb = new StringBuilder();
for (int i = 0; i < len; ++i)
{
sb.Append(word[len - i - 1]);
}
if(word == sb.ToString())
Console.WriteLine(word);
В этом случае следует использовать именно класс StringBuilder, а не
String, чтобы не замедлять набор строки.
Рис. 1.4. Переворачиваем слово
2. В палиндроме одинаковые буквы расположены симметрично относительно середины слова, а в обычном слове эта закономерность отсутствует. Значит, нам достаточно сравнить первую половину
26
букв со второй (если в слове нечётное количество букв, то букву в
середине слова ни с какой другой сравнивать не надо).
//длина слова:
int len = word.Length;
//слово-палиндром?
bool flg=true;
for (int i = 0; i < len / 2; ++i){
char ch1 = word[len – i - 1];
char ch2 = word[i];
if (ch1 != ch2){
//не палиндром:
flg = false;
break;
}
}
//палиндром:
if (flg) Console.WriteLine(word);
Первая буква слова word имеет нулевой индекс, а вовсе не первый,
как можно было бы ожидать!
На Рис. 1.5 этот процесс показан «на пальцах».
Вы можете выбрать тот способ, который вам больше по вкусу. Поскольку
все палиндромы удаётся обнаружить при однократном просмотре словаря, то сравнивать их эффективность смысла нет – и тот, и другой закончат
поиск практически одновременно.
С одним словом все понятно, но нам нужно просмотреть все слова русского
языка, то есть мы должны последовательно загружать с диска и проверять
все слова из файла. Весь процесс загрузки файла и поиска палиндромов мы
вынесем в отдельный метод palindromes:
27
28
Рис. 1.5. Ищем палиндромы
//ИЩЕМ ПАЛИНДРОМЫ В СПИСКЕ СЛОВ
static void palindromes(string fn){
Console.WriteLine("");
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("Палиндромы:");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine("");
//открываем файл словаря для чтения:
using (StreamReader r = File.OpenText(fn)){
string word = null;
//считываем слова из файла:
while (true){
//считываем очередное слово из файла:
word= r.ReadLine();
if (word == null) break;
//Console.WriteLine(word);
//длина слова:
int len = word.Length;
//первый способ
char[] s = word.ToCharArray();
Array.Reverse(s);
if(word == new string(s))
Console.WriteLine(word);
//второй способ
bool flg = true;
//слово-палиндром?
for (int i = 0; i < len / 2; ++i)
{
char ch1 = word[len - i - 1];
char ch2 = word[i];
if (ch1 != ch2)
{
//не палиндром:
flg = false;
break;
}
}
//печатаем найденный палиндром:
if (flg) Console.WriteLine(word);
} //while (word != null);
}
Console.Read();
}//palindromes
Обратите внимание на переменные ch1 и ch2, в которые записываются символы очередного слова, симметричные относительно его
середины. Без них можно обойтись, но, согласитесь, так программа
читается куда легче!
В листинге оставлены оба способа поиска палиндромов, поэтому
каждый из них будет найден дважды. Не думаю, что в этом есть
необходимость, поэтому закомментируйте тот способ, который вам
претит.
В данном случае мы точно знаем, что в словаре 27407 слов, поэтому нам
достаточно цикла for, чтобы загрузить все слова из файла. Однако не всегда известно, сколько именно строк в файле, поэтому мы организовали
бесконечный цикл while и проверили в нём каждое новое слово. Если считано пустое слово, значит, файл закончился. Дальше действие метода
должно быть вам понятно и без дополнительных объяснений.
29
Если вы хотите проконтролировать процесс загрузки файла, то раскомментируйте строку:
//Console.WriteLine(word);
Тогда каждое новое слово будет напечатано в текстовом окне. Конечно,
словарь загрузится и без нашего наблюдения, но при отладке программы
совсем неплохо «присмотреть» за её работой.
Итак, программа написана, запускаем её!
30
static void Main(string[] args){
//заголовок окна:
Console.Title = "Палиндромы";
//загружаем словарь в массив:
string fileName="OSH-W97.txt";
palindromes(fileName);
}//Main
Основная часть программы очень короткая. Мы просто передаём в метод
palindromes название файла со словарём, а уже в нём мы открываем файл с
помощью метода OpenText класса File и последовательно загружаем слова в
строковую переменную word. Наш алгоритм проверяет слово и, если оно
является палиндромом, печатает его в текстовом окне (Рис. 1.6, слева). Результаты мы получаем практически мгновенно.
Исходный код программы находится в папке Palindrome.
Свинский палиндром!
Проект Палиндромы
Для разового применения вполне достаточно консольного варианта программы. То же самое относится и к приложениям, которыми будете пользоваться только вы. Однако такой недружественный интерфейс вряд ли
порадует ваших друзей и коллег, которым будет трудно понять, как работает программа и что они должны сделать, чтобы она заработала. Поэтому
я предлагаю написать вариант программы с графическим интерфейсом, то
есть приложение Windows Forms. Его окончательный вид вы можете видеть на Рис. 1.6, справа.
Далее мы используем его как заготовку, поэтому вполне можем позволить
себе и некоторый кнопочный изыск в виде картинок.
Рис. 1.6. Вот они - перевёртыши!
31
Все элементы управления мы сведём в одну таблицу, по которой вы легко сумеете сконструировать весь интерфейс.
Свойства, имеющие одинаковые значения, мы для краткости, сестры таланта, повторять не будем.
Компонент
Форма
Кнопка
Кнопка
Кнопка
Кнопка
Список
Свойство
(Name)
FormBorderStyle
Size
StartPosition
Text
(Name)
BackgroundImage
BackgroundColor
BackgroundImageLayout
Cursor
Location
Size
ToolTip
(Name)
Location
ToolTip
(Name)
Location
ToolTip
(Name)
Location
ToolTip
(Name)
BackColor
Font
Location
Size
Значение
frmPal
FixedToolWindow
316; 500
CenterScreen
Палиндромы
btnDictLoad
 Загрузите!
White
None
Hand
2; 3
72; 72
Загрузить словарь!
btnSaveRes
80; 3
Сохранить список!
btnClear
158; 3
Очистить список!
btnClose
236; 3
Закрыть приложение!
lstRes
White
Microsoft Sans Serif; 9pt
2; 79
306; 394
На кнопках с картинками надписи выглядят неуместно. С другой
стороны, картинки не всегда понятны пользователям, поэтому к
32
ним следует добавить подсказки. А для этого нам понадобится
элемент управления
.
Как мы и договаривались, в таблице не дублируются одинаковые
свойства кнопок. Например, для всех кнопок вы должны загрузить
картинку, размеры всех кнопок одинаковы, и так далее.
И в этом, и во всех остальных приложениях вы не обязаны копировать предлагаемый интерфейс. Он даётся вам лишь как образец, а
вы можете переставить элементы управления так, как вам удобнее
и сподручнее ими пользоваться.
Для вывода на экран списков (строк, чисел) лучше всего подходит компонент список типа ListBox, который занимает на форме главное место.
Для принуждения программы к выполнению стандартных действий мы
установили 4 кнопки. Крайняя кнопка справа закрывает приложение:
//ЗАКРЫВАЕМ ПРИЛОЖЕНИЕ
private void btnClose_Click(object sender, EventArgs e)
{
this.Close();
}
Легко заметить, что в заголовке формы уже имеется кнопка того же
назначения. Таким образом, наша кнопка btnClose не очень-то и
нужна, но обычно ею не пренебрегают во всех приложениях.
Предпоследняя кнопка очищает список от ненужной информации:
//ОЧИЩАЕМ СПИСОК
private void button1_Click(object sender, EventArgs e)
{
lstRes.Items.Clear();
}
Продолжаем кнопочное знакомство с другого конца. Первая кнопка традиционно загружает словарь с диска:
//ЗАГРУЖАЕМ СЛОВАРЬ
private void btnDictLoad_Click(object sender, EventArgs e)
{
//очищаем словарь:
33
dict.Clear();
//загружаем словарь с диска:
OpenFileDialog ofd = new OpenFileDialog();
ofd.Title = "Загрузите словарь!";
ofd.Filter = "Text files (*.txt)|*.txt|All files (*.*)|*.*";
ofd.FilterIndex = 1;
ofd.RestoreDirectory = true;
if (ofd.ShowDialog() == DialogResult.OK)
{
StreamReader sr = new StreamReader(ofd.FileName);
//считываем слова:
string s = null;
while ((s = sr.ReadLine()) != null)
{
dict.Add(s);
}
sr.Close();
sr = null;
}
//ищем палиндромы:
searchPal();
}
Если вы пользуетесь одним-единственным словарем, то эта кнопка
будет лишней, но чаще словарей бывает несколько, так что нужно
обеспечить пользователю удобный доступ к ним. Мы для простоты
предполагаем, что словарь находится в папке с программой, и это
можно «усугубить» строчкой:
//папка с программой:
ofdLoad.InitialDirectory = Application.StartupPath;
Однако во всех программах используются одни и те же словари,
поэтому можно сразу указать путь к папке со словарями.
Для хранения слов мы заведём специальное поле dict:
ArrayList dict = new ArrayList();
Как раз того типа ArrayList, о котором мы говорили выше. Убедитесь,
насколько удобно пользоваться экземплярами этого класса! Нам не нужно
заботиться о размере списка – при необходимости он удлиняется автоматически. А перебирать слова можно с помощью лаконичного цикла:
34
foreach (string word in dict)
И здесь нам опять ничего не нужно знать о числе слов в списке!
Для выбора нужного файла мы создаём в методе btnDictLoad диалоговое
окно (Рис. 1.7).
35
Рис. 1.7. Выбираем словарь
Сразу же после загрузки словаря программа самостоятельно переходит к
поиску в нём палиндромов:
//ИЩЕМ ПАЛИНДРОМЫ
void searchPal()
{
//для всех слов из словаря:
foreach (string word in dict)
{
//длина очередного слова:
int len = word.Length;
bool flg = true;
//слово-палиндром?
for (int i = 0; i < len / 2; ++i)
{
char ch1 = word[len - i - 1];
char ch2 = word[i];
if (ch1 != ch2)
{
//не палиндром:
flg = false;
break;
}
}
//добавляем найденный палиндром к списку:
if (flg)
{
lstRes.Items.Add(word);
}
} //foreach
}
В этом приложении я сохранил только второй способ, а вы поступайте, как
знаете!
Палиндромов в нашем словаре оказалось совсем немного, но дабы не
утруждать свою память запоминанием этого скромного списка, мы
нажмём на последнюю из четырёх кнопок btnSaveRes и сохраним его на
долгую память в файле:
//СОХРАНЯЕМ СПИСОК
private void btnSaveRes_Click(object sender, EventArgs e)
{
SaveFileDialog sfd = new SaveFileDialog();
sfd.Title = "Сохраните список!";
sfd.Filter = "Text files (*.txt)|*.txt";
sfd.FileName = "Палиндромы";
sfd.RestoreDirectory = true;
if (sfd.ShowDialog() == DialogResult.OK)
{
StreamWriter sw = new StreamWriter(sfd.FileName);
//записываем слова:
string s = null;
for (int i=0; i<lstRes.Items.Count; ++i)
{
s= (string)lstRes.Items[i];
sw.WriteLine(s);
}
sw.Close();
sw = null;
MessageBox.Show("Файл " + sfd.FileName + " записан!",
"Палиндромы");
}
36
}
В методе btnSaveRes_Click мы создаём соответствующее диалоговое окно
(Рис. 1.8) - и все дела!
37
Рис. 1.8. Храните списки на диске!
Исходный код программы находится в папке Палиндромы.
Проект Детский лепет (Мама)
Лихо расправившись с перевертнями, мы быстро, но плавно переходим ко
второму приложению, то есть к поиску лепетальных слов. После
палиндромов это занятие покажется вам сущей безделицей.
Как мы выяснили, малые детки причудливо лепечут слова, состоящие из
двух одинаковых половинок. Начинают они с первого человеческого слова
МАМА, а затем из их уст появятся ПАПА, ДЯДЯ, БАБА, ЛЯЛЯ, КАКА, КОКО.
Повзрослев, они пролепечут и более сложные слова: КАНКАН и ВАРВАР.
Постарайтесь продолжить этот список!
А если не получится или затруднения окажутся чрезмерно
затруднительными, то беритесь за новое приложение Мама. Я лично так и
сделал и надеюсь, что вы быстро присоединитесь ко мне.
Интерфейс приложения мы беспардонно скопируем из
предыдущего творения и только слегка покопаемся в его коде.
нашего
Загрузка и выгрузка слов почти не изменились. Мы добавим методам
btnDictLoad_Click и btnSaveRes_Click толику местного колорита:
//ЗАГРУЖАЕМ СЛОВАРЬ
private void btnDictLoad_Click(object sender, EventArgs e)
{
. . .
//ищем мам:
searchMam();
}
//СОХРАНЯЕМ СПИСОК
private void btnSaveRes_Click(object sender, EventArgs e)
{
. . .
sfd.FileName = "Мамы";
. . .
}
Стиралка и закрывалка вообще устояли перед натиском эволюции, так что
нам осталось разобраться с ключевым методом
searchMam.
Удивительное дело: и он почти слепо следует старшему братику:
//ИЩЕМ МАМ
void searchMam()
{
//для всех слов из словаря:
foreach (string word in dict)
{
//длина очередного слова:
int len = word.Length;
if (len % 2 != 0 || len > 8) continue;
bool flg = true;
//слово-мама?
for (int i = 0; i < len / 2; ++i)
{
char ch1 = word[len / 2 + i];
char ch2 = word[i];
38
if (ch1 != ch2)
{
//не мама:
flg = false;
break;
}
}
//добавляем найденное слово к списку:
if (flg)
{
lstRes.Items.Add(word);
}
} //foreach
}
Давайте разбираться, почему новое приложение способно донашивать
наш предыдущий код! А поможет нам в этом очередная картинка (Рис. 1.9),
которая не оставляет ни малейших сомнений в правомерности наших
действий!
Рис. 1.9. Ищем слова-мамы
Ограничение длины слов для поиска условием len > 8 основано на
жизненном опыте и знании русского языка. В других языковых
культурах вполне могут встретиться слова и похлеще, так что вы
можете это условие удалить из кода в случае необходимости. Но
39
вот в английском языке я тоже не нашел шибко длинных мам (Рис.
1.10, справа).
В том же словаре [ОШ] наша программа отыскала всего ничего невнятных
слов (Рис. 1.10, слева).
40
Рис. 1.10. «Детские» слова – русские и английские
Подумайте, что будет с этими словами, если их загнуть в бараний
рог!
Исходный код программы находится в папке Мама.
Вертеть слова – занятие увлекательное, поэтому вы можете продолжить это достойное мероприятие самостоятельно.
1. Берите не одно, а пару разных слов. Среди них также можно
найти палиндромы, даже если ни одно из слов, входящих в пару,
само палиндромом и не является. Два слова как бы дополняют
друг друга до палиндромного состояния. Например, слова КРАН и
АРК, СИФОН-ОФИС, ВОРОНА-НОРОВ, НОРА-БАРОН, ТРОПА-ПОРТ
именно такие. Читать их поодиночке в обратном направлении
бесполезно, но вместе они образуют перевертень, например,
КРАНАРК. Конечно, смысла от этого слияния не добавилось, но зато это упражнение вполне может послужить вам подспорьем при
составлении литературных палиндромов типа ФРАУ И ЛЕДИ
СИДЕЛИ У АРФ.
Для их поиска годится тот же приём, что и в проекте Играем в
прятки со словами, только длинные слова нужно переворачивать,
а короткие должны быть на одну букву короче (не обязательное
требование).
2. Кроме обычных, линейных палиндромов существуют и циклические, или круговертни. Именно такими были фразы на греческих
сосудах.
Поскольку у всех палиндромов совпадают начальная и конечная
буквы, то их вполне можно записать по кругу, выбросив одну из
этих букв (Рис. 1.11).
Рис. 1.11. Круговой КАЗАК
41
Точно так же можно загнуть и слова-мамы без второй половины
(Рис. 1.12). Вот только читаться они будут только в одну сторону.
42
Рис. 1.12. Циклический КАНКАН
Четырёхбуквенные мамы можно записать и на обе стороны.
Зато с одним из подобных слов – ЛЮБЛЮ – связана романтическая
история. Владимир Маяковский подарил Лиле Брик кольцо, на котором были выгравированы ее инициалы – ЛЮБ. Если их читать по
часовой стрелке, то бесконечно повторяется слово люблю (Рис.
1.13). Подарок, достойный поэта!
Рис. 1.13. Любовь – кольцо!
Но нас больше интересуют двунаправленные циклические палиндромы:
ТРЕНЕР
ТОРЕРО
ПЕНСНЕ
РЕФЕРИ
АНАНАС
НИЗИНА
Легко заметить, что эти слова превращаются в настоящие палиндромы, если отбросить крайнюю букву – первую или последнюю.
Но мы вивисекцией заниматься не будем, а загнём их в бараний
рог – чтобы получился круговертень (Рис. 1.14)
Рис. 1.14. Круговертни
Ваша задача – выловить все циклические палиндромы из нашего
словаря. Напишите для библиотеки rvDict метод searchCPal для их
поиска!
43
Глава #3. Новые приключения неуловимых
слов
44
Даже неуловимые мстители - и те боролись с врагами революции целых
три фильма. Так почему бы и нам не продолжить поиски и розыски разных
заковыристых словечек в русском языке? - Пуркуа па, как говорят французы и русский мушкетёр Михаил Боярский! В переводе на общепонятный
язык: Прошу следовать за мной, дартаньяны!
Проект Занимательная транслитерация (Словари)
Транслитерация - это запись русских слов латинскими буквами.
Транслит часто используется для именования различных объектов
компьютерной программы и элементов управления, если программист не знает перевода слов на английский язык или просто хочет
оставить русские слова. Конечно, Си-шарп позволяет записывать
идентификаторы и русскими буквами, но вряд ли стоит пользоваться этой возможностью.
Другие сферы применения транслита: комментарии и сообщения
на русскоязычных сайтах, когда у посетителя отсутствует русская
раскладка клавиатуры; при оформлении загранпаспортов и при переводе русских фамилий в литературных произведениях.
Пример траслитерации мы можем найти в драме Три сестры Антона Павловича Чехова. Федор Ильич Кулыгин, учитель гимназии и
муж Маши рассказывает о курьёзном случае:
В какой-то семинарии учитель написал на сочинении "чепуха ", а
ученик прочел "реникса " - думал, по-латыни написано.
Конечно, в печатном варианте эти два слова совсем не похожи друг
на друга, поэтому совершенно непонятно, как их можно было перепутать. Для прояснения ситуации я изловчился написать чепуху
шрифтом Ukrainian Brush Script – и получилось (Рис. 3.1)!
Рис. 3.1. И правда, реникса!
В книге Сергея Федина [ФС99] вы отыщете немало забавных примеров подобной чепухи!
Давайте напишем приложение, которое будет автоматически переводить
русские слова на «латынь».
Начнём мы его с торжественной установки ещё одной кнопки на форму:
Компонент
Кнопка
Свойство
(Name)
Location
Text
Значение
btnTranslit
313; 340
Транслитерация!
Дальше всё просто. Формируем строковые массивы для замены всех русских букв одной или несколькими латинскими:
45
//ТРАНСЛИТЕРАЦИЯ
private void btnTranslit_Click(object sender, EventArgs e)
{
//русские буквы:
string rusLetters = "АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ";
//транслитерационные "символы":
string[] transLetters = {"A", "B", "V", "G", "D", "E", "YO", "ZH", "Z",
"I", "Y", "K", "L", "M", "N", "O", "P", "R",
"S", "T", "U", "F", "KH", "TS", "CH",
"SH", "SHCH", "'", "Y", "J", "E", "YU", "YA"};
46
Основная проблема транслитерации как раз и таится в массиве
transLetters. Действительно, у некоторых русских букв нет аналогов
в латинском алфавите, поэтому их приходится заменять «подходящими». И заменяют – кто во что горазд, поэтому вы с лёгкостью обнаружите множество примеров разнообразных «переводов» русских слов.
А дальше – ещё проще:
if (lex == null) return;
lstRes.Items.Clear();
//ищем в списке подходящие слова -->
//для всех слов из словаря:
foreach (string word in lex.list)
{
//создаем новую строку:
string s = "";
foreach (char ch in word)
{
int n = rusLetters.IndexOf(ch);
if (n > -1) s += transLetters[n];
}
lstRes.Items.Add(word + " - " + s);
} //foreach
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 27;
}
Мы последовательно просматриваем слова из списка и каждую букву очередного слова заменяем «транслитерационными» символами. Перекодированное слово выводим в компонент lstRes (Рис. 3.2).
47
Рис. 3.2. Русско-русский словарь
Если внимательно посмотреть на массив transLetters, то можно заметить, что некоторые буквы однозначно заменяются транссимволами. Например, А, Б, В. Другие, например, Ё требует два
символа – Y и O, которые уже обозначают другие буквы – Й и О. Таким образом, обратный перевод (декодирование) нельзя провести
однозначно.
Слово ЙОГУРТ при транслитерации превратится в YOGURT, а при
переводе в обратную сторону мы получим два слова: правильное –
ЙОГУРТ и неправильное – ЁГУРТ. В простых случаях достаточно просмотреть словарь и убедиться, что в нём имеется только первый вариант, который и является верным. Конечно, такая однозначность
не всегда достижима.
Исходный код программы находится в папках Транслитерация и Словари.
Проект Занимательная латиница (Словари)
Moya tvoya ne ponimaet!
Из разговора в чате
Занимаясь транслитерацией, вы, конечно, не могли не обратить внимания
на то, что некоторые кириллические буквы совпадают по написанию с латинскими, хотя и не обязательно обозначают один и тот же звук.
Латиницей называют буквы латинского алфавита и слова, записанные такими буквами. Кириллицей – слова, записанные русскими
буквами.
Предположим, что у нас имеются только латинские буквы. Сколько русских слов мы сможем напечатать?
Для определённости мы будем считать, что только русские буквы
АВСЕНКМОРТХ имеют аналоги в латинице.
За основу нового проекта мы возьмём программу Транслитерация, в которую добавим строковую константу ruslatin:
//ИЩЕМ "ЛАТИНСКИЕ" СЛОВА
private void btnLatin_Click(object sender, EventArgs e)
{
//русские-латинские буквы:
const string ruslatin = "АВСЕНКМОРТХ";
В этой строке находятся те русские буквы, которые мы решили считать
«латинскими».
Нам достаточно проверить, входит ли каждая буква очередного слова в
строку ruslatin. Если хотя бы одна буква «чисто русская», то мы такое слово
пропускаем и переходим к следующему. В противном случае выводим
найденное слово в текстовое окно (Рис. 3.3).
48
49
Рис. 3.3. Латинско-русский словарик составлен!
if (lex == null) return;
lstRes.Items.Clear();
//составляем латинско-русский словарь -->
//для всех слов из словаря:
foreach (string word in lex.list)
{
//ищем слова, записанные латиницей:
bool flg = true;
foreach (char ch in word)
{
int n = ruslatin.IndexOf(ch);
if (n == -1) //такой буквы нет!
{
flg = false;
break;
};
}
//нашли "латинское" слово:
if (flg) lstRes.Items.Add(word);
} //foreach
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 27;
}
Как видите, самые длинные русские слова, записанные латиницей, - это
ВЕРХОВЕНСТВО, КОММЕРСАНТКА и ОРКЕСТРАНТКА.
Ну, и конечно, не забывайте ставить новые кнопки!
Компонент
Кнопка
Свойство
(Name)
Location
Text
50
Значение
btnLatin
313; 377
Латиница!
Исходный код программы находится в папках Латиница и Словари.
1. Переделайте программу Транслитерация на два текстовых окна
и займитесь переводами известных произведений на «транслитерационный» язык.
Глава #5. Занимательная логопедия
-Февочка, скажи «ыба»
- Селёдка!
Логопедический диалог из комедии
По семейным обстоятельствам
Некоторые люди неверно произносят отдельные буквы (точнее, звуки, обозначаемые этими
буквами), а один логопеф не выговаривал даже
половину букв русского алфавита, что ничуть
не мешало ему учить других людей правильно
говорить. Иногда это приводило к непониманию, например, названия улиц Кировская и Киевская в его исполнении звучали совершенно
одинаково. В других случаях смысл его речей
был понятен, но смешон. А «смешон» - это как
раз то, что нам нужно!
Логопеф везде заменял букву Д буквой Ф (конечно, он
произносил звуки, а не буквы, но у нас будут как раз буквы): вместо девочка он говорил февочка, вместо будет –
буфет, ну и так фалее.
Если вы сделали (а сейчас мы это и проверим!) самостоятельное задание из главы Тыблоки, то переделать
тыблочную программу в логопефическую вам будет проще простого!
Понятное дело: без графического интерфейса нам не обойтись, поэтому
добавляем к окну по вкусу и нашим возросшим потребностям элементы
управления – два многострочных текстовых поля с метками и одну кнопку
(Рис. 5.1):
Компонент
Форма
Свойство
(Name)
MaximizeBox
Size
StartPosition
Text
Значение
frmLogopef
False
729; 582
CenterScreen
Логопеф
51
Кнопка
Метка
Метка
Многострочное
текстовое поле
Многострочное
текстовое поле
(Name)
Cursor
Font
ForeColor
Location
Size
Text
(Name)
Font
Location
Size
Text
(Name)
Location
Size
Text
(Name)
btnGo
Hand
Microsoft Sans Serif; 12pt; style=Bold
Red
12; 500
140; 32
ПЕРЕВЕСТИ!
label1
Microsoft Sans Serif; 12pt; style=Bold
12; 20
150; 20
Исходный текст:
label2
359; 20
212; 20
Логопефический текст:
rtxSource
Font
ForeColor
Location
Size
Text
(Name)
Microsoft Sans Serif; 12pt; style=Bold
0; 192; 0
12; 52
341; 442
ForeColor
Location
Blue
359; 52
rtxTarget
В левое текстовое поле нужно скопировать текст (или набрать его вручную - при надлежащем трудолюбии и упорстве), а затем нажать кнопку
ПЕРЕВЕСТИ!, которая выполнит перевод текста на логопефический язык и
напечатает его в правом текстовом поле.
//ПРОГРАММА ДЛЯ ПЕРЕВОДА ТЕКСТА НА
//ЛОГОПЕФИЧЕСКИЙ ЯЗЫК
public partial class Form1 : Form
{
…
//НАЖИМАЕМ КНОПКУ ПЕРЕВЕСТИ
private void btnGo_Click(object sender, EventArgs e)
52
{
//исходный текст:
string text = rtxSource.Text;
//логопефический текст:
string logopef = "";
//длина текста:
int len = text.Length;
//во всем тексте заменяем букву Д на Ф:
for (int i= 0; i < len; ++i){
//очередная буква:
char chr= text[i];
if (chr == 'Д') logopef += "Ф";
else if (chr == 'д') logopef += "ф";
else logopef += chr;
}
//печатаем перевод во втором окне:
rtxTarget.AppendText(logopef);
}
}
Важно: буква Д в тексте может быть и строчной, и ПРОПИСНОЙ, что мы и
учитываем в цикле for.
Наш переводчик готов к работе. Для пущего смеху лучше подобрать текст,
в котором много букв Д. Например, в Интернете можно найти
«однобуквицу» про Деда Данилыча (автор OJIesYA_EviL_MonKey), которая
вполне годится для наших экспериментов (Рис. ).
Тексты, все слова которых начинаются на одну и ту же букву, называются тавтограммами. Самая известная тавтограмма: Четыре
чёрненьких чумазеньких чертёнка чертили чёрными чернилами
чертёж - чрезвычайно чисто.
Исходный код программы находится в папке Логопеф.
53
54
Рис. 5.1. Фолгая форога в фюнах!
1. Подберите самостоятельно тексты с буквой Д и переведите их с
помощью нашего Логопефа.
2. Попробуйте сами придумать подобный текст – с учётом того, что
после перевода он должен стать очень смешным.
3. Добавьте к окну программы ещё одну кнопку – СТЕРЕТЬ, чтобы
программой можно было бы пользоваться неоднократно.
4. Как вы помните, киношный логопеф не выговаривал и букву Р,
поэтому её тоже можно заменить буквой Г или Й. Или вообще выбросить из текста.
Известный номер Владимира Винокура Запой тоже построен на
том, что пациент не выговаривал букву Р и потому жаловался доктору на ЗАПОЙ (Рис. 5.2), хотя у него был ЗАПОР.
55
Рис. 5.2. С Винокуром и не такое случалось!
В этой сценке встречается ещё немало смешных слов: егестатуя,
найколог, доктой, огьёмное желание, яз, пуйген. Как видите, юмористом может стать любой чеявек, если научится ковейкать слова!
Рис. 5.3. Чумачечие Потап и Настя (или наоборот?)
Этим приёмом с успехом попользовались Потап и Настя Каменских
(Рис. 5.3) в своей знаменитой песне про чумачечую весну.
5. В некоторых русских говорах вместо Ц произносят Ч: цапля – чапля (откуда и возникла русская фамилия Чаплин, которая не имеет к
Чарли Чаплину никакого отношения, поскольку это наш Цаплин).
6. Писатель-юморист Семён Альтов знаменит не только своими
смешными рассказами, но и особенностями их чтения: он глухие
звуки произносит как звонкие, что очень смешно. Например, канарейка у него стала ганарейгой, парикмахер – баригмакер. Заставьте
программу читать по-альтовски.
7. Как известно, москвичи (и мы вслед за ними) акают, то есть все
безударные О произносят как А, то есть Москва и Россия помосковски МАсква и РАссия. На слух мы уже привыкли к этому коверканью русской речи, но вот в напечатанном тексте это выглядит
– ну, сами узнаете как, когда напишете программу для перевода
русского текста на московский язык.
8. Помните песенку зайца из мультфильма «Ну, погоди»: А ну-ка,
давай-ка, плясать выходи!? Вы легко можете ко всем (или только к
некоторым) словам любого текста добавить частицу ка. Получится
«заячий» текст.
9. Можно перевести текст и на «волчий» язык, если после каждого
слова добавлять ну: Ну, Заяц, ну, погоди, ну!
10. Воспользуйтесь методом Replace, как мы это делали в программе Тыблоко, чтобы сократить код.
56
СЕКРЕТНЫЙ ТРЕНИНГ
Глава #8. Занимательная криптография
Язык дан человеку для того,
чтобы скрывать свои мысли.
Шарль Морис Талейран
Криптография в переводе с греческого означает
тайнопись. Она возникла одновременно с письменностью - для того, чтобы утаивать содержание письма или другого документа. Действительно, обычный текст может прочитать любой грамотный человек, а ведь иногда просто необходимо скрыть важную информацию от посторонних
лиц.
Наука, которая занимается изучением шифров,
называется криптологией и подразделяется на
криптографию (разрабатывает способы шифрования) и криптоанализ
(выполняет обратную задачу – расшифровывает сообщения).
Проект Простая литорея (Литорея)
- Барбамбия! Киргуду!
Загадочные слова из комедии
Бриллиантовая рука
В повести Фриды Абрамовны Вигдоровой Дорога в жизнь, в 21-ой главе У
вас ничего не выйдет рассказывается о криптографической проделке воспитанника детского дома Андрея Репина, который вёл в тетради протокол
собрания. И вот что у него получилось:
Богдащоричи: беврый одвят тефувид бо гдочорой, рдовой бо трову,
дведий бо чегдщике…
Он, конечно, хотел поразить воспитателей своим шифрованным письмом,
но один из них, Алексей Саввич, быстро смекнул:
– Да, тут есть логика. Постойте… Беврый одвят… беврый одвят… да
это же первый отряд! Так… тефувид – дежурит. Понимаете, он
оставил гласные, а остальной алфавит разделил пополам и поменял
согласные местами: вместо п – б, вместо в – р и наоборот…
57
Андрей Репин был посрамлён, но не угомонился. Об этом мы поговорим
дальше, а пока давайте-ка поразмыслим над его тайнописью.
Этот способ шифрования сообщений был известен ещё в Древней Руси и
называется простой литореей (не путайте с лотереей!). В то время букв
было больше, но и наши 33 буквы вполне годятся для шифрования. Правда, букву Ё придется исключить из списка, чтобы осталось чётное число
букв.
Букве Ё вообще не очень-то везёт в русском языке. Её уже не раз
пытались исключить из алфавита, но, к счастью, пока безуспешно.
Зато в 2005 году в городе Ульяновске был открыт памятник этой
славной букве (Рис. 8.1).
Рис. 8.1. Памятник букве Ё в «натуре» и на обложке журнала Наука
и жизнь
А стараниями господина Прохорова у нас появился Ё-мобиль (Рис.
8.2).
Рис. 8.2. Ё-моё! Ё-мобиль!
58
Буква Ё появилась в русском алфавите в 1797 году, так что возраст у
неё почтенный. Советую прочитать подробный рассказ о букве Ё
здесь: http://ru.wikipedia.org/wiki/Ё
Простая литорея называется также тарабарской грамотой. А
название литорея произошло от слова литера – буква.
Теперь расположим буквы в две строки, по 16 букв в каждой так, чтобы
они образовали вертикальные пары:
А Б В Г Д Е Ж З И Й К Л М Н О П
Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
Чтобы закодировать слово, достаточно заменить в нём каждую букву парной в этом шифре. Например, слово КРИПТОГРАФИЯ превратится в
ЪАШЯВЮУАРДШП. Пожалуй, не сразу и догадаешься, что за слово написано, хотя, как вы видите способ шифрования очень простой. Вот только
вручную заменять одни буквы другими довольно утомительно, да и ошибиться можно не раз. Поэтому давайте напишем программу, которая в два
счёта зашифрует любой текст.
Начните новый проект Литорея и скопируйте в него файл формы Form1.cs
из программы Логопеф.
Начинаем священнодействовать, то есть кодировать шифр!
//ПРОГРАММА ДЛЯ КОДИРОВАНИЯ ТЕКСТА
//МЕТОДОМ ПРОСТОЙ ЛИТОРЕИ
public partial class Form1 : Form
{
const string lit1 = "АБВГДЕЖЗИЙКЛМНОП";
const string lit2 = "РСТУФХЦЧШЩЪЫЬЭЮЯ";
Для работы с программой нам понадобятся две кнопки и два текстовых
поля
(Рис. 8.3).
Назначение каждого из них понятно и без пояснений.
Мы добавим только вторую кнопку - СТЕРЕТЬ, - которая имеет те же параметры, что и первая, поэтому в таблице приведены только те свойства, которые нужно исправить:
59
Кнопка
(Name)
Location
Text
btnClear
560; 502
СТЕРЕТЬ
60
Рис. 8.3. Интерфейс на два окошка
Она очищает оба текстовых поля:
//ОЧИСТИТЬ ТЕКСТОВЫЕ ОКНА
private void btnClear_Click(object sender, EventArgs e)
{
rtxSource.Clear();
rtxTarget.Clear();
}
Если нажата кнопка ПЕРЕВЕСТИ!, то мы считываем в переменную text весь
текст из элемента управления rtxSource, а затем последовательно просматриваем всю строку в цикле for.
//НАЖИМАЕМ КНОПКУ ПЕРЕВЕСТИ
private void btnGo_Click(object sender, EventArgs e)
{
//исходный текст:
string text = rtxSource.Text;
//литорейный текст:
string litorea = "";
//длина текста:
int len = text.Length;
//кодируем - заменяем буквы парными:
for (int i= 0; i < len; ++i){
//очередная буква:
char chr= text[i];
chr = char.ToUpper(chr);
int n = lit1.IndexOf(chr);
if (n > -1) // верхняя буква
//заменяем нижней:
litorea += lit2[n];
else
{
n = lit2.IndexOf(chr);
if (n > -1) //нижняя буква
//заменяем верхней:
litorea += lit1[n];
else //буква Ё или другой символ:
litorea = litorea + chr;
}
}
//печатаем перевод во втором окне:
rtxTarget.AppendText(litorea);
}
С помощью метода IndexOf мы легко узнаем, имеется ли символ chr в строках lit1 и lit2, а если имеется, то в какой из них – в первой или во второй. В
зависимости от результата проверки заменяем букву её парой. Букву Ё и
все остальные символы (например, пробелы, латинские буквы, цифры и
знаки препинания) просто копируем в новую строку litorea.
Закончив цикл, мы печатаем эту строку в правом текстовом поле
rtxTarget.
Перевод проходит «без шума и пыли», но все буквы становятся
ПРОПИСНЫМИ (Рис. 8.4).
От этой порчи текста легко избавиться, если в строковые константы lit1,
lit2 добавить и маленькие буквы.
61
62
Рис. 8.4. Толковый перевод!
Декодирование текста можно провести в той же программе. Достаточно
текст из правого поля перенести в левое и нажать кнопку ПЕРЕВЕСТИ!
(Рис. 8.5).
Рис. 8.5. Декодирование прошло успешно!
Исходный код программы находится в папке Литорея.
Литорея мудрая
В знаменитой повести А. Рыбакова Кортик мы также встречаемся с зашифрованной надписью, которая украшала ножны и сам кортик.
Вот что поведала нам глава 53 Ножны:
Мальчики забежали за церковный придел, и Коровин вытащил из кармана ножны.
Миша нетерпеливо выхватил их у него, повертел в руках, затем
осторожно снял ободок и вывернул шарик.
Ножны развернулись веером. Мальчики уставились на них, потом
удивленно переглянулись…
На внутренней стороне ножен столбиками были нанесены знаки:
точки, черточки, кружки. Точно так же, как и на пластинке кортика.
За разгадкой тайны кортика друзья обратились (Глава 56 Литорея) к директору школы Алексею Ивановичу, который и объяснил им, что надпись
на кортике и ножнах представляет собой литорею мудрую, и что надписи
на них можно прочитать, только соединив их вместе.
Так что же такое – литорея мудрая? – Давайте разбираться!
В старой России 30 букв алфавита делили на три равные части, по 10 букв
в каждой. В пределах первого десятка буквы последовательно обозначали
точками (Рис. 8.6).
Рис. 8.6. Буквы-точки
63
Второго – чёрточками (Рис. 8.7), а третьего – кружками или крестиками
(Рис. 8.8).
Как видите, знаки для каждой буквы записывались столбиком. А горизонтальная черта делила столбики пополам. Зная обозначение каждой буквы,
мы можем составить любой текст, например, Литорея мудрая (Рис. 8.9).
64
Рис. 8.7. Буквы-чёрточки
Рис. 8.8. Буквы-кружочки
Рис. 8.9. Надпись литореей мудрой
Теперь закроем нижнюю часть шифровки и попробуем восстановить
текст: Л Д-Й О-Ф О-Ф О-Ф Д-Й Щ-Я М О-Ф Д-Й О-Ф А Щ-Я. Удалось найти
три буквы (они выделены жирным шрифтом), для остальных мы установили только набор возможных значений. Да, задачка оказалась совсем непростой!
Поскольку нам нужны не 30, а все 33 буквы современного русского
алфавита, то у нас в каждой группе будет не по десять букв, а по
одиннадцать. По этой причине максимальная высота столбиков с
символами равна 11. Число нечётное, поэтому пришлось провести
горизонтальную линию так, чтобы в верхней части было до пяти
символов, а в нижней – все остальные.
Осталось разрезать полоску бумаги по горизонтальной линии на две части. Теперь, чтобы прочитать текст, нужно соединить обе части бумажки
по линии разреза. Точно так же было зашифровано сообщение на кортике
и ножнах. Если вы читали повесть А. Рыбакова, то помните, что на них было написано:
Сим гадом завести часы понеже проследует стрелка полудень башне
самой повернутой быть.
Несмотря на название, шифр не очень «мудрый»: некоторые буквы, на
обозначение которых пошло от одного до четырёх символов, остались незакодированными, что помогает расшифровать запись. Насколько помогает – определите сами.
Герои повести справились и с этой загадкой, а нам пора вернуться к тарабарской грамоте.
Проект Тарабарская грамота
Раздаются тары-бары:
"К нам приехали гусары!"
Песенка Трубачи из комедии
О бедном гусаре замолвите слово
Как мы знаем, простая литорея называется также тарабарской грамотой,
65
но есть и другие способы превратить русские тексты в тарабарщину. Этим
достойным делом мы сейчас и займемся.
Начните новый проект Тарабарская грамота и скопируйте в него файл
формы Form1.cs из программы Литорея.
Запишите исходный код программы в папку Тарабарская грамота. Давайте сразу же посмотрим, как работает программа (Рис. 8.10).
66
Рис. 8.10. И вправду полная тарабарщина!
Вы легко обнаружите некоторые изменения в интерфейсе. Во-первых, нам
пришлось увеличить ширину формы и правого многострочного текстового окна, потому что текст, записанный заглавными буквами гораздо шире
обычного:
Форма
Многострочное
текстовое поле
(Name)
Size
Text
(Name)
frmTar
864; 582
Тарабарская грамота
rtxTarget
Location
359; 52
Size
Text
477; 442
Во-вторых, нужно исправить надпись на правой метке.
Этот вид тайнописи наряду с обеими литореями применяли наши далёкие
предки, чтобы скрыть свои мысли и чаяния. На первый взгляд, текст справа написан не на русском языке, а на каком-то иноземном. Однако ни одна
русская буква при этом гуманном эксперименте не пострадала! Их ровно
столько же справа, сколько и слева, и трудно не заметить, что строчки в
правом текстовом поле стали длиннее. Вот в этом-то весь секрет: нужно по
вкусу добавить к русским буквам «тарабарские». Проще всего воспользоваться «европейскими» буквами и знаками, которых нет в русском языке.
Ну вот, с шифром мы разобрались, а теперь за дело!
//ПРОГРАММА ДЛЯ КОДИРОВАНИЯ ТЕКСТА
//МЕТОДОМ ТАРАБАРСКОЙ ГРАМОТЫ
public partial class Form1 : Form
{
const string rus=" АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ";
const string bukvy = "QWRZUIÜSDFGJLÖÄßYVN€£¥Ω∑";
Нам потребуются также русские буквы и знак пробела. Зачем? – Мы будем
вставлять инородные буквы только после русских, а для этого нам нужно
находить среди всех символов текста, в котором могут быть знаки препинания, цифры и служебные символы, русские буквы, Пробел тоже пригодится, потому что он стоит перед первой буквой слова, иначе все слова будут начинаться с правильной буквы. А вот перед начальной буквой строки
поставить другую букву сложнее. В этом случае стоит весь текст записать
одной строкой.
Следующий фрагмент кода программы Литорея остался без изменений, но
при желании вы можете заменить название правого поля более походящим rtxTarabar.
В процедуре, обрабатывающей нажатие кнопки ПЕРЕВЕСТИ!, мы перепишем только те строки, которые занимаются зашифровкой текста:
//НАЖИМАЕМ КНОПКУ ПЕРЕВЕСТИ
private void btnGo_Click(object sender, EventArgs e)
{
Random rand= new Random();
//исходный текст:
67
string text = rtxSource.Text;
//тарабарский текст:
string tarabar="";
//длина текста:
int len = text.Length;
//кодируем - добавляем тарабарские буквы:
for (int i= 0; i < len; ++i){
//очередная буква:
char chr= text[i];
chr = char.ToUpper(chr);
tarabar += chr;
//если это буква или пробел -->
if (rus.IndexOf(chr) > -1){
int n= rand.Next(100);
//если случайное число больше заданного,
//то добавляем к тексту тарабарскую букву:
if (n> 33){
n= rand.Next(bukvy.Length);
chr= bukvy[n];
tarabar += chr;
}
}
}
//печатаем перевод во втором окне:
rtxTarget.AppendText(tarabar);
}
Если вы хотите, чтобы тарабарские буквы добавлялись чаще, то уменьшите число в выражении n > 33, а если реже – увеличьте его.
Исходный код программы находится в папке Тарабарская
грамота.
1. А что же всё-таки написал в протоколе Андрей Репин? Вы будете
крепко озадачены, если раскодируете протокол в нашей программе. Вместо одной тарабарской грамоты вы получите другую:
СЮУФРЙЮАШЗШ: СХТАЛЩ ЮФТПВ ВХДГТШФ СЮ УФЮЗЮАЮЩ,
АФЮТЮЩ СЮ ВАЮТГ, ФТХФШЩ СЮ ЗХУФЙШЪХ
Как же так: мы выяснили, что Андрей Репин для шифрования использовал простую литорею, а она не действует! А дело в том, что
шифр Репина ещё проще, чем тот, который применяли мы. Он оста-
68
вил без изменения все гласные буквы, а согласные записал в две
строчки:
Б В Г Д Ж З К Л М Н
П Р С Т Ф Х Ц Ч Ш Щ
Легко заметить, что он исключил и некоторые другие буквы и
знаки, но сути дела это не меняет.
69
Исправьте программу Литорея, чтобы она одолела, наконец, дешифровку протокола.
2. Способ Андрея Репина легко изменить так, чтобы разгадать шифровку было труднее. Например, можно записать вторую строку букв
в обратном порядке:
Б В Г Д Ж З К Л М Н
П Р С Т Ф Х Ц Ч Ш Щ
3. Через некоторое время заведующий детским домом Семён Афанасьевич получил письмо вот такого содержания:
25 - 19,13 19, 2, 5, 13, 10, 13, 19 - 11, 8, 23,
9, 8 - 3, 11, 13, 18, 40 - 8, 18, 12, 2, 7, 2,
12, 40, 18, 25 -25 - 18, 1, 8, 10, 8 - 21, 14,
11, 21 - 21, 14, 11, 21, 12 - 17 - 5, 19, 8, 9,
17, 13 - 11, 10, 21, 9, 17, 13 – 25 - 11, 2, 7,
19, 8 - 4,50 - 21, 20, 13, 23 19, 8 - 5, 19, 13
- 4, 50, 23, 8 - 17, 19, 12, 13, 10, 13, 18, 19,
8 - 19, 2, 4, 23, 27, 11, 2, 12, 40 - 3, 2 - 7,
2, 5, 17 - 15, 10, 2, 7, 11, 2 - 7, 50 - 5, 19,
8, 9, 8, 9, 8 - 11, 8, 4, 17, 23, 17, 18, 40 19, 8 - 7, 18, 13 - 10, 2, 7, 19, 8 – 21 - 7, 2,
18 - 19, 17, 24, 13, 9, 8 - 19,13 7, 50, 14, 11,
13, 12 - 24, 13, 23, 8, 7, 13, 1 - 15, 10, 13,
6, 11, 13 - 7, 18, 13, 9, 8 - 16, 13, 19, 17, 12
- 18, 7, 8, 4, 8, 11, 21 - 18, 7, 8, 4, 8, 11, 2
- 11,23,25 - 19, 13, 9, 8 - 9, 23, 2, 7, 19, 8,
13 - 7, 50 - 22, 8, 12, 17, 12, 13 - 18, 11, 13,
23, 2, 12, 40 - 7,18,13 - 15, 8 - 11, 10, 21, 9,
8, 5, 21 - 19, 8 - 21 - 7, 2, 18 19, 17, 24, 13,
9, 8 - 19, 13 - 7, 50, 14, 11, 13, 12.
Он тут же хотел обратиться за помощью к Алексею Саввичу, разгадавшему первый шифр Репина (а вы, наверное, догадались, что
письмо был именно от него), но потом решил, что и сам справится с
новой головоломкой.
Заведующему очень помогла догадка: каждое число заменяет одну
и ту же букву. Затем он обратил внимание на то, что некоторые
числа встречаются чаще других, значит, им должны в русском языке
соответствовать буквы, которые также встречаются в словах чаще,
чем другие. Ну, и наконец, иногда буквы образуют характерные сочетания, по которым можно найти короткие слова, а потом …
А вот что было потом, прочитайте в повести Дорога в жизнь. Там вы
заодно и узнаете, почему глава называется У вас ничего не выйдет.
А ещё лучше – постарайтесь сначала самостоятельно прочитать
письмо. Для решения задачи компьютер вам не понадобится, а вот
таблица частоты русских букв вполне может пригодиться:
Пробел
О
Е
А
И
Т
Н
Р
С
В
П
К
Л
М
Д
У
Я
0,2005
0,0764
0,0732
0,0629
0,0577
0,0549
0,049
0,0459
0,0404
0,0355
0,033
0,0302
0,0299
0,0275
0,0265
0,0222
0,0153
Ы
Ь
З
Й
Б
Ч
Г
Ю
Ж
Х
Щ
Ф
Ш
Э
Ц
Ъ
0,0143
0,0138
0,0133
0,0125
0,0114
0,0094
0,0083
0,0081
0,0079
0,0048
0,0042
0,0036
0,0026
0,0023
0,0021
0,0003
Как видите, в этой таблице буква Ё считается как Е, и вызвано это
вовсе не пренебрежением к букве, а особенностями русского книгопечатания.
70
Вы можете отыскать и другие таблицы, в которых данные будут несколько отличаться. Это естественно: подсчёты можно
проводить по-разному. Но в целом и эта таблица даёт верное
представление.
4. Разработайте проект Ё-моё. Из нашего словаря составьте список
слов, в которые входит буква Ё. Задача несложная, но интересная:
вы узнаете, сколько таких слов в русском языке.
5. Добавьте к программе Тарабарская грамота метод, декодирующий зашифрованный текст.
71
ЧИСЛОВОЙ ТРЕНИНГ
Компьютер должен считать,
а человек - думать.
Программистская пословица
Трудно себе представить сколь-нибудь полезную программу, которая
обошлась бы без чисел. И в реальной жизни ситуация с числами «не лучше». Каждый день года обозначается числом, время дня и ночи, дни рождения и телефоны, цены и курсы валют, площадь квартиры в метрах и
квартплата в рублях… Числа везде и всюду!
Числовые головоломки и задачи, может быть, не так популярны и занимательны, как словесные, но и среди мира чисел мы отыщем немало интересного и познавательного для себя!
Глава #14. Простые числа
Будьте проще – и к вам потянутся люди.
Кредо простых чисел
Целые числа и их свойства изучает теория чисел, или высшая арифметика (есть и такая наука!). В занимательных задачах (да и в жизни тоже) нередко нужно быстро определить, делится ли одно число на другое или
нет. При этом сам результат деления неважен. У каждого натурального
числа имеется, по крайней мере, два делителя - это единица и само число.
Если других делителей нет, то число называется простым.
Проект Решето Эратосфена (Numbers)
Как мы уже выяснили, простыми называются натуральные числа, имеющие в точности два разных делителя. Из этого определения следует, что ни
нуль, ни единица к простым числам не относятся. Также очень легко установить, что первое простое число - это двойка, потому что она делится на
единицу и на саму себя (двойка – единственное чётное простое число).
Дальше мы легко найдем тройку, пятёрку, семёрку (кто посмелее, доберётся и до туза). Нам не составит труда продолжить этот ряд: 11, 13, 17, 23,
29, 31. Чтобы отбросить многие составные числа, достаточно воспользоваться признаками делимости, которые мы только что освежили в памяти.
Но проверять большие числа таким «стихийным» способом «опасно», потому что легко ошибиться при делении. На этот случай греческий матема-
72
тик Эратосфен (Рис. 14.1) придумал систематический способ поиска простых чисел, который в его честь назвали решетом Эратосфена.
73
Рис. 14.1. Ἐρατοσθένης ὁ Κυρηναῖος (276 - 194 до н.э.)
Действует он так [ЗП88, Задача 557].
Поиск простых чисел начинается с засыпки чисел в «решето», которое
удобно представить в виде прямоугольной таблицы. Наименьшее число это двойка, поскольку единица к простым числам не относится. А
наибольшее – любое, по вашему выбору. Мы ограничимся первой сотней
чисел (Рис. 14.2).
Находим в таблице двойку – первое простое число – и обводим ее кружком.
Очевидно, что все последующие числа, кратные двойке, простыми быть не
могут, поэтому мы их вычёркиваем. В данном примере мы будем просто
закрашивать клетки с составными числами (Рис. 14.3).
Как видите, уже после первого грубого просеивания в решете осталась
только половина чисел. Продвигаемся дальше по таблице и находим первое после двойки невычеркнутое число. Это тройка – второе простое число. Вычёркиваем всё ещё не вычеркнутые числа, кратные тройке (Рис.
14.4).
74
Рис. 14.2. Решето с первой сотней чисел
Рис. 14.3. Убираем чётные числа
Ну, а дальше всё повторяется. Находим следующее простое число - пятёрку, вычёркиваем числа, кратные пяти. Переходим к семёрке, затем к 11, к 13
и так далее, пока не дойдём до конца таблицы. Все числа в кружках - простые, остальные – составные (Рис. 14.5).
75
Рис. 14.4. Убираем числа, кратные трём
Рис. 14.5. Просеивание закончено!
Просеивание чисел – занятие необременительное и даже весёлое, но всётаки требует некоторого внимания и сноровки, поэтому лучше воспользоваться компьютером, тем более что алгоритм поиска незамысловатый, и
мы без труда переведём его на язык Си-шарпа.
Нам достаточно знать только конец диапазона чисел (поле end), ведь поиск всегда начинается с двойки, а сами натуральные числа мы будем записывать в массив number:
//РЕШЕТО ЭРАТОСФЕНА
class Resheto{
static int[] number;
static int end;
static int prime;
Поле prime мы отведём под текущее простое число.
static void Main(string[] args){
//заголовок окна:
Console.Title = "Решето Эратосфена";
//бесконечный цикл ввода данных //пока пользователь не закроет программу
//или не введет 0:
do{
Console.ForegroundColor = ConsoleColor.Yellow;
Console.Write("Введите конец диапазона: ");
end = Convert.ToInt32(Console.ReadLine());
//если конец диапазона равен 0, то программу закрываем:
if (end == 0) return;
//конец диапазона не меньше двойки:
if (end < 2) end = 2;
//ищем простые числа:
primes(end);
}
while (true);
} //Main
Дальше действуем по алгоритму Эратосфена:
static void primes(int n2){
Console.WriteLine("");
Console.ForegroundColor = ConsoleColor.Red;
Console.WriteLine("Простые числа:");
Console.ForegroundColor = ConsoleColor.Green;
Console.WriteLine("");
1. Записываем все числа, начиная с двойки, в массив:
76
//формируем массив натуральных чисел 2..end:
number = new int[n2+1];
for (int i = 2; i <= n2; ++i)
number[i] = i;
2. Первое простое число равно двум:
prime = 2;
3. «Вычёркиваем» из массива число prime*prime, а затем все числа, начиная
с этого числа через prime:
4 – 6 – 8 - … для prime= 2,
9 – 12 – 15 - … для prime= 3.
И так далее:
do{
for (int i = prime * prime; i <= end; i += prime)
number[i] = 0;
Конечно, мы не можем зачеркнуть число в массиве, поэтому присваиваем
соответствующему элементу массива значение нуль, которое будет означать, что это число составное.
4. Ищем первое «невычеркнутое» число – его значение в массиве должно
отличаться от нулевого:
//ищем следующее простое число:
prime++;
while (prime <= Math.Sqrt(end) && number[prime] == 0)
prime++;
Теперь поле prime содержит следующее простое число.
5. Если prime не превосходит корня квадратного из максимального числа
end, то переходим к пункту 3.
} while (prime <= Math.Sqrt(end));
В противном случае все простые числа в заданном диапазоне найдены, их
значения в массиве - ненулевые. Перебираем весь массив и по этому признаку находим простые числа. Каждое из них печатаем в текстовом окне и
параллельно записываем в файл:
77
//создаем новый файл для записи результатов писка:
using (FileStream fs = new FileStream("primes.txt", FileMode.Append)){
using (StreamWriter w = new StreamWriter(fs, Encoding.UTF8)){
w.WriteLine("Простые числа:");
w.WriteLine("");
//печатаем простые числа в текстовом окне
//и записываем в файл:
for (int i = 2; i <= end; ++i)
if (number[i] != 0){
Console.WriteLine(i);
w.WriteLine(i);
}
w.WriteLine("");
}
}
Console.WriteLine("");
} // primes
Поскольку в методе Main действует бесконечный цикл do-while, то пользователь может и дальше «решетить» простые чисел (Рис. 14.6). Несмотря на
«древность» алгоритма, он действует довольно быстро, но очень жаден до
памяти компьютера.
Рис. 14.6. Решето Эратосфена в действии!
78
Этот пример наглядно показывает нам, что для написания эффективной
программы нужен хороший алгоритм. А если алгоритм имеется, то перевести его на любой язык программирования совсем несложно.
И всё-таки наше решение следует улучшить. Можно вместо массива целых
чисел использовать массив типа bool. Так мы вместо 4 байтов на число затратим только один. Но можно сократить расход памяти ещё в 8 раз, отведя под число всего 1 бит. Для этого нам потребуется экземпляр класса
BitArray. Как известно, бит может принимать только два значения – 0 (false) и 1 (true). Первоначально мы все биты установим в единицу, а по результатам проверки те биты, которые соответствуют составным числам
(их индексы в массиве битов - составные числа), сбрасываем в нуль. Закончив просеивание, мы вновь просматриваем массив и выписываем числа с
единичными битами.
Вот такой алгоритм. Что же касается интерфейса программы, то я предлагаю взять за образец наш четырёхкнопочный из прежних программ. Всётаки графический интерфейс значительно удобнее консольного. Для ввода конца диапазона нам послужит компонент udNumber типа NumericUpDown. Ну и, конечно, нам не обойтись без кнопки btnSieve, в метод которой btnSieve_Click мы и проследуем:
//РЕШЕТО ЭРАТОСФЕНА
private void btnSieve_Click(object sender, EventArgs e)
{
//макс. число для проверки:
int number = (int)udNumber.Value;
sieve(number);
}
Здесь мы снимаем показания с компонента udNumber и передаём их методу sieve для просеивания чисел:
void sieve(int maxValue)
{
BitArray sieve = new BitArray(maxValue+1);
sieve.SetAll(true);
for(int i=2; i <= Math.Sqrt(maxValue); ++i)
if (sieve.Get(i))
for(int j=2*i; j <= maxValue; j += i)
sieve.Set(j, false); //- составное число
//печатаем простые числа:
for(int i=2; i <= maxValue; ++i)
if (sieve.Get(i)) //- простое число
lstRes.Items.Add(i);
lstRes.TopIndex = lstRes.Items.Count - 27;
79
lstRes.Items.Add("");
}
Дальше мы следуем своим рассуждениям о пользе битовых массивов, в результате чего и получаем аккуратный список простых чисел (Рис. 14.7).
80
Рис. 14.7. Простые числа в битовом решете!
Исходный код программы находится в папках Resheto и Numbers.
Проект Простые числа (Numbers)
Всем хорош алгоритм Эратосфена, но не годится для больших чисел:
слишком неэкономно он расходует память компьютера. Мы, конечно, и с
помощью решета легко узнаем, что 2011-й год - простой (естественно,
только с математической точки зрения), а следующим простым годом будет 2017-й. Но вот с числами 514229 и 39916801 нам уже придётся повозиться! В таких случаях правильнее один раз написать программу, чем
каждый раз считать вручную.
Чтобы сделать программу более универсальной, мы добавим ещё один
компонент NumericUpDown, чтобы пользователь мог задавать и верхнюю,
и нижнюю границу диапазона для поиска простых чисел. Для этого нам
нужно немного раздать интерфейс вширь. Кроме того, мы добавим кноп-
ку btnPrimes. Она действует почти так же, как и эратосфеновская, но вызывает метод primes – уже с двумя параметрами:
//ИЩЕМ ПРОСТЫЕ ЧИСЛА
private void btnPrimes_Click(object sender, EventArgs e)
{
//начальное число для проверки:
int number1 = (int)udNumber.Value;
//конечное число для проверки:
int number2 = (int)udNumber2.Value;
primes(number1, number2);
}
Здесь мы в цикле for последовательно перебираем числа от start до end:
void primes(int start, int end)
{
//проверяем все числа заданного диапазона:
for (int j = start; j <= end; ++j)
{
bool flg = true;
//проверяем, делится ли число j на числа
//2..корень квадратный из числа:
for (int i = 2; i <= Math.Sqrt(j); ++i)
//если делится, значит, число составное:
if (j % i == 0)
{
flg = false;
break;
}
//если нашли простое число,
if (flg)
{
//то печатаем его в списке:
lstRes.Items.Add(j);
}
} //for j
lstRes.TopIndex = lstRes.Items.Count - 27;
lstRes.Items.Add("");
}// primes
Проверка проходит так: очередное число мы поочерёдно делим на все
числа, начиная с двойки и кончая корнем квадратным из него. Так как
любое натуральное число делится на единицу и само на себя, то два разных делителя у него имеются в любом случае (кроме, единицы, разумеется). Если мы обнаружим хотя бы ещё один делитель, то это будет перебор:
число заведомо составное, и проводить испытания дальше нет смысла.
81
Если оно составное, то мы переходим к проверке следующего числа. Если
же простое, то выводим его на экран (Рис. 14.8).
82
Рис. 14.8. Список простых чисел составлен!
Недостаток нашего алгоритма кроется в делении каждого числа из заданного диапазона на все числа, начиная с двойки и заканчивая корнем квадратным. Но мы-то знаем, что делить следует только на уже найденные
простые числа, которых заведомо меньше. Это значит, что мы должны их
где-то хранить. Для этого сгодится и обычный массив, но мы позволим себе роскошь воспользоваться списком.
В этом случае начало диапазона лучше закрепить за двойкой, чтобы список простых чисел заполнялся правильно. Добавляем ещё одну кнопку
btnPrimesList, которая и понуждает метод primesL составлять список простых чисел:
private void btnPrimesList_Click(object sender, EventArgs e)
{
//конечное число для проверки:
int number2 = (int)udNumber2.Value;
List<int> lst = primesL(number1, number2);
lstRes.BeginUpdate();
foreach(int prime in lst)
lstRes.Items.Add(prime);
lstRes.EndUpdate();
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 27;
}
В методе primesL мы сразу помещаем двойку в список и переходим к следующему числу, то есть к тройке. Поскольку все остальные простые числа
нечётные, то это избавляет нас от необходимости проверять все числа –
мы можем ограничиться только нечётными, что мы и делаем, добавляя в
цикле while двойку к переменной num:
List<int> primesL(int end)
{
List<int> lst = new List<int>();
//добавляем в список первое простое число:
lst.Add(2);
bool flg = true;
int num= 3;
//проверяем все числа заданного диапазона:
while(num <= end)
{
flg = true;
//проверяем, делится ли введенное число на
//уже найденные простые числа:
foreach(int prime in lst)
if (num % prime == 0)
{
flg = false;
break;
}
//если нашли простое число,
if (flg)
{
//то добавляем его в список:
lst.Add(num);
}
num += 2;
} //while
return lst;
}// primesL
Когда метод primesL закончит работу и вернёт список методу
btnPrimesList_Click, мы просто распечатываем его на экране (Рис. 14.9), но с
тем же успехом можем использовать его и как-то иначе.
83
84
Рис. 14.9. Храните простые числа в списке!
Исходный код программы находится в папке Primes и Numbers.
1. Из Правил делимости чисел, которые мы рассмотрели в начале
урока, легко вывести признаки делимости чисел на 15, 16, 18, 20,
22, 24, 25, 100, 1000. Попробуйте!
2. В программе для поиска простых чисел замените список массивом. Оцените скорость поиска чисел.
3. Улучшите алгоритм поиска суперпростых чисел. Например, совершенно очевидно, что последней цифрой прямого простого числа не может быть 0, а первой – 2, 4, 6, 8. Также сумма цифр не
должна быть кратна трём.
4. Напишите программу для поиска других суперпростых чисел, о
которых мы говорили в начале проекта Суперпростые числа.
5. Найдите четвёрки простых чисел, принадлежащих одному десятку. Например, 11, 13, 17, 19. [ЗП88, Задача 558].
6. Совершенным называется натуральное число, равное сумме своих делителей, исключая само число. Первое совершенное число
равно шести: 6 = 1 + 2 + 3. Второе равно 28 = 1 + 2 + 4 + 7 + 14. Третье
– 496, четвёртое – 8128. Следующие совершенные числа уже гораздо больше. Напишите программу, которая находила бы несколько
совершенных чисел.
7. Натуральное число называется полусовершенным, если оно равно сумме всех или некоторых своих делителей, исключая само
число: 6, 12, 18, 20, 24, 28, 30, 36, 40. Например, 12 = 1 + 2 + 3 + 6
или 12 = 2 + 4 + 6.
Из этого определения следует, что всякое совершенное число является и полусовершенным, то есть полусовершенных чисел в заданном диапазоне не меньше, чем совершенных. Напишите программу, которая находила бы несколько полусовершенных чисел.
8. Два (различных) натуральных числа называются дружественными, если сумма всех делителей (исключая само число) первого числа равна второму числу, и наоборот. Первая пара дружественных
чисел была найдена несколько тысячелетий тому назад. Это числа
220 и 284. Следующая пара отыскалась только в 1860 году – 1184 и
1210. Сейчас известно несколько миллионов дружественных чисел.
Напишите программу для их поиска [ЗП88, Задача 560]. Учитывайте,
что числа в паре либо оба чётные, либо оба нечётные.
9. Напишите программу, которая графически показывает процесс
просеивания чисел через решето Эратосфена.
85
Глава #15. Занимательная математика
Предмет математики настолько серьёзен,
что полезно не упускать случаев
делать его немного занимательным.
Блез Паскаль
В мире найдётся еще много интересных чисел и помимо простых. В этой и
в следующей главе мы познакомимся с некоторыми из них. Я надеюсь, что
знакомство с ними скучать вас не заставит!
Проект Числа Фибоначчи (Numbers)
Числа Фибоначчи, как нетрудно догадаться, открыл Фибоначчи (он же
Леонардо Пизанский), средневековый математик (Рис. 15.7), автор Книги
абака (Liber Abaci), которую он написал в 1202 году.
Рис. 15.7. Леонардо Пизанский (Leonardo Pisano, 1170 - 1250), по прозвищу Фибоначчи (Fibonacci)
Впрочем, дотошные историки утверждают, что этот ряд чисел был
известен в Индии задолго до Фибоначчи, где он использовался при
стихосложении.
86
В трактате Книга абака Фибоначчи рассмотрел математическую
модель, связанную с кроликами. Он взял пару взрослых кроликов
(точнее, кролика и крольчиху) и предположил, что они могут производить на свет потомство каждый месяц. Причём у них всегда рождается пара крольчат разного пола, у которых через два месяца
также рождаются крольчата. Фибоначчи решил подсчитать, сколько
будет кроликов через год, если за это время ни один кролик не
умрёт. Числа Фибоначчи как раз и отражают рост популяции кроликов.
В книгах по программированию принято находить числа Фибоначчи с
помощью красивого рекурсивного алгоритма, который основан на
рекуррентном определении самих чисел. Первое число Фибоначчи равно 0,
второе число равно 1, а все последующие равны сумме двух предыдущих,
то есть третье число 0 + 1 = 1, четвёртое 1 + 1= 2, пятое 1 + 2 = 3 и так
далее, до бесконечности.
Интересные факты их жизни чисел Фибоначчи:
В 1964 году Дж. Кон (J. H. E. Cohn) доказал, что только четыре числа
Фибоначчи являются точными квадратами. Это F0 = 0, F1=1, F2=1 и F12
= 144.
Натуральное число n является числом Фибоначчи тогда и только тогда, когда 5n2 + 4 или 5n2 − 4 является точным квадратом.
F1 + F2 + F3 + … + Fn = Fn+2 -1
F1 + F3 + F5 + … + F2n-1 = F2n
F2 + F4 + F6 + … + F2n = F2n+1 -1
Fn2 + Fn+12 = F2n+1
Рекурсивные алгоритмы обычно довольно короткие, но не всегда
быстрые. Поэтому мы «засечём» время вычисления – для дальнейшего
принятия жёстких мер:
//НАХОДИМ ЧИСЛО ФИБОНАЧЧИ
private void btnFibo_Click(object sender, EventArgs e)
{
//число:
int number = (int)udNumber.Value;
87
DebugTimer dt = new DebugTimer();
dt.Start();
long f= fib(number);
dt.Stop();
lstRes.Items.Add(f);
lstRes.Items.Add("Время = " + dt.getMS().ToString());
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 27;
}
long fib(int n)
{
if (n < 2) return n;
else return fib(n - 1) + fib(n-2);
}
Для замера времени мы добавим в пространство имён rv новый
класс DebugTimer. Очень полезный «механизм» при разработке алгоритмов! Приглашаю всех ознакомиться с его кодом.
Как видите, весь алгоритм уложился в пару строк! Однако попробуем
найти 42-ое число Фибоначчи – и на это нашему алгоритму понадобилось
более 23 секунд (Рис. 15.8). Почти ручная работа!
Рис. 15.8. Кролики размножаются быстрее!
88
Попробуем разобраться, почему же такой красивый алгоритм медленно
работает.
Для чисел 0 и 1 он сразу возвращает соответствующие числа Фибоначчи.
Начало хорошее! Для двойки необходимо дважды вызвать метод fib (Рис.
15.9).
89
Рис. 15.9. Находим 2!
Для тройки дерево разветвляется (Рис. 15.10).
Рис. 15.10. Находим 3!
Для четвёрки – колосится вовсю (Рис. 15.11)!
Рис. 15.11. Находим 4!
Вот вам и ответ: наш алгоритм многократно вычисляет одни и те же
значения. Нетрудно представить, каким огромным станет дерево
рекурсивных вызовов даже для «скромных» чисел Фибоначчи.
Досужие люди подсчитали, что для 20-ого числа Фибоначчи потребуется 21 891 вызов метода, для 30-ого – 2 692 537, для 31-ого –
4 356 617 и для 32-ого – 7 049 155.
Чтобы ускорить вычисления, мы воспользуемся методами динамического
программирования, то есть просто запомним уже найденные числа
Фибоначчи в массиве. Этим мы убьём сразу двух зайцев (или кроликов) – и
заданное число получим, и все предыдущие числа сохраним в массиве!
Подселяем новую кнопку к соседям по форме и начиняем ее «массивным»
кодом:
//НАХОДИМ ЧИСЛА ФИБОНАЧЧИ
private void btnFibo2_Click(object sender, EventArgs e)
{
//число:
int number = (int)udNumber.Value;
DebugTimer dt = new DebugTimer();
BigInteger[] fibo = new BigInteger[3];
if (number > 2) fibo = new BigInteger[number+1];
//помещаем в массив первые числа Фибоначчи:
fibo[0] = 0;
fibo[1] = 1;
fibo[2] = 1;
dt.Start();
BigInteger f= fib2(fibo);
dt.Stop();
for (int i = 0; i <= number; ++i)
{
lstRes.Items.Add("Число " + i + " = " + fibo[i]);
}
lstRes.Items.Add("Время = " + dt.getMS().ToString());
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 17;
}
BigInteger fib2(BigInteger[] f)
{
long n = f.Length-1;
if (n == 1 || n== 2) return n;
for (int i = 3; i <= n; ++i)
{
f[i] = f[i-1] + f[i-2];
90
}
return f[n];
}
Я неспроста перешёл на «огромадные» числа типа BigInteger. Наша уловка
с массивом позволяет практически мгновенно находить совершенно
невероятные числа Фибоначчи (Рис. 15.12)! Всё-таки думать надо. Даже в
эпоху скоростных многоядерных компьютеров…
91
Рис. 15.12. Вычисляем мгновенно!
Легко заметить, что из всего массива чисел Фибоначчи нам для
вычисления следующего числа нужны только два последних элемента. И
если все числа Фибоначчи от первого до заданного, сохранять не нужно, то
можно обойтись и без массива. И при этом мы не потеряем скорость
вычислений! Вот как это делается:
//НАХОДИМ ЧИСЛО ФИБОНАЧЧИ
private void btnFibo3_Click(object sender, EventArgs e)
{
//число:
int number = (int)udNumber.Value;
DebugTimer dt = new DebugTimer();
dt.Start();
BigInteger f= fib3(number);
dt.Stop();
lstRes.Items.Add(f);
lstRes.Items.Add("Время = " + dt.getMS().ToString());
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 17;
}
BigInteger fib3(int n)
{
BigInteger f1=0, f2=1, f=1;
for (int i = 1; i <= n; ++i)
{
f = f1 + f2;
f2 = f1;
f1 = f;
}
return f;
}
Здесь нам понадобятся три переменных типа BigInteger f1, f2 и f.
Первые два числа Фибоначчи мы задаём сразу, а все последующие вычисляем как сумму двух предыдущих. То есть третье (если нулевое число
Фибоначчи считать первым; нередко последовательность чисел Фибоначчи начинается с единицы, а не с нуля, поэтому и возникают подобные
«разночтения») число 0 + 1 = 1, четвёртое 1 + 1= 2, пятое 1 + 2 = 3 и так далее:
f = f1 + f2;
f2 = f1;
f1 = f;
Проверка подтверждает наши ожидания – новый алгоритм считает быстро
и аккуратно (Рис. 15.13).
Исходный код программы находится в папке Numbers.
92
93
Рис. 15.13. Тоже неплохо!
А теперь мы напишем две родственные программы из школьной жизни –
для вычисления НОД (наибольшего общего делителя двух чисел) и НОК
(наименьшего общего кратного).
Проект Наибольший общий делитель, НОД
(Numbers)
Для вычисления НОД мы воспользуемся простым и быстрым
алгоритмами древнегреческого математика Евклида (Рис. 15.14).
94
Рис. 15.14. Евклид (Εὐκλείδης, ок. 325 года до н.э. - до 265 года до н.э.)
По-английски НОД называется gcd – greatest common divisor.
Простой алгоритм Евклида основан на следующих свойствах:
НОД(m,m) = m
НОД(m,n) = НОД(n,m)
НОД(m,n) = НОД(m-n, n) при m > n
Из них следует:
- Если m > n, то из m нужно вычесть n;
- Если m < n, то числа нужно поменять местами;
- Когда значения m и n сравняются, вычисление НОД заканчивается,
и НОД = m = n.
Для вычисления НОД нам нужны два числа - number1 и number2. Чтобы не
обременять пользователя лишними заботами, мы позволим ему вводить
числа в произвольном порядке, хотя для алгоритма важно, чтобы первое
число было больше второго, поэтому выправляем ситуацию, если это
необходимо.
При равенстве чисел алгоритм сработает правильно.
Затем мы передаём оба числа в метод nod1, который и реализует простой
алгоритм Евклида.
private void btnNOD1_Click(object sender, EventArgs e)
{
//первое число:
ulong number1 = (ulong)udNumber.Value;
//второе число:
ulong number2 = (ulong)udNumber2.Value;
//если первое число меньше второго,
//то меняем их значения:
if (number1 < number2)
{
ulong n = number1;
number1 = number2;
number2 = n;
}
DebugTimer dt = new DebugTimer();
dt.Start();
ulong nod= nod1(number1, number2);
dt.Stop();
lstRes.Items.Add("НОД(" + number1 + "," + number2 + ") = " + nod);
lstRes.Items.Add("Время = " + dt.getMS().ToString());
lstRes.Items.Add("");
lstRes.TopIndex = lstRes.Items.Count - 17;
}
Если меньшее из чисел (или оба) равны нулю, то за НОД, понятное дело,
следует принять первое число. Если же оба числа положительные, то
начинаем действовать по простому алгоритму Евклида:
ulong nod1(ulong n1, ulong n2)
{
//находим НОД:
if (n2 == 0)
return n1;
else
{
while (n2 != n1)
{
if (n1 >= n2) n1 -= n2;
else n2 -= n1;
}
return n1;
}
}
95
В цикле while мы на каждой итерации вычитаем из большего числа меньшее – до тех пор, пока значения переменных n1 и n2 не сравняются. Поскольку с каждым разом одно из чисел уменьшается, то рано или поздно
это условие будет выполнено.
Вычисленное значение НОД мы возвращаем методу btnNOD1_Click, который и публикует его в списке lstRes (Рис. 15.15).
Попутно мы измеряем время вычислений, которое, как вы видите, для небольших чисел практически нулевое. Нагнетаем обстановку, беря более
«солидные» числа, и простой алгоритм начинает буксовать (Рис. 15.16).
Рис. 15.15. Вычисляем НОД небольших чисел
96
А при дальнейшем увеличении чисел он попросту впадает в кому! И тут
нам на выручку приходит быстрый алгоритм Евклида. Он отличается от
простого алгоритма тем, что мы на каждой итерации мы находим остаток
от деления первого числа на второе, второе число становится первым, а
остаток - вторым. Так мы продолжаем до тех пор, пока остаток от деления
не станет равен нулю. Как и в первом случае, это условие обязательно будет выполнено.
Быстрый алгоритм Евклида основан на свойстве
НОД(m,n) = НОД(n,m%n) при m > n
Рис. 15.16. Простой алгоритм затормозил!
Этот алгоритм не собьёшь с толку никакими числами (Рис. 15.17)! Вы можете взять любые числа и убедиться, что алгоритм действительно работает очень быстро.
В данном проекте мы используем числа не типа uint, а ulong, чтобы
можно было вычислять НОД и очень больших чисел. Тут, конечно,
следует учитывать значения чисел: если они очень большие, то
лучше пользоваться быстрым, а не простым алгоритмом.
97
98
Рис. 15.17. Наша программа легко справляется и с большими числами!
Для большего понимания давайте вручную найдем НОД чисел 42 и 14:
number1 = 42
number2 = 14
Так как второе число больше нуля, то находим остаток от их деления:
n = 42 % 14 = 0
И присваиваем новые значения переменным:
number1 = 14
number2 = 0
Второе число теперь равно нулю, значит, НОД найден – он равен второму
числу, то есть 14.
Рассмотрим другой пример:
number1 = 56
number2 = 42
n = 56 % 42 = 14
number1 = 42
99
number2 = 14
Уже после одного цикла мы пришли к первому примеру.
Взаимно простые числа
Если наибольший общий делитель двух чисел m и n равняется единице, то
такие числа называются взаимно простыми:
НОД(m,n) = 1  числа m и n - взаимно простые
Для простых чисел это условие выполняется всегда, поскольку у них не
может быть общих делителей, больших единицы:
НОД(7,11) = 1
Составные числа, естественно, взаимно просты также только тогда, когда
у них нет общих простых делителей:
НОД(10,9) = 1  числа 10 и 9 - взаимно простые
НОД(10,8) = 2  числа 10 и 8 – не взаимно простые: у них имеется общий
делитель двойка.
Более подробно о взаимно простых числах вы можете прочитать в
книге [ОО80], на страницах 49-50.
Исходный код программы находится в папке Numbers и NOD.
Проект Наименьшее общее кратное, НОК (Numbers)
Зная наибольший общий делитель двух чисел, их наименьшее общее кратное очень просто вычислить по такой формуле:
НОК = число1 * число2 / НОД (число1, число2)
(1)
По-английски НОК называется lcd – least common denominator.
100
Мы возьмём за основу нашу предыдущую программу и воспользуемся методом nod2 для вычисления НОД. А дальше мы вычисляем НОК по формуле
(1):
//ВЫЧИСЛЯЕМ НАИМЕНЬШЕЕ ОБЩЕЕ
//КРАТНОГО ДВУХ ЧИСЕЛ (НОК)
private void btnNOK_Click(object sender, EventArgs e)
{
. . .
dt.Start();
ulong nok = nok2(number1, number2);
dt.Stop();
lstRes.Items.Add("НОК(" + number1 + "," + number2 + ") = " + nok);
. . .
}
ulong nok2(ulong n1, ulong n2)
{
if (n1 * n2 == 0)
return 0;
else
//вычисляем НОК:
return n1 * n2 / nod2(n1, n2);
}
Поскольку НОД вычисляется очень быстро, то и НОК мы получаем в считанные мгновения (Рис. 15.18).
Исходный код программы находится в папках Numbers и NOK.
101
Рис. 15.18. Вычисляем НОК
1. Формула Бине [ЗП88, Задача 556]. n-ное число Фибоначчи можно
вычислить по формуле Бине:
В ней буквой фи обозначено золотое сечение:
.
Из неё следует, что Fn равно ближайшему к
целому числу.
Так как абсолютная величина выражения
меньше единицы, то при больших n числа Фибоначчи можно вычислять по
прибиженной формуле:
102
Напишите метод, вычисляющий заданное число Фибоначчи по
формуле Бине.
2. Можно одновременно вычислить НОК и НОД чисел m и n, если
передать по ссылке в метод nodnok два числа:
void nodnok(ref ulong n1, ref ulong n2)
{
ulong x = n1;
ulong v = n1;
ulong y = n2;
ulong u = n2;
while (x != y)
{
if (x > y)
{
x -= y;
v += u;
}
else
{
y -= x;
u += v;
}
}
n1 = (x + y) / 2;
n2 = (v + u) / 2;
}
Добавьте кнопку и напишите для неё метод, который правильно
вызывает метод nodnok.
3. Фибоначчиевы монетки
Числа Фибоначчи неожиданно появляются в самых разных задачах,
когда их совсем не ждёшь! Например, давайте решим такую комбинаторную проблему: сколькими способами можно разложить n
одинаковых монеток так, чтобы они располагались друг возле друга
по горизонтали или опирались на две нижележащие монеты? Запрещено одну монету ставить на другую столбиком (Рис. 15.22).
103
Рис. 15.22. Запрещённый приёмчик!
Мы начнём решение с одной монеты, которую, как ни крути, можно
уложить единственным способом (Рис. 15.23).
Рис. 15.23. Начальный капитал
То же самое можно сделать и с двумя монетами (Рис. 15.24).
Рис. 15.24. Удвоили!
С тремя монетами жить веселее, и мы находим два варианта их
укладки (Рис. 15.25).
Рис. 15.25. Две укладки трёх монет
Но ещё лучше, когда монет четыре (Рис. 15.26).
Рис. 15.26. Три укладки четырёх монет
А с пятью монетами мы становимся такими же богатенькими, как
сам Буратино (Рис. 15.27)!
Уже по первым раскладкам можно предположить, что и дальше мы
будем получать числа Фибоначчи.
А задание такое. Напишите программу, которая умеет генерировать
все фигурки из n монет и убедитесь, что число вариантов образует
последовательность Фибоначчи. Если же вам удастся нарисовать
монеты в виде окружностей, то вы одновременно решите и непростую геометрическую задачу – как начертить три окружности одного диаметра так, чтобы они касались друг друга.
104
105
Рис. 15.27. Не закапывайте ваши денежки, где попало, а собирайте в
аккуратные кучки!
КОМБИНАТОРНЫЙ ТРЕНИНГ
Комбинаторика - это раздел математики, который изучает множества
(совокупности, наборы) каких-либо элементов. Первая книга по комбинаторике вышла в 1666 году под названием Рассуждения о комбинаторном
искусстве. Её написал известный немецкий математик Готфрид Вильгельм
фон Лейбниц, который и придумал название комбинаторика для этого
раздела математики.
Как в жизни, так и в программировании комбинаторные задачи встречаются очень часто. Например, сколько различных слов можно составить из
букв русского алфавита? Сколько существует различных комбинаций при
игре в кости двумя или тремя кубиками? Сколько разных нарядов можно
составить из трёх юбок и четырёх блузок и так далее.
Все комбинаторные задачи решаются с помощью комбинаторных конфигураций: размещений, перестановок, сочетаний, композиций и разбиений.
Глава #18. Занимательная комбинаторика
А начнём мы наши комбинаторные забавы с перестановок элементов.
Возьмём множество, состоящее из трёх разных элементов, например, русских букв - {К, О, Т}. Всякое «слово», составленное из всех этих букв без повторений, и называется перестановкой элементов множества.
Поскольку в множестве элементы не упорядочены, то мы выпишем их
сначала в произвольном порядке, например так:
1. КОТ
Вот мы и получили первую перестановку, а значит, и первое слово – КОТ.
Оно «случайно» совпало с настоящим русским словом. Чтобы найти вторую перестановку, поменяем местами вторую и третью буквы:
2. КТО
Тоже получилось неплохо, ведь кто - это русское местоимение.
Теперь давайте поменяем первую и вторую буквы:
3. ТКО
Такого слова нет (в старой речи была частица –тко, имеющая тот же
смысл, что и современная -ка: бери-тко, читай-тко), а вот четвёртая пере-
106
становка снова удачная. Чтобы её получить, поменяем местами вторую и
третью буквы:
4. ТОК
Снова меняем первую и вторую буквы - и получаем пятую перестановку:
5. ОТК
Не ахти какое слово, но Отдел технического контроля тоже сгодится.
107
И последнюю перестановку мы найдём, переставив две последние буквы:
6. ОКТ
ОКТ – тоже сокращение от Оптическая когерентная томография, так что
все наши перестановки из трёх букв К, О, Т оказались не совсем бессмысленными. Конечно, с другими буквами результат был бы другим.
Но почему мы можем утверждать, что нашли все перестановки множества
из трёх элементов? – Давайте рассуждать логически. На первом месте в
слове может стоять любая из трёх букв. На второе место можно поставить
любую из двух оставшихся, а для последнего места останется только одна
буква. Таким образом, всего можно составить 3 х 2 х 1 = 6 разных слов. Но
мы ровно столько и составили, значит, других слов из этих букв составить
нельзя (естественно, мы используем каждую букву только один раз!).
Если взять множество из четырёх разных элементов, то, рассуждая аналогично, мы придём к выводу, что из них можно составить 4 х 3 х 2 х 1 = 24
разных слова. Этот ряд легко продолжить сколь угодно далеко, а произведение чисел от единицы до заданного называется факториалом. Как его
вычислять, мы уже знаем по Числовому тренингу.
Проект Генерируем перестановки (Permutation)
Мы научились ловко узнавать общее число перестановок. Ну, пусть мы
знаем, что из трёх разных букв можно составить 3! разных слов, но ведь
программа Factorial не даёт ответа на очевидный вопрос: а как составить
эти перестановки? С множеством из трёх элементов мы легко справились,
а если взять больше – четыре, пять, а то и восемь?
Оказывается, мы не первые, кто задался этим вопросом. Ещё в семнадцатом веке английские звонари научились выбивать на нескольких разных
колоколах «мелодии», состоящие из всех перестановок этих колоколов.
Например, для трёх колоколов нужно было сыграть такую мелодию:
Первый колокол – второй – третий.
Второй колокол – первый – третий.
Дальше вы и сами продолжите эту музыку.
Колоколов, конечно, было больше, а последовательность колокольных
ударов нужно было держать в голове. Например, в Книге рекордов Гиннеса
рассказывается о том, что в 1963 году за 17 с лишним часов удалось выбить на восьми колоколах все 8! = 40320 перестановок. В семнадцатом веке, конечно, эти музыкально-комбинаторные экзерсисы были короче, но,
тем не менее, запомнить многие сотни перестановок было совсем непросто, поэтому звонари придумывали свои способы для «генерирования»
всех колокольных перестановок. Один из таких способов мы и положим в
основу компьютерной программы, которая быстро и правильно выпишет
все перестановки элементов заданного множества.
Сначала программа выписывает первую перестановку. Например,
множества из четырёх элементов это будет
для
1234
Затем она циклически меняет местами первый и второй, второй и третий,
третий и четвёртый элементы. После этого снова - первый-второй, второйтретий, третий-четвёртый элементы, и так далее, пока не будут сгенерированы все перестановки (Рис. 18.1).
Нам вполне хватит двух целых переменных и трёх массивов:
//ПРОГРАММА ДЛЯ ГЕНЕРИРОВАНИЯ
//ВСЕХ ПЕРЕСТАНОВОК ЭЛЕМЕНТОВ МНОЖЕСТВА ЧИСЕЛ 1..nElem
public partial class frmPermutation : Form
{
const int MAX_ELEM= 8;
// макс. число элементов в множестве
int nElem=0;
// число элементов в множестве
int nPerm=0;
// номер перестановки
int [] p = new int [MAX_ELEM+1]; // массив, содержащий очередную перестановку
int [] c = new int [MAX_ELEM+1];
int [] pr = new int [MAX_ELEM+1];
108
109
Рис. 18.1. Перестановочная программа в работе!
Важно ограничить число элементов множества, иначе список перестановок будет очень большим. Удобнее всего это сделать в процедуреобработчике нажатия на кнопку:
//Обрабатываем нажатие кнопки "Генерировать!"
private void btnPerm_Click(object sender, EventArgs e)
{
//считываем введенное число:
nElem = (int)udNum.Value;
//проверяем заданное число:
if (nElem <= 0) return;
if (nElem > 8){
MessageBox.Show("Число должно быть от 1 до 8!", "Перестановки");
return;
//Console.ForegroundColor= ConsoleColor.Red;
//Console.WriteLine();
}
//находим все перестановки nElem-го множества:
perm(nElem);
//устанавливаем курсор для ввода нового числа:
udNum.Focus();
//прокручиваем список вниз:
lstPerm.TopIndex = lstPerm.Items.Count-22;
}//btnPerm_Click
Если пользователь ввёл правильное число, то мы переходим в метод
perm, где и генерируются все перестановки.
Первая перестановка состоит из последовательного ряда чисел 1 .. nElem:
//Генерируем все перестановки множества 1..num
//и выводим в список
void perm (int num){
int k;
for (int i= 1; i <= num; ++i)
{
p[i]= i;
c[i]=1;
pr[i]=1;
}
nPerm=0;
c[num]=0;
//печатаем первую перестановку:
nPerm++;
lstPerm.BeginUpdate();
writePerm(num);
Метод writePerm для печати перестановок очень простой:
//ПЕЧАТАЕМ ОЧЕРЕДНУЮ ПЕРЕСТАНОВКУ
void writePerm(int num)
{
string s="";
s = nPerm + "> ";
for (int i = 1; i <= num; ++i) s += p[i] + " ";
lstPerm.Items.Add(s);
}
Мы составляем строку s из номера перестановки и последовательности
цифр 1.. num, а затем выводим готовую строку в список lstPerm.
Если вас интересуют только сами перестановки, без номеров, закомментируйте строку:
//s = nPerm + "> ";
110
Все остальные перестановки мы получаем из первой, меняя местами соседние элементы. Тут важно определить номера элементов для обмена.
Как это работает в программе, проследите сами:
int j = 1;
while (j < num){
j= 1;
int x= 0;
while (c[j] == num - j + 1){
pr[j] = - pr[j];
c[j] = 1;
if (pr[j]== 1) x++;
j++;
}
if (j < num){
if (pr[j]== 1) k= c[j] + x;
else k= num - j + 1 - c[j] + x;
int tmp= p[k];
p[k]= p[k+1];
p[k+1] = tmp;
//печатаем очередную перестановку:
nPerm++;
writePerm(num);
c[j]++;
}
}//while
lstPerm.Items.Add("");
lstPerm.EndUpdate();
}
На Рис. 18.2 показано окно программы, которая сгенерировала более 40
тысяч перестановок. Чтобы список быстрее заполнялся строками, мы пошли на хитрость: перед началом вывода строк указали программе, что
список на экране обновлять не нужно до тех пор, пока мы не сгенерируем
все перестановки:
lstPerm.BeginUpdate();
А затем все строки разом появляются на экране:
lstPerm.EndUpdate();
Для больших списков скорость печати возрастает в десятки раз!
111
112
Рис. 18.2. Все перестановки множества 1..8 – звонить - не перезвонить!
Компонент
Форма
Свойство
(Name)
FormBorderStyle
MaximizeBox
Size
StartPosition
Text
Метка
(Name)
Font
Location
Text
NumericUpDown (Name)
Font
Значение
frmPermutation
FixedSingle
False
424; 498
CenterScreen
Перестановки
label1
Microsoft Sans Serif; 12pt; style=Bold
7; 9
Введите число 1..8
udNum
Microsoft
Sans
Serif;
20,25pt;
style=Bold
Кнопка
Список
ForeColor
Location
Maximum
Minimum
Size
TextAlign
Value
(Name)
Cursor
FlatStyle
Font
Blue
11; 32
8
1
110; 38
Right
4
btnPerm
Hand
Flat
Microsoft
Sans
Serif;
11,25pt;
style=Bold
ForeColor
Green
Location
12; 429
Size
395; 31
Text
Генерировать перестановки!
(Name)
lstPerm
BackColor
WhiteSmoke
BorderStyle
FixedSingle
Font
Lucida Console; 11,25pt
HorizontalScrollBar True
Location
12; 76
Size
395; 347
Исходный код программы находится в папке Permutation.
Проект Как собрать Дрим тим? (Subset)
Решим ещё одну жизненно важную задачу. Представим себе, что на Чемпионате мира по футболу нужно выставить на игру 11 основных игроков,
выбрав их из 16 кандидатов.
Общее число футболистов, с точки зрения комбинаторики, - это число
элементов в множестве, а число игроков в команде – число элементов
подмножестве. Таким образом, нам нужно найти все подмножества заданного множества. Каждое подмножество какого-либо множества иначе
113
называют набором из заданного числа элементов, или сочетанием. В сочетании порядок элементов не играет роли, поэтому мы отберём только
11 игроков в команду, а как между ними поделить номера на футболках (а,
значит, и их амплуа на поле), это уже задача тренера.
Объявим новые переменные программы Subset:
public partial class frmSubset : Form
{
const int MAX_ELEM= 30;
//
int nElem=0;
//
int k= 0;
//
int [] a = new int [MAX_ELEM+1]; //
множество
int nSubset;
//
макс. число элементов в множестве
число элементов в множестве
число элементов в подмножестве
массив, содержащий очередное подномер подмножества
В этой программе пользователь вводит два числа, которые мы должны
проверить, иначе расчеты окажутся неверными. Важно учесть, что в подмножестве элементов не больше, чем в множестве.
//Обрабатываем нажатие кнопки "Генерировать сочетания!"
private void btnSubset_Click(object sender, EventArgs e)
{
//считываем число элементов множества:
nElem = (int)udNum.Value;
//считываем число элементов подмножества:
k = (int)udSub.Value;
//проверяем заданное число:
if (k > nElem)
{
MessageBox.Show("Число должно быть от 1 до" + nElem + "!", "Подмножества");
return;
}
//генерируем все подмножества:
subSet();
}//btnSubset_Click
Если данные пользователя успешно прошли проверку, то мы генерируем
все подмножества:
//Генерируем все сочетания множества 1..nElem
//из k элементов и выводим в список
void subSet()
{
int i = 0;
//lstSubset.BeginUpdate();
for (i= 1; i <= k; ++i) a[i]= i;
114
nSubset=0;
int p= k;
while (p >= 1)
{
//печатаем очередное подмножество:
nSubset++;
writeSubset();
if (k == nElem) break;
if (a[k]== nElem) p--;
else p= k;
if (p >= 1)
for (i= k; i >= p; --i)
a[i]= a[p] + i - p + 1;
}
lstSubset.Items.Add("");
lstSubset.TopIndex = lstSubset.Items.Count - 22;
//lstSubset.EndUpdate();
}
Затем пользователь может ввести другие данные и продолжить работу с
программой.
Метод печати очередного подмножества почти не отличается от процедуры печати перестановок:
//ПЕЧАТАЕМ ОЧЕРЕДНУЮ ПЕРЕСТАНОВКУ
//ЭЛЕМЕНТОВ МНОЖЕСТВА
void writeSubset()
{
string s = "";
s = nSubset + "> ";
for (int i = 1; i <= k; ++i) s += a[i] + " ";
lstSubset.Items.Add(s);
if (lstSubset.Items.Count % 100 == 0)
lstSubset.TopIndex= lstSubset.Items.Count-27;
}
Запустив программу и введя наши данные: 16 элементов в множестве и 11
– в подмножестве, мы увидим огромный список из 4368 разных команд
(Рис. 18.3)! Комбинаторную задачу мы решили, а вот какая из этих сборных действительно станет командой мечты, тут комбинаторика бессильна!
115
116
Рис. 18.3. Вот сколько сборных можно послать на чемпионат!
Иногда полезно заранее узнать, сколько же получится сочетаний при тех
или иных исходных данных - не печатать же весь список подмножеств, если нам интересно узнать только их число! А на этот случай в комбинаторике припасена несложная формула:
В нашей программе n = nElem.
Как видите, в комбинаторике без факториала не обойтись!
Компонент
Форма
Метка
Свойство
(Name)
FormBorderStyle
MaximizeBox
Size
StartPosition
Text
(Name)
Font
Location
Text
NumericUpDown (Name)
Font
Метка
Кнопка
Список
ForeColor
Location
Maximum
Minimum
Size
TextAlign
Value
(Name)
Location
Text
(Name)
Cursor
FlatStyle
Font
ForeColor
Location
Size
Text
(Name)
Значение
frmSubset
FixedSingle
False
436; 582
CenterScreen
Сочетания
label1
Microsoft Sans Serif; 12pt; style=Bold
7; 9
Введите
число
элементов
в
множестве 1..30
udNum
Microsoft
Sans
Serif;
20,25pt;
style=Bold
Blue
11; 39
30
1
110; 38
Right
4
label2
7; 80
Введите
число
элементов
в
подмножестве 1..
btnSubset
Hand
Flat
Microsoft
Sans
Serif;
11,25pt;
style=Bold
Green
11; 500
395; 31
Генерировать сочетания!
lstSubset
117
BackColor
BorderStyle
Font
HorizontalScrollBar
Location
Size
WhiteSmoke
FixedSingle
Lucida Console; 11,25pt
True
12; 147
395; 347
Исходный код программы находится в папке Subset.
118
Литература
[AK96]
Apt Krzysztof R.
From Logic Programming
to Prolog
Prentice Hall, 1996.- 345 c.
ISBN: 013230368X
[DJ76]
Degrazia Joseph
Math is Fun
Emerson Books, 1976. - 158 c.
119
[РВ10]
Рубанцев Валерий
Хитори: круче, чем судоку
Эксмо-Пресс, 2010. – 288 с.
ISBN: 978-5-699-39575-0
Серия: Зарядка для ума
120
[РВ11]
Рубанцев Валерий
Delphi в примерах, играх
и программах. От простых приложений, решения задач и до программирования
интеллектуальных игр
Наука и Техника, 2011. – 672
с.
ISBN: 978-5-94387-664-6
Серия: Самоучитель
121
122
ЗАРЕГИСТРИРУЙТЕСЬ - ЭТО БЕСПЛАТНО

Похожие документы