Probleme de Taietura

Probleme de tăietură

h1. Probleme de taietură

h1. Probleme de tăietură

== include(page="template/implica-te/scrie-articole" user_id="andrici_cezar") ==

Această nouă dreaptă va fi intersectată de celelalte drepte în $n$ puncte distincte. Fiecare segment de dreaptă şi semidreaptă în care este împărţită a $(n + 1)$-a dreaptă taie o regiune veche în două regiuni noi. De aici obţinem că <tex> d_{n+1} = d_{n} + n + 1 </tex>.

Aşadar, vom avea <tex> d_{n} = n + (n - 1) + (n - 2) + \ldots + 2 + d_{1} </tex>. Astfel, folosind indentitatea <tex> 1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2} </tex>, obţinem <tex> d_{n} = \dfrac{n(n + 1)}{2} + 1 </tex>.

Aşadar, vom avea <tex> d_{n} = n + (n - 1) + (n - 2) + \ldots + 2 + d_{1} </tex>. Astfel, folosind identitatea <tex> 1 + 2 + 3 + \ldots + n = \dfrac{n(n+1)}{2} </tex>, obţinem <tex> d_{n} = \dfrac{n(n + 1)}{2} + 1 </tex>.

Menţionăm că problemele în care se cere maximizarea numărului de regiuni în care un pătrat, un triunghi sau un cerc este împărţit de $n$ drepte, au aceeaşi soluţie.

