HanuAncutei.com - ARTA de a conversa!

Bine ati venit ca musafir! ( Logare | Inregistrare )

 
Reply to this topicStart new topic
> Pentru Informaticieni
Catalin
mesaj 4 Mar 2004, 09:23 AM
Mesaj #1


Filosof boem
******

Grup: Membri
Mesaje: 6.222
Inscris: 10 July 03
Din: Bucuresti
Forumist Nr.: 445



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).


--------------------
A nation cannot prosper for long when it favors only the prosperous - Obama
Go to the top of the page
 
+Quote Post
E.B.E.
mesaj 4 Mar 2004, 10:59 AM
Mesaj #2


Domnitor
******

Grup: Membri
Mesaje: 1.292
Inscris: 20 November 03
Din: Delft, NL
Forumist Nr.: 1.248



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


--------------------

I spend my time thinking of Angel... praying she ain't thinking of me...

Go to the top of the page
 
+Quote Post
Catalin
mesaj 4 Mar 2004, 12:49 PM
Mesaj #3


Filosof boem
******

Grup: Membri
Mesaje: 6.222
Inscris: 10 July 03
Din: Bucuresti
Forumist Nr.: 445



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


--------------------
A nation cannot prosper for long when it favors only the prosperous - Obama
Go to the top of the page
 
+Quote Post
Promo Contextual
mesaj 4 Mar 2004, 12:49 PM
Mesaj #


ContextuALL









Go to the top of the page
 
Quote Post
E.B.E.
mesaj 4 Mar 2004, 09:55 PM
Mesaj #4


Domnitor
******

Grup: Membri
Mesaje: 1.292
Inscris: 20 November 03
Din: Delft, NL
Forumist Nr.: 1.248



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());

tongue.gif

Cine stie cunoaste de ce am scos limba smile.gif...

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 smile.gif 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 smile.gif

Acest topic a fost editat de E.B.E.: 4 Mar 2004, 09:56 PM


--------------------

I spend my time thinking of Angel... praying she ain't thinking of me...

Go to the top of the page
 
+Quote Post
Catalin
mesaj 4 Mar 2004, 11:12 PM
Mesaj #5


Filosof boem
******

Grup: Membri
Mesaje: 6.222
Inscris: 10 July 03
Din: Bucuresti
Forumist Nr.: 445



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.


--------------------
A nation cannot prosper for long when it favors only the prosperous - Obama
Go to the top of the page
 
+Quote Post
axel
mesaj 4 Mar 2004, 11:15 PM
Mesaj #6


Domnitor
******

Grup: Membri
Mesaje: 6.255
Inscris: 3 October 03
Forumist Nr.: 899



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


--------------------
Azi avem.

Go to the top of the page
 
+Quote Post
axel
mesaj 4 Mar 2004, 11:20 PM
Mesaj #7


Domnitor
******

Grup: Membri
Mesaje: 6.255
Inscris: 3 October 03
Forumist Nr.: 899



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


--------------------
Azi avem.

Go to the top of the page
 
+Quote Post
E.B.E.
mesaj 22 Mar 2004, 02:43 PM
Mesaj #8


Domnitor
******

Grup: Membri
Mesaje: 1.292
Inscris: 20 November 03
Din: Delft, NL
Forumist Nr.: 1.248



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... smile.gif


--------------------

I spend my time thinking of Angel... praying she ain't thinking of me...

Go to the top of the page
 
+Quote Post
Catalin
mesaj 22 Mar 2004, 03:39 PM
Mesaj #9


Filosof boem
******

Grup: Membri
Mesaje: 6.222
Inscris: 10 July 03
Din: Bucuresti
Forumist Nr.: 445



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.

Acest topic a fost editat de Catalin: 22 Mar 2004, 03:41 PM
Descarca fisierul/ele
Fisier atasat  figura.gif ( 4.48K ) Numar descarcari: 46
 


--------------------
A nation cannot prosper for long when it favors only the prosperous - Obama
Go to the top of the page
 
+Quote Post
side_story
mesaj 11 Apr 2004, 10:33 PM
Mesaj #10


Vornic
****

Grup: Membri
Mesaje: 267
Inscris: 10 March 04
Forumist Nr.: 2.527



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?
Descarca fisierul/ele
Fisier atasat  20.doc ( 23K ) Numar descarcari: 31
 


--------------------
Asculta adevarul din adancul inimii tale. Daca tu nu il poti auzi, nimeni nu ti-l va putea spune.
Go to the top of the page
 
+Quote Post
Napoleon9th
mesaj 6 Jun 2004, 04:14 PM
Mesaj #11


Vataf
***

Grup: Membri
Mesaje: 151
Inscris: 26 May 04
Din: Bucuresti
Forumist Nr.: 3.638



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..."
Go to the top of the page
 
+Quote Post

Reply to this topicStart new topic

 



RSS Versiune Text-Only Data este acum: 13 December 2017 - 03:20 AM
Ceaiuri Medicinale Informatii despre Certificat Energetic