Clasa a V-a lecția 16 - 06 dec 2019

From Algopedia
Jump to navigationJump to search

Anunțuri

Fără scheme logice

De acum înainte nu trebuie să mai faceți scheme logice. Ura! Atenție! Asta nu înseamnă că nu trebuie să gîndiți algoritmul înainte de a începe implementarea! Nu vă aruncați direct în Code::Blocks. Încercați mai întîi să vă ordonați gîndurile și să găsiți metoda de rezolvare. Abia cînd metoda de rezolvare este clară puteți să vă apucați de programul C.

Tema - comentarii

  • Teme nefăcute: nu vă faceți temele pe care le primiți. Poate că nu reușiți să punctați, nici o problemă. Însă vreau să văd că v-ați bătut capul cu ele. Orice încercare mă poate ajuta pe mine să vă dau sfaturi sau să înțeleg mai bine ce trebuie să repetăm. De asemenea, materia avansează. Dacă nu exersați și nu deprindeți ce studiem, mai târziu s-ar putea să fie prea târziu pentru unii dintre voi.
  • Nu citiți cu atenție textul problemei. Sau cel puțin așa lăsați impresia. Chiar dacă textul seamănă cu ceva ce am mai făcut, nu înseamnă că este identic și este o rezolvare anterioară. Vă grăbiți și apoi spuneți că nu înțelegeți de ce nu reușiți să punctați.
  • Pescuit: am mai discutat acest aspect. Pescuitul este trimiterea de multe surse la varena.ro cu scopul de a vedea dacă merge. Pentru a reuși trebuie să vă creați propriile teste la probleme, cel puțin trei, apoi să executați soluțiile în Code::Blocks pe aceste teste. Doar atunci cînd programul trece toate aceste teste, precum și exemplele din problemă, îl puteți trimite la varena.ro. Nu vă bateți joc! Atenție Andrei Grama.
  • Warnings: mulţi dintre voi aveţi avertismente de compilare, unele foarte grave, gen variabile neiniţializate. Vă rog să urmăriți mesajele din subsolul interfeței CodeBlocks, atunci când compilați programul, adică atunci când dați Build. Trebuie să aveți 0 warnings și 0 errors.
  • Variabile int: nu folosiţi altceva decît int. Nu vreau să văd long long sau alte minunății. Ele vor fi introduse la timpul lor. Atenție Andrei Grama.
  • Contor de la zero: v-am rugat ca buclele cu număr cunoscut de paşi (bucle for) să le executaţi cu contorul de la 0. Nu vreau să văd for ( i = 1; i <= n; i++ ) ci for ( i = 0; i < n; i++ ).

Tema lecția 14 – rezolvări

Concurs

Rezolvați problema concurs dată la OJI 2004 clasa a 5a.

Răspuns: nu voi detalia algoritmul, voi menționa doar că un punct unde puteați ușor să vă păcăliți este faptul că atunci cînd se cere cîți copii erau din aceeași școală cu primul copil trebuia să verificați că atît școlile cît și orașele sînt identice, deoarece pot exista școli cu același număr în orașe diferite.

Iată o soluție posibilă:

Concurs OJI 2004 clasa a 5a
#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, h, c, i, premiant, orash, scoalah, proras, prscoala;

  fin = fopen( "concurs.in", "r" );
  fscanf( fin, "%d%d", &h, &n );
  orash = h / 100;       // extragem orasul lui h
  scoalah = h / 10 % 10; // si scoala lui h
  premiant = 0;
  proras = 0;
  prscoala = 0;
  for ( i = 0; i < n; i ++ ) {
    fscanf( fin, "%d", &c );
    if ( h == c )
      premiant = 1;
    if ( c / 100 == orash ) {       // e din acelasi oras cu h
      proras++;
      if ( c / 10 % 10 == scoalah ) // e din aceeasi scoala cu h
        prscoala++;
    }
  }
  fclose( fin );

  fout = fopen( "concurs.out", "w" );
  if ( premiant == 1 )
    fprintf( fout, "DA\n" );
  else
    fprintf( fout, "NU\n" );
  fprintf( fout, "%d\n%d\n", proras, prscoala );
  fclose( fout );

  return 0;
}

Subcresc

Rezolvați problema subsecvență crescătoare

Răspuns: problema este foarte asemănătoare cu găsirea celei mai lungi subsecvențe de numere identice unul după altul în secvență. Tot ce vom schimba este semnul '=' în '<' și vom avea grijă să-l trecem pe b în a întotdeauna, la finalul buclei.

Iată o soluție posibilă:

