Programare Competitivă

Generarea șirurilor pe baza unor reguli

Până acum am citit numere și le-am prelucrat. Acum vom învăța să generăm noi înșine numere, urmând anumite reguli.

Ce înseamnă „generarea unui șir”?

Înseamnă să producem o succesiune de numere care respectă o regulă clară.

Exemple:

  • numerele pare de la 2 la 20: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20
  • puterile lui 2: 1, 2, 4, 8, 16, 32, 64, ...
  • multiplii lui 7: 7, 14, 21, 28, 35, ...

În fiecare caz, fiecare element se obține din cel anterior (sau după o formulă).

Exemplul 1: numerele pare de la 2 la n

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int i = 2; i <= n; i = i + 2) {
        cout << i << " ";
    }

    return 0;
}
Input:
16
Output:
2 4 6 8 10 12 14 16

Exemplul 2: puterile lui 2 mai mici decât n

Regula: fiecare element este dublul celui anterior.

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int p = 1;

    while (p <= n) {
        cout << p << " ";
        p = p * 2;
    }

    return 0;
}
Input:
100
Output:
1 2 4 8 16 32 64

Pas cu pas

Pas p p <= 100?
1 1 DA → afișăm
2 2 DA → afișăm
3 4 DA → afișăm
4 8 DA → afișăm
5 16 DA → afișăm
6 32 DA → afișăm
7 64 DA → afișăm
8 128 NU → ne oprim

Exemplul 3: multiplii unui număr

Generăm toți multiplii lui k mai mici sau egali cu n:

#include <iostream>
using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;

    for (int m = k; m <= n; m = m + k) {
        cout << m << " ";
    }

    return 0;
}
Input:
7 50
Output:
7 14 21 28 35 42 49

Exemplul 4: suma primelor n numere naturale (pas cu pas)

Generăm suma 1 + 2 + 3 + ... + n, afișând fiecare sumă parțială:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int suma = 0;

    for (int i = 1; i <= n; i++) {
        suma = suma + i;
        cout << suma << " ";
    }

    return 0;
}
Input:
6
Output:
1 3 6 10 15 21

Observă: 1, 1+2=3, 3+3=6, 6+4=10, 10+5=15, 15+6=21.

Exemplul 5: șirul cu regula a(n) = 2 * a(n-1) + 1

Dăm primul termen și generăm următorii pe baza formulei:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    int a = 1; // primul termen

    for (int i = 1; i <= n; i++) {
        cout << a << " ";
        a = 2 * a + 1;
    }

    return 0;
}
Input:
6
Output:
1 3 7 15 31 63

Pas cu pas

Pas a Formula
1 1 (start)
2 3 2 × 1 + 1 = 3
3 7 2 × 3 + 1 = 7
4 15 2 × 7 + 1 = 15
5 31 2 × 15 + 1 = 31
6 63 2 × 31 + 1 = 63

Observație: aceste numere sunt 2^n - 1 (1, 3, 7, 15, 31, 63, …). Regula a = 2 * a + 1 produce exact această secvență!

Exemplul 6: șirul pătratelor perfecte mai mici decât n

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i * i <= n; i++) {
        cout << i * i << " ";
    }

    return 0;
}
Input:
50
Output:
1 4 9 16 25 36 49

Exemplul 7: numerele cu proprietăți speciale

Afișăm numerele de la 1 la n care sunt simultan pare și divizibile cu 3:

#include <iostream>
using namespace std;

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0 && i % 3 == 0) {
            cout << i << " ";
        }
    }

    return 0;
}
Input:
30
Output:
6 12 18 24 30
De ce sunt aceleași cu multiplii lui 6?

Un număr care e par (divisibil cu 2) și divisibil cu 3 este automat divisibil cu 2 × 3 = 6.

Deci am putea scrie direct for (int i = 6; i <= n; i = i + 6).

Tipuri de reguli frecvente

Regulă Exemplu Cod
Adunare constantă 3, 6, 9, 12, … a = a + 3
Înmulțire constantă 1, 2, 4, 8, 16, … a = a * 2
Formulă cu termenul anterior 1, 3, 7, 15, … a = 2 * a + 1
Condiție de filtrare pare, prime, divisibile if (condiție)
Pătrate/cuburi 1, 4, 9, 16, … i * i

Greșeli frecvente

1. Buclă infinită la generare cu while

Dacă uiți să actualizezi valoarea la fiecare pas, bucla nu se mai termină:

int p = 1;
while (p <= n) {
    cout << p << " ";
    // lipsește p = p * 2;
}

2. Depășire la puteri și produse

Puterile cresc foarte repede. 2^31 depășește int. Folosește long long dacă valorile pot fi mari.

3. Condiția greșită de oprire

Atenție dacă regula cere „mai mic decât n” sau „mai mic sau egal cu n”:

  • p < n → nu îl include pe n
  • p <= n → îl include pe n

Ce să reții

  • Generarea înseamnă producerea de numere după o regulă.
  • Regula poate fi: adunare, înmulțire, formulă, sau filtrare.
  • Folosim for sau while în funcție de situație.
  • La fiecare pas trebuie actualizat termenul curent.
  • Atenție la depășiri și la condiția de oprire.

Probleme

pbinfoSir1→

pbinfoCifre7→

pbinfoSir7→

Cuprins Inapoi Inainte