close

Вход

Забыли?

вход по аккаунту

?

FreeBASIC21

код для вставкиСкачать
Пособие по языку FreeBASIC и программированию для учащихся школ, студентов институтов и преподавателей.
1
Евгений Рыжов, инженер
Программирование на языке FreeBASIC
пособие для начинающих
Пособие для начинающих программировать на языке высокого уровня FreeBASIC.
Работа состоит из нескольких глав. В главе 21 "Числовой коктейль" – продолжение
пособия, которое будет интересно для учащихся школ, студентов институтов,
а также преподавателей.
Фрагмент 21. "Числовой коктейль"
Сидели пили вразнобой
"Мадеру", "старку", "зверобой",
И вдруг нас всех зовут в забой...
Владимир Высоцкий
"Случай на шахте" (1967)
Слова из песни Высоцкого призваны подсказать читателям брошюры: вопервых, что материал ее не слишком прихотлив, отдельные разделы слабо связаны, а
во-вторых, что объем не предполагает длительного чтения – ведь рассматриваются
арифметические задачки, а не проблемы высшей математики!
2
Ниже приведены мнения двух маститых математиков,
подтверждают справедливость вышесказанного автором:
которые лишь
Арифметика — одна из древнейших, возможно, самая древняя
отрасль человеческого знания, и в то же время наиболее глубокие
тайны находятся где-то рядом с её избитыми истинами.
Генри Джон Стивен Смит,
английский математик, 19 век
Я глубоко убежден: не нужна высшая математика в школе.
Более того, высшая математика убивает креативность.
Андрей Александрович Фурсенко,
доктор физико-математических наук, 21 век
Содержание
0.
1.
2.
2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
3.
3.1.
3.2.
3.2.1.
3.2.2.
3.2.3.
3.2.4.
3.2.5.
3.3.
4.
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Машинные константы . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Бесхитростные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . .
Метод простого перебора . . . . . . . . . . . . . . . . . . . . . . . . .
Последовательность Фибоначчи. Золотое сечение . . . . .
Факториал числа. Треугольник Паскаля . . . . . . . . . . . . .
Факторизация целых чисел . . . . . . . . . . . . . . . . . . . . . . . .
Простые числа. Треугольник Гилбрета . . . . . . . . . . . . . .
Числа Каталана. Матрица Ганкеля . . . . . . . . . . . . . . . . . .
Производящая функция. Введение . . . . . . . . . . . . . . . . . .
Представление функций степенными рядами . . . . . . . . .
Операции над степенными рядами . . . . . . . . . . . . . . . . . .
Использование рекуррентных формул . . . . . . . . . . . . . . .
Умножение степенных рядов . . . . . . . . . . . . . . . . . . . . . .
Деление степенных рядов . . . . . . . . . . . . . . . . . . . . . . . . .
Возведение рядов в степень . . . . . . . . . . . . . . . . . . . . . . .
Обращение степенных рядов . . . . . . . . . . . . . . . . . . . . . .
Использование рядов в приближенных вычислениях . .
Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
8
11
11
13
22
28
30
39
45
46
49
49
50
52
53
55
57
63
Примечание 1: На первую страницу вынесен фрагмент картины-иллюзии от Роба
Гонсалвеса "Пуститься в плаванье" (Корабль или арка). Роб
Гонсалвес (Rob Gonsalves) — канадский художник, работающий в стиле
магического реализма, родился в цыганской семье Торонто в 1959 году.
Познакомившись с творчеством Дали и Танги, Гонсалвес нарисовал
свои первые сюрреалистические картины. "Магический реализм"
Магритта и Эшера оказал большое влияние на его будущие работы.
3
Обращение
к Администрации Web-сайта http://www.docme.ru/
его уважаемым учредителям
 Жданов Павел Евгеньевич
 Скрипченко Антон Александрович
 Огороднищук Максим Степанович
 Форофонтов Олег Игоревич
постоянным пользователям и заинтересованным посетителям
DocMe - русское документохранилище
Велика была моя радость, когда в 2011 обнаружил в сети наиполезнейший
ресурс (возможно, он был запущен значительно раньше) – сайт, обеспечивающий
сервис, с помощью которого можно легко публиковать, надежно хранить и удобно
обмениваться текстовыми документами в электронном виде. Пять лет четкой работы
это, по сегодняшним меркам, очень большой срок – что-то должно было случиться и...
случилось – необоснованное блокирование хранящихся файлов:
FreeBASIC22
От:
Docme <abuse@docme.ru>
Кому:
eugene_r@mail.ru
Дата:
31 мая 2016, 10:36:46
Тема:
Ticket Received - Abuse from Евгений
Dear Евгений,
We would like to acknowledge that we have received your request and a
ticket has been created. Мы получили и зарегистрировали Ваш запрос...
A support representative will be reviewing your request and will send you a
personal response (usually within 24 hours).
To refer current ticket issue please use ticket id: 4265 (ответа нет)
FreeBASIC21
От:
Docme <abuse@docme.ru>
Дата:
25 декабря 2016, 12:07:56
Тема:
Ticket Received – Блокировка – см. ниже!
Dear Евгений,
We would like to acknowledge that we have received your request and a
ticket has been created.
A support representative will be reviewing your request and will send you a
personal response.(usually within 24 hours).
To refer current ticket issue please use ticket id: 8265 (ответа нет)
К сожалению, не могу назвать точную дату блокирования файлов и
причину блокирования файлов, но подозреваю, что это печальный результат
неблагоприятного расположения звезд на небе...
Очень прошу инициатора блокирования файлов сообщать автору
"интеллектуальной собственности" причину по электронной почте
Eugene N. Ruzhov <eugene_r@mail.ru>
Всегда ваш, Евгений Рыжов, инженер-металлург, Москва
08 января 2017 года
4
0. Предисловие.
Подумаешь, тоже работа, Беспечное это житье:
Подслушать у музыки что-то
И выдать шутя за свое.
"Поэт" (1959)
Анна Андреевна Ахматова (1889—1966)
Материал брошюры подобран исходя из пожеланий, высказанных в письмах
читателей! При этом с прискорбием отмечу, что обсуждаемые в письмах вопросы,
немного обидели – ведь почти на все эти вопросы можно найти ответы в уже
доступных брошюрах автора... Весенний семестр 2016 года, кроме того показал, что
перед начинающими самостоятельно программировать постоянно встает вопрос о
соотношении необходимых сведений из области программирования и из области
математики: действительно ли программисту для успешной работы требуется
знание математики и, если нужно, то в какой мере?
Ответ зависит от того, что называть "математикой" и о каком
"программировании" будем говорить. В общем случае "программирование" — процесс
создания компьютерных программ. По известному выражению Никлауса Вирта
"Программы = алгоритмы + структуры данных" [01]; иными словами,
непосредственными задачами программирования являются конструирование новых и
подбор существующих используемых алгоритмов для целенаправленной обработки
абстрактных структур данных. Можно условно разделить все создаваемые программы
по назначению на:
 системные (предназначенные для управление компонентами компьютерной
системы);
 прикладные (предназначенные для выполнения конкретных пользовательских
задач);
 инструментальные (предназначенные для использования в ходе проектирования,
разработки и сопровождения системных и прикладных программ).
Каждая группа программ требует от программиста знания и использования
различных разделов математик в различном объеме. Для такой работы кое-какая
квалификация программиста необходима, но, как уверяют эксперты, сама работа
совсем не утомительная, хорошо оплачивается, а работать можно в пижаме и домашних
тапочках. Билл Гейтс, например, как-то сказал, что предпочитает нанимать для
выполнения сложной задачи в Microsoft ленивых программистов, потому что они
"всегда найдут самый простой способ для её выполнения". Не следует серьезно
относиться к этому заявлению, особенно если речь идет о создателях прикладных
программ – им нужно, прежде всего, уметь четко формулировать постановку задачи, а
следовательно провести детальное предварительное обследование объекта... Одно
можно сказать наверняка — умение оперировать абстрактными понятиями,
несомненно, помогает прикладным программистам в их работе.
Правильное решение проблемы абстрагирования имеет большое значение для
математики. С первого взгляда может показаться, что процесс абстрагирования в
5
математике состоит просто-напросто в том, что математик последовательно
отбрасывает все нематематические свойства и удерживает лишь свойства
математические. Но реальные предметы не обладают в точности теми свойствами,
которые отображаются в математике в виде сформулированных ею идеализации,
поэтому при образовании понятий важную роль играют такие виды абстракции, как
абстракция потенциальной осуществимости, когда отвлекаются от реальных границ
конструктивных возможностей человеческого сознания, связанных с ограниченностью
жизни человека в пространстве и времени; абстракция актуальной бесконечности,
которая связана с отвлечением от неосуществимости выполнить бесконечное число
актов проверки и оперирует с бесконечными множествами как с конечными. Подобным
вопросам посвящена старенькая, но не устаревшая, на мой взгляд, книга специалиста
по логике и методологии математики и естествознания Георгия Ивановича Рузавина
[02].
Не заморачиваясь определением понятия "алгоритм", просто примем к
сведению, что это некоторая конструктивная процедура и посмотрим, с какими
объектами алгоритмы имеют дело. В этой брошюре ограничим круг рассматриваемых
объектов простейшими элементами данных – числами. Как известно, число является
основным понятием математики, используемым для количественной характеристики,
сравнения, нумерации объектов и их частей. Письменными (графическими) знаками
для обозначения чисел служат цифры, а также символы математических операций.
Возникнув ещё в первобытном обществе из потребностей счёта, понятие числа с
развитием науки значительно расширилось. Цифры образуют систему знаков ("букв")
для записи чисел ("слов") (числовые знаки). Слово "цифра" без уточнения обычно
означает один из следующих десяти ("алфавит") знаков: 0 1 2 3 4 5 6 7 8 9 (т.н.
"арабские цифры" или точнее "западно-арабские цифры"). Многосторонний анализ
возникновения чисел и их развития в разных культурах приводит в своем
фундаментальнм труде [03] немецкий ученый-математик и историк науки Карл
Меннингер (1898-1963).
"Бог создал первые десять чисел, остальное — дело рук человека" -. сказал
немецкий математик Леопольд
Кронекер (1823—1891). Он имел
в виду, что могучее здание
математики построено на самой,
самой простой, элементарной
арифметике. Если не углубляться
в религию, то утверждение о том,
что Бог дал нам первые десять
чисел, означает, что эти числа
всегда были частью природы.
Иными словами математика
сначала
была
открыта
человечеством, а затем начала
обрастать деталями благодаря
стараниям бригады математиков.
Математика сегодня это наука о
структурах,
порядке
и
отношениях, сложившаяся на
основе
операций
подсчёта,
измерения и описания формы объектов. Математические объекты создаются путём
6
идеализации свойств реальных или других, уже существующих, математических
объектов и записи этих свойств на формальном языке. Математика не относится к
естественным наукам, но широко используется в них как для точной формулировки их
содержания, так и для получения новых результатов. Математика —
фундаментальная наука, предоставляющая (общие) языковые средства другим
наукам; тем самым она выявляет их структурную взаимосвязь и способствует
нахождению самых общих законов природы.
Завершить предисловие хочу предостережением: добывая актуальные "знания"
в сети, пожалуйста, будьте осмотрительны – в последнее время (хочу надеяться – не
преднамеренно) появилось множество досадных описок. Один из последних примеров
связан с модным "проверяльщиком чисел" на сайте:
http://aboutnumber.ru/



Сайт предназначен давать полезную информацию о свойствах чисел.
После приглашения ввел число: 111111111 и получил объемистый листинг:
Сто одиннадцать миллионов сто одиннадцать тысяч сто одиннадцать.
Целое рациональное число 111111111 является составным числом.
Квадрат числа: 12345678987654320. Чудно, однако!!!
Попробуем получить правильный ответ:
'
P R O G R A M "AP_a123"
'
12.08.1994
'------------------------------------------------------------'
Демонстрация правила: "Доверяй, но проверяй!"
'------------------------------------------------------------'
' http://aboutnumber.ru/111111111
' Квадрат числа: 12345678987654320?
#Lang "FB"
' режим совместимости с FreeBASIC
Open Cons For Output As #2
'Open "AP_a123.res" For Output As #2
Dim As LongInt N, N2
Print #2,: Print #2, " Trust but check!"
N = 11
'
Do
N2 = N^2
Print #2, Using " N = ############# N^2
=########################"; N; N2
N = 10*N+1
Loop While N < 11111111111
'
Close #2
Print: Print " Press to complete!!!"
Sleep
7
'
'
'
'
'
'
'
'
'
'
'
Результат выполнения программы:
Trust but check!
N =
11 N^2 =
121
N =
111 N^2 =
12321
N =
1111 N^2 =
1234321
N =
11111 N^2 =
123454321
N =
111111 N^2 =
12345654321
N =
1111111 N^2 =
1234567654321
N =
11111111 N^2 =
123456787654321
N =
111111111 N^2 =
12345678987654321
N =
1111111111 N^2 =
1234567900987654321
Ну, как тут ни вспомнить знаменитое пятистишье (1829):
О, сколько нам открытий чудных
Готовят просвещенья дух
И опыт, сын ошибок трудных,
И гений, парадоксов друг,
И случай, бог изобретатель...
Александр Сергеевич Пушкин
(1799 - 1837)
Философское отступление:
Мы живем в аристотелевской парадигме! А философы постоянно спорят, что
было бы, развивайся человечество в платоновской матрице? Быть может, не
существовало бы "Макдонольсов" и сериала "Ранетки", а деревья были бы чуточку
зеленее, а небо над нами чуточку голубее...
8
1. Машинные константы.
В процессорах Intel все операции с плавающей запятой выполняет специальное
устройство - FPU (Floating Point Unit) с собственными регистрами и набором команд,
поставлявшееся сначала в виде блока сопроцессора (8087, 80287, 80387, 80487), а
начиная с модели 80486DX - встраивающееся в основной процессор. При этом FPU
полностью соответствует стандартам IEEE 754 и IEEE 854 (с 80486). Подробности
можно найти в фундаментальных книгах по программированию на ассемблере [04] и по
архитектуре компьютера [05]. Здесь же, рассматривая FPU как черный ящик, отметим
лишь следующее: до 80-х годов каждый производитель компьютеров поддерживал
собственный формат чисел с плавающей точкой, которые отличались друг от друга.
Более того, в некоторых устройствах арифметические действия выполнялись
неправильно, поскольку арифметика с плавающей точкой имеет некоторые тонкости,
которые не очевидны для среднестатистического разработчика аппаратного
обеспечения. Чтобы изменить эту ситуацию, в конце 70-х годов Институт инженеров
по электротехнике и электронике (IEEE - Institute of Electrical and Electronics Engineers)
учредил комиссию по стандартизации арифметики с плавающей точкой. Целью было
не только дать возможность переносить данные с одного компьютера на другой, но и
обеспечить разработчиков аппаратного обеспечения заведомо правильной моделью. В
результате в 1985 году вышел стандарт IEEE 754. В настоящее время большинство
процессоров содержат команды с плавающей точкой, которые соответствуют этому
стандарту. В отличие от многих стандартов, ставших плодом неудачных компромиссов
и мало кого устраивавших, этот стандарт неплох, причем в значительной степени
благодаря тому, что его изначально разрабатывал один человек, профессор математики
университета Беркли Вильям Каган (William Kahan)...
Первые выводы, которые делает начинающий программист, сталкивающийся с
числами с плавающей точкой, следующие:
 При работе с действительными числами на точное равенство надеяться не стоит
даже при проведении простейших вычислений.
 Погрешности, связанные с неточным представлением действительных чисел, имеют
тенденцию накапливаться.
 В машинной действительной арифметике нарушаются даже простейшие свойства
чисел (например, коммутативность сложения), на которые с детства привыкли
надеяться.
Используя "научный метод" формальной абстракции (выделение особо важных
свойств предмета, которые сами по себе и независимо от предмета не существуют)
просто рассмотрим некоторые особенности работы с числами с плавающей точкой.
Какие основные внешние параметры машинной арифметики, интересуют
программиста? Прежде всего, это — максимальное представимое число, минимальное
предствимое число и точность машинного представления... В остальном, программист
полагается на лояльность "черного ящика" под названием FPU. Напомню: число с
плавающей точкой это принятая модель представления действительных чисел, в
которой число хранится в виде мантиссы и показателя степени и состоит из:
 Знака мантиссы (указывающего на отрицательность или положительность числа).
 Мантиссы (выражающей значение числа без учёта порядка).
 Знака порядка.
 Порядка (выражающего степень основания числа, на которое умножается
мантисса).
9
При этом существуют:
 наибольшее число с плавающей точкой OFL (OverFlow Level)
 наименьшее число с плавающей точкой UFL (UnderFlow Level)
Между значениями OFL и UFL крайне неравномерно распределены, представленные в
формате с плавающей точкой, действительные числа... Об этом достаточно популярно
сказано в книгах по машинным вычислениям [06] и [07], которые уже упоминались в
брошюрах ранее. В этих книгах приведены сведения о двух константах, определяемых
для каждой конкретной вычислительной системы:
 Машинный нуль (NUL - Machine zero) — числовое значение с таким
отрицательным порядком, которое воспринимается машиной как нуль.
 Машинный эпсилон (EPS - Machine epsilon) — числовое значение, меньше которого
