Imprimă pagina - Algoritmul lui Lee [need help ]

Titlul: Algoritmul lui Lee [need help ]
Scris de: Dascal Cezar din Ianuarie 28, 2009, 12:53:50

off..an nevoie, de Algoritmul lui Lee implementat de preferat in c++. Mentionez ca sunt elev in clasa a X-a..
Va rog,ajutati pe cei sa saraci cu duhul ca mine. :D

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: alexandru din Ianuarie 28, 2009, 14:59:28

Daca cauti pe net o sa gasesti uite : http://infoscience.3x.ro/c++/Algoritmul_lui_Lee.htm
sau http://www.ginfo.ro/revista/15_2/focus1.pdf iti zic sincer nu prea stiu ce face nici n-am auzit dar am dat shearch pe google :P

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Pripoae Teodor Anton din Ianuarie 28, 2009, 15:06:04

Uite un exemplu, am presupus ca tu vrei sa ajungi din start in end, si ai unele casute prin care nu poti trece, marcate cu '#' (diez).

Cod:

#include <queue> // pt queue
#include <algorithm>  // pt pair
#define mkp make_pair
#define ff first
#define ss second
#define punct pair<int,int>

using namespace std;

int A[1000][1000], D[1000][1000];

punct start, end;

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

int lee(){
	int i;
	
	initializare(); // initializam matricea D cu infinit, marginile cu -1 si punctul de inceput cu 0
	
	queue<punct> Q;
	punct now, now2;
	
	Q.push(start);	// bagam punctul de inceput in coada
	
	while (Q.empty() == false){			// cat timp coada nu e vida
		now = Q.front(); Q.pop(); // eliminam nodul din fata din coada
		if (now == end) // daca se poate returnam minimul
			return D[end.ff][end.ss];
		for (i = 0; i < 4; ++i){	// parcurgem vecinii
			now2 = mkp(now.ff + dx[i], now.ss + dy[i]);
			if (D[now2.ff][now2.ss] > D[now.ff][now.ss] + 1 && A[now2.ff][now2.ss] != '#'){
				// daca se poate ajunge cu cost mai bun si nu e ocupata casuta (sa zicem ca unele casute sunt ocupate, depinde de enuntul problemei
				D[now2.ff][now2.ss] = D[now.ff][now.ss] + 1; // modificam costul
				Q.push(now2);	// bagam in coada nodul curent
			}
		}
	}
	
	return -1; //daca se ajunge aici inseamna ca nu se poate ajunge la destinatie 
	
}

Spor :)

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Dascal Cezar din Februarie 01, 2009, 12:19:14

:D Merci mult !

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Cosmin Negruseri din Februarie 02, 2009, 23:07:36

Ce cauti tu se numeste algoritmul de cautare in latime. Nu exista algoritmul lui Lee cel putin el nu se refera la acest algoritm. Din pacate a intrat in constiinta publica a profesorilor din romania dupa ce acest algoritm a fost numit asa in una din cartile de probleme de algoritmica de la inceputul anilor 90.

Arhiva educationala are o problema in care e explicat algoritmul si daca te uiti la solutii poti vedea diverse implementari de 100 de puncte. Poti sa gasesti aici problema http://infoarena.ro/problema/bfs

Si pentru ceilalti, in loc sa hranim userii cu informatie mura in gura, e mai bine cateodata sa popularizam sectiuni ale siteului infoarena care ii ajuta sa isi rezolve problemele.

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Maria Stanciu din Februarie 03, 2009, 17:57:07

Citat din mesajul lui: Cosmin Negruseri din Februarie 02, 2009, 23:07:36

Si pentru ceilalti, in loc sa hranim userii cu informatie mura in gura, e mai bine cateodata sa popularizam sectiuni ale siteului infoarena care ii ajuta sa isi rezolve problemele.

A da cuiva "mura in gura" inseamna (in acest context) a-l ajuta pe celalalt, a pune la share ceea ce tu deja stii. De ce sa nu vrei sa ajuti sau sa explici atunci cand ti se solicita ajutorul sau explicatia? Sunt convinsa ca (mai ales utilizatorii noi care fac cont doar pentru a intreba despre o tema si apoi nu mai intra niciodata -poate- pe Infoarena) daca ar vrea o colectie de link-uri (folositoare) legate de intrebarea pe care o ridica ar da simplu search pe Google.

E o diferenta intre a interactiona cu oamenii, a purta o discutie, a oferi lamuriri, a putea intoarce o intrebare in caz de noi nelamuriri care se ivesc si a "te descurca" singur cu un site. Eu de cele mai multe ori prefer sa intreb pe cineva dispus sa-si faca timp sa-mi raspunda decat sa "sap" singura. Si cred ca cei mai multi suntem asa.

Raspunsul tau, de exemplu, mi s-a parut perfect inainte sa citesc precizarea pe care am citat-o. Ofera informatii suficiente si daca cel care a avut probleme considera ca-l poti ajuta mai departe te va intreba probabil si ce este cautarea in latime. Strecori printre randuri si un link folositor care duce intr-o alta sectie Infoarena. La final vii cu aceata precizare, careia ii vad logica, dar nu-i vad rostul intr-un topic, intr-un forum chiar, in care de cele mai multe ori raspunsurile sunt complete, tastate "de mana" si oferite cu bunavointa.

