Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 1045 Covor  (Citit de 1341 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« : Mai 10, 2010, 08:00:30 »

Aici puteti discuta despre problema Covor.
Memorat

Am zis Mr. Green
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #1 : Iunie 22, 2011, 21:40:29 »

Salut la toata lumea.

Am o rezolvare in O(N^2) pe care cred ca o pot si demonstra prin inductie, cu toate acestea iau 0 puncte. Imi puteti spune va rog daca afirmatia mea e corecta? Recursivitatea este asa:

  -  Daca pe pozitia A[ i ][ j ] este 0 si pe A[ i-1 ][ j ] == 0 si A[ i ][ j-1 ] == 0 ( adica si sus si la stanga sa fie 0 ) recursivitatea este A[ i ][ j ] = A[ i-1 ][ j ] + A[ i ][ j-1 ] + 1 - A[ i-1 ][ j-1 ]
  -  Daca A[ i-1 ][ j ] ( cea de deasupra ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de la stanga
  -  Daca A[ i ][ j-1 ] (cea de la dreapta ) e 1 atunci A[ i ][ j ] va lua doar numarul de 0-uri de deasupra

Este corecta aceasta rezolvare?
Eu am testat aceasta rezolvare pe mai multe teste, chiar am si verificat cu o solutie brute force, si toate imi dau corect.
De ex pentru testul :

Cod:
18
010101010101010111
111000101011010111
111000101011010101
111000101011111010
001010110101010101
111000101011010100
111000101011010100
111000101011111000
001010110101010100
111000101011010100
111000101011010100
111000101011111000
001010111110001000
101101011110001000
101101011110001000
101111100010101100
000000000000000000
000000000000000000

Da 1250 ?

Va rog frumos sa ma ajutati.
Multumesc!
« Ultima modificare: Iunie 22, 2011, 21:53:15 de către Lambru Andrei Cristian » Memorat
mathboy
Moderatori infoarena
Nu mai tace
*****

Karma: 150
Deconectat Deconectat

Mesaje: 259



Vezi Profilul
« Răspunde #2 : Iunie 22, 2011, 22:15:11 »

Si mie imi da tot 1250 Smile
Memorat
maritim
Vorbaret
****

Karma: 59
Deconectat Deconectat

Mesaje: 176



Vezi Profilul
« Răspunde #3 : Iunie 22, 2011, 22:18:30 »

Multumesc frumos pentru raspuns.

Mi-ai putea da si mie sursa prin PM te rog frumos? Din moment ce eu nu mai am idei de rezolvare mi-ar fi de mare ajutor.

Multumesc.

L.E. : Recurenta intr-un fel sau altul era gresita!
« Ultima modificare: August 22, 2013, 20:03:25 de către Lambru Andrei Cristian » Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #4 : Iunie 23, 2011, 11:50:16 »

Ce inseamna matricea A? Nu putem sa ne dam seama daca recurenta e corecta fara sa stim ce vrei sa calculezi. Smile
Memorat

Am zis Mr. Green
mvcl3
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 22



Vezi Profilul
« Răspunde #5 : Aprilie 10, 2014, 12:19:47 »

care va fi raspunsul pentru
2
00
00
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines