Probleme pentru olimpiade


Probleme pentru olimpiade 
(Rezolvari)
Clasele 10-12
Problema 1.   Suma cifrelor
     Să se afişeze toate numerele naturale formate din maximum 3 cifre cu proprietatea că suma cifrelor este S.
Input:             Suma cifrelor  se citeşte de la tastatură.
Output:           La ecran se vor afişa numerele respective separate printr-un spaţiu.
Exemplu:       Input:      3
Output:   3 12 21 30 102 111 120 201 210 300  
Rezolvare - metoda 1:
Algoritmul problemei:
Cercetăm aparte numerele de 1 cifră, de 2 cifre şi de 3 cifre. Pentru numerele formate dintr-o singură cifră, rezultatul este valoarea introdusă, dacă ea nu depăşeşte 9. Pentru numerele de 2 cifre, construim numărul din cifrele sale cu ajutorul a 2 cicluri, pentru fiecare cifră, primul de la 1 la 9, iar al doilea de la 0 la 9 şi pentru fiecare număr obţinut testăm condiţia ca suma cifrelor să fie egală cu valoarea dată.  Numerele ce respectă condiţia testată se afişează la ecran. Analog pentru numerele formate din 3 cifre, vom construi numerele din cifrele sale. Cifrele le obţinem cu ajutorul a 3 cicluri: primul de la 1 la 9, al doilea şi al treilea de la 0 la 9 şi pentru fiecare număr obţinut testăm condiţia ca suma cifrelor să fie egală cu valoarea dată. Afişăm la ecran numerele ce respectă condiţia cerută.
Programul în limbajul Pascal:
Program Suma_cifrelor_1;
Uses CRT;
Type Cifre=0..9;
Var a1,a2,a3:Cifre; { cifrele numarului }
    S:Byte; { suma cifrelor }
Begin
  ClrScr;
Write(’Introduceti suma cifrelor:’);ReadLn(S);
If S<9 Then Write(S,' ');
{ formarea numerelor de 2 cifre }
For a1:=1 To 9 Do
    For a2:=0 To 9 Do
        If a2+a1=S Then Write(a1,a2,' ');
{ formarea numerelor de 3 cifre }
For a1:=1 To 9 Do
    For a2:=0 To 9 Do
        For a3:=0 To 9 Do
            If a1+a2+a3=N Then Write(a1,a2,a3,' ');
Readkey
End.
Rezolvare – metoda 2:
Algoritmul problemei:
Utilizăm un tablou unidimensional cu 3 componente. Construim numerele din cifrele sale prin intermediul a 3 cicluri de la 0 la 9 după toate cifrele posibile şi le înscriem în tablou pe cele ce respectă condiţia: suma c ifrelor este egală cu numărul dat. La afişarea la ecran a componentelor tabloului, zerourile de la începutul tabloului se ignorează.
Programul în limbajul Pascal:
Program Suma_cifrelor_2;
Uses CRT;
Type Lin=Array[1..3] Of Byte;
Var A:Lin;
   c1,c2,c3:0..9;
   S,i,j:Byte;
Begin
 ClrScr;
  Write('Suma cifrelor=');ReadLn(S);
  For c1:=0 To 9 Do
      For c2:=0 To 9 Do
          For c3:=0 To 9 Do
  If c1+c2+c3=S Then Begin
                     A[1]:=c1;
                     A[2]:=c2;
                     A[3]:=c3;
  I:=1; While (A[I]=0) And (I<=3) Do Inc(I);
  If I<=3 Then Begin
                 For J:=I To 3 Do Write(A[J]); Write(' ')
               End
          Else Begin
                 WriteLn(’0’);
                 Break
               End  
                     End;
 Readln
End.
Rezolvare - metoda 3:
Algoritmul problemei:
Parcurgem prin intermediul unui ciclu toate numerele naturale de maxim 3 cifre de la 0 la 999. Pentru fiecare număr calculăm suma cifrelor şi o comparăm cu suma dată. Numerele, pentru care suma cifrelor sale este egală cu suma dată se afişează la ecran.
Programul în limbajul Pascal:
Program Suma_cifrelor_3;
Uses CRT;
Type Natural=0..MaxInt;
Var S,I:Natural;
Function Sum(X:Natural):Natural;
(* calculeaza suma cifrelor unui numar *)
Begin
  If X=0 Then Sum:=0
         Else Sum:=Sum(X Div 10) + X Mod 10
End;
Begin
  ClrScr;
