Clasa a V-a lecția 43 - 7 iun 2018
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 defor
cît și înfor
.
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].