Subsecvență crescătoare
#include <stdio.h>

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

  fin = fopen( "subcresc.in", "r" );
  fscanf( fin, "%d", &n );
  fscanf( fin, "%d", &a );
  lmax = 1;
  l = 1;
  for ( i = 1; i < n; i++ ) {
    fscanf( fin, "%d", &b );
    if ( b >= a ) {
      l++;
      if ( l > lmax )
        lmax = l;
    } else {
      l = 1;
    }
    a = b;
  }
  fclose( fin );

  fout = fopen( "subcresc.out", "w" );
  fprintf( fout, "%d\n", lmax );
  fclose( fout );
  return 0;
}

Problema de logică

Zece oameni sînt așezați în șir, unul în spatele altuia. Li se așează pe cap cîte o tichie neagră sau albă. Fiecare om poate să vadă tichiile oamenilor din fața lui. Începînd cu ultimul, cel mai din spate, oamenii strigă pe rînd "alb" sau "negru". După ce strigă, ei sînt scoși din rînd și duși într-o cameră unde sînt eliberați, dacă și-au ghicit culoarea tichiei, sau omorîți în caz contrar. Un om poate să audă ce au strigat, pe rînd oamenii din spatele său. Oamenii nu au voie să comunice în nici un alt fel, cum ar fi să tușească, să se atingă, etc, sau vor fi omorîți toți! Ei au voie să se sfătuiască înainte să fie așezați, pentru a stabili strategia prin care să salveze cîți mai mulți dintre ei. Voi trebuie să stabiliți ce strategie aleg oamenii și care este numărul maxim de oameni pe care îi puteți salva. Exemplu: să presupunem că oamenii aleg următoarea strategie: ei vor striga, pe rînd, "alb", cu toții. În acest caz vor supraviețui 5 oameni, pe medie.

  • O soluție în care salvăm 7.5 oameni pe medie este să cuplăm oamenii doi cîte doi, cel din spate strigînd culoarea celui din față, iar cel din față repetînd ce aude. În felul acesta salvăm sigur 5 oameni și pe medie 2.5 din ceilalți 5.
  • Putem încerca să generalizăm soluția anterioară: cuplăm oamenii cîte trei, cel din spate strigînd "alb" dacă ceilalți doi au culori identice, sau negru în caz contrar. Cel din fața lui va vedea ce culoare are cel rămas și va ști ce culoare are el. Omul cel mai din față va auzi ce au strigat cei din spatele lui și va deduce și el ce culoare are. Într-un grup de trei oameni doi își vor ghici culorile iar unul va avea șanse jumate/jumate. Formăm trei grupuri de cîte trei oameni, iar unul, care rămîne singur, va spune la întîmplare. În acest fel salvăm sigur 6 oameni și pe medie 2 din ceilalți 4.
  • Soluția optimă este următoarea: omul 10 se uită la ceilalți 9 și anunță negru dacă vede un număr impar de tichii negre, sau alb în caz contrar. Omul 9 numără tichiile negre din fața lui. Dacă paritatea numărului de tichii negre este aceeași cu paritatea anunțată de 10 înseamnă că el are tichie albă, altfel are neagră, deci știe ce să anunțe. Omul 8 face la fel, doar că adună la tichiile negre văzute și cîte tichii negre au fost în spatele lui. Toți oamenii își vor ghici tichiile, mai puțin 10 care are șanse jumate-jumate. Pe medie vom salva 9.5 oameni.


Concurs - rezolvare

Problema vrăji

Problema vrăji a fost dată la OJI 2006 clasa a 5-a.

Răspuns: această problemă pare la prima vedere foarte complicată. În realitate ea este banală. Impresia de grea este lăsată de lungimea textului și de formularea ei întortocheată. Să o traducem în limbaj informatic: problema cere ca, dîndu-se n perechi de numere să se calculeze produsul fiecărei perechi, apoi să se calculeze maximul din numerele rezultate precum si cel mai mare divizor comun al acestor numere.

Iată o rezolvare posibilă (voi prezenta numai programul C, las schema logică ca temă):

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, i, max, cmmdc, p, v, ob, r;

  fin = fopen( "vraji.in", "r" );
  fscanf( fin, "%d%d%d", &n, &p, &v );
  max = p * v;
  cmmdc = max;
  for ( i = 1; i < n; i++ ) {
    fscanf( fin, "%d%d", &p, &v );
    ob = p * v; // numarul de obiecte aduse intr-o ora este puterea ori viteza
    if ( ob > max ) // calculam maximul numarului de obiecte
      max = ob;
    while ( ob > 0 ) { // numarul cutiilor este cmmdc al tuturor numerelor
      r = cmmdc % ob;
      cmmdc = ob;
      ob = r;
    }
  }
  fclose( fin );

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

  return 0;
}


Tema lecția 15 – rezolvări

Cabina

Problema cabina dată la OJI 2007 clasa a 5a.

