Editorial
Problema lunii
Serial
Concursuri
Prima pagina !
Probleme rezolvate
Mozaic
Arhiva
Dialog
Triangularizarea unui poligon convex»» Multimi cardinal echivalente de puncte

Triangularizarea unui poligon convex


autor: Aurelian Ghita


Enunt: Sa se determine in cate moduri poate fi triangularizat un poligon convex cu n laturi. Prin triangularizare se intelege impartirea poligonului in n-2 triunghiuri sau trasarea a n-3 diagonale care nu se intersectaeza decat in varfurile poligonului.

Date de intrare: Fisierul de intrare (POLY.IN) contine un singur numar intreg n (1<=n<=2457) reprezentand numarul de laturi al poligonului convex.

Date de iesire: Fisierul de iesire (POLY.OUT) trebuie sa contina numarul triangularizarilor posibile.

Exemple:




        POLY.IN  POLY.OUT

	  5        5  

       



        POLY.IN  POLY.OUT

	  7        42  

       

Timp de executie: 1 secunda/test (pe un calculator cu procesor PentiumIII 500MHz).

Nota: Problema a fost propusa la prima runda a concursului de programare organizat de Gazeta de informatica (www.ginfo.ro).

Solutie: Problema este clasica fiind analizata pentru prima data de catre matematicianul L.Euler. Dificultatea acesteia consta in gasirea formulei dupa care se calculeaza numarul cautat. Vom da in continuare doua demonstratii pentru urmatoarea propozitie:

P: Numarul de moduri Tn in care se poate triangulariza un poligon convex cu n laturi este:

(prin se intelege combinari de n luate cate k).

Prima demonstratie se bazeaza pe calcularea lui Tn+1 in functie de Tn, Tn-1,..., T1, iar a doua pe realizarea unei bijectii intre multimea tuturor triangularizarilor posibile ale unui poligon cu n laturi si multimea arborilor binari cu n-2 varfuri.

Demonstratia 1: Incercam sa gasim o relatie de recurenta pentru Tn+1.Sa cosideram triunghiul A1An+1Ak Acesta imparte poligonul in doua poligoane,unul cu k laturi si unul cu n-k+2 laturi.Definim T2=1,T3=1.Dand lui k valori de la 2 la n obtinem:

Folosind aceasta formula este destul de complicat sa ajungem la formula in functie de n.De aceea vom calcula numarul descompunerilor poligonului A1A2A3...An din care face parte diagonala A1Ak.Aceasta inparte poligonul in dou poligoane A1A2A3...Ak si AkAk+1Ak+2...A1. Primul are k diagonale iar al doilea n-k+2 diagonale. Numarul cautat este egal cu TkTn-k+2. Dand lui n valori de la 3 la n-1 obtinem numarul de triangularizari ce contin toate diagonalele corespunzatoare varfului A1:

Daca inmultim acest numar cu n/2 vom obtine numarul descompunerilor ce contin toate diagonalele poligonului(se inmulteste cu n/2 deoarece fiecare diagonala corespunde la doua varfuri al poligonului):

Deoarece,conform enuntului, in fiecare descompunere sunt trasate n-3 diagonale, numarul de mai sus este egal cu (n-3)Tn:

Folosind (1) ecuatia anterioara devine:

...................................................................

Inlocuind n+1 cu n obtinem:

Demonstratia2:Se stie ca numarul arborilor binari cu n varfuri este:

Vom incerca sa gasim o bijectie intre multimea triangularizarilor unui poligon cu n laturi si multimea arborilor binari cu n-2 varfuri. O triangularizare data se poate codifica printr-un arbore binar astfel:se alege o latura a poligonului pe care o vom numi baza,iar triunghiul din care face parte baza corespunde radacinii arborelui binar. Celelalte doua laturi ale acestui triunghi reprezinta bazele celor 2 poligoane formate prin sectionarea poligonului initial.Triunghiurile care contin cele doua baze(cea din stanga si cea din dreapta-relativ la triunghiul ce defineste radacina arborelui) corespund radacinilor subarborilor stang si respectiv drept ai arborelui. Repetand acest procedeu pana obtinem poligoane degenerate, obtinem codificarea triangularizarii.

De aici obtinem foarte usor numarul cautat(Tn=Bn-2).

Cu privire la implementare, observam ca trebuie sa simulam operatiile cu numere mari;pentru n=2457 numarul pe care trebuie sa-l intoarca programul are peste 1400 de cifre. Se va simplifica fractia din scrierea explicita a combinarii obtinandu-se la numarator un produs de numere consecutive, iar la numitor un factorial. Programul realizeaza descompunerea in factori primi a numaratorului si numitorului fractiei si efectuarea impartirii.Numaratorul si numitorul fiind descompusi, aceasta se realizeaza foarte simplu. Pentru descompunerea in factori a numitorului este foarte utila formula urmatoare care calculeaza ce exponent are factorul prim p in descompunerea in factori primi a lui n!:

Formula este data ca o suma infinita, dar este evident ca de la un anumit k incolo partea intreaga va fi zero.

Programul prezentat poate fi optimizat, dar in forma prezentata este foarte usor de urmarit [Listing POLY.CPP]

Prima pagina Inceputul paginii


Autorul este elev al C.N. "B.P. Hasdeu" Buzau si poate fi contactat la:
aur@mail.ols.ro
sau
aur@hasdeu.bz.edu.ro