IX научно-практическая конференция учащихся

IX научно-практическая конференция учащихся

Алгоритмы разложения на египетские дроби

Авторы:

Богатырев Илья,

Каренгин Александр,

11 класс, МОУ СОШ №91

Научный руководитель:

Эвнин Александр Юрьевич, к. п. н., доцент каф.

прикладной математики ЮУрГУ

Челябинск, 2006

1. Историческая справка

Одним из древнейших письменных документов человечества и древнейшим математическим сочинением является папирус Райнда, датируемый ориентировочно 1600-1650 г. до н.э. Он был переписан писцом Ахмесом с текста, созданного еще во второй половине XIX века до н.э. Папирус, названный в честь своего первого владельца, был найден в 1858г., расшифрован и издан в 1870г. Теперь одна его часть хранится в Британском музее в Лондоне, а другая находится в Нью-Йорке. Папирус содержит математические задачи и таблицы, представляющие дроби 2/(2n+1) со знаменателями от 5 до 331 в виде суммы дробей с числителем 1.

Тем же периодом датируется и “Московский” папирус, полученный русскими египтологами в 1888г. и сейчас принадлежащий Государственному музею изобразительных искусств имени А.С. Пушкина. Он включает 25 математических задач. Кроме того, известен “Кожаный свиток египетской математики”, с большим трудом распрямленный в 1927, а сейчас хранящийся в Британском музее. Свиток также рассказывает об арифметике древних египтян.

Из этих документов стало известно о том, что в Древнем Египте при вычислениях использовались дроби с числителем 1. Такие дроби называют египетскими или аликвотными. При необходимости использовать дробь с другим числителем ее представляли в виде суммы нескольких египетских дробей, что зачастую намного усложняло вычисления даже при использовании специальных таблиц (подобных приведенной в папирусе Райнда). Подобные разложения рационального числа в сумму попарно различных египетских дробей называют египетской суммой.

Интересно, что разложения дробей в египетские суммы, приведенные в папирусе Райнда, отличаются краткостью и имеют сравнительно небольшие знаменатели слагаемых по сравнению с теми, что находятся современными методами. Единого мнения по вопросу способа нахождения этих разложений пока нет.

2. Теорема существования

Теорема. Любое положительное рациональное число может быть представлено в виде египетской суммы.

Доказательство.

Пусть дробь меньше единицы. Тогда по «жадному» алгоритму (см. ниже) выберем в соответствии с алгоритмом: . Из второго неравенства следует, что . Значит, после вычитания дроби числитель полученной дроби уменьшается. Таким образом, при выполнении каждого следующего шага алгоритма, числитель уменьшается, и рано или поздно становится равным единице.ÿ

Так как было доказано, что простое разложение числа в египетскую сумму существует всегда, то на первый план вышли такие проблемы, как обеспечение минимального количества дробей в разложении и уменьшение значений знаменателей слагаемых. Зачастую вводится дополнительное ограничение на четность знаменателей слагаемых и т.д.

3. Примеры алгоритмов разложения

3.1 “Жадный” алгоритм

Пусть исходное число равно . Тогда возьмем наибольшую дробь вида , которая не превосходит , и полученный остаток будет иметь вид . На втором шаге возьмем наибольшую дробь вида , , не превосходящую остаток, то есть: . На третьем шаге возьмем наибольшую дробь , , не превосходящую полученный остаток , и так далее до тех пор, пока числитель остатка не будет равен 1.

Нечетный “жадный” алгоритм – разновидность “жадного” алгоритма, в которой выбор очередного знаменателя разложения ограничен только нечетными числами.

3.2 Обратный “жадный” алгоритм

Пусть – несократимая дробь, . Пусть – наименьшие натуральные решения уравнения . Положим . Для полученной в остатке дроби повторим выполнение алгоритма. Если в обратном “жадном” методе на каждом шаге брать , то получится такой же результат, как при выполнении обычного “жадного” алгоритма. Разновидность этого алгоритма – нечетный обратный “жадный” алгоритм, в котором, как и в нечетном “жадном”, выбор очередного знаменателя ограничен только нечетными числами.

3.3 Алгоритм парных замен

Будем представлять дроби вида как сумму одинаковых дробей вида . После этого пары одинаковых дробей будем заменять следующим образом:

4. Примеры разложения некоторых дробей

Сначала приведем интересный пример разложения дроби из одной из задач папируса Райнда:

.

Нужно заметить, что для этой же дроби все описанные выше способы дают другое разложение, существенно отличающееся от приведенного:

.

Но далеко не всегда разложения, полученные разными методам, совпадают между собой, особенно если знаменатель искодной дроби – большая величина. Поэтому остановимся на каждом способе отдельно.

