Pentru Informaticieni |
Bine ati venit ca musafir! ( Logare | Inregistrare )
Pentru Informaticieni |
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
|
|
|
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... |
|
|
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!
-------------------- A nation cannot prosper for long when it favors only the prosperous - Obama
|
|
|
Promo Contextual |
4 Mar 2004, 12:49 PM
Mesaj
#
|
ContextuALL |
|
|
|
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:
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 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... |
||
|
|||
4 Mar 2004, 11:12 PM
Mesaj
#5
|
|||
Filosof boem Grup: Membri Mesaje: 6.222 Inscris: 10 July 03 Din: Bucuresti Forumist Nr.: 445 |
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
|
||
|
|||
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
Ce faci daca ti se cer sa spunem rezultat cu 5 zecimale? -------------------- Azi avem.
|
|
|
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.
|
|
|
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 |
Spune-mi si mie sa nu mor prost... -------------------- I spend my time thinking of Angel... praying she ain't thinking of me... |
||
|
|||
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
-------------------- A nation cannot prosper for long when it favors only the prosperous - Obama
|
|
|
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
-------------------- Asculta adevarul din adancul inimii tale. Daca tu nu il poti auzi, nimeni nu ti-l va putea spune.
|
|
|
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..." |
|
|
Versiune Text-Only | Data este acum: 25 April 2024 - 07:41 PM |