Clasa a V-a lecția 19 - 10 ian 2020

From Algopedia
Jump to navigationJump to search

Rezolvări lecție 17

Problema regele

Problema regele cere să rezolvaţi celebra problemă de logică a găsirii grămezii de monede mai uşoare cu un gram printr-o singură cîntărire. Deşi enunţul este stufos, ea este în realitate o problemă simplă. Din numărul de grame g putem calcula uşor numărul de grame lipsă la cîntar ca fiind

g = n * (n+1) / 2 * 10 - g; // numarul de grame lipsa

deoarece dacă toate monedele ar avea zece grame ele ar cîntări de zece ori suma lui Gauss pînă la n.

În concluzie vom căuta fişicul din care lipsesc g grame, adică fişicul în care scăzînd monedele rămase din n obţinem g. Programul care caută un număr într-o secvenţă a fost făcut în lecţia 12, cu diferenţa că aici este mai simplu, deoarece ştim că numărul apare sigur în secvenţă. Poziţia pe care apare acest număr este char numărul grămezii ce trebuie afişat.

Iată un program posibil:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, g, i, a;

  fin = fopen( "regele.in", "r" );
  fscanf( fin, "%d%d", &n, &g );
  g = n * (n+1) / 2 * 10 - g; // numarul de grame lipsa
  i = 1;
  fscanf( fin, "%d", &a );
  while ( n - a != g ) {
    fscanf( fin, "%d", &a );
    i++;
  }
  fclose( fin );

  fout = fopen( "regele.out", "w" );
  fprintf( fout, "%d\n", i );
  fclose( fout );

  return 0;
}

Problema plaja 2

Problema Plaja 2 dată la test.

Răspuns: tradusă în limbaj informatic ni se cere să calculăm cel mai mare divizor comun al celor n numere. Vom proceda astfel: vom porni cu primul număr din secvență ca cmmdc. Apoi citim pe rînd numerele secvenţei în bat şi calculăm cel mai mare divizor comun între cmmdc şi bat.

Iată programul:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, bat, cmmdc, r;

  fin = fopen( "plaja2.in", "r" );
  fscanf( fin, "%d%d", &n, &cmmdc );
  for ( i = 1; i < n; i++ ) {
    fscanf( fin, "%d", &bat );
    while ( bat > 0 ) {
      r = cmmdc % bat;
      cmmdc = bat;
      bat = r;
    }
  }
  fclose( fin );

  fout = fopen( "plaja2.out", "w" );
  fprintf( fout, "%d\n", cmmdc );
  fclose( fout );

  return 0;
}

Problema gardul

Problema gardul a fost dată la OJI 2003 clasa a 6a.

Forța brută

Să observăm că din enunț rezultă că pentru ca o scîndură să fie vopsită în roșu trebuie ca numărul ei de ordine (idicele ei) să fie divizibil cu p. De asemenea, pentru ca o scîndură să fie vopsită în albastru trebuie ca numărul ei de ordine să fie divizibil cu q. Iar pentru ca o scîndură să fie vopsită violet trebuie ca ea să fie vopsită și roșu și albastru, deci numărul ei de ordine se va împărți și la p și la q.

Drept care o primă idee este să folosim un contor cu care sa numărăm scîndurile. Pentru fiecare valoare a contorului vom testa dacă ea este divizibilă cu p sauq sau ambele și în funcție de aceasta vom aduna unu la numărul de scînduri vopsite roșu, sau albastru, sau violet.

Iată un program care se bazează pe această idee:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, p, q, i, alb, rosu, albastru, violet;

  fin = fopen( "gardul.in", "r" );
  fscanf( fin, "%d%d%d", &n, &p, &q );
  fclose( fin );

  alb = rosu = albastru = violet = 0;
  for ( i = 1; i <= n; i++ ) {
    if ( i % p == 0 )
      if ( i % q == 0 )
        violet++;
      else
        rosu++;
    else if ( i % q == 0 )
      albastru++;
    else
      alb++;
  }

  fout = fopen( "gardul.out", "w" );
  fprintf( fout, "%d\n%d\n%d\n%d\n", alb, rosu, albastru, violet );
  fclose( fout );

  return 0;
}

Rezolvarea elegantă

Rezolvarea anterioară va trece prin 100 000 de numere. Dacă n ar fi fost mai mare, sa zicem un miliard, ar fi trecut printr-un miliard de numere și ar fi depășit timpul. Este o rezolvare foarte ineficientă. Odată ce am ajuns în clasa a 5a putem găsi o soluție matematică, care să calculeze direct numerele de scînduri cerute.

Care este numărul de scînduri vopsite cu roșu, indiferent că vor fi vopsite și cu albastru? Este numărul de numere divizibile cu p. Am făcut această problemă în trecut, numărul este n / p. Similar, numărul de scînduri vopsite cu albastru este n / q. Care este numărul de scînduri vopsite în violet? Deoarece numărul unei scînduri vopsite violet trebuie să se dividă și cu p și cu q rezultă că el trebuie să dividă cel mai mic multiplu comun al lui p și q. Altfel spus, dacă ne imaginăm segmente de lungime p și q puse cap la cap pe axa numerelor naturale, cînd se vor întîlni capetele segmentelor? La punctul cmmmc, apoi 2 cmmmc, apoi 3 cmmmc și așa mai departe. De aceea numărul de scînduri vopsite violet va fi n / cmmmc(p, q).

Pentru a calcula numărul de scînduri vopsite doar roșu va trebui să scădem numărul de scînduri vopsite violet. La fel și pentru albastru. Scîndurile nevopsite se calculează scăzînd din n numărul de scînduri roșii, albastre și violet.