Cu respect,
Maria Stanciu

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: alexandru din Februarie 03, 2009, 18:23:37

@Stanciu Maria nu vreau sa te supar dar nu prea vad rostul comentului tau :P

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Maria Stanciu din Februarie 03, 2009, 18:33:24

Alexandru, comentariu meu era pentru cei care ii vad rostul.

Pentru restul el poate intra, ca si al tau, in categoria posturilor menite sa creasca numarul de posturi. Nu m-ai suparat cu nimic, nu-ti face griji :).

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: alexandru din Februarie 03, 2009, 19:09:50

Citat

in categoria posturilor menite sa creasca numarul de posturi

Pe oirce forum intru, un doi vad aceasta replica care ma scoate din nervi :readthis: cu ce ma ajuta ca imi cresc posturile, ma ajuta sa o gasesc pe zana maseluta, o comoara ascunsa daca am nr posturi = 500000, sau?...e o replica de adreptu lipsita de rost si sa nu zic altfel.

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Savin Tiberiu din Februarie 03, 2009, 19:21:33

Cred ca Cosmin se referea la un alt post care m-a deranjat oarecum si pe mine si chiar ma intrebam daca sa il sterg sau nu, mai exact postul lui Toni, care a pus acolo o implementare directa pe care daca o copiezi pur si simplu iti va rezolva problema insa nu vei intelege nimic. Exact ceea ce inseamna "a da mura in gura".

Anyway discutia devine offtopic.

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Maria Stanciu din Februarie 03, 2009, 21:43:07

Uite tocmai (cum zici si tu) ca Toni a pus mai sus o implementare directa ce poate fi folosita, chestie care in fond este exact ceea ce Dascal Cezar a cerut prin acest topic: "Algoritmul lui Lee implementat de preferat in c++". Chiar te-a suparat ca i-a raspuns :)? Astfel de implementari se mai gasesc pe net, a sterge postul de mai sus nu este o solutie pentru a evita fenomenul de a da copy-paste fara sa intelegi ceva.

Imi pare rau ca am dus discutia in offtopic, daca prin asta creez neplaceri moderatorilor. Si imi pare rau ca nu inteleg de ce priviti asa lucrurile.

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Pripoae Teodor Anton din Februarie 03, 2009, 23:40:13

Omul a cerut un algoritm in C++, i-am dat ce a cerut, i-am comentat toata sursa (cred ca mai mult din jumatate din sursa sunt comentarii), pentru a intelege ce face sursa. Daca el da copy paste la sursa e problema lui, nu vad de ce ar trebui sa ne pierdem noi timpul intr-un mod foarte useless pentru a ne intreba ce face el cu codul postat de mine. Sunt convins ca daca omul chiar ar fi vrut sa aiba mura in gura ar fi dat un post pe softpedia sau orice forum d-asta cu sute de useri online odata, unde intrebi ceva si in 10 minute ti-au raspuns deja 3 oameni, si ar fi obtinut raspunsul.

Numai bine,

Toni

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: alexandru din Februarie 04, 2009, 10:04:22

Pentru a termina cu datul "mura in gura", ar trebui inceput din scola unde proful da algoritum , toti il tocesc , 99%- nu-l inteleg si de aceea desi il stiu n-au habar cum sa-l aplice, plus oricene vera da la google un shearch si ai vreo 100 de exmple cu acel algrotim deci este inutil
And lets stop with this.... ok?

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: CHERA Laurentiu din Februarie 08, 2009, 20:40:33

editat de moderator: nu postati solutii complete la problemele din arhiva.

Ii felicit pe toti ce isi pierd timpul pentru a solutiona si a explica probleme pe acest forum! Le voi mai adauga tuturor cate un punct la Karma. Mie mi se pare "ok" postarea codurilor integral si in acelasi timp explicate, cel putin postul lui toni mi s-a parut ok si nu era foarte greu de inteles.
Imi cer scuze ca am postat problema respectiva! Am vrut doar sa fiu de ajutor! Era o implementare fara "stl". :ok:

Titlul: Răspuns: Algoritmul lui Lee [need help ]
Scris de: Sima Cotizo din Februarie 08, 2009, 21:22:23

In loc de rezolvarea integrala puteai sterge din sursa bucati incat sa ramana doar partea necesara a algoritmului. Nu strica "bucuria" altor participanti de a rezolva singuri unele probleme / de a descoperi metodele prin care se rezolva. Pentru problemele din arhiva nu se posteaza solutii integrale, iar daca vrei sa ajuti o poti face postand doar partea "care trebuie". :thumbup:

---

Cred ca discutia devine off-topic si in afara de vreo 2 posturi, restul nu isi au locul aici. Haideti sa nu o continuam inutil.

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Dascal Cezar din Ianuarie 28, 2009, 12:53:50