[Tutorial C++]Principiul Lui Dirichlet

GiovanY · Founder Data inscrierii: 05/Sep/2008 Mesaje: 1979

Principiul lui Dirichlet
v: 89 54 4 63 96 17 98 6 55 60
s(i)=v[1]+...+v[i]
s:89 143 147 210 306 323 421 427 482 542
exista i a.i. s(i)%n=0 => v[1]+v[2]+...+v[i]
oricare i S(i)%n!=0 x%n=(1,n-1)
=>S(i)%n={1. 2, ..., n-1} i={1, 2, ...,n}
=>exista j,k=(1,n)
pp.j<k a.i. s(j)=s(k)
S(j)%n-r => s(j)n*c+r
=> s(k)-s(j)=n*c1+r-n*c2-r=n(c1-c2)
r: 8 3 7 0 6 3 1 7 2 2
j=3
=>(s(8)-s(3))% n=0
k=8

Exemplu de problema care foloseste principiul lu Dirichelt este urmoatoarea:
Se considera un vector format din n elemente nr intregi pozitive.
Sa se afiseze:
o secventa formata din elemente consecutive pt care suma elementelor
secventei se divide cu n.