два соседних числа становятся неразличимыми.
Константы OFL и UFL определяются главным образом количеством битов
показателя, тогда как EPS - количеством битов мантиссы. Тем самым эти константы
характеризуют разные части представления с плавающей точкой. Имеют место
неравенства 0 < UFL < EPS < OFL...
Об этом уже сообщалось в брошюре Программирование на языке FreeBASIC
"Фрагмент 5. Некоторые штришки":
...есть две "цифири" без которых просто невозможно двигаться дальше!
Поэтому ниже воспроизводится программа на языке FreeBASIC, помогающая
понять смысл и оценить величину этих констант (одновременно проверяется
корректность "закладки" компилятором констант в память):
'
P R O G R A M "AP_NulEps0FB"
'
12.10.2012
'------------------------------------------------------------'
Программа для определения "машинных констант"
'------------------------------------------------------------'
Рассмотрены стандартные типы данных.
'
#Lang "FB"
' режим FreeBASIC-совместимости
' описание используемых переменных
Dim As Single PiS, EpsS, Eps1S, NulS, Nul1S
Dim As Double PiD, EpsD, Eps1D, NulD, Nul1D
Open Cons For Output As #2
'Open "AP_NulEps.res" For Output As #2
Print #2,: Print #2, " Specific Machine Constants": Print #2,
' стандартное представление переменных компилятором
PiS = 3.1415926535897932384626433832795028841971693993751
PiD = 3.1415926535897932384626433832795028841971693993751
Print #2, " Machine representation of Pi:"
Print #2, Using "
Single: #.#####################"; PiS
Print #2, Using "
Double: #.#####################"; PiD
'
' оценка величины машинного зпсилон
Print #2, " Performance of the machine Epsilon:"
10
EpsS = 1
' начальное значение
Do
' выполнять циклически
EpsS = EpsS/2
Eps1S = 1 + EpsS
Loop While Eps1S > 1
Print #2, "
Single:"; 2*EpsS
EpsD = 1
' начальное значение
Do
' выполнять циклически
EpsD = EpsD/2
Eps1D = 1 + EpsD
Loop While Eps1D > 1
Print #2, "
Double:"; 2*EpsD
'
' оценка величины машинного нуля
Print #2, " Representation of the machine Zero:"
NulS = 1
' начальное значение
Do
' выполнять циклически
Nul1S = NulS
NulS = NulS/2
Loop While NulS > 0
Print #2, "
Single:"; Nul1S
NulD = 1
' начальное значение
Do
' выполнять циклически
Nul1D = NulD
NulD = NulD/2
Loop While NulD > 0
Print #2, "
Double:"; Nul1D
'
Close #2
Print: Print "
Press to complete!!!"
Sleep
' Результат выполнения программы:
' Specific Machine Constants
' Machine representation of Pi:
'
Single: 3.141592741012573000000
'
Double: 3.141592653589793000000
' Performance of the machine Epsilon:
'
Single: 1.192093e-007
'
Double: 2.220446049250313e-016
' Representation of the machine Zero:
'
Single: 1.401298e-045
'
Double: 4.940656458412465e-324
Моя малышка показывает неплохие результаты, пожалуй, все как при
использовании "передовых" вычислительных комплексов!!!
11
2. Бесхитростные алгоритмы.
Простота делает жизнь не только
более приятной, но... и более
чистой и прекрасной.
Мишель де Монтень (1533—1592)
В этом разделе собраны небольшие программы на языке FreeBASIC
иллюстрирующие бесхитростные (примитивные) алгоритмы, которые эпизодически
вдруг оказываются необходимыми, а в сети сразу не находятся!
2.1. Метод простого перебора.
Многие задачи, учитывая характеристики современных компьютеров можно
решать, используя "бесхитростный алгоритм" простого перебора возможных
(правдоподобных) вариантов. Просто в каждой задачке желательно заранее определить
круг возможных вариантов.
Рассмотрим следующую
формулируется так:
задачу
для
младших
школьников,
которая
Мужику приспичило купить ровно 100
голов скота (бывает же такое)...
Сколько можно купить быков, коров и
телят имея только 100 рублей?
если
бык стоит 10 рублей,
корова - 5 рублей,
а теленок - 0.5 рубля.
Справка для горожан: указанные
животные выглядят примерно как на
рисунке слева!
Обозначим через B - количество быков; K - количество коров; T - количество
телят. После этого можно записать систему из двух уравнений:
B + K + T = 100
10*B + 5*K + 0.5*T = 100
Для решения задачи ниже предлагается программа на языке FreeBASIC,
включающая основной (бесхитростный) вариант и два варианта уточнения...
12
'
P R O G R A M "AP_ShoppingPets"
'
10.10.2012
'------------------------------------------------------------'
Решение задачи о покупке домашних животных перебором
'------------------------------------------------------------'
#Lang "FB"
' режим FreeBASIC-совместимости
'
Dim As Integer B, K, T
' количество голов животных
Dim As Single cB, cK, cT ' стоимость животного
Dim As Integer I
' выполненых проверок условия
Open Cons For Output As #2
'Open "AP_ShoppingPets.res" For Output As #2
Print #2, : Print #2, " Solving the problem of buying pets"
cB = 10: cK = 5: cT = 0.5
' Вариант 1: Полный перебр
I = 0
For B = 0 To 100
For K = 0 To 100
For T = 0 To 100
I = I + 1
If (cB*B+cK*K+cT*T = 100) And (B+T+K = 100) Then
Print #2, Using " Byk = ### Krv = ### Tel = ###"; B;
K; T
EndIf
Next T
Next K
Next B
Print #2, " Number of Inspections conditions ="; I
'
' Вариант 2: Сужение диапазона
I = 0
For B = 0 To 10
' 100/10
For K = 0 To 20
' 100/5
For T = 0 To 100 ' 100/0.5
I = I + 1
If (cB*B+cK*K+cT*T = 100) And (B+T+K = 100) Then
Print #2, Using " Byk = ### Krv = ### Tel = ###"; B;
K; T
EndIf
Next T
Next K
Next B
Print #2, " Number of Inspections conditions ="; I
'
' Вариант 3: Вычеркивание цикла телят
I = 0
For B = 0 To 10
For K = 0 To 20
T = 100 - (B+K)
I = I + 1
If (cB*B+cK*K+cT*T = 100) And (B+T+K = 100) Then
13
Print #2, Using "
Byk = ###
Krv = ###
Tel = ###"; B;
K; T
EndIf
Next K
Next B
Print #2, " Number of Inspections conditions ="; I
Close #2
Print: Print "
Press to complete!!!"
Sleep
' Результат выполнения программы:
' Solving the problem of buying pets
' Byk =
1 Krv =
9 Tel = 90
' Number of Inspections conditions = 1030301
' Byk =
1 Krv =
9 Tel = 90
' Number of Inspections conditions = 23331
' Byk =
1 Krv =
9 Tel = 90
' Number of Inspections conditions = 231
Согласитесь, небольшие "уточнения" алгоритма дают существенную экономию
времени решения задачи.
2.2. Последовательность Фибоначчи. Золотое сечение.
Красота и гармония стали важнейшими категориями
познания, в определенной степени даже его целью, ибо
в конечном итоге художник ищет истину в красоте,
а ученый — красоту в истине.
Васютинский Н.А., инженер-металлург
Древнейшие сведения о "золотой пропорции" относятся ко времени расцвета
античной культуры. О ней упоминается в трудах великих философов Греции Пифагора,
Платона, Эвклида. Платон привел формулировку золотого сечения, одну из самых
древних, дошедшую до нашего времени. Сущность ее сводится к тому, что для
соединения двух частей с третьей совершенным образом необходима пропорция,
которая бы "скрепила" их в единое целое. При этом одна часть целого должна так
относиться к другой, как целое к большей части. Такая пропорция отвечает
гармоническому соединению, она и является золотой. Термин "Золотое Сечение" был
введен Леонардо да Винчи, он назвал его "божественной пропорцией". Усилием
математиков золотая пропорция была объяснена, изучена и глубоко проанализирована.
В этих условиях появление книги по математике, написанной в 1202 году
итальянским математиком Леонардо из Пизы, явилось важным событием в "научной
жизни общества". В книге "Liber abacci" (Книга об абаке) были собраны известные в то
время сведения по математике, приводились примеры решения всевозможных задач. И
среди них была простая, не лишенная практической ценности для предприимчивых
итальянцев, задача о кроликах: "Сколько пар кроликов в один год от одной пары
рождается?" Далее в задаче поясняется, что природа кроликов такова, что через месяц
пара их производит на свет другую пару, а начинают размножаться кролики со второго
месяца после своего рождения. В результате решения этой немудреной задачи
14
получился ряд чисел 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и т.д. Этот ряд чисел был позже
назван именем Фибоначчи, так называли Леонардо (Fibonacci — сокращенное filius
Bonacci, то есть сын Боначчи, Боначчо" (Добродушный) - прозвище отца). Это имя уже
упоминалось в брошюрах:
Фрагмент 3. Некое техническое устройство.
2.2.5. Троичная ЭВМ "Сетунь".
Фрагмент 9. Методы оптимизации.
4.2. Поиск минимума методом Фибоначчи.
В настоящее время ряд, открытый Фибоначчи, узаконен в Онлайнэнциклопедии целочисленных последовательностей (On-Line Encyclopedia of Integer
Sequences - OEIS): https://oeis.org/A000045
Fibonacci numbers - последовательность A000045 в OEIS:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
Фибоначчи итальянский математик
(около 1170 — не ранее 1240)
О теории чисел Фибоначчи,
выросшей из знаменитой "задачи о
кроликах", можно прочитать в
небольшой
книге
Николая
Николаевича Воробьева [08].
Особенность
последовательности
чисел состоит в том, что каждый ее
член, начиная с третьего, равен
сумме двух предыдущих 2 + 3 =
5; 3 + 5 = 8; 5 + 8 = 13,
8 + 13 = 21; 13 + 21 = 34;
21 + 34 = 55 и т.д., а отношение
смежных чисел ряда приближается к
отношению
золотого
деления:
21/34 = 0,617, а 34/55 =
0,618.
Ряд Фибоначчи мог бы остаться только математическим казусом, если бы не то
обстоятельство, что все исследователи золотого деления в растительном и в животном
мире, не говоря уже об искусстве, неизменно приходили к этому ряду как
арифметическому выражению закона золотого деления. Ученые продолжали активно
развивать теорию чисел Фибоначчи и золотого сечения. Ю.Матиясевич с
использованием чисел Фибоначчи решает 10-ю проблему Гильберта. Возникают
изящные методы решения ряда кибернетических задач (теории поиска, игр,
программирования) с использованием чисел Фибоначчи и золотого сечения. В США
создается даже Математическая Фибоначчи-ассоциация, которая с 1963 года выпускает
специальный журнал. Одним из достижений в этой области является открытие
обобщенных чисел Фибоначчи и обобщенных золотых сечений. Но вот что странно:
произведение и частное двух любых различных чисел Фибоначчи, отличных от
единицы, никогда не является числом Фибоначчи...
15
Спираль Фибоначчи – графический образ последовательности чисел Фибоначчи.
На рисунке квадраты с зелеными сторонами имеют площади пропорциональные
числам Фибоначчи...
Если строки в
треугольнике
Паскаля (см. далее)
выровнять по левому
краю, то суммы
чисел,
расположенных
вдоль диагоналей,
идущих слева
направо и снизу
вверх, равны числам
Фибоначчи.
16
Члены знаменитой последовательности целых чисел (A000045 в OEIS) можно
определить с помощью рекуррентного соотношения:
F(n)  F(n  1)  F(n  2) для n  1
и двух начальных условий:
F(0)  0, F(1)  1
или в явном виде по формуле Бине как функцию от n :
F( n ) 
1  1 5 


5 2 


n
n

1  1 5 


5 2 


.
Следует заметить, что константу

1 5
 1.61803
2
называют "золотым сечением"
На первый взгляд трудно поверить в то, что эта формула, в которой в
произвольную целую степень возводятся два иррациональных числа, определяет n-ый
элемент последовательности целых чисел Фибоначчи, но тем не менее это так!
Справка: Жак Филипп Мари Бине (Jacques Philippe Marie Binet; 1786—1856) —
французский математик, механик и астроном.
Программа вычисления числа Фибоначчи без использования рекурсии
приведена ниже:
'
P R O G R A M "AP_Fibonacci0FB"
'
10.05.2015
'------------------------------------------------------------'
Программа итерационного вычисления числа Фибоначчи
'------------------------------------------------------------#Lang "FB"
' режим FreeBASIC-совместимости
'
' подпрограмма-функция итерационного определения чисел
Function Fib(N As Byte) As LongInt ' для (0 <= N <= 92)
Dim As LongInt Fib0, Fib1, Fib2
Dim As Byte I
Fib0 = 0: Fib1 = 1
If N <= 0 Then
Fib2 = Fib0
ElseIf N = 1 Then
Fib2 = Fib1
Else
For I = 2 To N
Fib2 = Fib1 + Fib0
Fib0 = Fib1: Fib1 = Fib2
Next I
EndIf
Fib = Fib2
End Function
'
17
' подпрограмма-функция вычисления по формуле Бине
Function FiBin(N As Byte) As LongInt
Dim As Double Fi, Fj, Fb
Fi = (1 + Sqr(5))/2: Fj = (1 - Sqr(5))/2
Fb = (Fi^n - Fj^n)/Sqr(5)
FiBin = Fb
End Function
'
' Основной модуль программы
Dim As Byte M, Mmax
Open Cons For Output As #2 ' вывод на консоль
'Open "AP_Fibonacci.res" For Output As #2 ' вывод в файл
Print #2,: Print #2," Table of values of the Fibonacci
Numbers:"
Mmax = 16
Print #2, "
M
Fib(M) FiBin(M)"
For M = 0 To Mmax
Print #2, Using "
## ######## ########"; M; Fib(M);
FiBin(M)
Next M
Close #2
Print: Print " Press to complete!!!"
Sleep
' Результат выполнения программы:
' Table of values of the Fibonacci Numbers:
'
M
Fib(M) FiBin(M)
'
0
0
0
'
1
1
1
'
2
1
1
'
3
2
2
'
4
3
3
'
5
5
5
'
6
8
8
'
7
13
13
'
8
21
21
'
9
34
34
'
10
55
55
'
11
89
89
'
12
144
144
'
13
233
233
'
14
377
377
'
15
610
610
'
16
987
987
Программа вычисления числа Фибоначчи с использованием рекурсии
приведена ниже:
'
P R O G R A M "AP_Fibonacci1FB"
'
10.05.2015
'------------------------------------------------------------'
Программа рекурсивного вычисления числа Фибоначчи
'-------------------------------------------------------------
18
#Lang "FB"
' режим FreeBASIC-совместимости
'
' подпрограмма-функция рекурсивного определения чисел
Function Fib(N As Byte) As LongInt ' для (0 <= N <= 92)
If N <= 0 Then
Fib = 0
ElseIf N = 1 Then
Fib = 1
Else
Fib = Fib(N-1) + Fib(N-2)
EndIf
End Function
'
' подпрограмма-функция вычисления по формуле Бине
Function FiBin(N As Byte) As LongInt
Dim As Double Fi, Fj, Fb
Fi = (1 + Sqr(5))/2: Fj = (1 - Sqr(5))/2
Fb = (Fi^n - Fj^n)/Sqr(5)
FiBin = Fb
End Function
'
' Основной модуль программы
Dim As Byte M, Mmax
Open Cons For Output As #2 ' вывод на консоль
'Open "AP_Fibonacci.res" For Output As #2 ' вывод в файл
Print #2,: Print #2," Table of values of the Fibonacci
Numbers:"
Mmax = 16
Print #2, "
M
Fib(M) FiBin(M)"
For M = 0 To Mmax
Print #2, Using "
## ######## ########"; M; Fib(M);
FiBin(M)
Next M
Close #2
Print: Print " Press to complete!!!"
Sleep
' Результат выполнения программы:
очевидно, совпадает с результатом предыдущей программы!
Иногда числа Фибоначчи рассматривают и для отрицательных значений n, как
двусторонне бесконечную последовательность. При этом члены с отрицательными
индексами легко получить с помощью эквивалентной формулы "назад":
F(n)  F(n  2)  F(n  1)
Ниже приведен текст программы на языке FreeBASIC для вычисления двусторонней
последовательности Фибоначчи.
'
P R O G R A M "AP_Fibonacci2FB"
'
11.05.2015
'------------------------------------------------------------' Числа Фибоначчи для положительных и отрицательных значений
'------------------------------------------------------------#Lang "FB"
' режим FreeBASIC-совместимости
19
' подпрограмма-функция вычисления по формуле Бине
Function FiBin(N As Byte) As LongInt
Dim As Double Fi, Fj, Fb
Fi = (1 + Sqr(5))/2: Fj = (1 - Sqr(5))/2
Fb = (Fi^n - Fj^n)/Sqr(5)
FiBin = Fb
End Function
' Основной модуль программы
Dim As Integer n, F(-12 To 12)
Open Cons For Output As #2 ' вывод на консоль
'Open "AP_Fibonacci.res" For Output As #2 ' вывод в файл
Print #2,: Print #2, " Fibonacci sequence"
F(0) = 0: F(1) = 1
For n = 2 To 12
F(n) = F(n-1) + F(n-2)
Print #2, Using " F(###) = #### FB = ####"; n; F(n);
FiBin(n)
Next
' числа Фибоначчи рассматривают и для отрицательных номеров
For n = -1 To -12 Step -1
F(n) = F(n+2) - F(n+1)
Print #2, Using " F(###) = #### FB = ####"; n; F(n);
FiBin(n)
Next
Close #2
Print: Print " Press to complete!!!"
Sleep
' Результат выполнения программы:
' Fibonacci sequence
' F( 2) =
1 FB =
1
' F( 3) =
2 FB =
2
' F( 4) =
3 FB =
3
' F( 5) =
5 FB =
5
' F( 6) =
8 FB =
8
' F( 7) =
13 FB =
13
' F( 8) =
21 FB =
21
' F( 9) =
34 FB =
34
' F( 10) =
55 FB =
55
' F( 11) =
89 FB =
89
' F( 12) = 144 FB = 144
' F( -1) =
1 FB =
1
' F( -2) =
-1 FB =
-1
' F( -3) =
2 FB =
2
' F( -4) =
-3 FB =
-3
' F( -5) =
5 FB =
5
' F( -6) =
-8 FB =
-8
' F( -7) =
13 FB =
13
' F( -8) = -21 FB = -21
' F( -9) =
34 FB =
34
' F(-10) = -55 FB = -55
' F(-11) =
89 FB =
89
' F(-12) = -144 FB = -144
20
Легко заметить, что F(  n)  ( 1)
n1
F (n )
Здесь стоит упомянуть новый класс рекуррентных числовых последовательностей,
которые являются обобщением классических чисел Фибоначчи. Эти числовые
последовательности, названные Лямбда-числами Фибоначчи, привели к открытию
нового класса математических констант, названных "металлическими пропорциями".
Количество металлических пропорций теоретически бесконечно, а их частным случаем
является классическая золотая пропорция.
Рассмотрим рекуррентное соотношение:
F(n)   F(n  1)  F(n  2) для n  1,   0 действительное число
и двух начальных условий:
F(0)  0, F(1)  1
Это рекуррентное соотношение «генерирует» бесконечное количество новых
числовых последовательностей, так как каждому  соответствует своя числовая
последовательность. Важно подчеркнуть, что их частными случаями являются
некоторые числовые последовательности, получившие широкую известность в
современной науке. В частности, для случая  = 1 это рекуррентное соотношение
порождает классические числа Фибоначчи, а для случая  = 2 - порождает числа
Пелля... Ниже приведена программа генерирования трех последовательностей лямбдачисел Фибоначчи.
'
P R O G R A M "AP_Fibonacci3FB"
'
12.05.2015
'------------------------------------------------------------'
Генерирование последовательностей лямбда-чисел Фибоначчи
'------------------------------------------------------------'
#Lang "FB"
' режим FreeBASIC-совместимости
' Подпрограмма-функция вычисления лямбда-числ Фибоначчи
Function Fib(Lmb As Byte, n As Byte) As LongInt
Dim As LongInt Fib0, Fib1, Fib2
Dim As Byte i
Fib0 = 0: Fib1 = 1
If n <= 0 Then
Fib2 = Fib0
ElseIf n = 1 Then
Fib2 = Fib1
Else
For i = 2 To n
Fib2 = Lmb*Fib1 + Fib0
Fib0 = Fib1: Fib1 = Fib2
Next i
EndIf
Fib = Fib2
End Function
'
21
' Основной модуль программы
Dim As Byte M, Mmax, Lmb
Open Cons For Output As #2 ' вывод на консоль
'Open "AP_Fibonacci.res" For Output As #2 ' вывод в файл
Print #2,: Print #2," Table of values of the Fibonacci
Numbers:"
Mmax = 16: Lmb = 2
Print #2, "
M
Fib1(M)
Fib2(M)
Fib3(M)"
For M = 0 To Mmax
Print #2, Using "
##"; M;
For Lmb = 1 To 3
Print #2, Using "
########"; Fib(Lmb, M);
Next Lmb
Print #2,
Next M
Close #2
Print: Print " Press to complete!!!"
Sleep
' Результат выполнения программы:
' Table of values of the Fibonacci Numbers:
'
M
Fib1(M)
Fib2(M)
Fib3(M)
'
0
0
0
0
'
1
1
1
1
'
2
1
2
3
'
3
2
5
10
'
4
3
12
33
'
5
5
29
109
'
6
8
70
360
'
7
13
169
1189
'
8
21
408
3927
'
9
34
985
12970
'
10
55
2378
42837
'
11
89
5741
141481
'
12
144
13860
467280
'
13
233
33461
1543321
'
14
377
80782
5097243
'
15
610
195025
16835050
'
16
987
470832
55602393
Даже для математиков может оказаться совершенно неожиданным
доказательство существования во множестве целых чисел бесконечного количества
рекуррентных числовых последовательностей, подобных числам Фибоначчи, которые
обладают уникальным математическим свойством, выраженным соотношением:
F 2 (n )  F(n  1)  F(n  1)  ( 1)n 1
22
2.3. Факториал числа. Треугольник Паскаля.
01. После того опять явился Иисус
ученикам Своим при море
Тивериадском...
09. Когда же вышли на землю, видят
разложенный огонь и на нем лежащую
рыбу и хлеб.
10. Иисус говорит им: принесите рыбы,
которую вы теперь поймали.
11. Симон Петр пошел и вытащил на
землю сеть, наполненную большими
рыбами, которых было сто пятьдесят три;
и при таком множестве не прорвалась
сеть.
Евангелие от Иоанна. Глава 21.
Одно из первых упоминаний о
нумерологии
в
истории
западной
цивилизации содержится в 21-й главе
Евангелия от Иоанна, где рассказывается
о чуде в море Тивериадском, свидетелем
которому стал Симон Петр, поймавший в
сеть за один раз 153 рыбы. Разумеется,
это чудо сотворил Иисус Христос. Число
153 непременно должно обладать какимито особыми свойствами. Рассмотрим
равенства для факториалов:
1!
2!
3!
4!
5!
=
=
=
=
=
1
1*2 = 2
1*2*3 = 6
1*2*3*4 = 24
1*2*3*4*5 = 120
Сумма равна 153...
Произведение первых n целых чисел, называемое n-факториал, оказалось
настолько важным, что теперь его рассматривают как основную арифметическую
операцию. Для оценки значения n! при очень большой величине n можно
воспользоваться формулой Стирлинга. В этом разделе факториалы будут нужны для
вычисления биномиальных коэффициентов. Напомню, в математике биномиальные
коэффициенты — это коэффициенты в разложении бинома Ньютона, т.е. выражения
(1+x)^n на отдельные слагаемые по степеням x, причём n может быть как целым, так
и произвольным действительным (или даже комплексным) числом! В этом случае
бином представляет собой бесконечный ряд... Несмотря на отсутствие комбинаторного
смысла, случай n = —1 оказывается одним из важнейших частных случаев. Некоторые
нецелые индексы, типа 1/2, также оказываются полезными.
Ниже представлена программа проверки максимально упрощенных
подпрограмм-функций для вычисления биномиальных коэффициентов. Первая
подпрограмма реализует "итерационный" алгоритм вычисления, вторая –
23
"рекурсивный". Прошу читателей обратить внимание на примечание в теле
рекурсивной подпрограммы...
'
P R O G R A M "AP_CBin1"
'
12.08.1994
'------------------------------------------------------------'
Проверка вычисления биномиальных коэффициентов
'------------------------------------------------------------'
используются итерационная и рекурсивные варианты
#Lang "FB"
' режим FreeBASIC-совместимости
'
' объявление используемых подпрограмм
Declare Function Cb(n As Byte, k As Byte) As LongInt
Declare Function C(n As Byte, k As Byte) As LongInt
'
' Основной модуль программы
Dim As Byte m, n, k
m = 12
' максимальное значение индекса
Dim As LongInt IC(m) ' вектор биномиальных коэффициентов
Open Cons For Output As #2
'Open "AP_CBin.res" For Output As #2
Print #2,
Print #2, " Calculation of Binomial Coefficients:"
Print #2,
Print #2, "
n
k --->"
'
For n = 0 To m
' перебор по n
For k = 0 To n
' перебор по k
IC(k) = Cb(n, k) ' обращение к функции
'
IC(k) = C(n, k)
' обращение к функции
Next k
'
Print #2, Using " ### >"; n;
For k = 0 To n
' перебор по k
Print #2, Using " ####"; IC(k);
Next k
Print #2,
Next n
'
Close #2
Print: Print " Press to complete!!!"
Sleep
'
' итерационная подпрограмма-функция
Function Cb(n As Byte, k As Byte) As LongInt
' C(n,k) - число сочетаний из n элементов по k (n >= k)
Dim As Byte i
Dim As LongInt m
m = 1
If k > n - k Then k = n - k
n = n + 1
For i = 1 To k
24
m = m*(n - i)/i
Next i
Cb = m
End Function
' рекурсивная подпрограмма-функция
Function C(n As Byte, k As Byte) As LongInt
' здесь 0 < m < n
If k = 0 Or k = n Then
C = 1
' запись C() = 1 требует аргументов!
Else
C = C(n-1,k-1) + C(n-1,k)
EndIf
End Function
' Результат выполнения программы:
' Calculation of Binomial Coefficients:
'
'
'
'
'
'
'
'
'
'
'
'
'
'
n
0
1
2
3
4
5
6
7
8
9
10
11
12
>
>
>
>
>
>
>
>
>
>
>
>
>
k --->
1
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
1
10
1
11
1
12
1
3
6
10
15
21
28
36
45
55
66
1
4
10
20
35
56
84
120
165
220
1
5
15
35
70
126
210
330
495
1
6
21
56
126
252
462
792
1
7
28
84
210
462
924
1
8
36
120
330
792
1
9
45
165
495
1
10
55
220
1
11
66
1
12
1
Полученная
таблица
(теоретически
бесконечная)
биномиальных
коэффициентов, имеющая треугольную форму получила название "треугольник
Паскаля" в честь французского математика Блеза Паскаля (Blaise Pascal; 1623—1662).
В 1654 году Паскаль пишет и в 1665 году издает "Трактат об арифметическом
треугольнике", где исследует свойства "треугольника Паскаля" и его применение к
подсчёту числа сочетаний, не прибегая к алгебраическим формулам, что имеет
применение, например, в теории вероятностей. Сегодня треугольник Паскаля наиболее
типичный образец Онлайн-энциклопедия целочисленных последовательностей (OEIS):
https://oeis.org/A007318
(Greetings from The On-Line Encyclopedia of Integer Sequences)
Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!).
Эта важная числовая таблица рассматривается в лекции Владимира Андреевича
Успенского, изданной в виде брошюры для школьников [09].
Возможно "расширение" биномиальных коэффициентов, допуская в
биномиальной теореме, чтобы n было целым отрицательным. Ниже приведена
программа, иллюстрирующая эту возможность:
'
P R O G R A M "AP_CBin2"
'
10.05.2015
'------------------------------------------------------------'
Расширение треугольника Паскаля "вниз" и "вверх"
'-------------------------------------------------------------
25
#Lang "FB"
' режим FreeBASIC-совместимости
' объявление используемой подпрограммы
Declare Function Cb(n As Byte, k As Byte) As LongInt
'
Dim As Byte n, n1, k
Dim As LongInt IC(9)
'
Open Cons For Output As #2
'Open "AP_CBin.res" For Output As #2
Print #2,
Print #2, " Calculation of Binomial Coefficients:"
Print #2,
Print #2, "
n \ k
0
1
2
3
4
5
6
7
8
9"
For n = -8 To 8
Print #2, Using " ###"; n;
For k = 0 To 9
If n < 0 Then
n1 = -n+k-1
Else
n1 = n
EndIf
IC(k) = Cb(n1, k)
If n < 0 And k Mod 2 <> 0 Then IC(k) = -IC(k)
Next k
For k = 0 To 9
Print #2, Using " ######"; IC(k); ' обращение к функции
Next k
Print #2,
Next n
'
Close #2
Print: Print "
Press to complete!!!"
Sleep
'
' итерационная подпрограмма-функция
Function Cb(n As Byte, k As Byte) As LongInt
' C(n,k) - число сочетаний из n элементов по k (n >= k)
Dim As Byte i
Dim As LongInt m
m = 1
If k > n - k Then k = n - k
n = n + 1
For i = 1 To k
m = m*(n - i)/i
Next i
Cb = m
End Function
' Результат выполнения программы:
представлен на следующей странице в таблице 1.
26
Таблица 1.
Расширение треугольника Паскаля "вниз" и "вверх"
n\k
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
8
0
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
-8
-7
-6
-5
-4
-3
-2
-1
0
1
2
3
4
5
6
7
8
2
36
28
21
15
10
6
3
1
0
0
1
3
6
10
15
21
28
3
-120
-84
-56
-35
-20
-10
-4
-1
0
0
0
1
4
10
20
35
56
4
330
210
126
70
35
15
5
1
0
0
0
0
1
5
15
35
70
5
-792
-462
-252
-126
-56
-21
-6
-1
0
0
0
0
0
1
6
21
56
6
1716
924
462
210
84
28
7
1
0
0
0
0
0
0
1
7
28
7
-3432
-1716
-792
-330
-120
-36
-8
-1
0
0
0
0
0
0
0
1
8
8
6435
3003
1287
495
165
45
9
1
0
0
0
0
0
0
0
0
1
9
-11440
-5005
-2002
-715
-220
-55
-10
-1
0
0
0
0
0
0
0
0
0
27
Ниже представлены две небольшие программы, вычисляющие факториал числа
с использованием двух алгоритмов (пожалуй, самая простая программа для сравнения
двух методов):
'
P R O G R A M "AP_Factorial0FB"
'
10.05.2015
'------------------------------------------------------------'
Программа итерационного вычисления факториала числа
'------------------------------------------------------------'
' Произведение всех натуральных чисел от 1 до N включительно.
' По договорённости: 0! = 1.
#Lang "FB"
' режим FreeBASIC-совместимости
' Функция вычисления факториала (0 <= N <= 25)
Function Fact(N As Byte) As LongInt
Dim As LongInt K, F
F = 1
For K = 1 To N
F = F*K
Next K
Fact = F
End Function
'
' Основной модуль программы
Dim As Byte M, Mmax
Open Cons For Output As #2 ' вывод на консоль
'Open "AP_Factorial.res" For Output As #2 ' вывод в файл
Print #2,: Print #2," Table of values of the Factorial:"
Mmax = 16
Print #2, "
M
M!"
For M = 0 To Mmax
Print #2, Using " ## ##############"; M; Fact(M)
Next M
Close #2
Print: Print " Press to complete!!!"
Sleep
' Результат выполнения программы:
' Table of values of the Factorial:
'
M
M!
'
0
1
'
1
1
'
2
2
'
3
6
'
4
24
'
5
120
'
6
720
'
7
5040
'
8
40320
'
9
362880
' 10
3628800
' 11
39916800
28
'
'
'
'
'
12
479001600
13
6227020800
14
87178291200
15 1307674368000
16 20922789888000
Для той же цели служит небольшая программа, вычисляющая факториал числа с
использованием рекурсивного алгоритма:
'
P R O G R A M "AP_Factorial1FB"
'
10.05.2015
'------------------------------------------------------------'
Программа рекурсивного вычисления факториала числа
'------------------------------------------------------------' Произведение всех натуральных чисел от 1 до N включительно:
' По договорённости: 0! = 1.
#Lang "FB"
' режим FreeBASIC-совместимости
' Рекурсивная функция вычисления факториала (0 <= N <= 25)
Function Fact(N As Byte) As LongInt
If N < 2 Then
Fact = 1
Else
Fact = N*Fact(N-1)
EndIf
End Function
'
' Основной модуль программы
Dim As Byte M, Mmax
Open Cons For Output As #2 ' вывод на консоль
'Open "AP_Factorial.res" For Output As #2 ' вывод в файл
Print #2,: Print #2," Table of values of the Factorial:"
Mmax = 16
Print #2, "
M
M!"
For M = 0 To Mmax
Print #2, Using " ## ##############"; M; Fact(M)
Next M
Close #2
Print: Print " Press to complete!!!"
Sleep
2.4. Факторизация целых чисел.
Напомню, под "факторизацией" натурального числа понимается его разложение
в произведение простых множителей. Существование и единственность (с точностью
до порядка следования множителей) такого разложения следует из основной теоремы
арифметики. Ниже приведены две программы, которые решают эту задачу.
Программа разложения натурального числа на простые множители без
использования рекурсии:
29
'
P R O G R A M "AP_FactInteger"
'
16.12.2014
'------------------------------------------------------------'
Разложение натурального числа на простые множители
'------------------------------------------------------------' Итеративная программа разложения числа.
' Пример: 378 = 2*3*3*3*7
#Lang "FB"
' режим FreeBASIC-совместимости
'
' Основной модуль программы
Dim As Integer n, m
Print " Factorization of Integers"
n = 378: m = 2
If n >= 1 Then
Print " Natural number"; n; " = ";
Do While n <> 1
If n Mod m = 0 Then
Print m;
n = n\m
Else
m = m + 1
EndIf
Loop
Print
EndIf
Print: Print "
Press to complete!!!"
Sleep
Программа разложения
использованием рекурсии:
натурального
числа
на
простые множители
'
P R O G R A M "AP_FactInteger2"
'
16.12.2014
'------------------------------------------------------------'
Разложение натурального числа на простые множители
'------------------------------------------------------------' Рекурсивная функция разложения числа.
' Пример: 378 = 2*3*3*3*7
#Lang "FB"
' режим FreeBASIC-совместимости
'
' используемая подпрограмма-функция
Function Factor(n As Integer, m As Integer) As Integer
If n Mod m = 0 Then
Print m;
Factor(n\m, m)
Else
If m <= n Then Factor(n, m+1)
EndIf
End Function
'
' Основной модуль программы
с
30
Dim As Integer n, m
Print " Factorization of Integers"
n = 378: m = 2
Print " Natural number"; n; " = ";
Factor(n, m)
Print: Print "
Press to complete!!!"
Sleep
Надеюсь, эти программки будут полезными!
2.5. Простые числа. Треугольник Гилбрета.
В метафорическом смысле простые числа — как вредоносный вирус: если он
захватывает ум математика, его очень трудно искоренить. Евклид, Ферма, Эйлер,
Гаусс, Риман, Рамануджан и многие другие известные математики стали его жертвой.
Хотя некоторым и удалось более-менее излечиться, все они страдали навязчивой идеей
найти "волшебную формулу", которая определяет, какое простое число будет следовать
за определенным натуральным числом. Однако никому еще не удалось открыть это
правило...
Всем известно, что "простое число" это — натуральное (целое положительное)
число, имеющее ровно два различных натуральных делителя — единицу и самого себя.
Натуральные числа, большие единицы, не являющиеся простыми, называются
составными. Казалось бы, какие могут быть проблемы? Но человек – существо
ищущее! Попутно вспомним двух математиков, которые почти не упоминаются в
литературных источниках, но внесли свой вклад с оттенком таинственности, это Пьетро Катальди и Норман Гилбрет.
31
Частенько
прилагательным
"простой" снабжаются объекты
только
первоначально кажущийся простым. Вот и "простые числа", как выяснилось в процессе
накопления научных знаний, появляются в различных областях математики и являются
одним из самых загадочных и тяжелых для изучения монстров. Чтобы убедиться в
этом, достаточно прочитать статью математика из Боннского университета "Первые
пятьдесят миллионов простых чисел", опубликованную в сборнике статей [10]. Автор,
Дон Цагир, предъявляет список мировых рекордов (наибольших известных простых
чисел) показывающий, что простые числа следует признать самыми капризными и
строптивыми из всех объектов, какие только изучают математики, одновременно
стараясь убедить, что простые числа чуть ли не с педантической точностью
подчиняются строгим законам.
Первую известную таблицу простых
чисел составил в 1603 году итальянский
математик Пьетро Антонио Катальди
(Pietro Antonio Cataldi; 1548—1626). Она
охватывала все простые число от 2 до
743. Катальди, профессор математики во
Флоренции и Болонье, впервые указал
способ извлечения квадратных корней и
активно
занимался
поисками
совершенных чисел. В его записках были
указаны значения шестого и седьмого
совершенных чисел: 8 589 869 056
(шестое число), 137 438 691 328 (седьмое
число). В истории навсегда осталась
тайна, как он сумел найти их. До сих
пор предложено только одно объяснение
этой загадке (оно было дано еще его
современниками): помощь божественного
провидения,
подсказавшего
своему
избраннику верные значения двух
совершенных чисел.
В настоящее время составлены таблицы всех простых чисел, не превосходящих
50 миллионов, далее известны только отдельные их представители. Читателей всегда
привлекает гигантизм, поэтому укажу здесь два самых больших известных на
сегодняшний момент простых числа. Наибольшим известным простым числом по
состоянию на январь 2016 года является (2^74207281 – 1). Оно содержит 22338618
десятичных цифр и является простым числом Мерсенна. Его нашли 17 сентября 2015
года в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS,
однако все проверки завершились лишь 7 января 2016 года. До этого в книгу рекордов
Гиннеса было записано число (2^86243 – 1), содержащее 25962 десятичных знака.
Найдено оно было в рекламных целях – демонстрация фирмой IBM возможностей
очередного суперкомпьютера, которому для проверки этого числа на простоту с
помощью специальных изощренных тестов (пригодных только для чисел вида 2^(n-1))
потребовалась неделя работы и куча денег. И это трата денег происходит в то время,
когда у нас в России более трети населения живет за чертой бедности...
Простые способы нахождения начального списка простых чисел вплоть до
некоторого значения дают алгоритмы:
32



