Perl. Примеры программ

Антон Николаевич Швец

2022-04-14T14:11:14+03:00

Содержание

Предисловие

Благодарности

Как пользоваться этим руководством?

Требования к броузеру

Про алгоритмический язык Perl

Источники сведений о языке Perl

Что потребуется?

Соглашения

Оформление программ или их фрагментов
Командная строка

Интерактивность

1. Самая первая программа

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

2. Конструкции языка Perl

Переменные, константы, выражения

Общие сведения о переменных
Переменные в Perl
Скалярные переменные
Скалярные константы и выражения
Массивы
Ассоциативные массивы

Управляющие конструкции

Блок-схемы
Условная конструкция
Циклы

Процедуры

Определение и объявление процедур
Параметры процедуры
Возврат из процедуры
Вызов процедуры
Локализация переменных
Рекурсия

Ссылки

Создание ссылок
Использование ссылок
Копирование ссылок
Определение вида ссылки

3. Стиль

Выравнивание строк текста
Пробелы

4. Арифметическая прогрессия

Постановка задачи
Параметры командной строки
Готовая программа

5. Звёздочки

Постановка задачи

Сплошной квадрат
Шахматная доска
Пустой квадрат
Вложенные квадраты

Разработка

Сплошной квадрат
Шахматная доска
Пустой квадрат
Вложенные квадраты

Готовая программа

Сплошной квадрат
Шахматная доска
Пустой квадрат
Вложенные квадраты

6. Вычисление числа $π$

Способы приближённого вычисления числа $π$

Постановка задачи

Идеи реализации

Суммирование рядов и вычисление произведений
Вывод произведения Виета
Метод Монте-Карло
Игла Бюффона
Вычисление по формуле Броункера

Готовая программа

Ряд Лейбница
Ряд Эйлера
Произведение Валлиса
Произведение Виета
Метод Монте-Карло

Сравнение разных методов вычисления

7. Факториал

Постановка задачи

Идеи реализации

Извлечение числа из командной строки
Итерации
Рекурсия

Готовая программа

Итеративная версия
Рекурсивная версия

8. Быстрое возведение в степень

Постановка задачи

Идеи реализации

Итеративные версии

Готовая программа

Наивная версия
Быстрая рекурсивная версия
Быстрая итеративная версия

9. Числа Фибоначчи

Постановка задачи

Идеи реализации

Прямое вычисление
Вывод формулы Бине
Рекуррентное вычисление
Рекурсивная версия
Рекурсивная версия с мемоизацией
Матричная версия

Готовая программа

Прямое вычисление
Рекуррентное вычисление
Рекурсивная версия
Рекурсивная версия с мемоизацией
Матричная версия

10. Треугольник Паскаля

Построение и некоторые свойства треугольника Паскаля

Треугольник Паскаля и числа Фибоначчи
Треугольники Паскаля и Серпинского
Треугольник Паскаля и простые числа

Постановка задачи

Идеи реализации

Разработка

Готовая программа

11. Угадывание чисел

Постановка задачи
Идеи реализации
Готовая программа

12. Вычисление НОД

Постановка задачи

Идеи реализации

Алгоритм Евклида (рекурсивная версия)
Индуктивное вычисление НОД нескольких чисел
Алгоритм Евклида (итеративная версия)

Готовая программа

Рекурсивная версия
Итеративная версия

Сравнение рекурсивной и итеративной версий программы

13. Факторизация чисел

Постановка задачи
Идеи реализации
Готовая программа

14. Поиск простых чисел

Постановка задачи

Идеи реализации

Наивный перебор
Оптимизированный перебор делителей
Перебор с запоминанием найденных простых чисел
Решето Эратосфена
Колёсный метод
Замечания

Разработка

Наивный перебор
Оптимизированный перебор делителей
Перебор с запоминанием найденных простых чисел
Решето Эратосфена
Колёсный метод

Готовая программа

Наивный (сплошной) перебор делителей
Оптимизированный перебор делителей
Перебор делителей среди запомненных простых
Решето Эратосфена
Колёсный метод

Сравнение разных версий программы

15. Десятичные дроби

Постановка задачи

Идеи реализации

Превращение обыкновенной дроби в десятичную
Наивное решение
Метод Черепахи и Зайца
Сравнение двух версий программы

Разработка

Наивное решение
Решение методом Черепахи и Зайца

Готовая программа

Наивное решение
Решение методом Черепахи и Зайца

16. «Квадратные» телефонные номера

Постановка задачи
Идеи реализации
Разработка
Готовая программа

17. Перестановки

Постановка задачи

