Pagini recente » Cod sursa (job #2002045) | Diferente pentru utilizator/sanzianagrecu intre reviziile 3 si 2 | Atasamentele paginii Profil nustiuba123 | Profil victorsofiischii | Diferente pentru grigore-moisil-2010/solutii/pietre2 intre reviziile 14 si 2
Nu exista diferente intre titluri.
Diferente intre continut:
h2(#pietre2). 'Pietre2':problema/pietre2
*Soluţie $1$*
Rezolvare 1
Rezolvarea se bazează pe observaţia că dacă vom procesa înălţimile în ordine crescătoare, atunci vom putea actualiza un drum de lungime maximă ce se termină în fiecare din aceste pătrăţele în mod corect.
Soluţia se bazează pe observaţia că dacă vom procesa înălţimile în ordine crescătoare, atunci vom putea actualiza un drum de lungime maximă ce se termină în fiecare din aceste pătrăţele în mod corect.
Astfel, algoritmul va sorta crescător toate cele $n^2^$ pătrăţelele :
Astfel, algoritmul va sorta crescător toate cele n2 pătrăţelele în funcţie de înălţime şi...
== code(cpp) |
== code(cpp)|
Algoritm Rezolvă(n):
pentru fiecare (h, i, j) execută: // pătrăţelul (i, j) cu înălţimea h
pentru fiecare vecin (h’, i’, j’) cu h = h’ + 1 execută:
Sfârşit(algoritm)
==
În implementare se va ţine cont ca pătrăţelele de pe marginea matricei care sunt puncte de plecare să fie marcate iniţial cu $0$.
Complexitate: $O(N^2^ log(N))$.
În implementare se va ţine cont ca pătrăţelele de pe marginea matricei care sunt puncte de plecare să fie marcate iniţial cu 0.
Complexitate: O(N^2^ log(N)).
*Soluţie $2$*
Problema, în ciuda faptului că limita pentru n este mare, se putea aborda şi cu backtracking. Cu o rezolvare asemănătoare cu cea de mai jos se putea obţine $90$ puncte.
Rezolvare 2
Problema, în ciuda faptului că limita pentru n este mare, se putea aborda şi cu backtracking. Cu o rezolvare asemănătoare cu cea de mai jos se putea obţine 90 puncte.
În programul principal:
== code(cpp) |
Algoritm Pietre(n,t): // n: dimensiunea tabloului t
max = 0 // lungimea maximă a drumului
maxlin = 0 // linia de unde porneşte cel mai lung drum
maxcol = 0 // coloana de unde porneşte cel mai lung drum
lin = 1 // vom încerca să intrăm în tablou pornind din linia 1
max = 0 // lungimea maximă a drumului }
maxlin = 0 // linia de unde porneşte cel mai lung drum }
maxcol = 0 // coloana de unde porneşte cel mai lung drum }
lin = 1 // vom încerca să intrăm în tablou pornind din linia 1 }
pentru col=1,n execută:
maxnou = 0 // maximul actual
rez[lin,col] = 1 // marcăm punctul de pornire
cauta(lin,col,2) // căutăm un drum având acest punct de start
dacă maxnou > max atunci // actualizarea
maxnou = 0 // maximul actual }
rez[lin,col] = 1 // marcăm punctul de pornire }
cauta(lin,col,2) // căutăm un drum având acest punct de start }
dacă maxnou > max atunci // actualizarea }
max = maxnou
maxlin = lin
maxcol = col
sfârşit(algoritm)
Algoritm Cauta(lin,col,pas):
pentru i=1,4 execută: // un element are 4 vecini
lin_nou = lin + x[i] // indicele de linie al vecinului
col_nou = col + y[i] // indicele de coloană
// dacă am generat o poziţie pe teren }
pentru i=1,4 execută: { un element are 4 vecini }
lin_nou = lin + x[i] //{ indicele de linie al vecinului }
col_nou = col + y[i] //{ indicele de coloană }
//{ dacă am generat o poziţie pe teren }
dacă (lin_nou = {1,2,...,n}) şi (col_nou = {1,2,...,n}) atunci
dacă rez[lin_nou,col_nou] = 0 atunci // dacă nu am fost aici
// dacă numărul pietrelor este cu 1 mai mare
dacă rez[lin_nou,col_nou] = 0 atunci //{ dacă nu am fost aici }
//{ dacă numărul pietrelor este cu 1 mai mare }
dacă t[lin_nou,col_nou] = t[lin,col] + 1 atunci
rez[lin_nou,col_nou] = pas // facem pasul
dacă pas > maxnou atunci //actualizăm maximul actual
rez[lin_nou,col_nou] = pas //{ facem pasul }
dacă pas > maxnou atunci { actualizăm maximul actual }
maxnou = pas
sfârşit(dacă)
Cauta(lin_nou,col_nou,pas+1) // încercăm să continuăm drumul
rez[lin_nou,col_nou] = 0 // ştergem pasul, pentru că vom căuta alt drum
Cauta(lin_nou,col_nou,pas+1) { încercăm să continuăm drumul }
rez[lin_nou,col_nou] = 0 { ştergem pasul, pentru că vom căuta alt drum }
sfârşit(dacă)
sfârşit(dacă)
sfârşit(dacă)
==
unde şirurile $x$ şi $y$ au valorile:
$x = (-1,0,1,0)$
$y = (0,1,0,-1)$
*Soluţie 3*
Problema se poate rezolva şi în complexitatea $O(N^2^)$ folosind memoizarea. Astfel, vom calcula pentru fiecare element al matricii cât se poate urca dacă pornim din elementul respectiv. Pseudocodul funcţiei care calculează pentru fiecare element cât se poate urca dacă pornim din elementul respectiv arată astfel:
== code(cpp) |
funcţie din(i, j):
dacă(D[i][j] != 0) atunci
returnează D[i][j]
sfârşit dacă
D[i][j] = 1
pentru fiecare vecin (i’, j’) al perechii (i, j) execută:
dacă A[i][j] + 1 = A[i’][j’] şi D[i][j] < din(i’, j’) + 1 atunci
D[i][j] = din(i’, j’) + 1
sfârşit dacă
sfârşit pentru
Sfârşit(din)
==
Se observă că fiecare pentru fiecare element al matricii, funcţia este apelată de un număr constant de ori, deci complexitatea algoritmului este $O(N^2^)$.
unde şirurile x şi y au valorile:
x = (-1,0,1,0)
y = (0,1,0,-1)
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.