Počítanie regiónov v rovine v "Úvod do algoritmov: kreatívny prístup" - algoritmus

Čítam knihu „Úvod do algoritmov: kreatívny prístup“. Dostala som však otázku o dôkaze vzorca Počítanie regiónov v rovine.

Autor používa indukciu na vykonanie dôkazu na strane 13 a 14.

strana 13

Potrebujeme teda iba dokázať, že prítomnosť n-tej línie spôsobí, že (n + 1) tretí riadok pridá jednu ďalšiu oblasť

strana 14

Ale pridanie (n + 1) tretí riadok, keď je prítomný n-tý riadok, ovplyvňuje R do dvoch oblastí (R je odrezaný z dvoch na štyri regióny) namiesto iba pridania jedného.

Zdá sa, že hypotéza zlyhala. ale

Preto (n + 1) tretí riadok pridá n oblasti bez prítomnosti n-tej čiary, ale pridá n + 1 regióny s n-tou čiarou a dôkaz je úplný.

Som naozaj zmätený. Ako je možné získať dôkaz? Vie niekto prečo? Vopred ďakujem.

odpovede:

Najprv si prečítajte hypotézu:

Ak pridáte ďalšiu čiaru k čiaram N-1 vo všeobecnej polohe v rovine, zvýši sa počet regiónov o N.

Hypotéza N sa používa iba vtedy, keď (N)th-Line chýba, aby sa ubezpečil, že (N + 1)th- Čiara zvyšuje regióny N (samozrejme, keď (N)th- Linka chýba.)

Teraz chceme ísť o krok vpred v prípade N + 1.

Tu máme (N)th-Line sa vracia a skontrolujte región R a ďalšie regióny. mimo R, ako (N)th- Čiara rozdeľuje oblasť, ktorá nesúvisí s (N + 1)th-Línia. (N + 1)th- Riadok zvyšuje (N-1) riadkov, bez R, bez ohľadu na to, ako (N)th-Linka funguje. Tiež kvôli prítomnosti (N)th- riadok, R je rozdelený do 4 regiónov namiesto 3, v porovnaní s pôvodnými 2 regiónmi. Teda (N + 1)th-Linka prispieva (N-1) + 2 = N+1 linky.

Všimnite si, že keď hovoríme o regióne mimo R, (N-1) linky zvýšené o (N + 1)th-Line sľubuje hypotéza N.Keď hovoríme o hypotéze N, záleží iba na počte riadkov, a nie na tom, ktorý riadok. Preto hypotéza nezlyhala, pretože ju používame s absenciou (N)th-Línia.

Ospravedlňujeme sa za podrobný osobný výklad a dúfam, že vám to môže pomôcť.