Жадный алгоритм относительно прост в применении. Его действие можно проиллюстрировать такими примерами:

; ;

.

Однако даже в приведенных разложениях заметен существенный недостаток жадного алгоритма: знаменатели слагаемых возрастают довольно быстро и даже при сравнительно небольшом их числе принимают относительно большие значения. В нечетной разновидности алгоритма этот недостаток становится еще заметнее, например:

(дальнейшие знаменатели превосходят 1000000000, а количество слагаемых в разложениях – более 20)

Во многом такого недостатка лишен обратный жадный алгоритм. Для тех же дробей он позволяет получить приемлемые результаты:

;

.

А если не учитывать ограничение на четность знаменателя, то полученные результаты будут еще более короткими:

.

Вообще, для многих дробей разложения, создаваемые именно этим методом, выглядят наиболее “удачными” и совпадают с теми, что приводятся в папирусе Райнда. Один из примеров “удачного” разложения:

(для сравнения, обычный жадный метод дает разложение из 4 слагаемых с наибольшим знаменателем, равным 40602).

Но и у этого метода есть существенный недостаток, заметный в приведенных примерах: количество слагаемых в разложении относительно велико. Кроме того, для многих дробей даже с небольшими знаменателями разложения превышают разумные пределы и по количеству слагаемых, и по величине их знаменателей.

Алгоритм парных замен позволяет получить сходные результаты, особенно при разложении небольших дробей (со знаменателем менее 30). Но при увеличении знаменателя объем промежуточных вычислений по данному алгоритму возрастает очень быстро, что особенно заметно при разложении большого количества дробей с помощью компьютера, а знаменатели слагаемых и их количиство возрастают примерно с той же скоростью, что и в жадном алгоритме:

.

Для сравнения, та же дробь при использовании обратного жадного алгоритма дает гораздо более простое разложение:

.

Но однозначно указать, каким из способов произвольное число раскладывается в египетскую сумму наиболее “удачно”, не удается. При этом нужно определить, какое из свойств (длина разложения, наибольший знаменатель и т.п.) считать самым важным, важен ли объем выполняемых вычислений, учесть порядок исходных значений и т.д. Но можно попытаться указать некоторые наиболее существенные черты различных способов разложения и сравнить эти способы между собой по различным показателям.

5. Сравнение различных алгоритмов

Мы посчитали, что отдельных примеров разложения дробей различными способами недостаточно для оценки эффективности этих способов и их корректного сравнения. Для этой цели была составлена программа (использовался язык программирования PASCAL, исходный текст программы см. в приложении), осуществляющая перебор всех правильных дробей со знаменателями, не превосходящими некоторой величины, задаваемой пользователем, и разложение этих дробей в египетские суммы пятью различными способами: жадным, обратным жадным, способом парных замен, и двумя способами – жадным и обратным жадным – с введением дополнительного условия нечетности знаменателей. Успешность разложения определялась по таким показателям, как количество слагаемых (чем меньше, тем лучше) и наибольший знаменатель (также чем меньше, тем лучше). Для каждой дроби определялись лучший и худший способ по обоим показателям.

Мы посчитали, что правильным решением также будет рассмотрение не всех разложений, а только тех, длина и наибольший знаменатель которых лежат в некоторых разумных пределах. В нашем случае такими пределами мы посчитали длину разложения в 30 слагаемых и величину наибольшего знаменателя в . Количество разложений, не удовлетворяющих данным условиям, также подсчитывалось для каждого способа отдельно и по итоговому значению суммы вычислялась доля “неудачных” разложений.

Итак, для значений знаменателя исходной дроби от 5 до 50 мы получили следующие значения:

Доля “неудачных” разложений дробей вида

(значения округлены до целых)

Методы
Жадный	0 %	0 %	0 %	0 %	0 %	0 %
обратный жадный	0 %	7 %	9 %	12 %	14 %	16 %
Парных Замен	0 %	3 %	7 %	7 %	15 %	20 %
нечетный жадный	26 %	41 %	47 %	47 %	47 %	49 %
нечетный обратный жадный	44 %	44 %	43 %	45 %	47 %	48 %

Методы
Жадный	0 %	1 %	1 %
Обратный Жадный	19 %	20 %	22 %
Парных замен	20 %	26 %	30 %
Нечетный жадный	50 %	52 %	53 %
нечетный обратный жадный	49 %	50 %	50 %

На основании данных подобной таблицы (с шагом изменения знаменателя m, равным 1) построены диаграммы (отдельно для способов с ограничением четности знаменателя и без).

Кроме того, приведем полные результаты проверки по всем упомянутым показателям сравнения для некоторых m: (проверка была проведена для значений m =5 – 50,75,100,125,150,200)

m<21

Доли “неудачных” разложений:

-жадный метод - 0 %;