решето Эратосфена,
решето Сундарама
решето Аткина.
Наиболее популярным для начинающих следует признать алгоритм "решето
Эратосфена". Решето Эратосфена - алгоритм, который позволяет найти все простые
числа. Алгоритм прост в написании и работает так: для начала вычеркивается каждое 2
число (2, 4, 6, 8, 10 и т.д.) Далее вычеркивается каждое третье (6, 9, 12, 15, 18, 21 и т.д.)
Потом - число 5, т.к. число 4 вычеркнуто, и вычеркивается каждое 5 число (10, 15, 20,
25 и т.д.) В результате все не вычеркнутые числа будут простыми. Почему Решето?
Потому что древние греки делали записи на табличках из воска и числа выкалывались
иголкой, поэтому после произведения всех операций табличка напоминала решето,
через которое «просеивались» все составные числа, а оставались только числа простые.
Эратосфен дал таблицу простых чисел до 1000.
Эратосфен Киренский (276 год до н.э.—194 год до н.э.) — греческий
математик, астроном, географ, филолог и поэт. Отрывок из ещё одного сочинения
Эратосфена приводит во "Введении в арифметику" Никомах Герасский. То же делает и
Ямвлих в своём комментарии к этому сочинению Никомаха. Предмет этого отрывка
состоит в изложении найденного Эратосфеном способа определения произвольного
количества последовательных простых чисел...
Имя Эратосфена связано с методом нахождения простых чисел. Однако этот
метод вовсе не является его самым важным достижением. На самом деле Эратосфен
вошел в историю науки как первый человек, вычисливший размер Земли. Используя
методы, доступные в III в. до н.э., он смог посчитать длину полярной окружности с
погрешностью менее одного процента.
На практике, кроме поиска очередного простого числа и получения "полного
списка" простых чисел, часто требуется проверить, является ли некоторое заданное
число простым. Алгоритмы, решающие эту задачу, называются тестами простоты.
Существует множество полиномиальных тестов простоты, но большинство их
являются вероятностными (например, тест Миллера — Рабина) и используются для
нужд криптографии. В 2002 году было доказано, что задача проверки на простоту в
33
общем виде полиномиально разрешима, но предложенный детерминированный тест
Агравала — Каяла — Саксены имеет довольно большую вычислительную сложность,
что затрудняет его практическое применение. Кроме того привлекательной
представляется проблема распределения простых чисел на числовой оси.
Ниже приведена программа на языке FreeBASIC для подсчета количества
простых чисел в интервале от 1 до подвижной верхней границы:
'
P R O G R A M "AP_GenPrimeNumb"
'
12.10.2012
'------------------------------------------------------------'
Подсчет количества простых чисел в интервале
'------------------------------------------------------------' Generator of prime numbers
'
#Lang "FB"
' режим совместимости с FreeBASIC
#Include "crt/math.bi" ' математические функции (ceil)
'
Dim As Integer imax, i, j, lim, n
Open Cons For Output As #2
'Open "AP_GenPrimeNumb.res" For Output As #2
imax = 10
' верхняя граница интервала
Do
' делать в цикле
n = 0
' пока простых чисал нет
For i = 1 to imax ' перебор и анализ всех чисел
j = 2
' делитель
lim = ceil(Sqr(i))' округление корня до ближайшего
большего
While (i Mod j <> 0) And (j <= lim)
j = j + 1
' следующий делитель
Wend
If (j > lim) Then ' достигнут предел
If i = 1 Then i = i + 1 ' не слишком красиво!
n = n + 1
' было простое число
EndIf
Next i
Print #2, Using " imax = #########
n = ########"; imax; n
imax = 10*imax
Loop While imax <= 100000000 ' 5761455
Close #2
Print: Print "
Press to complete!!!"
Sleep
' Результат выполнения программы:
' imax =
10
n =
4
' imax =
100
n =
25
' imax =
1000
n =
168
' imax =
10000
n =
1229
' imax =
100000
n =
9592
' imax =
1000000
n =
78498
' imax = 10000000
n =
664579
' imax = 100000000
n = 5761455
34
Рассмотрим функцию ( x ) , выражающую количество простых чисел, меньших
или равных x (в нуле она имеет значение 0 и скачком увеличивается на 1 в точках x =
2, 3, 5 и т.д.). В таблице 3 приведена оценка отношения простых чисел к количеству
всех натуральных чисел в интервале, а на рисунках ниже – графики функции ( x ) , для
различных интервалов.
Обратите внимание насколько "нерегулярным" выглядит график ( x ) при
малых значениях х (<= 100).
При больших значениях x (<= 1000000) график выглядит вполне "гладким".
На следующей странице приведена соответствующая таблица 2.
35
Таблица 2.
Отношение простых к количеству всех натуральных чисел в интервале
x
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Верхняя граница
интервала
10^01
10^02
10^03
10^04
10^05
10^06
10^07
10^08
10^09
10^10
10^11
10^12
10^13
10^14
10^15
10^16
 (x)
