Подсчет областей на плоскости в «Введение в алгоритмы: творческий подход»

Question

Я читаю книгу «Введение в алгоритмы: творческий подход». Но возник вопрос о доказательстве формулы подсчета областей на плоскости.

Использование автор индукции сделать доказательство на странице 13 и странице 14.

страница 13

Таким образом, нам нужно лишь доказать, что наличие п-й линии приводит к (п + 1) -й строки, чтобы добавить один дополнительный регион

страница 14

Но, добавление (п + 1) -й линии, когда присутствует n-я строка, влияет на R на две области (R вырезается из двух-четырех областей) вместо простого добавления.

Кажется, что гипотеза не удалась. Но

Следовательно, (n + 1) -я строка добавляет n областей без присутствия n-й строки, но добавляет n + 1 областей с n-й строкой, и доказательство завершено.

Я действительно смущен. Как закончить проверку? Кто-нибудь знает, почему? Спасибо заранее.

Answer 1

первый обзор Давайте гипотеза:

Добавление еще одну строку в N-1 строк в общем положении в плоскости увеличивает количество областей на N.

Гипотеза N только используется, когда (N) я -Line отсутствует, чтобы убедиться, что (N + 1) я -Line делает увеличение N областей (конечно, когда (N) я -Line отсутствует.)

Теперь мы хотим сделать шаг вперед к случаю N + 1.

Здесь мы имеем (N) й -Line возвращается и проверить регион R и другие регионы. вне R, как (N) th -Линия разделяет область, не связанную с (N + 1) th -Line. (N + 1) th-Line увеличивается (N-1) линий, за исключением R, независимо от того, как (N) th -Line работает. Кроме того, из-за наличия (N) th -Line, R разделен на 4 области вместо 3 по сравнению с исходными 2 областями. Таким образом, (N + 1) th-Line вносит (N-1) + 2 = N+1 линий.

Обратите внимание, что когда мы говорим о регионе за пределами R (N-1) линий увеличилась на (N + 1) й -LINE обещан гипотезой о N. Кроме того, когда мы говорим о Гипотеза N, только количество строк имеет значение, а не какая линия. Поэтому гипотеза не сработала, поскольку мы используем ее с отсутствием (N) th-Line.

Извините за подробный личный перевод и надеюсь, что это может помочь.