Sa se determine o alegere a semnelor + si -

Se citeste n. Sa se determine o alegere a semnelor + si - astfel incit sa avem relatia  n=0.

Analiza problemei – elaborarea algoritmului:

Problema a fost data la olimpiada scolara de informatica. Daca se incearca o abordare 'in forta' si 'la prima mina' vor trebui verificate 2ⁿ posibilitati de asezare a semnelor + si -. Adica se obtine un algoritm exponential, total ineficient. Solutia 'eleganta' ce rezulta printr-o analiza mai aprofundata:

-mai intai se va imparti suma in doua parti: cea cu plus si cea cu minus.

Privindu-se atent se observa ca se pot deosebi trei cazuri:

1. cind avem intre cele n numere un numar impar de numere impare (de ex.n=3,5,6) caz in care numerele impare nu pot fi repartizate in cele doua parti (plus si minus) decit astfel: un nr.par de numere impare intr-o parte si un nr.impar de nr impare in cealalta; implica ca cele doua parti au paritati diferite, deci suma lor nu poate fi 0 !

Acest caz apare cind n=4k+1, 4k+2.

2. cind n=4k atunci numerele de la 1 la n pot fi grupate cite patru astfel:

1-2-3+4, , (4i+1)-(4i+2)-(4i+3)+(4i+4), si vor avea suma 0 pe fiecare grupa de patru !

3. altfel, n=4k+3, putem grupa numerele asemanator ca la cazul dinainte cu exceptia primei grupe: -1-2+3, 4-5-6+7, , (4i)-(4i+1)-(4i+2)+(4i+3),reazultind din nou suma 0 pe fiecare grupa !

Program Plus_Minus;

Var

n,i,c:byte;

BEGIN

Writeln('Se citeste n. Sa se determine o alegere a semnelor + si - ');

Writeln('astfel incit sa avem relatia n=0.');

Write('n:');Readln(n);

c:=n mod 4;

case c of

1,2: Writeln('Nu exista solutie.');

0: For i:=1 to n div 4 do

write('+',4*(i-1)+1,'-',4*(i-1)+2,'-',4*(i-1)+3,'+',4*(i-1)+4);

3:begin

Write('-1-2+3');

For i:=1 to n div 4 do

write('+',4*i,'-',4*i+1,'-',4*i+2,'+',4*i+3);

end;

end;

Readln;

END.