Количество
простых чисел
4
25
168
1229
9592
78498
664579
5761455
50847534
455052511
4118054813
37607912018
346065536839
3204941750802
29844570422669
279238341033925
x/  (x)
отношение
2.5000
4.0000
5.9524
8.1367
10.4254
12.7392
15.0471
17.3567
19.6666
21.9755
24.2833
26.5901
28.8963
31.2018
33.5069
35.8117
коэффициент
1.6000
1.4881
1.3670
1.2813
1.2219
1.1812
1.1535
1.1331
1.1174
1.1050
1.0950
1.0867
1.0798
1.0739
1.0688
36
Можно определить каждый раз отношение количества простых чисел к
количеству всех натуральных чисел: x / ( x ) и затем коэффициент показывающий
изменение этого отношения при переходе от некоторой данной степени десяти к
следующей. Смелая догадка: этот коэффициент стремится к единице, давая надежду
построить асимптотическую формулу Закона Распределения Простых Чисел!
Неплохое совпадение, например, дает формула: x( i ) / ( i )  Log ( x( i )  1) .
Первым глубокие исследования о том, как
разбросаны
простые
числа
среди
остальных натуральных чисел получил
великий русский математик и механик
Пафнутий Львович Чебышёв (1821—
1894) — основоположник петербургской
математической
школы,
академик
Петербургской академии наук (с 1859) и
ещё 24 академий мира. До сих пор
математики не знают формулы, с
помощью которой можно получить
простые числа одно за другим, нет даже
формулы, дающей только простые числа.
Так как простые числа играют важную
роль в изучении всех остальных чисел, то надо было бы составить их список...
Первую славу П.Л.Чебышеву доставили его два мемуара о простых числах. Первый из
них, "Об определении числа простых чисел не превосходящих данной величины"
(1848), появился первоначально в качестве приложения к знаменитой "Теории
сравнений". Второй мемуар, "О простых числах" (1950), был напечатан в Журнале
Лиувилля. Обе работы посвящены восходящему к глубокой древности и в высшей
степени трудному вопросу о распределении простых чисел в натуральном ряде. Обе
работы и комментарии к ним можно почитать в сборнике избранных трудов [11].
Прежде чем перейти к следующей части пункта, хочу извиниться перед
читателями за то, что не могу точно определить, как в русскоязычных документах
следует называть математика, имя которого пишется "Norman Gilbreath"!
Специалистами были предложены
правдоподобные варианты:
 Норман Джилбрейт,
 Норман Гильбрайт,
 Норман Гилбрет,
 Норман Гилбрец...
следующие
Мне понравился вариант "Норман Гилбрет", на
нем и остановился, но с благодарностью приму
обоснованный вариант читателей!
Норман Лоуренс Гилбрет (родился в 1936 году) американский
компьютерщик,
математик
и
фокусник-любитель. Гипотеза Гилбрета была
впервые изложена им каракулями на салфетке в
37
1958 году - гипотеза в теории чисел, утверждающая, что если взять последовательность
простых чисел, применить к ней разностный оператор со взятием абсолютных значений
и повторять этот процесс к получающимся последовательностям, то получаемые
последовательности всегда будут начинаться на 1. Однако ещё в 1878 году
французский математик Франсуа Прот (1852—1879) опубликовал предполагаемое
доказательство этой же гипотезы, которое, как затем выяснилось, было ошибочным...
Заманчиво воспроизвести "симфонию" единиц арифметического треугольника
Паскаля, используя гипотезу Гилбрета! Ниже приведена программа построения
треугольника по условиям гипотезы Гилбрета:
'
P R O G R A M "AP_TriangGilbreath"
'
12.10.2014
'------------------------------------------------------------'
Построение треугольника по условиям гипотезы Гилбрета
'------------------------------------------------------------'
#Lang "FB"
' режим совместимости с FreeBASIC
#Include "crt/math.bi" ' математические функции (ceil)
'
Dim As Integer imax, i, j, lim, n
n = 16
' количество связано с imax
Dim As Integer Pn(n)
Open Cons For Output As #2
'Open "AP_TriangGilbreath.res" For Output As #2
imax = 55: n = 0
' несколько искусственно!
For i = 1 to imax ' перебор и анализ всех чисел
j = 2
' делитель
lim = ceil(Sqr(i)) ' округление корня до ближайшего большего
while (i Mod j <> 0) And (j <= lim)
j = j + 1
' следующий делитель
Wend
if (j > lim) Then ' достигнут предел
If i = 1 Then i = i + 1 ' не слишком красиво!
n = n + 1
Pn(n) = i
EndIf
Next i
' вывод исходной строки
Print #2,: Print #2, Using " ### number of primes:"; n
For i = 1 To n
Print #2, Pn(i);
Next i
' выполнение условий гипотезы
Print #2,: Print #2,: Print #2, " Triangle Gilbreath";
For j = n To 1 Step -1
For i = 2 To j
Pn(i-1) = Abs(Pn(i) - Pn(i-1))
Next i
Print #2,
38
For i = 1 To j-1
Print #2, Pn(i);
Next i
Next j
Close #2
Print: Print "
Press to complete!!!"
Sleep
' Результат выполнения программы:
' 16 number of primes:
' 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53
' Triangle Gilbreath
' 1 2 2 4 2 4 2 4 6 2 6 4 2 4 6
' 1 0 2 2 2 2 2 2 4 4 2 2 2 2
' 1 2 0 0 0 0 0 2 0 2 0 0 0
' 1 2 0 0 0 0 2 2 2 2 0 0
' 1 2 0 0 0 2 0 0 0 2 0
' 1 2 0 0 2 2 0 0 2 2
' 1 2 0 2 0 2 0 2 0
' 1 2 2 2 2 2 2 2
' 1 0 0 0 0 0 0
' 1 0 0 0 0 0
' 1 0 0 0 0
' 1 0 0 0
' 1 0 0
' 1 0
' 1
Треугольник Гилбрета
39
2.6. Числа Каталана. Матрица Ганкеля.
Англоязычная Википедия
https://en.wikipedia.org/wiki/Catalan_number
утверждает, что известно не менее 66 различных прикладных областей, которые
провоцируют появление чисел Каталана. В 1976 году математик Генри Гулд
опубликовал библиографию работ, в которой приведено 450 случев использования
чисел Каталана (Henry W. Gould: "Bibliography of Bell and Catalan Numbers"). Во многих
из случаев известные математики и не подозревали, что имеют дело с этими числами!
Любопытно, что числа Каталана были впервые получены и применены не для
решения комбинаторных задач, а при рассмотрении чисто геометрических проблем.
Конкретно, C(n) определяет число способов, которыми можно разделить выпуклый
многоугольник с (n + 2) сторонами на треугольники путем проведения (n – 1)
непересекающихся диагоналей. Эта задача была впервые поставлена ЛЭйлером (L.
Euler) и решена в 1759 году Сегнером (J. A. v. Segner). Каталан в 1838 решил
следующую задачу: "Пусть имеется цепочка из n букв, расположенных в заданном
порядке. Необходимо расставить (n – 1) пару скобок так, чтобы внутри каждой пары
стояло ровно два "выражения". Этими спаренными выражениями могут быть либо две
соседние буквы, либо два соседних выражения. Сколькими способами могут быть
поставлены скобки?"
Эжен Шарль Каталан (Eugene-Charles
Catalan;
1814—1894)—
бельгийский
математик. Получил образование в
Парижской политехнической школе, где
его
научным
руководителем
был
французский математик Жозеф Лиувилль
(Joseph Liouville; 1809—1882). В 1865
Каталан получил кафедру анализа в
Льежском университете и стал членом
Брюссельской академии, а в 1881 году
избран членом Российской академии
наук.
С
задачей
Каталана
математики
сталкиваются не часто, но ее часто
приходилось решать проектировщикам
компьютерной техники, особенно на
ранних стадиях ее становления. Речь идет
о "Польской записи" выражений (при
помощи
стека
компьютер
может
вычислять
бесскобочное
польское
выражение). Различают:

