Clasa a V-a lecția 22 - 20 ian 2015

From Algopedia
Revision as of 06:32, 3 February 2016 by Cristian (talk | contribs) (→‎Temă)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Tema - rezolvări

Rezolvări aici [1]

Lecţie

Probleme olimpiada pe şcoală - rezolvări

Problema cifre 4

Problema cifre 4 este o problemă de bazele informaticii. Ea necesită doar noţiuni introductive de algoritmi şi programare.

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, maxcf, max2cf, npp, cf, cf2;

  fin = fopen( "cifre4.in", "r" );
  fscanf( fin, "%d", &n ); // citire numar n
  fclose( fin );

  maxcf = n % 10;   // initializam cifra maxima cu ultima cifra a numarului
  npp = 0;          // numarul de cifre patrate perfecte este initial zero
  if ( maxcf == 0 || maxcf == 1 || maxcf == 4 || maxcf == 9 )
    npp++;          // doar cifrele 0, 1, 4 si 9 sint patrate perfecte
  max2cf = n % 100; // initializam numarul maxim de 2 cifre cu ultimele 2 cifre
  n /= 10;          // eliminam ultima cifra
  while ( n > 0 ) { // cita vreme mai avem cifre in n
    cf = n % 10;        // extragem ultima cifra in cf
    if ( cf > maxcf )   // o comparam cu maximul
      maxcf = cf;       // daca este mai mare, o retinem in maxim
    if ( cf == 0 || cf == 1 || cf == 4 || cf == 9 ) // cf este patrat perfect?
      npp++;            // daca da, adunam unu la contorul de patrate perfecte
    cf2 = n % 100;      // extragem numarul format din ultimele doua cifre
    if ( cf2 > max2cf ) // este mai mare decit maximul?
      max2cf = cf2;     // daca da, il retinem
    n/= 10;             // eliminam ultima cifra a numarului
  }

  fout = fopen( "cifre4.out", "w" );
  fprintf( fout, "%d\n%d\n%d\n", maxcf, npp, max2cf );
  fclose( fout );

  return 0;
}

Problema gondola

Problema gondola este o problemă cu secvenţe. Rezolvarea ei nu necesită vectori. Problema se poate rezolva în mai multe feluri. Voi prezenta mai jos o soluţie bazată pe memorarea ultimei înălţimi şi a ultimei diferenţe de înălţime între doi stîlpi consecutivi.

În primul rînd să observăm că toate înălţimile pe care le vom lua în calcul în rezolvare provin din suma a două secvenţe şi anume secvenţa originală de înălţimi plus secvenţa postamentelor, care are o regulă de generare:

stîlpi:     h0   h1   h2   h3   h4   h5 ...
postamente: 1    2    3    1    2    3 ...

înălţimi:   h0+1 h1+2 h2+3 h3+1 h4+2 h5+3 ...

Observăm că regula de generare a postamentelor este:

postamentul i: pi = 1 + i % 3

Punctul a

Primul punct este banal, el cere suma înălţimilor.

Punctul b

Şi al doilea punct este relativ simplu. Vom memora ultima înălţime, pentru a putea calcula diferenţa dintre înălţimea curentă şi ultima. Vom avea grijă că diferenţa poate fi în sens crescător sau descrescător.

Punctul c

La punctul c ni se cere să găsim maximul diferenţelor de diferenţe. De acee trebuie să memorăm ultima diferenţă, pe care o vom compara cu diferenţa curentă. La fel, vom avea grijă că această diferenţă poate fi în sens crescător sau descrescător.

Iată o soluţie posibilă:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, h1, h2, d1, d2, dd, maxd, maxdd;
  long long s;

  fin = fopen( "gondola.in", "r" );
  fscanf( fin, "%d", &n );   // numarul de stilpi
  fscanf( fin, "%lld", &s ); // citim prima inaltime direct in suma
  s++;                       // adunam inaltimea postamentului
  fscanf( fin, "%d", &h1 );  // citim a doua inaltime
  h1 += 2;                   // adunam postamentul
  if ( h1 > s )  // calculam prima diferenta de inaltime
    maxd = d1 = h1 - s;
  else
    maxd = d1 = s - h1;
  s += h1;       // adunam inaltimea la suma
  maxdd = 0;     // initial diferenta de diferente este zero
  // incepem sa citim stilpii, incepind cu al treilea (i=2)
  for ( i = 2; i < n; i++ ) {
    fscanf( fin, "%d", &h2 ); // citim inaltimea stilpului
    h2 = h2 + 1 + i % 3;      // adunam postamentul
    s += h2;
    if ( h2 > h1 )            // calculam diferenta curenta
      d2 = h2 - h1;
    else
      d2 = h1 - h2;
    if ( d2 > maxd )  // actualizam diferenta maxima
      maxd = d2;
    if ( d2 > d1 )    // calculam diferenta ultimelor doua diferente
      dd = d2 - d1;
    else
      dd = d1 - d2;
    if ( dd > maxdd ) // actualizam diferenta de diferente maxima
      maxdd = dd;
    h1 = h2; // memoram ultima inaltime
    d1 = d2; // memoram ultima diferenta
  }
  fclose( fin );

  fout = fopen( "gondola.out", "w" );
  fprintf ( fout, "%lld\n%d\n%d\n", s, maxd, maxdd );
  fclose( fout );

  return 0;
}

Temă

Atenţie: rezolvaţi problemele următoare folosind vectori de frecvenţă! Acesta este scopul temei.

Tema 22 clasa a 5a

Rezolvări aici [2]