Write(’Introduceti suma cifrelor:’);ReadLn(S);
For I:=0 To 999 Do
If Sum(I)=S Then Write(I,' ');
ReadLn
End.
Problema  2.   Piramida norocului
     Pentru a afla numărul norocos al unei persoane în funcţie de numele ei, există o tehnică veche ce consta în construirea piramidei norocului efectuând doar operaţii de adunare în mulţimea cifrelor. Fiecărei litere a alfabetului i se asociază o cifră nenulă, conform tabelului de mai jos:
1
2
3
4
5
6
7
8
9
a
b
c
d
e
f
g
h
I
j
k
l
m
n
o
p
Q
R
s
t
u
v
w
x
y
Z

     Cifra norocoasă se determină astfel:  se notează în dreptul fiecărei litere cifra corespunzătoare şi se adună două câte două cifrele vecine, obţinându-se un nou şir de cifre cu care se va proceda la fel până în momentul în care se obţine o  singură cifră. De fiecare dată se va obţine un număr nenul mai mic sau egal cu 9 ca rezultat al unei adunări dintre două cifre.  Pentru rezultatele mai mari ca 9 se va aplica din nou operaţia de adunare a cifrelor rezultatului obţinîndu-se în final tot o singură cifră. Introducîndu-se de la tastatură un şir de caractere ce reprezintă  numele unei persoane, afişaţi piramida norocului şi determinaţi cifra norocoasă corespunzătoare.
Input:     numele persoanei se va citi de la tastatură (literele mari sau mici)
Output:    la ecran se va afişa piramida norocului astfel:
- cifrele din fiecare rînd al piramidei se vor afişa  despărţite printr-un spaţiu;
- primul rând de cifre al piramidei va fi aliniat la marginea din stânga a ecranului, celelalte
  rânduri vor fi astfel afişate încât să dea forma piramidei aşa cum este afişată în exemplul de
  mai jos.
Exemplu: Input:    Sonia
  Output:
1 6 5 9 1 à  1+6=7 6+5=11=1+1=2 5+9=14=1+4=5 9+1=10=1+0=1
 7 2 5 1
  9 7 6
   7 4
    2
Rezolvare:
Algoritmul problemei:
     Ideiea algoritmului este foarte simplă: construim primul nivel al piramidei, înlocuind fiecare literă prin cifra respectivă. Afişăm nivelul obţinut. Construim nivelul următor adunînd cifrele vecine ale nivelului anterior: prima cu a doua, a doua cu a treia, ..., penultima cu ultima cifră. Dacă la careva moment obţinem un număr mai mare ca 9, scriem în locul lui suma cifrelor sale. Afişăm acest nivel. Retranscriem nivelul al doilea în structura de date destinată primului nivel şi calculăm valorile nivelului următor conform algoritmului descris. Repetăm procesul pînă cînd rămîne o singură cifră.
     Prezentăm în continuare 2 programe în limbajul Pascal, ce implementează acest algoritm. Primul program utilizează în calitate de structuri de date pentru păstrarea valorilor a două nivele vecine a piramidei şirurile de caractere, al doilea – tablourile unidiminsionale.
Programul 1:
Program Piramida_norocului_1;
Uses CRT;
Var N,K:Byte;
    Pi,Po,Po2:String;
    T:Integer;
    A:LongInt;
    S:Boolean;
Function Suma(Q:String):String;
Var E:String;
Begin
  Val(Q,A,T);
While A>9 Do A:=A div 10+A mod 10;
             Str(A,E); Suma:=E
End;
Begin
  ClrScr;
  Write(’Introduceti numele:’);ReadLn(Pi);Po:='';
  S:=True;
For K:=1 To Length(Pi) Do
Case UpCase(Pi[K]) Of 'A','J','S':Po:=Po+'1';
                      'B','K','T':Po:=Po+'2';
                      'C','L','U':Po:=Po+'3';
                      'D','M','V':Po:=Po+'4';
                      'E','N','W':Po:=Po+'5';
                      'F','O','X':Po:=Po+'6';
                      'G','P','Y':Po:=Po+'7';
                      'H','Q','Z':Po:=Po+'8';
                      'I','R':Po:=Po+'9'
   Else Begin
        WriteLn('nu ati introdus corect');
        S:=False
        End
End;
If S Then Begin
For K:=1 To Length(Po) Do
    Write(Po[K],' '); N:=1; writeln;
While length(Po)>1 Do Begin  Po2:='';
For K:=1 To Length(Po)-1 Do
    Po2:=Po2+Suma(Copy(Po,K,2));
If N>0 Then For K:=1 To N Do Write(' ');
For K:=1 To Length(Po2) Do Write(Po2[K],' ');Po:=Po2;
Inc(N); WriteLn End End;
Readkey
End.
Programul 2:
Program Piramida_norocului_2;
Uses CRT;
Const s1='ABCDEFGHI';
      s2='JKLMNOPQR';
      s3='STUVWXYZ';