Нормальная Польская нотация или префиксная нотация (Normal Polish notation;
NPN) - форма записи логических, арифметических и алгебраических выражений, в
которой операнды расположены за знаками операций, например: + 3 4
40

Обратная Польская нотация или постфиксная нотация (Reverse Polish notation;
RPN) - форма записи математических и логических выражений, в которой операнды
расположены перед знаками операций, например: 3 4 +
Числа Каталана образуют числовую последовательность, которая представлена
на сайте: https://oeis.org/A000108
Catalan numbers: C(n) = binomial(2n,n)/(n+1) =
(2n)!/(n!(n+1)!).
1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845,
35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640,
343059613650, 1289904147324, 4861946401452,...
Много интересного об этих и других специальных числах натурального ряда
можно найти в интересной книге Елены Ивановны Деза [12]. Помимо теоретической
части, каждый раздел содержит обширный список задач, от простейших до весьма
сложных, решение которых может послужить стимулом к самостоятельным научным
исследованиям в соответствующей области.
Для вычисления n-ого члена последовательности Каталана можно использовать:
прямую формулу:
C(n) = (2*n)!/((n+1)*n!*n!)
рекурсивную формулу:
C(n) = (2*(2*n-1)/(n+1))*C(n-1)
Примечание 2: Как будет видно из результатов программы, теоретически красивая
прямая формула не может быть использована на практике без
всяческих ухищрений!
'
P R O G R A M "AP_FunCat"
'
10.10.2014
'------------------------------------------------------------'
Вычисление последовательности чисел Каталана
'------------------------------------------------------------'
' Генерация последовательности A000108 (OEIS)
#Lang "FB"
' режим совместимости с FreeBASIC
'
' вспомогательная функция вычисления факториала
Declare Function fact(n As Integer) As LongInt
'
' Основной модуль программы
Dim As Byte i, n
n = 16
' Длина последовательности чисел
Dim As LongInt C(n), fi, f2i
Open Cons For Output As #2
'Open "AP_FunCat.res" For Output As #2
'
' вычисление по прямой формуле
Print #2,: Print #2, " Check direct formula"
i = 10
' это максимальное значение!
fi = fact(i): f2i = fact(2*i)
C(i) = f2i/((i+1)*fi*fi)
41
Print #2, "
i
Cat(i)"
Print #2, Using " ## #############"; i; C(i)
'
' вычисление по рекурсивной формуле
Print #2,: Print #2, " Sequence of numbers Catalana"
Print #2, "
i
Cat(i)"
For i = 0 To n
If i = 0 Then
C(i) = 1 ' значение числа с номером нуль
Else
C(i) = (2*(2*i-1)/(i+1))*C(i-1) ' рекуррентная формула
EndIf
Print #2, Using " ## #############"; i; C(i)
Next i
Close #2
Print: Print " Press to complete!!!"
Sleep
'
' подпрограмма-функция вычисления факториала
Function fact(k As Integer) As LongInt
Dim As LongInt i, f
f = 1
For i = 1 To k
f = f*i
Next i
fact = f
End Function
' Результат выполнения программы:
' Check direct formula
'
i
Cat(i)
' 10
16796
' Sequence of numbers Catalana
'
i
Cat(i)
'
0
1
'
1
1
'
2
2
'
3
5
'
4
14
'
5
42
'
6
132
'
7
429
'
8
1430
'
9
4862
' 10
16796
' 11
58786
' 12
208012
' 13
742900
' 14
2674440
' 15
9694845
' 16
35357670
42
В линейной алгебре есть интересный объект: матрица Ганкеля (или ганкелева
матрица) названная в честь Германа Ганкеля (Hermann Hankel; 1839—1873),
который представляет собой квадратную матрицу специального вида.
Матрица Ганкеля размером n*n, образующие элементы которой A(i,j)
являются числами Каталана C(i+j-2), имеет определитель равный 1 независимо от
значения n.
Кроме того, если индексация "сдвигается", так что элемент A(i,j) заполняется
числами Каталана C(i+j-1), то определитель по-прежнему будет равен 1, независимо
от значения n.
'
P R O G R A M "AP_DetCat"
'
12.08.2014
'------------------------------------------------------------'
Программа вычисления определителя матрицы Ганкеля
'------------------------------------------------------------'
#Lang "FB"
' режим совместимости с FreeBASIC
' Подпрограмма вычисления определителя квадратной матрицы
Declare Sub MDet(n As Byte, A() As Double, ByRef Det As
Double)
'
' Основной модуль программы
Dim As Byte n, m, i, j, k, s
n = 6: m = 2*n
Dim As LongInt C(m)
Dim As Double A(n, n), Det
Open Cons For Output As #2
'Open "AP_DetCat.res" For Output As #2
' вычисление по рекурсивной формуле
Print #2,: Print #2, " Sequence of numbers Catalana"
Print #2, "
k
Cat(k)"
For k = 0 To m
If k = 0 Then
C(k) = 1 ' значение числа с номером нуль
Else
C(k) = (2*(2*k-1)/(k+1))*C(k-1) ' рекуррентная формула
EndIf
Print #2, Using " ## #############"; k; C(k)
Next k
' Формирование исходной матрицы Ганкеля
Print #2,: Print #2, "
Calculate the determinant of a square
matrix"
For s = 0 To 1 ' сдвиг элементов матрицы
For i = 1 To n
For j = 1 To n
A(i,j) = C(i+j-2+s)
Next j
Next i
43
' Вывод исходной матрицы Ганкеля
Print #2,: Print #2, Using "
Initial matrix: Shift Is = ##";
s
For i = 1 To n
For j = 1 To n
Print #2, Using " #######"; A(i,j);
Next j
Print #2,
Next i
'
MDet(n, A(), DET)
'
Print #2,: Print #2, Using "
Det(A) = ####.#######"; DET
Next s
Close #2
Print: Print " Press to complete!!!"
Sleep
'
' Подпрограмма вычисления определителя квадратной матрицы
Sub MDet(n As Byte, A() As Double, ByRef Det As Double)
' n
- размерность квадратной матрицы;
' A() - элементы исходной матрицы;
' Det - величина определителя матрицы.
Dim As Integer i, j, k, k1
Dim As Double R, P
P = 1
For k = 1 To n - 1
k1 = k + 1: Det = A(k,k): j = k
For i = k1 To n
R = A(i,k)
If Abs(R) > Abs(Det) Then
Det = R: j = i
EndIf
Next i
'
If Det = 0 Then Exit Sub
If j <> k Then
For i = k To n
R = A(k,i): A(k,i) = A(j,i): A(j,i) = R
Next i
P = -P
EndIf
For j = k1 To n: A(k,j) = A(k,j)/Det: Next j
For i = k1 To n: R = A(i,k)
For j = k1 To n: A(i,j) = A(i,j) - A(k,j)*R: Next j
Next i
P = P*Det
Next k
Det = P*A(n,n)
End Sub
'
'
44
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
Результат выполнения программы:
Sequence of numbers Catalana
k
Cat(k)
0
1
1
1
2
2
3
5
4
14
5
42
6
132
7
429
8
1430
9
4862
10
16796
11
58786
12
208012
Calculate the determinant of a square matrix
Initial matrix: Shift Is =
1
1
2
1
2
5
2
5
14
5
14
42
14
42
132
42
132
429
Det(A) =
1.0000000
0
Initial matrix: Shift Is =
1
2
5
2
5
14
5
14
42
14
42
132
42
132
429
132
429
1430
Det(A) =
1.0000000
1
5
14
42
132
429
1430
14
42
132
429
1430
4862
42
132
429
1430
4862
16796
14
42
132
429
1430
4862
42
132
429
1430
4862
16796
132
429
1430
4862
16796
58786
Согласитесь, результат поражает своей непредсказуемостью!
45
3. Производящая функция. Введение.
Производящая функция является устройством,
отчасти напоминающим мешок. Вместо того чтобы
нести отдельно много предметов, что могло бы
оказаться затруднительным, мы собираем их вместе,
и тогда нам нужно нести лишь один предмет – мешок.
Дьёрдь Пойа "Математика и правдоподобные рассуждения"
Думаю, полезно будет полистать книгу [13] венгерско-швейцарскоамериканского математика и популяризатора науки Дьёрдя Пойа (George Polya,
Джордж Полиа; 1887—1985). Обратите внимание на главу VI "Одно более общее
утверждение", которая в полном объеме приводит мемуар Эйлера по теме нашей главы.
Дело в том, что название "проводящая функция" ввел Лаплас при разработке созданной
им математической теории вероятностей. Однако, не давая ему названия, Эйлер
пользовался аппаратом производящих функций задолго до Лапласа в нескольких
сочинениях, применяя этот математический аппарат к различным задачам
комбинаторного анализа и теории чисел. Эйлер же развил идею Муавра, когда работал
на Академию наук в Петербурге. Дирихле поднял метод до уровня основного
аналитического инструмента, применяемого в теории простых чисел...
Сегодня название "Производящая функция" используется в трех случаях:
 Производящая функция канонического преобразования — функция, частные
производные от которой задают искомое каноническое преобразование.
 Производящая функция моментов — способ задания вероятностных
распределений случайной величины.
46

Производящая функция последовательности — формальный степенной ряд,
коэффициенты которого образуют заданную последовательность.
Далее
под
названием
"Производящая
функция"
подразумевается
Производящая функция последовательности в классическом (полиномиальном)
виде, служащая своеобразным связующим элементом между дискретными
математическими объектами (числовыми последовательностями) и непрерывными
математическими объектами (степенными рядами) и делающая возможным
использование средств математического анализа.
3.1. Представление функций степенными рядами.
Производящая функция это бельевая веревка, на которой
вывешивают числовые последовательности для показа.
Герберт С. Уилф
Пусть дана некоторая последовательность чисел: a 0 , a 1 , a 2 , ... a n , ...
0
1
2
n
Образуем степенной ряд: a 0 x  a 1 x  a 2 x  ...  a n x  ...
Если этот ряд сходится в какой-то области к некоторой функции f(x) , то эту функцию
f ( x ) называют производящей для последовательности чисел a 0 , a 1 , a 2 , ... a n , ...
1
Например, из формулы
 1  x  x 2  ...  x n  ...
(1  x )
1
вытекает, что функция f ( x ) 
является производящей для последовательности
(1  x )
чисел 1, 1, 1, ... 1, ...
47
А из формулы
1
 1  2x  3x 2  ...  (n  1)x n  ... вытекает, что функция
2
(1  x )
1
является производящей для последовательности чисел 1, 2, 3, ..., n , ...
(1  x ) 2
Здесь будут интересны, прежде всего, производящие функции для
последовательностей
a 0 , a 1 , a 2 , ... a n , ...
так
или
иначе
связанных
с
комбинаторными задачами. С помощью этих функций можно изучить самые разные
свойства этих последовательностей (в дальнейшем можно рассмотреть, как связаны
производящие функции с решением рекуррентных соотношений). Математики XVIIIXIX веков знали "ходовые" функции "в лицо". Вряд ли число специалистов, владеющих
этим искусством сейчас, превышает их число столетие назад. А ведь корни
производящей функции, ее асимптотическое поведение, круг сходимости, тип
особенностей, топология соответствующей римановой поверхности могут многое
сказать о характере описываемых ею объектов. Производящая функция представляет
последовательность чисел в виде ряда по степеням формальной переменной. Поэтому
наряду с термином "производящая функция" часто используется термин "формальный
степенной ряд".
В качестве иллюстрации метода, ниже приведена "историческая справка".
В 50-х годах XVIII века Эйлер решал "комбинаторную" задачу, которая
формулируется следующим образом: какой величины грузы можно взвесить гирями в
2 0 , 21 , 2 2 , 2 3 , ... , 2m , ... граммов и сколькими способами?
Уже никто не помнит, как быстро и каким путем Эйлер шел к решению задачи,
но окончательный вариант решения великого петербургского математика, дошедший
до нас, поражает своей неожиданностью!
Эйлер рассматривает бесконечное произведение двучленов:
G( z )  (1  z 1 )(1  z 2 )(1  z 4 )(1  z 8 )...
(1)
которое, после раскрытия скобок и приведения подобных членов, представляется в
виде бесконечного степенного ряда от формальной переменной z :
G( z )  1  g 1 z 1  g 2 z 2  g 3 z 3  g 4 z 4  ...
(2)
Что же представляют собой коэффициенты ряда g k ?
k
Каждый g k — это коэффициент при одночлене z , а z
k
— получается как
2m
произведение каких-то одночленов среди z
(не более одного из каждой скобки в
выражении (1)). Иными словами, g k — это в точности число разных представлений
0
1
2
3
m
числа k в виде суммы некоторых из чисел 2 , 2 , 2 , 2 , ... , 2 , ... Другими словами
g k — это число способов взвешивания груза в k граммов заданными гирями. А это
как раз то, что нужно найти в задаче!
Итак, для окончательного решения исходной задачи остается всего-навсего
вычислить коэффициенты g k .
48
Следующий шаг Эйлера поражает не менее предыдущего. Он записывает
очевидные тождества:
(1  z 1 )(1  z 1 )  (1  z 2 ) ;
(1  z 2 )(1  z 2 )  (1  z 4 ) ;
(1  z 4 )(1  z 4 )  (1  z 8 ) ;
а после перемножения и сокращения на общие множители получает:
(1  z 1 ) (1  z 1 )(1  z 2 )(1  z 4 )(1  z 8 )...  1
(3)
Из сравнения выражений (1) и (3) получает:
(1  z 1 ) G (z )  1
откуда
G( z ) 
1
 1  z  z 2  z 3  z 4  ...
