Главная страница «Первого сентября»Главная страница журнала «Информатика»Содержание №21/2008


В мир информатики
Задачник

Задача о разрезании пирога

Не задумывались ли вы над вопросом: “Сколько кусков пирога можно получить, делая n прямолинейных разрезов ножом”? Или более научно: каково максимальное число L областей, на которые плоскость делится n прямыми? Впервые эта задача была решена в 1826 году швейцарским математиком Якобом Штейнером.

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

 

Рис. 1
(каждая прямая неограниченно продолжается
в обоих направлениях2)

Вы наверняка думаете, что Ln = 2n! Добавление новой прямой попросту удваивает число областей. К сожалению, это неверно. Мы могли бы достигнуть удвоения, если бы новая n-я прямая рассекала каждую старую область на две части. Но когда добавляется третья прямая — жирная линия на рис. 2, — мы быстро обнаруживаем, что она может рассекать самое большее три старые области вне зависимости от того, как расположены первые две прямые.

Таким образом, L3 = 4 + 3 = 7 — самое большее, что можно сделать.

 

Рис. 2

А по некотором размышлении на ум приходит и подходящее обобщение, позволяющее нам установить формулу зависимости расчета количества плоскостей при n прямых от такого же количества при n – 1 прямых3. Новая n-я прямая (при n > 0) увеличивает число областей на k тогда и только тогда, когда рассекает k старых областей, а рассекает она k старых областей тогда и только тогда, когда пересекает прежние прямые в k – 1 различных местах. Две прямые могут пересекаться не более чем в одной точке. Поэтому новая прямая может пересекать n – 1 старых прямых не более чем в n – 1 различных точках, и мы должны иметь k n. Нами установлена верхняя граница Ln Ln – 1 при n > 0.

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

Ln = Ln – 1 + n при n > 0,

L0 = 1.

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

алг Пирог

нач цел число_разрезов, число_кусков, i

|Ввод исходного значения

вывод нс, "Введите число разрезов"

ввод число_разрезов

число_кусков := 1 |Когда разрезов нет

|Последовательно определяем число кусков

|для одного, двух, … разрезов,

|используя "предыдущее значение"

нц для i от 1 до число_разрезов

число_кусков := число_кусков + i

кц

|Вывод результата

вывод нс, "Общее число кусков пирога равно "

вывод число_кусков

кон

Так как для расчета значения Ln нужно знать Ln – 1, то можно использовать прием, который в программировании называют “рекурсией” [2]. Создадим простую и логичную рекурсивную (использующую самую себя в качестве вспомогательной) функцию:

алг цел Число_кусков(арг цел число_разрезов)

нач

если число_разрезов = 0

то

|Значение функции

знач := 1

иначе

|Используем рекурсию

знач := Число_кусков(число_разрезов - 1)

+ число_разрезов

все

кон

Основная часть программы, использующая эту функцию, оформляется очень кратко:

алг Пирог

нач цел число_разрезов

|Ввод исходного значения

вывод нс, "Введите число разрезов"

ввод число_разрезов

вывод нс, "Общее число кусков пирога равно "

вывод Число_кусков(число_разрезов)

кон

Конечно, компьютер — исполнитель “добросовестный”, делающий все, что нужно (в приведенных программах — выполняет 100 операций сложения). А нельзя ли облегчить ему задачу — найти формулу для расчета искомого значения?

Зачастую можно разобраться в рекуррентности, “развертывая” или “разматывая” ее всю до конца (точнее — до начала) следующим образом:

Ln = Ln – 1 + n =

= Ln – 2 + (n – 1) + n =

= Ln – 3 + (n – 2) + (n – 1) + n =

= L0 + 1 + 2 + … + (n – 2) + (n – 1) + n =

= L0 + Sn, где Sn = 1 + 2 + … + (n – 2) + (n – 1) + n.

Учитывая, что L0 = 1, можем записать: Ln = 1 + Sn. Другими словами, Ln на единицу больше суммы Sn первых n положительных целых чисел.

Таблица нескольких первых значений Sn выглядит так:

Эти числа называются также “треугольными числами”, поскольку Sn представляет собой число шаров, расставленных треугольником в n рядов. Например, четырехрядная расстановка состоит из S4 = 10 шаров:

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

алг Пирог2

нач цел число_разрезов

вывод нс, "Введите число разрезов"

ввод число_разрезов

число_кусков :=

Сумма_чисел(число_разрезов) + 1

вывод нс, "Общее число кусков пирога равно "

вывод Число_кусков(число_разрезов)

кон

— где Сумма_чисел — функция для расчета суммы первых n целых чисел:

алг цел Сумма_чисел(арг цел n)

нач цел сумма, i

сумма := 0

нц для i от 1 до n

сумма := сумма + i

кц

знач := сумма

кон

Но для вычисления Sn вместо использования функции можно воспользоваться рассуждениями, представленными в виде формул:

Мы просто складываем Sn с самой собой, записанной в обратном порядке, так что сумма в каждой из n колонок справа равна n + 14. После упрощения имеем:

Ну вот мы и получили требуемую формулу:

Соответствующая программа будет совсем небольшой:

алг Пирог3

нач цел число_разрезов, число_кусков

вывод нс, "Введите число разрезов"

ввод число_разрезов

число_кусков := div(число_разрезов *

* (число_разрезов + 1), 2) + 1

вывод нс, "Общее число кусков пирога равно "

вывод Число_кусков(число_разрезов)

кон

Задание для самостоятельной работы

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

Литература

1. Школа программирования: Тематический выпуск газеты-вкладки “В мир информатики” (“Информатика” № 11/2005).

2. Рекурсия / “В мир информатики” № 5 (“Информатика” № 37/2003).

3. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

Десять утверждений

Определите, есть ли среди следующих утверждений истинные:

1) только одно утверждение в этом списке ложно;

2) только два утверждения в этом списке ложны;

3) только три утверждения в этом списке ложны;

4) только четыре утверждения в этом списке ложны;

5) только пять утверждений в этом списке ложны;

6) только шесть утверждений в этом списке ложны;

7) только семь утверждений в этом списке ложны;

8) только восемь утверждений в этом списке ложны;

9) только девять утверждений в этом списке ложны;

10) все десять утверждений в этом списке ложны.


2 Но пирог, к сожалению, ограничен в размерах :(.

3 Напомним (см., например, [1]), что формулу, выражающую очередной член последовательности через один или несколько предыдущих членов, называют “рекуррентным соотношением”. Например, для арифметической прогрессии такая формула: ai = ai – 1 + d (каждый последующий член равен предыдущему, увеличенному на разность прогрессии).

TopList