Răspuns: problema este structurată pe trei niveluri:

  • Pentru a răspunde cîți oameni se urcă în cabină avem nevoie să ne uităm la ultima pereche din secvență.
  • Pentru a calcula consumul cabinei avem nevoie să ne uităm la ultimele două perechi din secvență, pentru a calcula diferența de înălțime.
  • Pentru a găsi stațiile speciale avem nevoie să ne uitam la trei perechi consecutive, pentru a spune dacă înălțimea din mijloc este fie mai mare decît celelalte două, fie mai mică.

O idee de rezolvare este să memorăm ultimele două perechi, iar cînd vine cea curentă vom calcula oamenii la zi bazat doar pe ea, consumul între stații bazat pe ea si perechea anterioară și, în final, dacă stația anterioară a fost specială, comparînd-o cu cea din-naintea ei și cu cea actuală. Iată o rezolvare bazată pe aceste idei (voi prezenta numai programul C, las schema logică ca temă):

#include <stdio.h>

int main () {
  FILE *in, *out;
  int n, i, a1, a2, a3, b, nro, l, spec;

  in = fopen( "cabina.in", "r" );
  fscanf( in, "%d", &n );
  fscanf( in, "%d%d", &a1, &nro ); // citim separat prima statie
  fscanf( in, "%d%d", &a2, &b );   // tratam separat statia 2
  nro = nro + b;
  if ( a2 > a1 )
    l = 3 * (a2 - a1);  // daca urca adunam 3 * diferenta
  else
    l = a1 - a2;        // daca coboara adunam diferenta
  spec = 0;
  for ( i = 2; i < n; i++ ) {
    fscanf( in, "%d%d", &a3, &b );
    nro = nro + b;
    if ( a3 > a2 )
      l = l + 3 * (a3 - a2);  // daca urca adunam 3 * diferenta
    else
      l = l + a2 - a3;        // daca coboara adunam diferenta
    if ( (a1 < a2 && a2 > a3) || (a1 > a2 && a2 < a3) )
      spec++; // am gasit o statie speciala
    a1 = a2;  // transferam inaltimile una intr-alta
    a2 = a3;
  }
  fclose( in );

  out = fopen("cabina.out","w" );
  fprintf( out, "%d\n%d\n%d\n", nro, l, spec );
  fclose( out );

  return 0;
}

Cifre comune

Problema cifre comune.

Răspuns: ni se cere să spunem numărul de cifre comune celor două numere, să le spunem m și n. O primă idee ar fi să extragem pe rînd cifrele lui m și să mergem în n și să le eliminăm. La eliminare contorizăm o cifră comună.

Acest algoritm este destul de greu de implementat. Vă propun unul ceva mai simplu: știm că sînt numai zece cifre cu totul. Putem, deci, să alegem o cifră, să spunem 0, și să numărăm de cîte ori apare în fiecare din numerele m și n. Minimul dintre cele două numere de apariție este chiar numărul de cifre 0 comune. Putem relua acest pas pentru fiecare cifră, adunînd numărul de cifre comune găsite.

Iată programul bazat pe această soluție (voi prezenta numai programul C, las schema logică ca temă):

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int m, n, mc, nc, cf, ncfm, ncfn, cfcom;

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

  cfcom = 0; // la inceput avem zero cifre comune
  for ( cf = 0; cf < 10; cf++ ) { // incercam fiecare cifra
    // calculam de cite ori apare cf in numarul m
    ncfm = 0;
    mc = m;
    while ( mc > 0 ) { 
      if ( mc % 10 == cf )
        ncfm++;
      mc = mc / 10;
    }

    // calculam de cite ori apare cf in numarul n
    ncfn = 0;
    nc = n;
    while ( nc > 0 ) { 
      if ( nc % 10 == cf )
        ncfn++;
      nc = nc / 10;
    }

    // cifra cf apare in ambele numere de un numar de ori egal cu minimul
    // dintre numarul de aparitii
    if ( ncfm < ncfn )
      cfcom = cfcom + ncfm;
    else
      cfcom = cfcom + ncfn;
  }

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

  return 0;
}

Lecție

Din motive tehnice, filmul lecției nu putut fi recuperat cu succes.

Concurs: o întrecere colegială. Simulăm un concurs, dar cu reguli relaxate. Mai exact, dupa ce vă străduiți la maxim și simțiți că v-ați împotmolit aveți voie:

  • să puneți întrebări
  • să cereți ajutorul instructorului

Iată concursul: Concurs clasa a 5-a

Felicitări primilor clasați!

Temă

Tema 16: să se rezolve următoarele probleme (program C trimis la vianuarena):

  • seif2 (concurs simulare IQ Academy 2017 clasa a 5a)
  • case (OJI 2006 clasa a 5a)
  • ucif (OJI 2005 clasa a 5a)

Cei care ați trimis deja rezolvări la concurs aveți grijă să le retrimiteți în cadrul temei.

Rezolvări aici [1]