Clasa a V-a lecția 34 - 10 apr 2020
Tema - rezolvări
Problema prime
Problema prime este o aplicație directă a ciurului lui Eratostene.
#include <stdio.h>
char ciur[3000001];
int main() {
FILE *fin, *fout;
int n, x, d, i, a;
long long suma;
fin = fopen( "prime.in", "r" );
fscanf( fin, "%d%d", &x, &n );
fclose( fin );
// ciurul lui eratostene pina la 3000000
for ( d = 2; d * d <= 3000000; d++ )
if ( ciur[d] == 0 )
for ( i = d * d; i <= 3000000; i += d )
ciur[i] = 1;
// cel mai mare numar mai mic sau egal cu x
a = x;
while ( ciur[a] == 1 )
a--;
// suma primelor n numere strict mai mari decit x
suma = 0;
for ( i = 0; i < n; i++ ) {
x++;
while ( ciur[x] == 1 )
x++;
suma += x;
}
fout = fopen( "prime.out", "w" );
fprintf( fout, "%d\n%lld\n", a, suma );
fclose( fout );
return 0;
}Problema apropiate1
Problema apropiate1 a fost dată la ONI 2004 clasa a 6a.
O rezolvare obișnuită ar fi să căutăm pentru fiecare număr dat cele mai apropiate numere prime atît la stînga cît și la dreapta. Vom alege numărul cel mai aproape din cele două.
Această metodă va repeta, desigur, instrucțiunile de căutare, pentru cele două căutări. Putem să scriem programul de așa natură încît să nu repetăm cod? Putem să schimbăm ordinea căutarii elementelor: vom căuta mai întîi cele două numere alăturate numărului dat. Apoi următoarele două, la distanță 2. Apoi următoarele. Și așa mai departe. Cu alte cuvinte, dacă a este numărul dat, vom testa de primalitate următoarele numere, în ordine:
- a, a+1, a-1, a+2, a-2, a+3, a-3, ...
Primul număr prim găsit va fi cel căutat. Această căutare pleacă cu primul număr către dreapta. S-ar putea, însă, să trebuiască să căutăm mai întîi către stînga. Acest lucru depinde de C.
Soluția finală se bazează pe găsirea unui șir de numere ce se adună la a, pentru a genera șirul de mai sus. Șirul va fi de forma:
- 0, 1, -1, 2, -2, 3, -3, ...
dacă C = 2, sau:
- 0, -1, 1, -2, 2, -3, 3, ...
dacă C = 1. Observăm că șirul este, în principiu, i/2 cu i variind din unu în unu. Ajustăm pentru a obține exact valorile dorite. Găsiți explicația detaliată în program:
#include <stdio.h>
#define MAXA 4000000
char ciur[MAXA + 1];
int main() {
FILE *fin, *fout;
int n, dir, d, i, a, s, inc;
for ( d = 2; d * d <= MAXA; d++ )
if ( ciur[d] == 0 ) // este prim?
for ( i = d * d; i <= MAXA; i += d )
ciur[i] = 1; // marcam multiplii ca numerele neprime
fin = fopen( "apropiate1.in", "r" );
fout = fopen( "apropiate1.out", "w" );
fscanf( fin, "%d%d", &n, &dir );
dir = 2 * dir - 3; // devine -1 sau 1
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d", &a );
// inc va trece prin valorile 1 2 3 4 5 ...
// inc/2 va trece prin valorile 0 1 1 2 2 3 3 ...
// s va trece prin valorile dir -dir dir -dir etc
// inc/2*s va trece prin valorile 0 -1 1 -2 2 -3 3 etc.... sau prin
// 0 1 -1 2 -2 3 -3 etc (depinde de dir)
inc = 1;
s = -dir; // pornim cu semnul invers deoarece primul testat este 0
while ( ciur[a + inc / 2 * s] == 1 ) {
inc++;
s = -s; // schimbam semnul
}
fprintf( fout, "%d ", a + inc / 2 * s );
}
fprintf( fout, "\n" );
fclose( fin );
fclose( fout );
return 0;
}Problema kdiv
Problema kdiv este o aplicație a ciurului lui Eratostene. Putem modifica algoritmul astfel încît să calculeze numărul de factori primi ai fiecărui număr mai mic sau egal cu n. Atenție! Nu vom folosi varianta optimizată a algoritmului, care merge pînă la radical din n, deoarece ne interesează nu doar dacă un număr este prim sau nu, ci și cîți divizori primi are acel număr.
Iată o soluție posibilă:
#include <stdio.h>
// nrdiv[i] = 0 daca i este prim, sau numarul de divizori primi in caz contrar
char nrdiv[1000001];
int main() {
FILE *fin, *fout;
int n, k, i, d, a, nrk;
for ( d = 2; d <= 1000000; d++ )
if ( nrdiv[d] == 0 ) // numar prim
for ( i = d; i <= 1000000; i += d ) // marcam inca un divizor prim
nrdiv[i]++;
fin = fopen( "kdiv.in", "r" );
fscanf( fin, "%d%d", &n, &k );
nrk = 0;
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d", &a );
if ( nrdiv[a] == k )
nrk++;
}
fclose( fin );
fout = fopen( "kdiv.out", "w" );
fprintf( fout, "%d\n", nrk );
fclose( fout );
return 0;
}Lecție
Nu există video. Lecția este doar teoretică și disponibilă online.
Vector mulțime
Se dă un vector v de n elemente. Să se transforme într-un vector mulțime. Cu alte cuvinte, să se elimine duplicatele din vector. Un vector mulțime este un vector în care orice element apare o singură dată.
Avem mai multe soluții posibile. O primă soluție se bazează pe vectori de frecvență. Putem construi un vector de apariții ale elementelor din v. Apoi vom colecta elementele din vectorul de apariții înapoi in v. Această soluție funcționează pentru valori relativ mici ale elementelor din v.
Dacă valorile din v sînt prea mari pentru a folosi un vector de frecvență, atunci putem să verificăm fiecare element din vector și să îl copiem în alt vector, w, numai dacă el nu apare deja în vectorul w. Iată această soluție:
// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului w
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in w
j = 0;
while ( j < m && w[j] != v[i] )
j++;
if ( j == m ) { // daca elementul v[i] nu exista in vectorul w, il adaugam
w[m] = v[i];
m++;
}
}Observație importantă: vectorul w are întotdeauna lungime mai mică sau cel mult egală cu vectorul v.
De aceea putem să nu folosim un vector diferit w, ci să lucrăm chiar pe vectorul v! Codul este identic cu cel de mai sus, înlocuind w cu v:
// avem vectorul v de n elemente, vrem sa il transformam in vector multime
m = 0; // numarul de elemente al vectorului multime
for ( i = 0; i < n; i++ ) { // fiecare element din v va fi cautat in multime
j = 0;
while ( j < m && v[j] != v[i] )
j++;
if ( j == m ) { // daca elementul v[i] nu exista in multime, il adaugam
v[m] = v[i];
m++;
}
}
// in final vectorul v de lungime m contine multimea vectorului originalCăutare subvector în vector
Dați doi vectori, p (vectorul de căutat) și v (vectorul în care se caută) să se spună de cîte ori apare vectorul p în v. De exemplu dacă p = [1, 2, 1] și v = [1, 2, 1, 2, 1, 3, 1, 2, 1] atunci p apare de 3 ori in v.
Să observăm că aparițiile vectorului p în vectorul v pot fi suprapuse, ca în exemplul de mai sus. Un algoritm direct este să încercăm toate pozițiile de suprapunere ale vectorului p peste vectorul v și să testăm dacă toate elementele din p se potrivesc cu cele din v:
1, 2, 1, 2, 1, 3, 1, 2, 1 0: 1, 2, 1 1: 1, 2, 1 2: 1, 2, 1 3: 1, 2, 1 4: 1, 2, 1 5: 1, 2, 1 6: 1, 2, 1 |
Suprapunînd vectorul p peste v observăm că avem potriviri la pozițiile 0, 2 și 6. Iată programul pentru această metodă:
// avem vectorul v de n elemente si vectorul de cautat p, de m elemente
nr = 0; // numarul de aparitii este initial zero
for ( poz = 0; poz < n – m + 1; poz++ ) { // pentru fiecare pozitie posibila
i = 0;
while ( i < m && p[i] == v[poz + i] ) // ne oprim la prima inegalitate
i++;
if ( i == m ) // daca toate elementele au fost egale
nr++; // am mai gasit o aparitie a lui p in v
}
// acum nr contine numarul de aparitii ale lui p in vVom vedea în anii următori că există și algoritmi mai eficienți pentru rezolvarea acestei probleme.
Comparație vectori
Dați doi vectori de caractere să se spună care este ordinea lor lexicografică. Cu alte cuvinte, ordinea în care vor apărea cele două cuvinte în dicționar.
Un vector v1 este lexicografic mai mic decît alt vector v2 dacă v1 și v2 sînt egale de la 0 la i-1, iar poziția i este fie în afara vectorului v1, fie v1[i] < v2[i]. Vom compara elementele vectorilor pe aceleași poziții cîtă vreme sînt egale, oprindu-ne la prima diferență, sau cînd unul din vectori se termină. Acolo vom decide care din vectori este mai mic.
Iată programul:
// avem vectorii v1 de n1 elemente si v2 de n2 elemente
i = 0;
while ( i < n1 && i < n2 && v1[i] == v2[i] ) // cita vreme avem egalitate
i++; // avansam i
// pentru ca v1 sa fie primul in ordine lexicografica trebuie ca
// fie i sa fi depasit ultimul element din v1, fie ca v1[i] < v2[i]
// pentru a doua conditie e nevoie ca v2 sa aiba ceva pe pozitia i
if ( i == n1 || (i < n2 && v1[i] < v2[i]) )
m = 0;
else
m = 1;Rotire multiplă de vector *
Se dă un vector v de n elemente și un număr k. Să se rotească vectorul cu o poziție către început cu k poziții. De exemplu, pentru k=3 [1, 6, 2, 7, 4, 3, 2] se va transforma în [7, 4, 3, 2, 1, 6, 2].
O soluție ar putea fi să rotim vectorul cîte o poziție de k ori. Această soluție face multe deplasări, respectiv k∙n. Un algoritm mai bun este următorul:
- Răstoarnă vectorul v.
- Răstoarnă subvectorul v[0..n-k-1]
- Răstoarnă subvectorul v[n-k..n-1]
De ce funcționează acest algoritm?
Care este numărul de deplasări ale acestui algoritm? Demonstrați că este 3∙n.
Sortarea prin selecție (select sort)
Se dă un vector de n elemente. Să se sorteze prin metoda selecției. Prin sortare înțelegem ordonare crescătoare a elementelor vectorului. Metoda selecției este următoarea: vom găsi maximul din vector, împreună cu poziția sa. Apoi vom interschimba maximul cu ultimul element din vector. Astfel ne vom asigura că ultimul element este chiar cel corect în vectorul ordonat. Ne-a rămas astfel un vector cu n-1 elemente, care trebuie sortat. Vom proceda la fel: vom găsi maximul în subvectorul de n-1 elemente, precum și poziția lui, și-l vom muta la coadă, rezultînd un vector de n-2 elemente. Continuăm procedura pînă ce vectorul este sortat.
Iată o exemplificare grafică:
9 2 8 3 6 5 3 9 6 | 6 2 8 3 6 5 3 9 | 9 6 2 8 3 6 5 3 | 9 9 6 2 3 3 6 5 | 8 9 9 5 2 3 3 6 | 6 8 9 9 5 2 3 3 | 6 6 8 9 9 3 2 3 | 5 6 6 8 9 9 3 2 | 3 5 6 6 8 9 9 2 | 3 3 5 6 6 8 9 9 | 2 3 3 5 6 6 8 9 9 |
Iată programul:
// avem vectorul v de n elemente
for ( u = n – 1; u > 0; u-- ) { // pozitia ultimului element din subvector
max = v[0];
p = 0; // p este poziția maximului
for ( i = 1; i <= u; i++ )
if ( v[i] > max ) { // memoram noul maxim si pozitia lui
max = v[i];
p = i;
}
// interschimbam maximul de pe pozitia p cu ultimul element, pe pozitia u
v[p] = v[u];
v[u] = max;
}Vă recomand folosirea algoritmului de sortare prin selecție și nu a sortării cu bule, deoarece face mai puține operații. În practică el este de cinci pînă la zece ori mai rapid. Desigur, și mai rapidă este sortarea prin vectori de frecvență, numită și sortare prin numărare, atunci cînd ea poate fi aplicată (cînd numerele sînt foarte mici).
Temă
Tema 34: să se rezolve următoarele probleme (program C trimis la vianuarena):
- siruri1 dată la OJI 2004 clasa a 7a
- case1 dată la ONI 2009 clasa a 5a
- arme dată la OJI 2012 clasa a 7a, ca aplicație a sortării prin selecție
Rezolvări aici [1]
