Czytam książkę "Introduction to Algorithms: A Creative Approach". Ale dostałem pytanie o dowód na wzór Liczących się Regionów na płaszczyźnie.
Autor używa indukcji, aby wykonać dowód na stronie 13 i stronie 14.
strona 13
W związku z tym musimy tylko udowodnić, że obecność n-tej linii powoduje, że linia (n + 1) th dodaje jeden dodatkowy region
strona 14
Ale dodanie (n + 1) th linii, gdy n-ta linia jest obecna, wpływa na R na dwa regiony (R jest wycięte z dwóch do czterech regionów) zamiast tylko dodawania jednego.
Wygląda na to, że hipoteza nie powiodła się. Ale
Stąd linia (n + 1) th dodaje n regionów bez obecności n-tej linii, ale dodaje regiony n + 1 z n-tą linią, a dowód jest kompletny.
Jestem naprawdę zdezorientowany. W jaki sposób można uzyskać dowód? Czy ktoś wie, dlaczego? Z góry dziękuję.
Odpowiedzi:
0 dla odpowiedzi № 1Najpierw przejrzyjmy hipotezę:
Dodanie jeszcze jednej linii do linii N-1 w ogólnej pozycji w płaszczyźnie zwiększa liczbę regionów o N.
Hipotezę N stosuje się tylko wtedy, gdy (N)th-Line jest nieobecny, aby upewnić się, że (N + 1)th-Line zwiększa regiony N (oczywiście, gdy (N)th-Line jest nieobecny.)
Teraz chcemy zrobić krok naprzód w sprawie N + 1.
Tutaj mamy (N)th-Linia wraca i sprawdza region R i inne regiony. na zewnątrz R, jak (N)th-Line dzieli region niezwiązany z (N + 1)th-Linia. (N + 1)th-Line zwiększa (N-1) linie, z wyłączeniem R, nie ważne jak (N)th-Line działa. Również ze względu na obecność (N)th-Linia, R jest podzielony na 4 regiony zamiast 3, w porównaniu do dwóch oryginalnych regionów. Tak więc (N + 1)th-Line przyczynia (N-1) + 2 = N+1 kwestia.
Zauważ, że kiedy mówimy o regionie poza R, (N-1) linie wzrosły o (N + 1)th-Line jest obiecana przez Hipotezę N. Ponadto, gdy mówimy o Hipotezy N, liczy się tylko liczba linii, a nie linia. Dlatego hipoteza nie uległa awarii, ponieważ używamy jej z brakiem (N)th-Linia.
Przepraszamy za szczegółowe osobistą interpretację i nadzieję, że może pomóc.