Type Tab=Array[1..255] Of Byte;
Var Nume:String;
    A,B:Tab;
    Sp,K,H,N,I:Byte;
    V:Boolean;
Begin
  ClrScr;
  Write('Introduceti numele persoanei:');ReadLn(Nume);
      V:=True;
  For I:=1 To Length(Nume) Do
      If Not (Upcase(Nume[I]) in ['A'..'Z']) Then V:=False;
  If V Then Begin
            N:=0;
  For I:=1 To Length(Nume) Do
  If Pos(Upcase(Nume[I]),S1)>0 Then Begin
                                    Inc(N);A[N]:=Pos(Upcase(Nume[I]),S1)
                                    End
  Else  If Pos(Upcase(Nume[I]),S2)>0 Then Begin
                                          Inc(N);A[N]:=Pos(Upcase(Nume[I]),S2)
                                          End
  Else Begin
       Inc(N);A[N]:=Pos(Upcase(Nume[I]),S3)
       End;
  For I:=1 To N Do Write(A[I],' '); WriteLn;
      K:=N; Sp:=0;
  While K>1 Do Begin
                 B:=A;
        For H:=1 To K-1 Do Begin
            A[H]:=A[H]+A[H+1];
  If A[H]>9 Then A[H]:=(A[H] Mod 10)+(A[H] Div 10)
               End;
  K:=H; Inc(Sp);
  For H:=1 To Sp Do Write(' ');
  For H:=1 To K Do
      Write(A[H],' ');
      WriteLn
  End   End
  Else WriteLn('numele nu este introdus corect');
  Readln
End.
Problema  3.  Parcurgerea matricei
     Se dă matricea A[N,N]  de  numere întregi(N≤10). De parcurs matricea în următoarea ordine:
primul  se va afişa elementul A[N,1], urmează  mişcarea în dreapta, apoi paralel cu diagonala principală, mişcarea în sus, apoi iarăşi paralel cu diagonala principală, ş.a.m.d., ultimul element va fi A[1,N].
Input:             De la tastatură se întroduce N şi  elementele matricei
Output:          La ecran se vor afişa elementele în ordinea indicată
Exemplu:   Input:   4
 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16
                        Output:    13 14 9 5 10 15 16 11 6 1 2 7 12 8 3 4
Rezolvare:
Algoritmul problemei:Esenţa parcurgerii tabloului este ciclică: se merge la dreapta, pe diagonală în sus, în sus, pe diagonală în jos. Este important de remarcat că pe diagonală se merge pînă la margine (pînă cînd poziţia parcurgerii este adiacentă unui perete); la mişcarea în sus şi la dreapta – doar pe o celulă. Algoritmul este următorul: se ia o variabilă (am noptat-o prin M) care poate lua valorile 0,1, 2, 3, 4. 0 înseamnă deplasare la dreapta, 1 – pe diagonală în sus, 2 – în sus, 3 – pe diagonală în jos. Se organizează un ciclu Reapeat cu condiţia de oprire (k=1)  and (h=n), unde k,h – poziţia curentă a elementului prelucrat curent. Se începe din colţul (1,n) şi se porneşte cu M=0. Dacă M>3, el se resetează la 0. Dacă M=2 sau M=0, după schimbarea poziţiei se va mări contorul M; dacă M=3 sau M=1, M se măreşte cu o unitate doar în cazul în care nu se poate merge mai departe. Pentru a evita parcurgerea ciclică a diagonalei principale (nu poate merge la dreapta, alege următoarea opţiune, care este pe diagonală în sus; cînd ajunge în colţul (1,1) trebuie să meargă în sus, nu poate şi alege următoarea opţiune – diagonală în jos; ciclu infinit) s-a introdus un tablou bidimensional în care sînt marcate toate poziţiile trecute. Tipărirea elementului se face la sfîrşitul ciclului.
Programul în limbajul Pascal:
Program Parcurgerea_matricei;
Uses CRT;
Type Tab=Array[1..10,1..10] Of Integer;
Var A,B:Tab;
    N,K,H,M,Dc:Byte;
    S:Boolean;
{0=right; 1=diagup; 2=up; 3=diagdown}
Procedure Citire;
Var I,J:Byte;
Begin
Write(’Dimensiunea matricei:’);ReadLn(N);
   For I:=1 To N Do
       For J:=1 To N Do
           Begin
   Write(’A[’,I,’,’,J,’]=’);
   ReadLn(A[I,J])
          End 