h2(#aplicatia-3). Aplicaţia #3: '!! Really Strange !!':http://online-judge.uva.es/p/v105/10519.html (UVA)
bq. Se dau $n$ cercuri care se intersectează oricare două în două puncte şi nu există trei care se intersectează într-un punct; se cere să se determine numărul zonelor în care este împarţit planul de aceste $n$ cercuri.

Restricţii: $n ≤ 10^100$.

Restricţii: $n ≤ 10^100^$.

h3. Rezolvare

Observăm ca sunt indeplinite condiţiile de maximalitate cerute mai sus (vezi aplicaţia '#2':probleme-de-taietura/aplicatia-2), deci rezultatul este <tex> c_{n} </tex>. Singura problemă care rămâne este implementarea operaţiilor cu numere mari (dacă soluţia nu este implementată în _Java_).

Observăm ca sunt indeplinite condiţiile de maximalitate cerute mai sus (vezi aplicaţia '#2':probleme-de-taietura#aplicatia-2), deci rezultatul este <tex> c_{n} </tex>. Singura problemă care rămâne este implementarea operaţiilor cu numere mari (dacă soluţia nu este implementată în _Java_).

h2(#aplicatia-4). Aplicaţia #4

bq. Dându-se un număr natural $n$, se cere numărul maxim de regiuni în care $n$ triunghiuri pot împărţi planul.

p=. !probleme-de-taietura?poza-8.bmp!
 

p=. !probleme-de-taietura?poza-9.bmp!
h3. Rezolvare

Şi în această problemă urmăm acelaşi raţionament. Este evident că trebuie ca fiecare plan să se intersecteze cu toate celelalte, că oricare trei plane trebuie să nu aibă nicio dreaptă comună, că oricare trei plane nu trebuie să fie paralele cu nicio dreaptă şi oricare patru plane nu trebuie să aibă niciun punct comun.

Notăm <tex> p_{n} </tex> numărul maxim de zone în care $n$ plane împart spaţiul. Dacă adăugăm un nou plan, acesta va fi intersectat de celelalte plane în $n$ drepte, drepte printre care, datorită restrictiilor pe care le-am pus, nu vom avea două paralele sau trei care să se intersecteze într-un punct.

Notăm <tex> p_{n} </tex> numărul maxim de zone în care $n$ plane împart spaţiul. Dacă adăugăm un nou plan, acesta va fi intersectat de celelalte plane în $n$ drepte, drepte printre care, datorită restricţiilor pe care le-am pus, nu vom avea două paralele sau trei care să se intersecteze într-un punct.

Acest plan va fi împărţit în <tex> d_{n} </tex> regiuni de aceste drepte datorită restricţiilor impuse. Fiecare regiune din plan taie o zonă din spaţiu în două noi zone, de unde <tex> p_{n+1} = d_{n} + p_{n} </tex>.

Am folosit identităţile <tex> 1 + 2 + \ldots + n = \dfrac{n(n+1)}{2} </tex> şi <tex> 1 + 2^2 + 3^2 + \ldots + n^2 = \dfrac{n(n+1)(2n+1)}{6} </tex>, identităţi care se pot demonstra uşor prin inducţie.

Menţionăm că dacă vrem să împărţim un cub, un cilindru, o sfera etc. în număr maxim de regiuni folosind $n$ plane, formula se păstrează.

Menţionăm că dacă vrem să împărţim un cub, un cilindru, o sferă etc. în număr maxim de regiuni folosind $n$ plane, formula se păstrează.

h2(#aplicatia-7). Aplicaţia #7 (Bursele Agora, 2001)

Pornim la fel ca în cazul problemei anterioare; oricare două sfere se vor intersecta şi nu vor exista trei sfere care să se intersecteze în acelaşi punct. Vom nota cu <tex> s_{n} </tex> numărul maxim de regiuni în care poate fi împărţit spaţiul cu $n$ sfere. Să vedem ce se întâmplă când adăugăm o sferă.

Această sferă va fi intersectată de toate celelalte $n$ sfere în $n$ cercuri; pentru ca numărul de regiuni noi să fie maxim aceste cercuri vor împărţi sfera într-un număr maxim de regiuni; acest număr este <tex> c_{n} </tex> aşa cum am discutat în aplicaţia '#2':probleme-de-taietura/aplicatia-2.

Această sferă va fi intersectată de toate celelalte $n$ sfere în $n$ cercuri; pentru ca numărul de regiuni noi să fie maxim aceste cercuri vor împărţi sfera într-un număr maxim de regiuni; acest număr este <tex> c_{n} </tex> aşa cum am discutat în aplicaţia '#2':probleme-de-taietura#aplicatia-2.

Obţinem astfel:
<tex> s_{n+1} = c_{n} + s_{n} </tex>

h2(#aplicatia-8). Aplicaţia #8: 'Thinking Backward':http://uva.onlinejudge.org/external/106/10623.html (UVA)
bq. Se consideră un număr $N$ care reprezintă numărul maxim de regiuni în care poate fi împărţit planul de către $m$ elipse, $n$ cercuri şi $p$ triunghiuri. Se cere să se determine toate valorile posibile pentru $m$, $n$ şi $p$.

Restricţii: $N$ întreg fără semn reprezentabil pe $32$ biţi; $0 &le; m < 100$; $0 &le; n < 20 000$; $0 &le; p < 100$.

Restricţii: $N$ întreg, fără semn, reprezentabil pe $32$ biţi; $0 &le; m < 100$; $0 &le; n < 20 000$; $0 &le; p < 100$.

h3. Rezolvare

h3. Rezolvare

În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul de programator... Vom folosi aceeaşi idee ca şi în cazul celorlalte probleme, adică numărăm pe rând în câte zone este împărţit planul de prima dreaptă, primele două drepte până ajunge la toate cele $n$ drepte. Aşadar, vom adăuga în ordine dreptele la configuraţia noastră. Când adăugăm o dreaptă, aceasta va fi intersectată de dreptele deja adăugate în $k$ puncte nu neapărat distincte; pe noi ne intereseaza punctele distincte şi, pentru a le număra, putem sorta punctele (în complexitate $O(k log k)$) sau putem folosi o tabelă de dispersie, caz în care timpul necesar debine $O(k)$. Dacă numărul de puncte distincte este egal cu $l$, atunci numărul total de zone va creşte cu $l$. Astfel, algoritmul are complexitatea $O(n^2^ log n)$ dacă folosim sortarea sau $O(n^2^)$ dacă folosim tabela de dispersie.

În sfârşit o problemă în care avem nevoie să folosim calculatorul şi talentul de programator... Vom folosi aceeaşi idee ca şi în cazul celorlalte probleme, adică numărăm pe rând în câte zone este împărţit planul de prima dreaptă, primele două drepte până ajungem la toate cele $n$ drepte. Aşadar, vom adăuga în ordine dreptele la configuraţia noastră.
 
Când adăugăm o dreaptă, aceasta va fi intersectată de dreptele deja adăugate în $k$ puncte nu neapărat distincte; pe noi ne intereseaza punctele distincte şi, pentru a le număra, putem sorta punctele (în complexitate $O(k log k)$) sau putem folosi o tabelă de dispersie, caz în care timpul necesar devine $O(k)$.
 
Dacă numărul de puncte distincte este egal cu $m$, atunci numărul total de zone va creşte cu $m$.
 
Astfel, algoritmul are complexitatea $O(n^2^ log n)$ dacă folosim sortarea sau $O(n^2^)$ dacă folosim tabela de dispersie.

h2(#aplicatia-10). Aplicaţia #10: 'The partition of a cake':http://uva.onlinejudge.org/external/5/527.html (UVA)

bq. Avem un tort în formă pătratică; dimensiunea acestuia este $1000 x 1000$. Folosim un cuţit pentru a tăia tortul. Va trebui să determinăm în câte bucăţ a fost împărţit tortul după o serie de tăieturi.
Numărul tăieturilor nu va fi mai mare de $8$. După tăiere, lungimea oricărei laturi a partiţiei nu va fi mai mică decât unu. Coordonatele vârfurilor tortului vor fi $(0,0) (0,1000) (1000,1000) (1000,0)$. Tăieturile se vor intersecta în două puncte cu marginile tortului. În imagine este prezentat un tort tăiat în zece bucăţi.

bq. Avem un tort în formă pătratică; dimensiunea acestuia este $1000 x 1000$. Folosim un cuţit pentru a tăia tortul. Va trebui să determinăm în câte bucăţi a fost împărţit tortul după o serie de tăieturi. Numărul tăieturilor nu va fi mai mare de $8$. După tăiere, lungimea oricărei laturi a partiţiei nu va fi mai mică decât unu. Coordonatele vârfurilor tortului vor fi $(0,0) (0,1000) (1000,1000) (1000,0)$. Tăieturile se vor intersecta în două puncte cu marginile tortului. În imagine este prezentat un tort tăiat în zece bucăţi.

p=. !probleme-de-taietura?poza-10.bmp!

Există într-adevăr o astfel de formulă care poartă denumirea de _formula lui Euler pentru grafurile planare_. Dacă graful este conex, această formulă este $f - m + n = 2$, unde prin $f$ am notat numărul de feţe, prin $m$ numărul de muchii şi prin $n$ numărul de vârfuri. Formula include faţa exterioară. Această formulă poate fi demonstrată în foarte multe moduri. Dacă doriţi să vedeţi 19 metode de demonstrare puteţi să vizitaţi '_Nouăsprezece demonstraţii ale formulei lui Euler: V-E+F=2_':http://www.ics.uci.edu/~eppstein/junkyard/euler/.

O demonstraţie simplă se bazează metoda inducţie matematice pornind de la un arbore şi adăugând pe rând câte o muchie. La început avem o singură faţă, cea infinită, deci ipoteza de inducţie se verifică: $1 - (n - 1) + n = 2$ se verifică. Fiecare muchie adăugată împarte o faţă în două, deci, dacă inainte aveam $f - m + n = 2$, acum vom avea $f{~1~} - m{~1~} + n = 2$, unde $f{~1~} = f + 1$ şi $m{~1~} = m + 1$. Aşadar, am demonstrat formula şi putem foarte uşor să rezolvăm problema. Mai trebuie numai să avem grijă ca pentru fiecare componentă conexă să numărăm faţa infinită. Această formulă este adevarată şi în spaţiu pentru poliedre.

O demonstraţie simplă se bazează metoda inducţie matematice pornind de la un arbore şi adăugând pe rând câte o muchie. La început avem o singură faţă, cea infinită, deci ipoteza de inducţie se verifică: $1 - (n - 1) + n = 2$. Fiecare muchie adăugată împarte o faţă în două, deci, dacă inainte aveam $f - m + n = 2$, acum vom avea $f{~1~} - m{~1~} + n = 2$, unde $f{~1~} = f + 1$ şi $m{~1~} = m + 1$. Aşadar, am demonstrat formula şi putem foarte uşor să rezolvăm problema. Mai trebuie numai să avem grijă ca pentru fiecare componentă conexă să numărăm faţa infinită. Această formulă este adevarată şi în spaţiu pentru poliedre.

h2(#aplicatia-12). Aplicaţia 12: Cercuri (Algoritmus)

O atenţie deosebită trebuie acordată punctelor de intersecţie prin care trec mai mult de două cercuri, pentru a nu le număra de mai multe ori. Putem rezolva această problemă prin sortarea punctelor de intersecţie ale unui cerc cu toate celelalte cercuri.

De asemenea, este ncesară eliminarea cercurilor identice (cu acelaşi centru şi raze egale). Din orice mulţime formată din astfel de cercuri este păstrat doar un singur element.

De asemenea, este necesară eliminarea cercurilor identice (cu acelaşi centru şi raze egale). Din orice mulţime formată din astfel de cercuri este păstrat doar un singur element.

Deoarece pentru fiecare cerc este necesară o sortare a punctelor de intersecţie, complexitatea algoritmului va fi $O(n^2^ log n)$.

4398