Идеи реализации

Представление перестановок в программе
Рекурсивная реализация
Итеративные реализации

Разработка

Рекурсивная реализация
Итеративные реализации

Готовая программа

Рекурсивная реализация
Итеративные реализации

18. Сортировка

Общие сведения

Постановка задачи

Идеи реализации

Глупая сортировка
Пузырьковая сортировка
Шейкерная сортировка
Сортировка вставками
Сортировка выбором
Древесная сортировка
Быстрая сортировка
Умная сортировка
Перемешивание

Разработка

Глупая сортировка
Пузырьковая сортировка
Шейкерная сортировка
Сортировка вставками
Сортировка выбором
Древесная сортировка
Быстрая сортировка
Умная сортировка
Перемешивание

Готовая программа

Глупая сортировка
Пузырьковая сортировка
Шейкерная сортировка
Сортировка вставками
Сортировка выбором
Древесная сортировка
Быстрая сортировка
Умная сортировка
Перемешивание

19. Квадратный корень

Постановка задачи

Идеи реализации

Метод бисекций
Метод Ньютона
Условие остановки

Разработка

Метод бисекций
Метод Ньютона

Готовая программа

Метод бисекций
Метод Ньютона

20. Файловый ввод/вывод

Понятие файла

Файловая система

Файловая иерархия и директории
Основное и полное имя файла
Абсолютные и относительные имена файлов
Текущая директория

Операции ввода-вывода

Открытие и закрытие файла
Чтение
Запись
Форматированный вывод

Стандартные дескрипторы

Переадресация ввода/вывода

Кодовые страницы

Общие сведения
Проблемы, связанные с кодовыми страницами

Юникод

Универсальный набор символов UCS
Кодировка UTF-8
Perl и Юникод

Команды как файлы

Несколько примеров

Вывод содержимого файла на экран
Вывод первых и последних строк файла
Удаление повторяющихся строк

21. Индуктивные вычисления

Пространство последовательностей

Индуктивные функции на пространстве последовательностей

Определение
Достоинства индуктивных функций
Примеры
Стационарные значения

Индуктивные расширения

Примеры
Минимальные индуктивные расширения

22. Непрерывные дроби

Общие сведения

Определение
Примеры

Идеи реализации

Индуктивное вычисление
Вычисление по формуле Броункера

23. Проверка баланса скобок

Постановка задачи

Идеи реализации

Стек

Разработка

Готовая программа

24. Подсчёт символов, слов и строк

Постановка задачи
Идеи реализации
Готовая программа

25. Путь с максимальной суммой в числовом треугольнике

Постановка задачи

Идеи реализации

Метод грубой силы
Рекурсивное решение
Рекурсия с мемоизацией
Индуктивное решение

Разработка

Метод грубой силы
Рекурсивная версия
Рекурсивная версия с мемоизацией
Индуктивная версия

Готовая программа

Метод грубой силы
Рекурсивная версия
Рекурсивная версия с мемоизацией
Индуктивная версия

26. Форматирование текста

Постановка задачи
Готовая программа

27. Сравнение файлов

Постановка задачи

Идеи реализации

Считывание файлов в переменные целиком
Считывание байта за байтом
Буферизация

Разработка

Готовая программа

28. Вывод содержимого директории

Постановка задачи

Идеи реализации

Разработка

Схема программы
Файловые тесты -d и -f
Чтение оглавления директории

Готовая программа

29. Поиск одинаковых файлов

Постановка задачи

Идеи реализации

Наивная группировка
Хеширование и гнездование

Разработка

Готовая программа

30. Регулярные выражения

Машина регулярных выражений

Шаблоны поиска

Символы и метасимволы
Символьные классы
Анкеры (привязки)
Альтернативы
Квантификаторы
Группировка и захват
Опции поиска
«Прожорливость» шаблонов

Операторы поиска и замены

Оператор поиска
Оператор замены
Оператор связывания
Встроенная процедура split

31. Римская числовая нотация

Постановка задачи

Идеи реализации

Перевод в римскую нотацию
Перевод из римской нотации

Разработка

Перевод в римскую нотацию: toroman.pl
Перевод из римской нотации: parseroman.pl

Готовая программа

Перевод в римскую нотацию: toroman.pl
Перевод из римской нотации: parseroman.pl

32. Поиск простых чисел с помощью регулярных выражений

Постановка задачи
Идеи реализации
Разработка
Готовая программа

33. Диофантовы уравнения

Постановка задачи
Идеи реализации
Разработка
Готовая программа

34. Спикер

Постановка задачи

Идеи реализации

