Clasa a V-a lecția 43 - 7 iun 2018

From Algopedia
Jump to navigationJump to search

Tema - comentarii

Probleme generale

  • Nu închideți fișiere (rămășițe freopen).
  • Declarați variabile după ce deschideți fișierele (rămășițe freopen).
  • Deoarece aveți nevoie de o variabilă de tip long long le declarați pe toate de tip long long, să fiți siguri. Chiar și pe cele de ciclu, variabila i.
  • Aveți mari probleme în a vă da seama ce înmulțiri vor da depășire pe întreg, trebuie să exersați asta.
  • În continuare nu vă creați teste, deși știți că veți fi penalizați.
  • În continuare unii din voi rezolvați temele fără a aplica ceea ce ați învățat la lecție, deși problemele de la temă sînt aplicații ale noțiunilor din lecție. Drept care scrieți cod complicat, sau care nu funcționează, cum ați făcut la problema încâlceală.
  • În continuare aveți avertismente serioase de compilare pe care le ignorați.

Problema puteri2

Nu aveați nevoie de al doilea vector. Foarte mulți dintre voi l-ați folosit. Unii din voi au declarat toate variabilele de tip long long, deși doar una era utilă. O parte din voi au mers mai departe: au declarat toate variabilele long long mai puțin vectorul a[], apoi ați folosit elementele lui pentru a calcula a[i]*a[i], ceea ce evident a dus la depășire.

Analiză 1

Să analizăm următorul program: (Victor Nicola 10p)

#include <stdio.h>
#define N 10000
#define IMP 100019

unsigned long long a[N], b[N];