End;
Begin
  ClrScr;
  Citire;
For K:=1 To N Do
For H:=1 To N Do B[K,H]:=1;
M:=0; K:=N; H:=1; Write(A[N,1]:3);
Repeat
  S:=False;
If M>3 then M:=0;
If Not S And (M=3) And (H<N) And (K<N) And (B[K+1,H+1]>0)
   Then Begin
        Inc(H);
        Inc(K);
        S:=True
        End
   Else
   If Not S And (M=3) Then Inc(M);
If Not S And (M=2) And (K>1) Then Begin
                                  Dec(k);
                                  Inc(m);
                                  S:=True
                                  End
                              Else
If Not S And (M=2) And (K=1) Then Inc(M);
If Not S And (M=1) And (H>1) And (K>1) And (B[K-1,H-1]>0)
   Then Begin
        Dec(H);
        Dec(K);
        S:=True
        End
   Else If Not S And (M=1)
                          Then Inc(M);
If Not S And (M=0) And (H<N) Then
         Begin
           Inc(H); Inc(M); S:=True
         End
Else If Not S And (M=0) Then Inc(M);
If S Then Begin
            Write(A[K,H]:3);
            B[K,H]:=0
          End
Until (K=1) And  (H=N);
Readkey
End.
Clasele 5-9
Problema 1. Suma cifrelor pare
     Se dă un  număr întreg N (0≤N≤32000). Calculaţi suma cifrelor pare din numărul N.
Input:            Numărul N se citeşte de la tastatură.
Output:        Suma cifrelor  se afişează la ecran.
Exemplu:     Input:    24329
           Output:  8
Rezolvare:
Algoritmul problemei:
Cifrele unui număr pot fi extrase de la dreapta la stînga prin împărţiri repetate la 10. Iniţial deîmpărţitul este numărul dat. Se împarte deîmărţitul la 10 şi restul reprezintă ultima cifră a numărului, iar cîtul devine deîmpărţit pentru următoarea împărţire. Se împarte noul deîmpărţit la 10, restul este penultima cifră, cvîtul devine din nou deîmpărţit ş.a.m.d., pînă cînd deîmpărţitul devine 0. Pentru fiecare cifră obţinută testăm condiţia, dacă ea este pară. Pentru calcularea sumei cifrelor pare se utilizează o variabilă, care iniţial se zerografiază şi cînd obţinem o cifră pară, adunăm valoarea ei la valoarea variabilei destinată pentru calcularea sumei.
Programul în limbajul Pascal:
Program Suma_cifrelor_pare;
Uses CRT;
Type Natural=0..MaxInt;
     Cifre=0..9;
Var N,S:Natural;
    C:Cifre;
Begin
  ClrScr;
  Write('Introduceti numarul:');ReadLn(N);
  S:=0;
  Repeat
    C:=N Mod 10;
    If C Mod 2=0 Then S:=S+C;
    N:=N Div 10
  Until N=0;
  If S=0 Then WriteLn('Numarul nu contine cifre pare')
         Else WriteLn(S);
  ReadLn
End.
Problema  2. Cuvînt
     Se dă un text  alcătuit din litere mici ale alfabetului latin şi cuvintele sînt separate prinr-un spaţiu (lungimea textului≤255). Afişaţi la ecran cel mai lung cuvînt cu literele sale în ordine alfabetică. Dacă astfel de cuvinte sunt cîteva, de afişat primul din ele. Dacă nu-i nici un cuvînt de acest fel, la ecran se va afişa simbolul „?”
Input:            Textul se citeşte  de la tastatură.
Output:        Cuvîntul găsit se afişează la ecran.
Exemplu:     Input:     apa abc abcd adfa pqrs adadad arar p
                     Output:  abcd
Rezolvare:
Algoritmul problemei:
Declarăm o variabilă pentru înregistrarea cuvîntului de lungime maximă cu literele în ordine alfabetică, căreia iniţial i se atribuie valoarea „şir vid”. Copiem cîte un cuvînt din propoziţie şi pentru fiecare cuvînt obţinut testăm, dacă literele sunt în ordine alfabetică. Dacă condiţia se respectă, comparăm lungimea cuvîntului cu lungimea cuvîntului maximal şi păstrăm în memorie în variabila respectivă acel cuvînt, la care lungimea este mai mare. Dacă nu a fost găsit nici un cuvînt cu literle ordonate alfabetic, atunci variabila destinată pentru înregistrarea cuvîntului de lungime maximă va avea valoarea „şir vid”.
Programul în limbajul Pascal:
Program Cuvint_maximal;
Uses CRT;
Var P,Cmax,Cuv:String;
    L:Byte;