Google Translate
Адрес URL
MPV

Разработка

Готовая программа

35. Соответствие шаблону

Постановка задачи

Идеи реализации

Неспортивное решение
Рекурсивное решение

Разработка

Неспортивное решение
Рекурсивное решение

Готовая программа

Неспортивное решение
Рекурсивное решение

36. Близость последовательностей

Постановка задачи

Идеи реализации

Подсчёт количества путей в прямоугольном графе
Рекурсивное решение
Динамическое программирование
Вычисление функции Беллмана
Алгоритм Майерса

Разработка

Рекурсивное решение
Алгоритм Вагнера — Фишера

Готовая программа

Рекурсивное решение
Итеративное решение
Алгоритм Вагнера — Фишера

37. «Жизнь» Джона Конвея

Постановка задачи

Идеи реализации

Порядок перебора клеток
Края клетчатого поля
Определение размера экрана
Управление терминалом
Расстановка клеток на первом кадре
Достойное завершение программы
Хранение состояния клетчатого поля

Разработка

Структура программы

Готовая программа

38. Объектно-ориентированное программирование

Идеология ООП

Примеры

Животные
Простые числа: фильтрация

Готовая программа

Животные
Простые числа: фильтрация

39. Битовая реализация числового множества

Идеи реализации

Класс как библиотечный модуль
Интерфейс класса BitSetSimple
Структура модуля
Данные объекта класса BitSetSimple
Манипуляции с отдельными битами в строке

Реализация методов класса BitSetSimple

Методы add и delete
Метод get
Метод set
Метод toString

Готовая программа (предварительная версия)

Дальнейшие улучшения класса BitSetSimple

Использование встроенной процедуры vec
Улучшения в конструкторе
Преобразование множества в список чисел
Создание копий
Минимальный и максимальный элементы, сумма
Проверка пустоты

40. Тетрис

Постановка задачи

Идеи реализации

Общие соображения
Объектная модель игры
Класс Term::Slangy
Системы координат
Класс Tetris::Figure
Класс Tetris::Game
Класс Tetris::UI

Разработка

Класс Tetris::Figure
Класс Tetris::UI
Класс Tetris::Game

Готовая программа

41. Бегущая строка

Постановка задачи

Идеи реализации

Шрифт
Формат BDF

42. Полимино

Постановка задачи

Идеи реализации

Рекурсивный подход
Кодирование фигур
Отросток
Утрата односвязности
Равные фигуры
Вывод результатов
XML и его приложения
Построение фигуры по клеткам
Класс Polyomino

Разработка

Класс Polyomino
Основная часть программы

Готовая программа

43. Черепашья графика

Общие сведения

Черепаший язык
Язык LOGO и системы черепашьей графики

Постановка задачи

Идеи реализации

Выбор графических средств
Состояние черепахи
Класс Turtle
Класс RGBColor

Разработка

Класс Turtle

Готовая программа

Класс Turtle
Класс RGBColor

44. L-системы

Общие сведения

Определение и пример
Развитие
L-системы и моделирование процессов роста
L-системы и фрактальные кривые
Фракталы
Скобочные L-системы и деревья
Обобщения
Алгоритмическая ботаника

Идеи реализации

Способы построения новых классов на основе имеющихся
Наследование
Класс LSystem
Простая реализация
«Ленивая» реализация

Разработка

Простая реализация
«Ленивая» реализация

Готовая программа

Простая реализация
«Ленивая» реализация

45. Задача коммивояжёра

Общие сведения

Задачи комбинаторной оптимизации
Метод градиентного спуска
Метод имитации отжига

46. Палиндромы

Постановка задачи

Идеи реализации

Построение палиндромов
Оценка качества палиндрома
Словарь
Словарь на основе массива
Словарь на основе двух упорядоченных массивов
Словарь на основе дерева
Словарь на основе сжатого дерева
Объектная модель палиндрома

Разработка

Класс Palindrome

Готовая программа

Класс Palindrome
Реализация со словарём на базе массива
Реализация со словарём на базе двух деревьев

47. Трассировка растровых изображений

Общие сведения

Цифровые модели изображения
Трассировка и растеризация

Постановка задачи

Идеи реализации

Интерфейс PerlMagick
Расстояние между изображениями
Метод имитации отжига
Объектная модель трассировщика — класс Tracer
Трассировка с использованием непрозрачных треугольников
Трассировка с использованием прозрачных треугольников

Готовая программа

48. Множество Мандельброта

Постановка задачи

Идеи реализации

