Versiunea pentru tiparit a acestui topic

Click aici pentru a vizualiza acest topic in formatul original

HanuAncutei.com - ARTA de a conversa _ Enigme si Ghicitori _ Pentru Informaticieni

Trimis de: Catalin pe 4 Mar 2004, 09:23 AM

Avem o camera de L metri lungime si l metri latime. Un amic rauvoitor a aruncat pe jos in aceasta camera 100 de monede de diferite feluri. Stiind pozitiile (coordonatele centrelor) si razele lor sa se calculeze suprafata totala ocupata de ele in camera (unele monede au cazut suprapuse peste altele si, ca atare, spatiul total ocupat este mai mic decit suma ariilor monedelor).

Trimis de: E.B.E. pe 4 Mar 2004, 10:59 AM

Si cu ce ma aleg daca scriu programul? Ca deja am o idee despre cum s-ar face.

Trimis de: Catalin pe 4 Mar 2004, 12:49 PM

Nu trebuie sa scrii nici un program... doar ideea ma interesa! Si nu te alegi decat cu felicitarile mele!

Trimis de: E.B.E. pe 4 Mar 2004, 09:55 PM

Okay, uite ca vine, in Java:

CODE

double[] coordsx = ..., coordsy = ..., radii = ...;

Area combinedArea = new Area();

for (int i = 0; i < COINS_COUNT; i++) {
Shape coin = new Ellipse2D.Double(coordsx[i], coordsy[i], radii[i], radii[i]);
combinedArea.add(new Area(coin));
}

System.out.println("Aria ocupata este: " + combinedArea.value());

Cine stie cunoaste de ce am scos limba

...

Serios acum, cand am spus ca "ma gandesc la o solutie", ma gandeam la o solutie incompleta... Care ia in considerare doar cazul in care maxim doua monede se intersecteaza. Pentru cazul in care "n" monede se intersecteaza, nu vad acum alta solutie decat ceva de genul:

- se formeaza clase de monede "conectate" prin arii.
- se calculeaza aria unei clase printr-o reuniune a frontierelor cercurilor (ceva cam cum am scris eu mai sus) urmata de integrare pe suprafata.

Aceasta implica insa un volum de programare care ma sperie

si pentru unele lucruri nu stiu algoritmii... Sigur daca m-as apuca de cautat as gasi... Dar sunt sigur ca exista o solutie mai simpla, altfel nu ar fi fost pusa problema. Il astept pe Catalin sa imi confirme sau infirme presupunerea

Trimis de: Catalin pe 4 Mar 2004, 11:12 PM

QUOTE

Dar sunt sigur ca exista o solutie mai simpla, altfel nu ar fi fost pusa problema. Il astept pe Catalin sa imi confirme sau infirme presupunerea

Pana acum eu am gasit o solutie simpla care insa iti rezolva problema cu o anumita eroare... ca sa reduci eroarea trebuie sa cresti complexitatea algoritmului.

Trimis de: axel pe 4 Mar 2004, 11:15 PM

Solutia la care te-ai gandit tu aproximeaza prea grosolan rezultatul
Ce faci daca ti se cer sa spunem rezultat cu 5 zecimale?

Trimis de: axel pe 4 Mar 2004, 11:20 PM

Ce e mai grav e ca e probmela de ACM. Cu alte cuvinte ar trebui sa se gaseasca rezolvarea in timp destul de scurt (ore) si programul sa fie destul de scurt.

http://acm.uva.es/archive/data/p2895.html

Trimis de: E.B.E. pe 22 Mar 2004, 02:43 PM

QUOTE (Catalin)

Pana acum eu am gasit o solutie simpla care insa iti rezolva problema cu o anumita eroare

Spune-mi si mie sa nu mor prost...

Trimis de: Catalin pe 22 Mar 2004, 03:39 PM