Function V(X:String):Boolean;
(* verifica, daca literele cuvintului sunt
                           in ordine alfabetica *)
Var C:Boolean;
    I:Byte;
Begin
  C:=True; I:=1;
  While C And (I<Length(X)) Do
  If X[I]<=X[I+1] Then Inc(I)
                  Else C:=False;
  V:=C
End;
Begin
  ClrScr;
  Write('Introduceti propozitia:');ReadLn(P);
  Cmax:='';
  While P<>'' Do Begin
                   L:=Pos(' ',P);
                   If L>0 Then Begin
                                 Cuv:=Copy(P,1,L-1);
                                 Delete(P,1,L)
                               End
                          Else Begin
                                 Cuv:=P;
                                 Delete(P,1,Length(P))
                               End;
   If V(Cuv) Then
             If Length(Cuv)>Length(Cmax) Then Cmax:=Cuv
                 End;
   If Cmax=’’ Then WriteLn('?')
              Else WriteLn(Cmax);
  ReadLn
End.
Problema  3. Problema lui Yang
     Micul chinez Yang a învăţat să numere cu ajutorul beţişoarelor. Într-o zi, supărat pe părinţi, acesta îşi rupe toate beţişoarele în două bucăţi. Ştim că iniţial ele aveau aceeaşi lungime şi că Yang a separat bucăţile de sus într-o grămadă şi cele de jos în altă grămadă, dar nu a păstrat ordinea în cadrul grămezilor.
     Scrieţi un program care să indice lungimea iniţială a beţişoarelor şi cum se grupează  bucăţile de sus cu cele de jos pentru a obţine beţişoarele iniţiale.
     Se cunoaşte numărul iniţial de beţe şi lungimile bucăţilor din cele două grămezi.
Input:            numărul iniţial de beţişoare  şi lungimile bucăţilor din cele două grămezi se citesc de la tastatură
Output:        Se afişează la ecran lungimea iniţială a beţişoarelor şi cum se grupează.
Exemplu:   Input:     N=4 şi grămezile 4 2 1 5  respectiv  5 3 2 6
Output:7
4 3
2 5
1 6
5 2
Rezolvare:
Algoritmul problemei:
Observăm, că lungimea beţişoarelor va fi egală cu suma dintre cea mai mare valoare dintr-o gramadă cu cea mai mică valoare din cealaltă grămadă. Utilizăm două tablouri unidimensionale pentru înregistrarea lungimii beţişoarelor. Ordonăm primul tablou crescăto, al doilea-descrescător  şi afişăm la ecran perechile de elemente din tablourile date ce se găsesc pe aceeaşi poziţie, care şi reprezintă 2 capete ale unuia şi aceluiaşi beţişor.
Programul în limbajul Pascal:
Program Betisoare;
Uses CRT;
Type Natural=0..MaxInt;
     Lin=Array[1..100] Of Natural;
Var A,B:Lin;
    N,I:Byte;
Procedure Citire;
Begin
  Write('Introduceti numarul de betisoare:');ReadLn(N);
  WriteLn('Introduceti lungimile betisoarelor din I gramada:');
  For I:=1 To N Do
      Begin
  Write('Lungimea[',I,']=');ReadLn(A[I])
      End;
  WriteLn('Introduceti lungimile betisoarelor din II gramada:');
  For I:=1 To N Do
      Begin
  Write('Lungimea[',I,']=');ReadLn(B[I])
      End
End;
Procedure SortCresc(N:Byte; Var X:Lin);
Var I,C:Natural;
    V:Boolean;
Begin
  V:=True;
  While V Do Begin
        V:=False;
  For I:=1 To N-1 Do
  If X[I]>X[I+1] Then Begin
                        V:=True;
                        C:=X[I]; X[I]:=X[I+1]; X[I+1]:=C
                      End
              End
End;
Procedure SortDescresc(N:Byte; Var X:Lin);
Var I,C:Natural;
    V:Boolean;
Begin
  V:=True;
  While V Do Begin
        V:=False;
  For I:=1 To N-1 Do
  If X[I]<X[I+1] Then Begin
                        V:=True;
                        C:=X[I]; X[I]:=X[I+1]; X[I+1]:=C
                      End
              End
End;
Begin
  ClrScr;
  Citire;
  SortCresc(N,A); SortDescresc(N,B);
  WriteLn(A[1]+B[1]);
  For I:=1 To N Do
      WriteLn(A[I],' ',B[I]);
  ReadLn
End.

Niciun comentariu:

Trimiteți un comentariu

Abonați-vă la: Postări (Atom)