Комплексные числа
Построение множества Мандельброта
Определение ограниченности орбиты
Способ изображения множества Мандельброта
Симметричность множества Мандельброта

Разработка

Готовая программа

49. Линейные уравнения

Общие сведения

Идеи реализации

Линейные уравнения и METAPOST
Объектная модель капсулы
Упрощение линейных выражений
Исключение неизвестной
Класс Capsule

Разработка

Приготовления
Методы known и value
Метод simplify
Метод equation

Готовая программа

50. Расчёт электрического сопротивления

Общие сведения

Резистор
Последовательное и параллельное соединение резисторов
Сложное соединение резисторов

Постановка задачи

Идеи реализации

Формат описания схемы
Вычисление сопротивления

Разработка

Готовая программа

Предметный указатель

Именной указатель

Библиография

Список иллюстраций

2.1. Блок-схема для конструкции if
2.2. Блок-схема для конструкции if … else
2.3. Блок-схемы для конструкций if … elsif и if … elsif … else
2.4. Блок-схема для цикла с предусловием
2.5. Блок-схема для цикла с постусловием
2.6. Блок-схема для цикла for
6.1. «Исчерпывание» площади круга
6.2. Вычисление числа $π$ методом Монте-Карло
6.3. Игла Бюффона
6.4. Игла Бюффона — области пересечения
9.1. Рекурсивные вызовы при вычислении чисел Фибоначчи
10.1. Треугольник Паскаля — Серпинского
10.2. Построение треугольника Серпинского
10.3. Связь треугольника Паскаля с простыми числами
14.1. Колёса для проверки чисел на простоту
15.1. Черепаха и Заяц: первый этап
15.2. Черепаха и Заяц: второй этап
15.3. Черепаха и Заяц: третий этап
17.1. Одометр (с сайта http://avto-all.com)
18.1. Глупая сортировка
18.2. Пузырьковая сортировка
18.3. Шейкерная сортировка
18.4. Сортировка вставками
18.5. Сортировка выбором
18.6. Упорядоченные бинарные деревья
19.1. Метод бисекций
19.2. Метод Ньютона
33.1. Решение линейных диофантовых уравнений с двумя неизвестными (страницы из брошюры [24])
36.1. Скриншот команды vim -d
36.2. Поиск LCS двух строк
36.3. Функция Беллмана в задаче поиска LCS
37.1. «Жизнь» Джона Конвея
37.2. Скриншот программы life.pl
37.3. Тор
38.1. Прохождение простых и составных чисел через фильтры
40.1. Фигуры тетриса
40.2. Скриншот программы tetris.pl
40.3. Системы координат в программе tetris.pl
41.1. Кернинг
41.2. Лигатура
41.3. Вёрстка
41.4. Растры для разных разрешений
41.5. Кривая Безье
42.1. Скриншот программы InkView
42.2. Преобразование контурного описания полимино в клеточное
43.1. Скриншот программы KTurtle
43.2. Скриншот программы InkScape
44.1. Множество Мандельброта
44.2. Дельта реки Лена
44.3. Стохастическая паутина
45.1. Вероятность мутации для метода имитации отжига
45.2. Решение задачи коммивояжёра методом имитации отжига
47.1. Растровое изображение и результат его трассировки программой autotrace
47.2. Определение принадлежности точки треугольнику
48.1. Множество Мандельброта
48.2. Множество Мандельброта (фрагмент)
48.3. Растровое изображение в режимах TrueColor и Palette
50.1. Резисторы (с сайта РадиоКот)
50.2. Схематическое изображение резистора
50.3. Последовательное и параллельное соединение резисторов
50.4. Смешанное соединение резисторов
50.5. Сложное соединение резисторов
50.6. Разметка схемы
50.7. Разметка схемы после перенумерации

Список таблиц

20.1. Кодовая страница ASCII (символы 0‥127)
20.2. Кодовая страница ISO8859-1 (вторая половина; символы 128‥255)
20.3. Кодовая страница KOI8-R (вторая половина; символы 128‥255)
20.4. Кодовая страница CP866 (вторая половина; символы 128‥255)
20.5. Кодовая страница CP1251 (вторая половина; символы 128‥255)
31.1. Запись десятичных разрядов римскими цифрами
40.1. Формы фигур тетриса и кодирующие их строки
44.1. Поколения снежинки Коха
44.2. L-система для кривой Серпинского
44.3. Поколения кривой Серпинского
44.4. L-система для дракона Хартера — Хейтвея
44.5. Поколения дракона Хартера — Хейтвея
44.6. L-система для кривой Госпера
44.7. Поколения кривой Госпера


		Предисловие