(1  z )
(4)
т.е. хорошо известная формула суммы геометрической прогрессии...
Сравнивая выражения (4) с (2) Эйлер заключает, что g k  1 для всех значений k , т.е.
0
1
2
3
m
всякий груз в целое число граммов можно взвесить гирями в 2 , 2 , 2 , 2 , ... , 2 , ...
граммов, притом единственным способом!
Примечание 3: Уже из этого примера видно, что успех метода связан с возможностью
записать производящую функцию формального степенного ряда G ( z ) в
компактном виде.
Примечание 4: Выдающийся немецкий математик К. Вейерштрасс (1815—1897),
развивший и поставивший на строгую логическую основу теорию
степенных рядов, рассматривал лишь сходящиеся стеленные ряды, н
критиковал Эйлера за сомнительные трюки с «бесконечными
многочленами». Современная алгебраическая теория формальных
степенных рядов, которой мы здесь касаемся, вполне строга, однако по
сути ближе к "наивному" подходу Эйлера, чем к строгой
аналитической теории Вейсрштрасса.
49
3.2. Операции над степенными рядами.
Из нашего девиза "Цель расчетов — не
числа, а понимание" следует, что
человек, который должен этого понимания
достигнуть, обязан знать, как
происходит вычисление. Если он не понимает,
что делается, то очень маловероятно,
чтобы он извлек из вычислений что-нибудь ценное.
Он видит голые цифры, но их истинное
значение может оказаться скрытым в вычислениях.
Р.В.Хэмминг
Слова вынесенные в эпграф принадлежат американскому математику Ричарду
Уэсли Хэммингу (Hamming Richard Wesley; 1915—1998), работы которого в сфере
теории информации оказали существенное влияние на компьютерные науки и теорию
телекоммуникаций. Хэмминг обладал широчайшей эрудицией и прославился не только
как ученый, но и как выдающийся педагог, в основу деятельности которого положены
два тезиса, неоднократно повторяемые:
"Цель расчетов — понимание, а не числа"
и
"Прежде чем решать задачу, подумай, что делать с ее решением"
Для читателей может быть интересной книга Хэмминга [14], посвященная
численным методам математического анализа, а в ней глава 4 "Вычисление
бесконечных рядов", где отмечается, что в книгах обычно рассматриваются
сходимость, расходимость и суммируемость рядов, но почти все они пренебрегают
действительным вычислением (суммированием) рядов. Одна из причин этого состоит в
том, что существует очень мало методов для суммирования рядов в конечном виде...
Кроме того, в качестве справочника можно использовать книгу Богдана
Александровича Попова и Геннадия Семеновича Теслера [15], которая содержит
основные сведения о наиболее употребительных элементарных и специальных
функциях, методы вычисления функций, основанные на многочленной аппроксимации.
Так глава 2 посвящена алгоритмам вычисления элементарных функций, в том числе,
степенных функций. Достаточно подробно рассматриваются рекуррентные формулы
для выполнения действий над степенными рядами (умножение, деление, возведение в
произвольную степень и обращение рядов с действительными или комплексными
коэффициентами) в книге Павла Феодосьевича Фильчакова [16].
3.2.1. Использование рекуррентных формул.
Как следует из Примечания 2, при работе со степными рядами в практически
важных случаях приходится использовать рекуррентные формулы для подсчета
коэффициентов.
50
Ниже приведена вспомогательная программа, демонстрирующая использование
рекуррентных формул для работы с популярными экспоненциальными функциями (они
пригодятся дальше):
'
P R O G R A M "AP_FunExp"
'
10.10.2012
'------------------------------------------------------------'
Коэффициенты разложения функций в степенной ряд
'------------------------------------------------------------' Коэффициенты разложения функций Exp(x), Exp(-x) и Exp(-2x)
#Lang "FB"
' режим совместимости с FreeBASIC
Dim As Integer i, n
Dim As Double E0, E1, E2
Open Cons For Output As #2
'Open "AP_FunExp.res" For Output As #2
Print #2,: Print #2, " Coefficients of functions in Power
Series"
n = 8
' Старшая степень ряда
Print #2, "
i
Exp(x)
Exp(-x)
Exp(-2x)"
For i = 0 To n
If i = 0 Then
E0 = 1: E1 = 1: E2 = 1 ' начальные значения коэффициентов
Else
E0 = E0/i: E1 = (-1)*E1/i: E2 = (-2)*E2/i ' рекуррентные
формулы
EndIf
Print #2, Using " ## ##.######## ##.########
##.########"; i; E0; E1; E2
Next i
Close #2
Print: Print " Press to complete!!!"
Sleep
' Результат выполнения программы:
' Coefficients of functions in Power Series
'
i
Exp(x)
Exp(-x)
Exp(-2x)
'
0
1.00000000
1.00000000
1.00000000
'
1
1.00000000 -1.00000000 -2.00000000
'
2
0.50000000
0.50000000
2.00000000
'
3
0.16666667 -0.16666667 -1.33333333
'
4
0.04166667
0.04166667
0.66666667
'
5
0.00833333 -0.00833333 -0.26666667
'
6
0.00138889
0.00138889
0.08888889
'
7
0.00019841 -0.00019841 -0.02539683
'
8
0.00002480
0.00002480
0.00634921
3.2.2. Умножение степенных рядов.
Ниже приведена программа, умножение степенных рядов с действительными
коэффициентами. Коэффициенты степенных рядов вычисляются по рекуррентным
формулам для функций, представленных в разделе 3.2.1.
51
'
P R O G R A M "AP_PSMul"
'
10.10.2012
'------------------------------------------------------------' Умножение степенных рядов с действительными коэффициентами
'------------------------------------------------------------'
#Lang "FB"
' режим совместимости с FreeBASIC
' используется подпрограмма
Declare Sub PSMul(n As Integer, g() As Double, h() As Double,
f() As Double)
'
' основной модуль программы
Dim As Integer n, i, j
n = 8
' максимальная степень ряда
Dim As Double g(n), h(n), f(n)
' подготовка коэффициентов степенных рядов сомножителей
g(0) = 1: h(0) = 1
' свободные члены
For i = 1 To n
' перебрать индексы
g(i) = g(i-1)/i: h(i) = (-2)*h(i-1)/i ' рекуррентные
формулы
Next i
'
Open Cons For Output As #2
'Open "AP_PSMul.res" For Output As #2
Print #2, : Print #2, " Power series Multiplication"
' обращение к подпрограмме умножения
PSMul(n, g(), h(), f())
'
' вывод выходных данных подпрограммы
Print #2, " Calculated Coefficients:"
Print #2, "
i
f(i)"
For i = 0 To n
Print #2, Using " ### ###.##########"; i; f(i)
Next i
Close #2
Print: Print " Press to complete!!!"
Sleep
'
' Текст подпрограммы умножения степенных рядов
Sub PSMul(n As Integer, g() As Double, h() As Double, f() As
Double)
Dim As Integer i, j
For j = 0 To n
f(j) = 0
For i = 0 To j
f(j) = f(j)+g(i)*h(j-i)
Next i
Next j
End Sub
'
'
'
52
'
'
'
'
'
'
'
'
'
'
'
'
'
Результат выполнения программы:
Power series Multiplication
Calculated Coefficients:
i
f(i)
0
1.0000000000
1
-1.0000000000
2
0.5000000000
3
-0.1666666667
4
0.0416666667
5
-0.0083333333
6
0.0013888889
7
-0.0001984127
8
0.0000248016
3.2.3. Деление степенных рядов.
Ниже приведена программа, деления степенных рядов с действительными
коэффициентами. Коэффициенты степенных рядов вычисляются по рекуррентным
формулам для функций, представленных в разделе 3.2.1.
'
P R O G R A M "AP_PSDiv"
'
10.10.2012
'------------------------------------------------------------'
Деление степенных рядов с действительными коэффициентами
'------------------------------------------------------------'
#Lang "FB"
' режим FreeBASIC-совместимости
' используется подпрограмма
Declare Sub PSDiv(n As Integer, g() As Double, h() As Double,
f() As Double)
'
' основной модуль программы
Dim As Integer n, i, j
n = 8
' максимальная степень ряда
Dim As Double g(n), h(n), f(n)
' подготовка коэффициентов степенных рядов сомножителей
g(0) = 1: h(0) = 1
' свободные члены
For i = 1 To n
' перебрать индексы
g(i) = g(i-1)/i: h(i) = 2*h(i-1)/i
' рекуррентные
формулы
Next i
Open Cons For Output As #2
'Open "AP_PSDiv.res" For Output As #2
Print #2,: Print #2, " Power series Division"
' обращение к подпрограмме деления
PSDiv(n, g(), h(), f())
'
' вывод выходных данных подпрограммы
Print #2, " Calculated Coefficients:"
Print #2, "
i
f(i)"
53
For i = 0 To n
Print #2, Using " ### ###.##########"; i; f(i)
Next i
Close #2
Print: Print " Press to complete!!!"
Sleep
' Текст подпрограммы деления степенных рядов
Sub PSDiv(n As Integer, g() As Double, h() As Double, f() As
Double)
Dim As Integer i, j
Dim As Double A, B
A = 1/h(0)
For j = 0 To n: f(j) = g(j): Next j
For j = 0 To n
B = A*f(j)
If j+1 <= n Then
For i = j+1 To n: f(i) = f(i)-B*h(i-j): Next i
EndIf
Next j
For j = 0 To n: f(j) = A*f(j): Next j
End Sub
' Результат выполнения программы:
' Power series Division
' Calculated Coefficients:
'
i
f(i)
'
0
1.0000000000
'
1
-1.0000000000
'
2
0.5000000000
'
3
-0.1666666667
'
4
0.0416666667
'
5
-0.0083333333
'
6
0.0013888889
'
7
-0.0001984127
'
8
0.0000248016
3.2.4. Возведение рядов в степень.
Ниже приведена программа, возведения рядов с действительными
коэффициентами в действительную степень. Коэффициенты степенных рядов
вычисляются по рекуррентным формулам для функций, представленных в разделе
3.2.1.
'
P R O G R A M "AP_PSPwr"
'
10.10.2012
'------------------------------------------------------------'
Возведение степенного ряда в действительную степень
'------------------------------------------------------------'
#Lang "FB"
' режим совместимости FreeBASIC
'
54
' вспомогательная функция - возведение в степень
Declare Sub PSPwr(n As Integer, P As Double, A() As Double,
B() As Double)
' исходные данные задачи:
Data 6
' старшая степень ряда
Data 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0 ' коэффициенты
'
Dim As Integer n, i, j
Dim As Double P
Read n
Dim As Double A(n), B1(n), B2(n), X, C1, C2
Open Cons For Output As #2
'Open "AP_PSPwr.res" For Output As #2
Print #2, : Print #2, " Power Series Exponentiation"
For i = 0 To n
Read A(i)
Next i
'
P = 0.5
' первое заданное значение степени
PSPwr(n, P, A(), B1())
'
P = -0.5
' второе заданное значение степени
PSPwr(n, P, A(), B2())
'
X = 0.23
' значение аргумента из области сходимости ряда
Print #2, " Calculated Coefficients:"
Print #2, "
i
B1(i)
B2(i)"
For i = 0 To n
Print #2, Using " ### ###.########## ###.##########"; i;
B1(i); B2(i)
Next i
' подсчет значений функций суммированием рядов
C1 = 0: C2 = 0
For i = 0 To n
C1 = C1 + B1(i)*X^i: C2 = C2 + B2(i)*X^i
Next i
Print #2, Using " Cal =###.########## ###.##########"; C1; C2
Print #2, Using " For =###.########## ###.##########";
Sqr(1+X); 1/Sqr(1+X)
Close #2
Print: Print " Press to complete!!!"
Sleep
' подпрограмма возведения ряда в степень
Sub PSPwr(n As Integer, P As Double, A() As Double, B() As
Double)
Dim As Integer i, j
Dim As Double Z, S, Q
B(0) = A(0)
' временно!
Z = P: If P = 0 Then Z = 1
B(1) = Z*A(1): If N >= 2 Then
For i = 2 To n
S = Q
55
For j = 1 To i-1
S = S+(P*(i-j) - j)*B(j)*A(i-j)
Next j
B(i) = Z*A(i)+S/i
Next i
End If'
End Sub
' Результат выполнения программы:
' Power Series Exponentiation
' Calculated Coefficients:
'
i
B1(i)
B2(i)
'
0
1.0000000000
1.0000000000
'
1
0.5000000000
-0.5000000000
'
2
-0.1250000000
0.3750000000
'
3
0.0625000000
-0.3125000000
'
4
-0.0390625000
0.2734375000
'
5
0.0273437500
-0.2460937500
'
6
-0.0205078125
0.2255859375
' Cal = 1.1090531881
0.9016755032
' For = 1.1090536506
0.9016696347
3.2.5. Обращение степенных рядов.
Ниже приведена программа, обращения степенного ряда с действительными
коэффициентами. Коэффициенты степенных рядов вычисляются по рекуррентным
формулам для функций, представленных в разделе 3.2.1.
'
P R O G R A M "AP_PSRvr"
'
26.06.1996
'------------------------------------------------------------' Обращение степенных рядов с действительными коэффициентами
'------------------------------------------------------------'
#Lang "FB"
' режим совместимости с FreeBASIC
'В контрольном примере найдено 6 коэффициентов
'(n = 6) обращенного степенного ряда для функции:
'у = Log(1+x) = x — x^2/2 + x^3/3 -...
'x = Exp(x)-1 = y + y^2/2 + y^3/6 +...
Declare Sub PSRvr(n As Integer, A() As Double, B() As Double)
'
' блок исходных данных
Data 8
' старшая степень ряда
Data -1/2, 1/3, -1/4, 1/5, -1/6, 1/7, -1/8 ' коэффициенты
'
' основной модуль программы
Dim As Integer n, i
Read n
Dim As Double A(n), B(n)
Open Cons For Output As #2
'Open "AP_PSRvr.res" For Output As #2
56
Print #2,: Print #2, " Power series Reverse": Print #2,
For i = 2 To n: Read A(i): Next i
' первое (прямое) преобразование
PSRvr(n, A(), B())
'
Print #2, " Calculated Coefficients (direct):"
For i = 1 To n: Print #2, Using " ## ##.#####^^^^"; i; B(i):
Next i
' второе (обратное) преобразование
PSRvr(n, B(), A())
'
Print #2, " Calculated Coefficients (contra):"
For i = 1 To n: Print #2, Using " ## ##.#########"; i; A(i):
Next i
'
Close #2
Print: Print " Press to complete!!!"
Sleep
'
Sub PSRvr(n As Integer, A() As Double, B() As Double)
Dim As Integer i, j, k, m
Dim As Double R(n), Q(n), S
A(1) = 0: B(0) = 0: B(1) = 1
For k = 2 To n: B(k) = 0
For i = 0 To k: R(i) = 0: Next i
For j = k To 1 Step -1
Q(0) = R(0)-A(j)
For i = 1 To k: Q(i) = R(i): Next i
For i = 0 To k
S = 0
For m = 0 To i: S = S + B(m)*Q(i-m): Next m
R(i) = S
Next i
Next j
For i = 2 To k: B(i) = R(i): Next i
Next k
End Sub
' Результат выполнения программы:
' Power series Reverse
'
' Calculated Coefficients (direct):
'
1
1.00000E+00
'
2
5.00000E-01
'
3
1.66667E-01
'
4
4.16667E-02
'
5
8.33333E-03
'
6
1.38889E-03
'
7
1.98413E-04
'
8
2.48016E-05
'
'
'
57
'
'
'
'
'
'
'
'
'
Calculated Coefficients (contra):
1
1.000000000
2 -0.500000000
3
0.333333333
4 -0.250000000
5
0.200000000
6 -0.166666667
7
0.142857143
8 -0.125000000
3.3. Использование рядов в приближенных вычислениях.
В процессе развития интегрального исчисления было отмечено, что существуют
функции, первообразные которых не выражаются в конечном виде через элементарные
функции. Поэтому найти определенный интеграл от таких функций бывает
затруднительно. Однако вычислить такой интеграл с заданной точностью всегда можно
с помощью степенных рядов. Далее используется материал уже представленный в
брошюре "Фрагмент 12. Численное интегрирование" и в брошюре "Фрагмент 20.
Метод Монте-Карло". Кроме того используется материал из учебного пособия [17], где
в §4 приведено описание приложения рядов к приближенным вычислениям, в
частности, на странице 538 есть пример приближенного вычисления интегралов
практически воспроизведенный в нижеследующей программе на языке FreeBASIC.
Демонстрационная программа получилась довольно длинной, но зато легко
читаемой. Кроме того, из нее легко вырезать отдельные фрагменты для дальнейшего
использования... Для наглядности ниже сохранен весь вывод программы для
дальнейшего анализа...
'
P R O G R A M "AP_FunExp2"
'
10.10.2012
'------------------------------------------------------------'
Демонстрационная программа использования степенных рядов
'------------------------------------------------------------'
#Lang "FB"
' режим совместимости с FreeBASIC
' исследуемая функция одной переменной
Function Fun(X As Double) As Double
Fun = Exp(-x^2) ' при увеличении X стрмится к нулю
End Function
' подпрограмма интегрирования методом прямоугольников
Declare Sub QRECT(A As Double, B As Double, m As Integer,
ByRef D As Double)
' подпрограмма обращения степенных рядов
Declare Sub PSRvr(n As Integer, A() As Double, B() As Double)
'
' основной модуль программы
Dim As Integer i, n, m
n = 24
' старшая степень ряда
58
Dim As Double C(n), C2(2*n), Ci(2*n), Cr(2*n), X, Fe, Fs, Fi,
Fr
Dim As Double A, D
Open Cons For Output As #2
'Open "AP_FunExp.res" For Output As #2
' вычисление значений коэффициентов ряда
Print #2,: Print #2, " Coefficients of functions in Power
Series"
Print #2, "
i
Exp(x)
Exp(-x^2)"
' для наглядности коэффициенты вычисляются по шагам
For i = 0 To n
' коэффициенты экспоненты
If i = 0 Then
C(i) = 1: C2(i) = C(i) ' начальное значение
Else
C(i) = C(i-1)/i
' рекуррентая формула для Exp(x)
EndIf
Next i
For i = 0 To n
' коэффициенты исследуемой функции
C2(i) = 0
Next i
For i = 0 To n
C2(2*i) = C(i)
If i Mod 2 <> 0 Then C2(2*i) = -C2(2*i)
Next i
' вывод полученных коэффициентов
For i = 0 To n
Print #2, Using "
##
##.######## ##.########"; i; C(i);
C2(i)
Next i
' вычисление значений функции
Print #2,: Print #2, "
X
Exp(-x^2)
PowSer"
For X = 0 To 2 Step 0.25
Fe = Exp(-x^2)
Fs = 0
For i = 0 To 2*n
Fs = Fs + C2(i)*X^i
Next i
Print #2, Using " ##.## ##.######## ##.########"; X; Fe;
Fs
Next X
' вычисление интеграла двумя способами
Print #2,: Print #2, " Coefficients of the Integral"
Print #2, "
i
ExpI(-X^2)"
For i = 0 To n
If i = 0 Then
Ci(i) = 0
' начальное значение
Else
Ci(i) = C2(i-1)/i ' интеграл степени
EndIf
Print #2, Using " ## ##.########"; i; Ci(i)
Next i
'
59
m = 128
' Количество вычисляемых точек
Print #2,: Print #2, " Integral
Exp(-X^2)Q
Exp(X^2)S"
A = 0.0
' фиксированная нижняя граница
For X = 0.0 To 2.0 Step 0.25
QRECT(A, X, m, D) ' вызов подпрограммы интегрирования
Fi = 0
For i = 0 To n
Fi = Fi + Ci(i)*X^i
Next i
Print #2, Using " ##.###
###.##########
###.##########";
X; D; Fi
Next X
' при увеличении B интеграл стремится...
' переход к обратной функции
Print #2,: Print #2, " Inverse function Coefficients"
PSRvr(n, Ci(), Cr())
For i = 0 To n
Print #2, Using " ## ##.########"; i; Cr(i) ' знаки???
Next i
'
Print #2,: Print #2, " Value of the Inverse Function:"
Print #2, "
Func
X"
For X = 0.0 To 0.5 Step 0.125
Fr = 0
For i = 0 To n
Fr = Fr + Cr(i)*X^i
Next i
Print #2, Using " ##.#####
###.##########"; X; Fr
Next X
Print #2,
' проверка для обратных значений:
'X = 0.2448879618
' получено 0.2500000794
'X = 0.4612815016
' получено 0.5000006336
'Fr = 0
' пожалуй, очень неплохо!
'For i = 0 To n ' укороченный ряд!
'Fr = Fr + Cr(i)*X^i
'Next i
'Print #2, Using " X = 1/3
###.##########"; Fr
Close #2
Print: Print " Press to complete!!!"
Sleep
' подпрограмма интегрирования функции методом прямоугольников
Sub QRECT(A As Double, X As Double, m As Integer, ByRef D As
Double)
' X - переменная интегрирования
' A - нижний предел интегрирования (фиксированный)
' B - верхний предел интегрирования (подвижный)
' D - вычисленное значение интеграла
' n - количество вычисляемых точек функции
' h - шаг интегрирования
Dim As Double h, s
Dim As Integer i
60
h =(X-A)/m: s = 0
' величина шага и накопленной суммы
X = A + h/2
' середины прямоугольников
For i = 1 To m
' выполнить для n точек
s = s + Fun(X)
' прибавить значение функции
X = X + h
' увеличить аргумент
Next i
' следующая точка
D = s*h
' вычисление "площади"
End Sub
' подпрограмма обращения степенного ряда
Sub PSRvr(n As Integer, A() As Double, B() As Double)
Dim As Integer i, j, k, m
Dim As Double R(n), Q(n), S
A(1) = 0: B(0) = 0: B(1) = 1
For k = 2 To n: B(k) = 0
For i = 0 To k: R(i) = 0: Next i
For j = k To 1 Step -1
Q(0) = R(0)-A(j)
For i = 1 To k: Q(i) = R(i): Next i
For i = 0 To k
S = 0
For m = 0 To i: S = S + B(m)*Q(i-m): Next m
R(i) = S
Next i
Next j
For i = 2 To k: B(i) = R(i): Next i
Next k
End Sub
' Результат выполнения программы:
' Coefficients of functions in Power Series
'
i
Exp(x)
Exp(-x^2)
'
0
1.00000000
1.00000000
'
1
1.00000000
0.00000000
'
2
0.50000000 -1.00000000
'
3
0.16666667
0.00000000
'
4
0.04166667
0.50000000
'
5
0.00833333
0.00000000
'
6
0.00138889 -0.16666667
'
7
0.00019841
0.00000000
'
8
0.00002480
0.04166667
'
9
0.00000276
0.00000000
'
10
0.00000028 -0.00833333
'
11
0.00000003
0.00000000
'
12
0.00000000
0.00138889
'
13
0.00000000
0.00000000
'
14
0.00000000 -0.00019841
'
15
0.00000000
0.00000000
'
16
0.00000000
0.00002480
'
17
0.00000000
0.00000000
'
18
0.00000000 -0.00000276
'
19
0.00000000
0.00000000
'
20
0.00000000
0.00000028
'
21
0.00000000
0.00000000
61
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
22
23
24
X
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00000000
0.00000000
0.00000000
Exp(-x^2)
1.00000000
0.93941306
0.77880078
0.56978282
0.36787944
0.20961139
0.10539922
0.04677062
0.01831564
-0.00000003
0.00000000
0.00000000
PowSer
1.00000000
0.93941306
0.77880078
0.56978282
0.36787944
0.20961139
0.10539922
0.04677062
0.01831564
Coefficients of the Integral
i
ExpI(-X^2)
0
0.00000000
1
1.00000000
2
0.00000000
3 -0.33333333
4
0.00000000
5
0.10000000
6
0.00000000
7 -0.02380952
8
0.00000000
9
0.00462963
10
0.00000000
11 -0.00075758
12
0.00000000
13
0.00010684
14
0.00000000
15 -0.00001323
16
0.00000000
17
0.00000146
18
0.00000000
19 -0.00000015
20
0.00000000
21
0.00000001
22
0.00000000
23 -0.00000000
24
0.00000000
Integral
0.000
0.250
0.500
0.750
1.000
1.250
1.500
1.750
2.000
Exp(-X^2)Q
0.0000000000
0.2448879618
0.4612815016
0.6302464934
0.7468260040
0.8179010255
0.8561902029
0.8744162765
0.8820821360
Exp(-X^2)S
0.0000000000
0.2448878872
0.4612810064
0.6302452707
0.7468241327
0.8178989233
0.8561865786
0.8743335275
0.8799081145
62
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
'
Inverse function Coefficients
0
0.00000000
1
1.00000000
2
0.00000000
3
0.33333333
4
0.00000000
5
0.23333333
6
0.00000000
7
0.20158730
8
0.00000000
9
0.19263668
10
0.00000000
11
0.19532548
12
0.00000000
13
0.20593586
14
0.00000000
15
0.22320976
16
0.00000000
17
0.24697023
18
0.00000000
19
0.27765383
20
0.00000000
21
0.31614262
22
0.00000000
23
0.36371759
24
0.00000000
Value of the Inverse Function:
Func
X
0.00000
0.0000000000
0.12500
0.1256582600
0.25000
0.2554492865
0.37500
0.3945516789
0.50000
0.5510394098
Такой вот незатейливый переход от теории к практике! Простите...
63
4. Список литературы
[01] Вирт Н. Алгоритмы и структуры данных. М.: Мир, 1989. 360 с.
[02] Рузавин Г.И. О природе математического знания. M.: Мысль, 1968. 304 с.
[03] Меннингер К. История цифр. Числа, символы, слова. М.: ЦентрПолиграф, 2011.
543 с.
[04] Зубков С.В. Assembler для DOS, Windows и Unix. М. : ДМК Пресс ; СПб. : Питер,
2004. 608 с.
[05] Таненбаум Э. Архитектура компьютера. СПб: Питер, 2007. 844 с.
[06] Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических
вычислений. М.: Мир, 1980, 280 с.
[07] Каханер Д., Моулер К., Нэш С. Численные методы и математическое обеспечение.
М.: Мир, 1998. 575 с.
[08] Воробьев Н.Н. Числа Фибоначчи. М.: Наука, 1978. 144 с.
[09] Успенский В.А. Треугольник Паскаля. М.: Наука, 1979. 48 с.
[10] Живые числа. Сб. статей. М.: Мир, 1985. 128 с.
[11] Чебышёв П.Л. Избранные труды. М.: АН СССР, 1955. 929 с.
[12] Деза Е.И. Специальные числа натурального ряда. М.: ЛИБРОКОМ, 2011. 240 с.
[13] Пойа Д. Математика и правдоподобные рассуждения. М.: Наука, 1975. 462 с.
[14] Хемминг Р.В. Численные методы для научных работников и инженеров. М.:
Наука, 1972. 400 с.
[15] Попов Б.А., Теслер Г.С. Вычисление функций на ЭВМ. Справочник. Киев:
Наукова думка. 1984. 600 с.
[16] Фильчаков П.Ф. Численные и графические методы прикладной математики:
Справочник. Киев: Наукова думка, 1970. 803 с.
[17] Шнейдер В.Е., Слуцкий А.И., Шумов А.С. Краткий курс высшей математики. М.:
Высш. школа, 1972. 640 с.
P.S. Несмотря на "внеплановость" работы, расстаюсь не без сожаления, в надежде,
что тот скудный материал, который изложен в брошюре, будет дополнен читателями!
Но сегодня лимит времени и объема брошюры исчерпан!
До новых встреч!
Пишите: eugene_r@mail.ru
25.03.2016
Документ
Категория
Информатика
Просмотров
51
Размер файла
1 481 Кб
Теги
степенные ряды, алгоритм, программа, freebasic, производящая функция
1/--страниц
Пожаловаться на содержимое документа