int main() {
  FILE *fin, *fout;
  int n, i;
  unsigned long long rez, r;
  fin = fopen( "puteri2.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i ++ )
    fscanf( fin, "%llu", &a[i] );
  for ( i = 0; i < n; i ++ )
    fscanf( fin, "%llu", &b[i] );
  fclose( fin );

  rez = 0;
  for ( i = 0; i < n; i ++ ) {
    r = 1;
    while ( b[i] ) {
      if ( b[i] % 2 == 1 )
        r = ( r * a[i] ) % IMP;
      a[i] = a[i] * a[i];
      b[i] /= 2;
    }
    rez += r;
  }

  fout = fopen( "puteri2.out", "w" );
  fprintf( fout, "%llu\n", rez % IMP );
  fclose( fout );
  return 0;
}

Răspunsuri

  • Programul este corect ca algoritm.
  • Memorează șirul b inutil.
  • unsigned long long?
  • Depășire la a[i] = a[i] * a[i];

Analiză 2

Să analizăm următorul program: (Karina Dumitrescu 10p)

#include <stdio.h>

int main(){
    FILE *fin=fopen("puteri2.in", "r");
    FILE *fout=fopen("puteri2.out", "w");
    long long n, i, s, p;
    fscanf(fin, "%lld", &n);
    int a[n], b[n];
    for(i=0; i<n; i++)
        fscanf(fin, "%lld", &a[i]);
    for(i=0; i<n; i++)
        fscanf(fin, "%lld", &b[i]);
    s=0;
    for(i=0; i<n; i++){
        p=1;
        while(b[i]>0){
            if(b[i]%2==1)
                p=(p*a[i])%100019;
        a[i]=(a[i]*a[i])%100019;
        b[i]=b[i]/2;
        }
        s=(s+p)%100019;
    }
    fprintf(fout, "%lld", s);
    return 0;
}

Răspunsuri

  • Deschide fișiere și apoi declară variabile (rămășiță freopen).
  • Nu închide fișiere (rămășiță freopen).
  • Declară toate variabilele long long, inutil. Inclusiv i, variabila de for.
  • Declară vectorii în mijlocul programului.
  • Declară vectorii în main, în loc de deasupra lui main.
  • Citește vectori de tip int cu %lld (deci ignoră avertismentele de compilare)
  • Depășire la a[i]=(a[i]*a[i])%100019;

Analiză 3

Să analizăm următorul program: (Alexandru Nicu 100p)

#include <stdio.h>
#include <stdlib.h>
int v1[10001],v2[10001];
int main() {
    FILE *fin,*fout;
    fin=fopen("puteri2.in","r");
    fout=fopen("puteri2.out","w");
    long long p,b,a,n,i,s;
    fscanf(fin,"%lld",&n);
    for(i=1; i<=n; i++) {
        fscanf(fin,"%d",&v1[i]);
    }
    for(i=1; i<=n; i++) {
        fscanf(fin,"%d",&v2[i]);
    }
    s=0;
    for(i=1; i<=n; i++) {
        p=1;
        a=v1[i];
        b=v2[i];
        while(b>0) {
            p=p%100019;
            if(b%2==1)
                p=p*a;
            a=(a*a)%100019;
            b=b/2;
        }
        s+=p;
        s%=100019;
    }
    fprintf(fout,"%lld",s);
    return 0;
}

Răspunsuri

  • Folosește inutil un vector pentru a păstra șirul b.
  • Declară vectorii cu un element în plus, pentru a putea folosi indecși începînd cu 1.
  • Deschide fișiere, apoi declară variabile (rămășițe freopen).
  • Nu închide fișiere (rămășițe freopen).
  • Declară toate variabilele de tip long long, inutil, inclusiv variabila de ciclu for.
  • Toate ciclurile for sînt de la 1 la n, nu de la 0 la n-1.
  • Alex: ai venit un an de zile la IQ Academy degeaba. Nu ai reținut bazele.

Problema incalceala

Unii din voi ați scris cod complet diferit de cel din lecție, uitînd să testați pe parcurs dacă s < 0 (ați testat doar la final că s == 0). Apoi, după ce am adăugat teste la problemă, ați modificat programul. Alții v-ați oprit corect atunci cînd ați detectat că s < 0, dar ați uitat să citiți restul liniei, pînă la \n pentru a trece la următoarea linie.

Analiză 1

Să analizăm următorul program: (Luca Ilie 40p)

#include <stdio.h>
#include <string.h>
int main()
{
    FILE*fin,*fout;
    fin=fopen("incalceala.in","r");
    fout=fopen("incalceala.out","w");
    char c='0';
    int s=0,i,ok=0;
    for(i=0; i<5; i++)
    {
        while(c!='\n' && s>=0)
        {
            c=fgetc(fin);
            if(c=='(')
                s++;
            else if(c==')')
                s--;
            if(s<0)
                ok=1;
        }
        if(s!=0)
            ok=1;
        if(ok==0)
            fprintf(fout,"1\n");
        else
            fprintf(fout,"0\n");
        c=fgetc(fin);
        c='0';
        s=0;
        ok=0;
    }
    fclose( fin );
    fclose( fout );
    return 0;
}

Răspunsuri

  • Declară variabile în interiorul programului.
  • Ciclul while testează egalitatea lui c cu \n, apoi prima instrucțiune în ciclu citește c
  • Folosește stegulețul ok inutil, deoarece oricum testează în ciclu dacă s >= 0
  • Inițializarea variabilelor s și ok se face după folosirea lor, în loc de înainte, în ciclu. Aceasta duce la duplicare de cod, o dublă inițializare.
  • Tipărirea se putea face mai elegant tipărind 1-ok, sau, și mai simplu, inversînd valorile lui ok (1 pentru bun, 0 pentru incorect)
  • De ce nu funcționează, totuși? Deoarece el se oprește la prima eroare în expresie, dar nu citește "în gol" restul liniei.

Analiză 2

Să analizăm următorul program: (Andreea Chivu 100p)

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

int main()
{
    FILE*fin,*fout;
    int i,s;
    char c;

    fin=fopen("incalceala.in","r");
    fout=fopen("incalceala.out","w");

    for(i=0;i<5;i++)
    {
        s=0;
        c=fgetc(fin);
        while(c!='\n' && s>=0)
        {
            if(c=='(')
               s++;
            else if (c==')')
                s--;
            c=fgetc(fin);
        }

        while(c!='\n')
            c=fgetc(fin);

        if (s==0)
            fprintf(fout,"%d\n",1);
        else
            fprintf(fout,"%d\n",0);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}

Răspunsuri

  • Totul este perfect. Da, se poate. Bravo!

Analiză 3

Să analizăm următorul program: (Aexandru Hossu 100p)

#include <stdio.h>

#define SIZE 5

int main() {
  FILE *fin, *fout;
  int sum, cont;
  char ch;
  int i;

  fin = fopen ("incalceala.in", "r");

  fout = fopen ("incalceala.out", "w");

  ch = fgetc (fin);
  for (i = 0; i < SIZE; i++) {
    cont = 0;
    sum = 0;
    while (ch != '\n' && ch != EOF) {
      if (ch == '(')
        sum++;
      else if (ch == ')')
        sum--;
      if (sum < 0)
        cont = 1;
      ch = fgetc (fin);
    }
    if ((cont == 1 || sum != 0))
      fprintf (fout, "0\n");
    else if (sum == 0)
      fprintf (fout, "1\n");
    ch = fgetc (fin);
  }

  fclose (fin);

  fclose (fout);

  return 0;
}

Răspunsuri

  • Folosește o constantă pentru numărul testelor. Foarte frumos!
  • Testează inutil EOF, știm că la final se află \n
  • Testează toate caracterele unei linii la egalitatea cu paranteze, chiar și după ce știm că expresia este incorectă.
  • Are un test inutil else if (sum == 0). Condiția este în mod obligatoriu adevărată.
  • Citirea inițială a lui ch se face la final de ciclu for, în loc de început. Aceasta duce la duplicare de cod, deoarece citirea trebuie făcută atît înainte de for cît și în for.

Problema abc1

Îi mulțumesc lui Remus pentru soluția lui. Ea mi-a arătat că testele erau incomplete. Le-am schimbat, drept care s-ar putea ca scorurile unora din voi să se fi micșorat. Motivul pentru aceasta este pentru că unii din voi aveați calcule cu depășiri, dar care nu influențau rezultatul. În urma noilor teste îl influențează. Foarte mulți din voi ați dat soluții ciudate, greoaie, încîlcite. Aveați o armă puternică: exponențierea rapidă. Nu ați folosit-o corect. Ar fi bine să recitiți subiectul la algopedia. Voicu a folosit unsigned int pentru a evita problema dată de depășire. El a luat 100p, dar faptul că scrie un program care depășește întregul, fără a-și da seama, nu este în regulă.

Analiză 1

Să analizăm următorul program: (Tudor Mușat 100p)

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

int main() {
    FILE *fin = fopen( "abc1.in", "r" ), *fout = fopen( "abc1.out", "w" );

    int p, a, c;
    long long b;
    fscanf( fin, "%d%lld%d", &a, &b, &c );
    b %= 4;
    a %= 10;
    p = 1;
    while ( c > 0 ) {
        if ( c % 2 == 1 )
            p = p % 4 * b;
        b = b * b % 4;
        c /= 2;
    }
    p %= 4;
    if ( p == 1 ) {
        fprintf( fout, "%d", a );
    } else if ( p == 2 )
        fprintf( fout, "%d", a * a % 10 );
    else if ( p == 3 )
        fprintf( fout, "%d", a * a * a % 10 );
    else
        fprintf( fout, "%d", a * a * a * a % 10 );
    return 0;
}

Răspunsuri

  • Nu închide fișiere (rămășiță freopen).
  • Declară variabile după instrucțiunile de deschidere de fișiere (rămășiță freopen).
  • Are depășiri la p = p % 4 * b;
  • Variabila b este de tip long long inutil, putea să fie int.
  • Ultima parte se putea face mult mai simplu într-un for

Analiză 2

Să analizăm următorul program: (Remus Rughiniș 40p)

#include <stdio.h>
#include <stdlib.h>
  int uc[10]={1,2,4,4,2,1,1,4,4,2};
int main(){
  FILE *fin, *fout;
  int a,b,c,i,s;
  long long n;
  fin=fopen("abc1.in","r");
  fscanf(fin,"%d%d%d",&a,&b,&c);
  fclose(fin);
  n=1;
  a=a%10;
  while(c>0){
    if(c%2==1)
      n*=b;
    b=b*b;
    c=c/2;
  }
  n=n%uc[a];
  if(n==0)
    n=uc[a];
  i=1;
  s=a;
  while(i<n){
    s=s*a;
    i++;
  }
  fout=fopen("abc1.out","w");
  fprintf(fout,"%d",s%10);
  fclose(fout);
  return 0;
}

Răspunsuri

Analiză 3

Să analizăm următorul program: (Armin Asgari 100p)

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

int main() {
    FILE *fin , *fout;
    fin = fopen ( "abc1.in" , "r" );
    fout = fopen ( "abc1.out" , "w" );
    int x , b , c , uc;
    long long put , a , n;
    fscanf ( fin , "%d%d%d" , &x , &b , &c );
    n = ( long long ) c;
    a = ( long long ) b;
    put = 1;
    while ( n ) {
        if ( n % 2 == 1 )
            put = ( long long ) ( put * a ) % 4;
        a = ( long long ) ( a * a ) % 4;
        n = n / 2;
    }
    uc = x % 10;
    if ( put == 0 )
        fprintf ( fout , "%d" , ( uc * uc * uc * uc ) % 10 );
    else if ( put == 1 )
        fprintf ( fout , "%d" , uc );
    else if ( put == 2 )
        fprintf ( fout , "%d" , ( uc * uc ) % 10 );
    else if ( put == 3 )
        fprintf ( fout , "%d" , ( uc * uc * uc ) % 10 );
    fclose ( fin );
    fclose ( fout );
    return 0;
}

Răspunsuri

Tema - rezolvări

Rezolvări aici [1]

Lecție

<html5media height="720" width="1280">https://www.algopedia.ro/video/2017-2018/2018-06-07-lectie-info-43-720p.mp4</html5media>

Elementul majoritar

Majoritar: dat un vector cu n elemente să se spună dacă conține un element majoritar. Un element majoritar este un element care apare de cel puțin n/2 + 1 ori. Încercați să dați o soluție mai bună decît sortarea.

Răspuns: dacă există un element majoritar, maj, rezultă că fiecare din elementele vectorului diferite de maj poate fi cuplat cu un element egal cu maj astfel încît după ce toate cuplările au fost făcute să rămînă cel puțin un element maj necuplat. Ideea de rezolvare este să simulăm această cuplare. Vom porni cu primul element al vectorului ca un candidat de element majoritar. Parcurgem elementele vectorului ținînd minte cîți candidați necuplați avem. De fiecare dată cînd dăm peste un element egal cu candidatul incrementăm numărul de elemente necuplate. Cînd dăm peste un element diferit scădem numărul de elemente necuplate. Dacă la un moment dat vom avea zero candidați necuplați și mai vine un element diferit de candidat rezultă că am eliminat din vector un număr egal de candidați și non-candidați, drept pentru care putem reporni problema pentru vectorul rămas: vom considera elementul curent drept candidat, cu o apariție.

La final vom rămîne cu un candidat ce trebuie acum verificat: numărăm de cîte ori apare el in vector printr-o parcurgere. Dacă apare de măcar n/2+1 ori am găsit elementul majoritar, altfel el nu există. Complexitatea acestei soluții este liniară, O(n), algoritmul făcînd două parcurgeri prin vector.

Iată o implementare posibilă:

#include <stdio.h>

int v[3000000];

int main() {
  FILE *fin, *fout;
  int n, i, nr, maj;

  // citire vector
  fin = fopen( "majoritar.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  // cautam candidatul la element majoritar
  maj = v[0];
  nr = 1;
  for ( i = 1; i < n; i++ )
    if ( v[i] == maj ) // cita vreme avem maj incrementam numarul de maj gasite
      nr++;
    else {
      nr--;            // altfel decrementam numarul de maj
      if ( nr < 0 ) {  // daca am scazut sub zero
        maj = v[i];    // alegem drept candidat elementul curent
        nr = 1;        // care apare o data
      }
    }

  // verificare candidat la element majoritar
  nr = 0;
  for ( i = 0; i < n; i++ ) // numaram de cit ori apare maj in vector
    if ( v[i] == maj )
      nr++;

  fout = fopen ( "majoritar.out", "w" );
  if ( nr > n / 2 ) // daca maj apare de mai mult de n/2 ori este majoritar
    fprintf( fout, "%d %d\n", maj, nr );
  else
    fprintf( fout, "-1\n" );
  fclose( fout );
}

De ce este această soluție mai bună decît sortarea? Deoarece face mai puține operații, vom vedea în anul următor exact care este diferența. În mare, știm că sortarea prin selecție face un număr de operații proporțional cu pătratul numărului de numere. Acest algoritm face un număr de operații proporțional cu numărul de numere, deci mult, mult mai puține atunci cînd numărul de numere este mare.

Minime multiple

Să calculăm nrmin, numărul de elemente minime într-un vector. Prima idee, probabil cea mai simplă, este să executăm doi pași. În prima trecere găsim minimul, în cea de-a doua numărăm de cîte ori apare. Iată această soluție:

  min = v[0];
  for ( i = 1; i < n; i++ )
    if ( v[i] < min )
      min = v[i];
  nrmin = 0;
  for ( i = 0; i < n; i++ )
    if ( v[i] == min )
      nrmin++;

O idee care duce la o soluție mai bună este să facem o singură trecere. Atunci cînd găsim un element mai mic decît minimul, îl păstrăm cu un număr de apariții 1. Atunci cînd găsim un element egal cu minimul, pur și simplu incrementăm numărul de apariții. Iată programul:

  min = v[0];
  nrmin = 1;
  for ( i = 1; i < n; i++ )
    if ( v[i] < min ) {
      min = v[i];
      nrmin = 1;
    } else if ( v[i] == min ) {
      nrmin++;
    }

De ce este această soluție mai bună? Deoarece:

  • face o singură trecere prin vector.
  • poate să rezolve problema fără să aibă nevoie de stocarea elementelor într-un vector.

Temă

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

  • majoritar dată la cercul de informatică Tudor Vianu, clasa a 6a
  • reorganizare dată la ONI 2003, clasa a 6a

Rezolvări aici [2].