Clasa a VI-a lecția 1 - 18 sep 2013

From Algopedia
Jump to navigationJump to search

Lecție

Complexitatea algoritmilor

Complexitate: ce înseamnă, cîte operații pe secundă execută un calculator, ce operații sînt "scumpe".

Iată un exemplu:

Cifra k Rezolvare
Calculați cifra k a unui număr n, numărînd cifrele de la dreapta la stînga. 
while ( k > 1 ) {
  n = n / 10;
  k--;
}
cf = n % 10;

Complexitate: proporțional cu numărul de cifre al lui n

Alt exemplu: afișați descompunerea în factori primi a numărului n. Exemplu: 1176 = 23 x 31 x 72. Optimizarea descompunerii în factori primi. Complexitățile aferente.

Ideea rezolvării constă în existenţa unui singur factor prim mai mare decât radicalul numărului. O implementare a acestei probleme de complexitate O(sqrt(n)): 

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    
    int div = 2; //Incepem cautarea factorilor primi de la primul numar prim
    //Cautam factorii primi pana la radicalul numarului
    while (div * div <= n) {
        int exp = 0;
        while (n % div == 0) {
            n = n / div;
            ++exp;
        }
 
        if (exp > 0)
            printf("Factor prim %d, la puterea %d\n", div, exp);

        ++div;
    }
    //In cazul in care mai exista un factor prim, acesta este chiar numarul ramas
    if (n != 1)
        printf("Factor prim %d, la puterea 1\n", n);
}

Recapitulare cunoștințe informatică

Rezolvați următoarele exerciții. Pentru fiecare exercițiu rezolvat calculați complexitatea timpului de execuție (numărul de operații efectuat de algoritm în funcție de datele de intrare).

Numere cu două cifre

Spuneți dacă numărul n este format din exact două cifre repetate de oricâte ori. 23223 și 900990 sînt astfel de numere, pe cînd 593 și 44002 nu. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Iată o metodă de rezolvare: eliminăm ultima cifra, c1, a numărului, iar apoi continuăm să eliminăm ultima cifră cîtă vreme este egală cu c1. Apoi eliminăm iarăși ultima cifră, c2, iar apoi continuăm să eliminăm ultima cifră cîtă vreme este egală cu c1 sau c2. Iată soluția bazată pe această idee: 

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    if (n < 10)
        printf("NU");
    else {
        // Retinem ultima cifra din numar in c1
        int c1 = n % 10;
        n = n / 10;
        // Eliminam toate aparitiile lui c1 din coada numarului
        while (n > 0 && n % 10 == c1)
            n = n / 10;
        // Daca numarul nu mai are alte cifre, afisam NU
        if (n == 0)
            printf("NU");
        else {
            // Retinem urmatoarea cifra din numar in c2
            int c2 = n % 10;
            n = n / 10;
            // Cat timp ultima cifra a numarului este c1 sau c2, o eliminam
            while (n > 0 && (n % 10 == c1 || n % 10 == c2))
                n = n / 10;
            // Daca numarul ramas este nul, afisam DA
            if (n == 0)
                printf("DA");
            else
                printf("NU");
        }
    }
}

Putere

Calculați an în mod cît mai eficient (a și n numere naturale). Problema este cunoscută şi sub numele de ridicare la putere în timp logaritmic. Ideea din spatele acestei rezolvări este următoarea:

  • Dacă n este par, atunci an = a2*n/2 = (a2)n/2
  • Dacă n este impar, atunci n-1 este par și avem an = a * an-1 = a * a2*(n-1)/2 = a * (a2)(n-1)/2 = a * (a2)n/2

În formulele de mai sus am considerat că / este împărțirea întreagă din limbajul C. Se observă că indiferent de paritatea lui n, la fiecare pas al iterației putem transforma a în a * a și apoi putem împărți n la 2. Doar în cazurile cînd n este impar vom acumula valoarea curentă a lui a la produsul calculat. Iată soluția bazată pe această idee: 

#include <stdio.h>

int main() {
    int a, n;
    scanf("%d%d", &a, &n);

    int p = 1;
    while (n > 0) {
        if (n % 2 == 1)
            p = p * a;
        a = a * a;
        n = n / 2;
    }
    printf("%d", p);
}

Secvență monotonă

Spuneți dacă o secvență de numere este monotonă. O secvență este monotonă dacă numerele ei sînt fie în ordine crescătoare fie în ordine descrescătoare. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Complexitatea acestei soluții este liniară, egală cu numărul de elemente ale secvenţei: O(n). 

#include <stdio.h>

int main() {
    int n, a, b, i, cresc, monoton;
    scanf( "%d", &n );
    scanf( "%d%d", &a, &b );
    i = 2;
    // Ignoram toate elemente egale de la inceput, pentru a stabili monotonia sirului
    while (i < n && a == b) {
        a = b;
        scanf("%d", &b);
        ++i;
    }
    // Daca toate numerele sunt egale, secventa este monotona
    if (i == n) {
        printf("DA");
    }
    else {
        // Daca sirul tinde crescator, cresc = 1; Altfel, cresc = 0.
        if (a < b)
            cresc = 1;
        else
            cresc = 0;
        // Retinem monotonia initiala
        monoton = cresc;
        // Cat timp nu am terminat de parcurs sirul si este pastrata monotonia initiala
        while (i < n && monoton == cresc) {
            a = b;
            scanf("%d", &b);
            if (a < b)
                cresc = 1;
            else
            if (a > b)
                cresc = 0;
            ++i;
        }
        if (monoton == cresc)
            printf("DA");
        else
            printf("NU");
    }
    return 0;
}

Paranteze

Dată o secvență de 0 și 1, unde 0 înseamnă paranteză deschisă '(', iar 1 înseamnă paranteză închisă ')', spuneți dacă secvența reprezintă o expresie corectă de paranteze și dacă da calculați numărul maxim de paranteze una într-alta. Exemplu: 0 1 0 0 1 0 1 1 este corectă și are factorul de imbricare de 2, pe cînd secvența 0 0 0 1 1 1 0 este incorectă. Nu aveți voie să folosiți tablouri (vectori sau matrice).

Am discutat despre problemă, fără sa ducem soluția pînă la capăt.

Tema

  • Cîți ani bisecți între anul a și anul b. Interval închis [a, b]
  • Cîte zile între două date calendaristice corecte (maxim 2 miliarde zile)
  • Opțional: problema cu ușile de la codechef: http://www.codechef.com/BTCD2012/problems/DOORS

Doors

There are N doors of a palace, all of which are operated by a set of buttons. One day, Alice, who is just 8 years old, gets access to these buttons. Having recently learnt the multiplication tables, she decides to press buttons in a particular order. First, she presses all the buttons that are multiples of 1. Next, she presses all buttons that are multiples of 2, then 3 and so on until N; after which she leaves.

Each press of button toggles the state of the door, i.e. a door that is open will be closed by the button press and opened if closed initially.

Given that all doors were closed initially, give the number of doors that are open after she leaves.

Input

The input contains several lines. First line contains the number 't', which represents the number of test cases that follow. This is followed by 't' lines of numbers which represent 'N'. 0 < t < 1000000 0 < N < 100000000

Output

For each input, output the number of doors that are open at the end.

Example

Input: 

4
4
10
16
27

Output: 

2
3
4
5

Time Limit: 3 sec

Rezolvări aici [1]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_VI-a_lecția_1_-_18_sep_2013&oldid=10055"