-обратный жадный метод -10 %;

-метод парных замен -5 %;

- нечетный жадный метод -50 %;

- нечетный обратный жадный метод -45 %;

Количество слагаемых в разложении (количество лучших/худших разложений):

-жадный метод: 0/153;

-обратный жадный метод: 1/8;

-метод парных замен: 61/0;

- нечетный жадный метод:0/28;

- нечетный обратный жадный метод:35/40;

Наибольший знаменатель в разложении (количество лучших/худших показателей):

-жадный метод:122/1;

-обратный жадный метод:138/0;

-метод парных замен:2/89;

- нечетный жадный метод:24/68;

- нечетный обратный жадный метод:0/14;

m<51

Доли “неудачных” разложений:

-жадный метод - 1%;

-обратный жадный метод - 23%;

-метод парных замен - 37%;

- нечетный жадный метод -53%;

- нечетный обратный жадный метод – 50%;

Количество слагаемых в разложении (количество лучших/худших разложений):

-жадный метод: 0/972;

-обратный жадный метод: 0/134;

-метод парных замен: 742/0;

- нечетный жадный метод: 0/212;

- нечетный обратный жадный метод: 0/297;

Наибольший знаменатель в разложении (количество лучших/худших показателей):

-жадный метод: 2905/32;

-обратный жадный метод: 4609/0;

-метод парных замен:2/5639;

- нечетный жадный метод: 749/679;

- нечетный обратный жадный метод: 0/14;

При небольших значениях знаменателя исходной дроби лидером можно признать обычный жадный алгоритм, благодаря практически полному отсутствию у него “неудачных” разложений и хорошим значениям максимального знаменателя. Обратный жадный метод является лучшим по величине знаменателей, а метод парных замен – по длине разложения. Однако, метод парных замен показывает нестабильные результаты для различных дробей (что очень хорошо видно на диаграмме).

m<101

Доли “неудачных” разложений:

-жадный метод - 3 %;

-обратный жадный метод - 35%;

-метод парных замен - 44%;

- нечетный жадный метод -58 %;

- нечетный обратный жадный метод - 53%;

Количество слагаемых в разложении (количество лучших/худших разложений):

-жадный метод: 0/3656;

-обратный жадный метод: 19/761;

-метод парных замен:1485/0;

- нечетный жадный метод: 0/924;

- нечетный обратный жадный метод: 662/1378;

Наибольший знаменатель в разложении (количество лучших/худших показателей):

-жадный метод: 1692/72;

-обратный жадный метод: 2999/0;

-метод парных замен: 2/4052;

- нечетный жадный метод: 438/729;

- нечетный обратный жадный метод: 0/14;

m<201

Доли “неудачных” разложений:

-жадный метод - 11%;

-обратный жадный метод -68 %;

-метод парных замен -94 %;

- нечетный жадный метод -98 %;

- нечетный обратный жадный метод - 84%;

Количество слагаемых в разложении (количество лучших/худших разложений):

-жадный метод: 0/13584;

-обратный жадный метод: 74/3733;

-метод парных замен: 4430/1;

- нечетный жадный метод:0/3930;

- нечетный обратный жадный метод:1771/5842;

Наибольший знаменатель в разложении (количество лучших/худших показателей):

-жадный метод: 5016/305;

-обратный жадный метод: 10258/0;

-метод парных замен:2/17538;

- нечетный жадный метод: 1365/1905;

- нечетный обратный жадный метод: 0/14;

Для больших значений знаменателя исходной дроби соотношения показателей в целом сохраняются. Становится заметно небольшое преимущество нечетного обратного жадного алгоритма перед нечетным жадным практически по всем показателям. Но обращает на себя внимание очень большой разброс результатов одного и того же метода по разным показателям, что еще раз подтверждает отсутствие лидера среди методов в общем случае и важность определения приоритетного показателя (длина, величина знаменателя и т.п.) при выборе способа разложения.

Библиографический список

1. Гашков С.Б., Чубариков В.Н. Арифметика. Алгоритмы. Сложность вычислений/ Под ред. В.А. Садовничего. – М.: Высш. шк., 2000.

2. Кохась К.П. Египетские дроби //Задачи Санкт-Петербургской олимпиады школьников по математике/ Сост.: С.Л. Берлов, С.В. Иванов, Д.В. Карпов и др. – СПб: изд-во СПБгУ, 2001.

3. Brown K.S. Reverse greed for unit fractions. www.mathpages.com/home/kmath150.htm

4. Brown K.S. Minimizing the denominators of unit fraction expansions. www.mathpages.com/home/kmath348.htm

5. Brown K.S. The greedy algorithm for unit fractions. www.mathpages.com/home/kmath454.htm

Дата добавления: 2015-08-28