Această soluție matematică va face mult mai puține calcule, deoarece cmmmc se calculează rapid cu algoritmul lui Euclid. Iată un program bazat pe această idee:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, p, q, qc, r, cmmdc, cmmmc, alb, rosu, albastru, violet;

  fin = fopen( "gardul.in", "r" );
  fscanf( fin, "%d%d%d", &n, &p, &q );
  fclose( fin );

  // calcul cmmdc
  cmmdc = p;
  qc = q;
  while ( qc != 0 ) {
    r = cmmdc % qc;
    cmmdc = qc;
    qc = r;
  }
  cmmmc = p * q / cmmdc; // cmmmc
  violet = n / cmmmc;                 // calcul numar de scinduri violet
  rosu = n / p - violet;              // calcul numar de scinduri rosii
  albastru = n / q - violet;          // calcul numar de scinduri albastre
  alb = n - violet - rosu - albastru; // calcul numar de scinduri nevopsite

  fout = fopen( "gardul.out", "w" );
  fprintf( fout, "%d\n%d\n%d\n%d\n", alb, rosu, albastru, violet );
  fclose( fout );

  return 0;
}


Rezolvări lecție 18

Problema cursa Formula 1

Problema Cursa Formula 1 este o problemă simplă ca și rezolvare însă are un text lung și poate fi relativ greu de parcurs, dacă nu sunteți atenți. Singura particularitate asupra problemei este că nu citiți un șir de numere, citiți mai multe rânduri.

Iată o posibilă rezolvare:

#include <stdio.h>
#include <stdlib.h>

int main()
{
    FILE *fin, *fout;
    int n, x, y, ai, bi, ci, i, timp, min, nmin;

    fin = fopen( "cursaf1.in", "r" );
    fscanf(fin, "%d%d%d" , &n , &x , &y );
    min = 22000001; //această valoare este calculată din 
                    //limitele date în cerința problemei

    for( i=0 ; i<n ; i++ ){
        fscanf( fin , "%d%d%d" , &ai , &bi , &ci ); //citim toate valorile de pe un rând
        timp = x * ai + 2 * bi * y + bi * ci ;
        if( min > timp ) {
            min = timp;
            nmin = i;
        }
    }

    fclose(fin);
    fout = fopen( "cursaf1.out" , "w" );
    fprintf( fout, "%d %d" , nmin+1 , min );
    fclose( fout );

    return 0;
}

Problema centru prim

Problema centru prim este o problemă banală care v-a pus foarte multe probleme. Trebuie să tăiați prima și ultima cifră a numărului și apoi să testați că este prim. Toate aceste operații au fost făcute la cerc. Ultima cifră se elimină prin împărțire la zece, iar prima cifră prin calcul restului împărțirii la cea mai mare putere a lui 10 care este mai mică sau egală cu numărul. Testarea unui număr prim a fost făcută la cerc.

Iată o soluție:

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, p10, d;

  fin = fopen( "centruprim.in", "r" );
  fscanf( fin, "%d", &n );
  fclose( fin );

  // calculam cea mai mare putere a lui zece care incape in n
  p10 = 1;
  while ( p10 <= n )
    p10 = p10 * 10;
  p10 = p10 / 10;

  n = n % p10; // taiem ultima cifra
  n = n / 10; // taiem prima cifra

  // testam daca n este prim
  d = 2;
  while ( d * d <= n && n % d > 0 )
    d++;

  fout = fopen( "centruprim.out", "w" );
  if ( d * d > n && n > 1 )
    fprintf( fout, "1\n" ); // n este prim
  else
    fprintf( fout, "0\n" ); // n nu este prim
  fclose( fout );

  return 0;
}

Problema pădure

Problema pădure cere să calculați subsecvența de lungime maximă cu proprietatea că oricare două numere consecutive în secvență au un divizor comun (nu sunt prime între ele).

Problema este relativ banală, fiind similară cu problemele număr maxim de numere identice din secvență și Subcresc. Pentru a o rezolva vom memora ultimul număr din secvență, apoi vom testa dacă are în comun un divizor cu numărul curent. Dacă are, vom mări secvența cu unu, altfel vom reseta lungimea secvenței la unu.

Cum testăm dacă două numere au un divizor comun? Cea mai eficientă metodă este să calculăm cel mai mare divizor comun cu algoritmul lui Euclid.

Iată un program bazat pe aceste idei:

// Cristian Francu on 2017-11-20
// solutie log n prin cmmdc
#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, x, y, l, lmax, a, b, r;

  fin = fopen( "padure.in", "r" );
  fscanf( fin, "%d%d", &n, &x );
  lmax = 1;
  l = 1; // secventa curenta este x, are lungime 1
  for ( i = 1; i < n; i++ ) {
    fscanf( fin, "%d", &y );
    // calculam cmmdc intre x si y, fara a distruge x si y
    a = x;
    b = y;
    while ( b > 0 ) {
      r = a % b;
      a = b;
      b = r;
    }
    // daca cmmdc este diferit de 1, adaugam y la secventa curenta
    if ( a > 1 ) {
      l++;
      if ( l > lmax ) // secventa curenta e mai lunga decit cea maxima?
        lmax = l;
    } else // altfel incheiem secventa curenta si incepem una noua, cu y
      l = 1;
    x = y;
  }
  fclose( fin );

  fout = fopen( "padure.out", "w" );
  fprintf( fout, "%d\n", lmax );
  fclose( fout );

  return 0;
}

Temă

Tema constă într-o singură problemă să ne intrăm din nou în ritm.

  • Test (OJI 2007, clasa a 5a)

Rezolvări aici [1]