Imparti suprafata camerei in patratele de latura a. Dup-aia, pentru fiecare patratel in parte, testezi in timp liniar daca mijlocul sau se afla macar intr-un cerc. Daca da, aduni a^2 la aria totala. In felul asta obtii o solutie aproximativa. Eroarea este proportionala cu a*numarul de monede. Efortul de calcul este proportional cu a^2*numarul de monede. Dupa cum spunea axel, pentru o eroare de 10^-5 ne-ar trebui 10^-10*numarul de monede pasi. Ceea ce e deja cam mult pentru calculatoarele actuale.

Problema de la acm cerea eroare de 10^-3 si avea 100 de monede. Asta inseamna un efort de ordinul 10^-8 calcule. Timpul de rulare era 1 sec. Pare ca vei depasi... dar oricum, destul de aproape.

Alta varianta, mai buna pe cazul mediu si care cred ca merge pe datele de test de la acm, este sa aplici principiul din spatele codarii imaginilor:

Avem o coada q in care tinem minte dreptunghiuri. Initial, coada contine un singur element, dreptunghiul total.
Luam aria = suprafata dreptunghiului total

Pas 1. Scot din coada un dreptunghi.
Pas 2. Daca (Err=4*aria_dreptunghiului_scos*n*2*pi*raza<10^-3) return aria (n e numarul de monezi si 2*pi*raza*n reprezinta lungimea maxima a cercurilor)
Pas 3. Impart suprafata dreptunghiului in alte 4 dreptunghiuri egale (dupa principiul stanga-sus, dreapta-sus, stanga-jos, dreapta-jos)
Pas 4. Pentru fiecare dintre cele 4 dreptunghi,
Testezi daca se intersecteaza cu sau contine un cerc (asta trebuie facut in timp liniar dar nu mi-e clar cum deocamdata)
Daca da, atunci il pun in coada.

Daca nu, atunci scad suprafata sa din suprafata totala.

Pas 5. Ma intorc la pas 1.

In coada vom avea dreptunghiuri din ce in ce mai mici. In momentul in care aria unui dreptunghi scos din coada devine a, inseamna ca s-au epuizat toate dreptunghiurile de arie 4*a ceea ce inseamna ca aproximarea a devenit deja mai mica de Err calculat.

Figura se interpreteaza in felul urmator: cu albastru este dreptunghiul eliminat din primul pas. Cu verde, cele eliminate dupa prima crestere a adancimii iar cele rosii dupa cea de-a 2-a. Aria totala este cea care ramane alba la sfarsitul rularii algoritmului. Se obtin imbunatatiri imense daca suprafata ocupata este mult mai mica decat suprafata totala. Daca suprafata ocupata este comparabila cu cea totala, nu exista nici o imbunatatire semnificativa fata de algoritmul simplu initial.

figura.gif ( 4.48K ) : 46

Trimis de: side_story pe 11 Apr 2004, 10:33 PM

Am si eu o problema. De clasa a XI-a, cu toate ca nu cred ca sunteti prea multi dintre voi pe la liceu... Fisierul atasat.
M-am gandit la o solutie:
1.Aplici un algoritm de aflare a drumului min (Djisktra sau ceva) numai pentru durata.
2.Analizezi daca acest drum nu este prea scump. Daca nu este, atunci ai gasit drumul cel bun. Daca este prea scump, elimini cel mai scump salt din el (muchia cu cel mai mare cost prin care trece) si reiei 1.

Nu stiu daca returneaza intotdeauna sol. buna, insa alt program suficient de rapid nu am reusit sa gasesc...voi?

20.doc ( 23K ) : 31

Trimis de: Napoleon9th pe 6 Jun 2004, 04:14 PM

Poti sa aplici algoritmul pentru determinarea celor mai ieftine K trasee (cauta online "wae99slides" sau "Computing the K Shortest Paths", sau daca nu poti sa vezi format PostScript trimite-mi un PM sa-ti dau fisierul in format PDF), in ordine, si pentru fiecare verifici daca reprezinta o solutie. Daca nu, treci la urmatorul traseu.

"Parerea mea..."