#include <iostream>

using namespace std;

// PRIMERE SA FUNKCIJAMA GLEDATI NA KRAJU, NAKON STO PREDJETE SVE DRUGE PRIMERE IZ OVOG FAJLA

// Napisati funkciju koja racuna zbir 1+2+...+n = n*(n+1)/2

// iterativna verzija n! = 1 * 2 * ... * n
int faktorijal (int n){
    int rez = 1;
    for (int i=2; i<=n; i++)
        rez = rez*i;
    return rez;
}

// rekurzivna verzija
int rek_fakt (int n){
    if (n <= 1) //n==1
        return 1;
    else
        return n*rek_fakt(n-1);
}

/*
/* n! = 1 * 2 * ... * n

bazni slucaj:         1! = 1
induktivni slucaj:    n! = n * (n-1) * (n-2) * ... * 1
                         = n * (n-1)!
matematicka indukcija P(n) --- faktorijal(n) = n!
(I) bazni slucaj 1! ?= 1
(II) induktivni slucaj: pp (n-1)! dobro izracunat =>? da li je dobar n!
    n! = n * (n-1)!

    faktorijal(n) = n * faktorija(n-1)

3! = 3 * 2!
2! = 2 * 1!
1! = 1


Dokazati matematickom indukcijom da vazi 1+2+...+n = n*(n+1)/2

Baza indukcije: n = 1,
proveravamo formulu, sa leve strane dobijamo 1, sa desne strane dobijamo 1, znaci jednakost vazi

Induktivni korak: pretpostavimo da vazi formula za vrednost n (1+2+...+n = n*(n+1)/2) i
                  pokusavamo da dokazemo da formula vazi za vrednost n+1

Odnosno treba da proverimo da li vazi sledeca jednakost:
1+2+...+n+(n+1) = (n+1)*(n+2)/2

Sa leve strane mozemo transformisati izraz na sledeci nacin:
1+2+...+n+(n+1) = n*(n+1)/2 + (n+1) --- na osnovu induktivne pretpostavke (da tvrdjenje vazi za vrednost n)
            ... = (n+1)*(n/2 + 1)   --- kada izvucemo (n+1) ispred oba sabirka
            ... = (n+1)*(n+2)/2     --- kada izvucemo zajednicki imenilac iz oba sabirka u zagradi

I vidimo da smo dobili izraz sa desne strane, sto znaci da smo dokazali i induktivni korak.
*/

// f(0) = 1, f(1) = 1, f(2) = f(0)+f(1)... 1,1,2,3,5,8,...
// Domaci - napisati rekurzivnu i iterativnu varijantu ove funkcije

int main()
{
    // Kombinovanje naredbi ponavljanja - zadaci

    int n, i, j;

    cout << "Unesite ceo broj: " << endl;
    cin >> n;

    // Trougao sa pravim desnim gornjim uglom
    // ***
    //  **
    //   *

    for (i=0; i<n; i++) {    // i = 0 *****
        for(j=0; j<i; j++)   // i = 1 _****
          cout << " ";       // i = 2 __***

        for (j=i; j<n; j++) // j=0; j<n-i; j++
          cout << "*";
        cout << endl;
    }


    // Piramida od cifara
    //    1
    //   2 2
    //  3 3 3

    for (i=1; i<=n; i++){
        for(j=i; j<n; j++)
          cout << " ";

        for(j=1; j<=i; j++) //ispis i puta
            cout << i << " ";
        cout << endl;
    }


    // Nizovi

    int brojevi[3]; // niz celih brojeva
    string reci[3]; // niz stringova

    // Domaci - uraditi sve zadatke sa petlje i sve primere koje nismo uradili na casu

    // Primer: unos i ispis elemenata niza

    // Primer: suma elemenata niza, maksimalni element niza, prosecna vrednost niza

    // Primer: broj elemenata veci od proseka --- mora da se koristi niz

    // Primer: unosi se broj n, a zatim n brojeva između 1 i 10.
    // Ispisati koliko puta se svaki od brojeva pojavio.

    cout << "Unesite broj elemenata niza:" << endl;
    cin >> n;

    /*
    1 2 1 | 2 | 1 1 1 1 1 1 |

    br1 ima 0 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    br2 ima 0 + 1 + 1
    br3 ima ...
    br4 ...
    5 ...
    6 ...
    7 ...
    8 ...
    9 ...
    10 ...
    */


    // niz dimenzije 11 da bi mogli da pristumo indeksima 1 do 11
    int koliko_puta[11];    // indeksi idu od 0 do 10

    int br;
    // inicijalizacija
    for (br=1; br<=10; br++)
        koliko_puta[br] = 0;

    cout << "Unesite elemente niza: " << endl;
    int x;
    for (i=0; i<n; i++){
        cin >> x;
        koliko_puta[x]++;
    }

    for (br=1; br<=10; br++)
        if (koliko_puta[br] != 0)  // isto kao if (koliko_puta[br])
            cout << "Broj " << br << " se pojavljuje " << koliko_puta[br] << " puta" << endl;

    // Dodatak - modifikovati prethodnu petlju tako da ispisuje samo one brojeve koji su se stvarno pojavili u nizu


    // Primer: Veliki zbir

    int MAX_DUZINA = 10; // 100
    int broj1[MAX_DUZINA];
    int broj2[MAX_DUZINA];

    int brcif1, brcif2;

    // postavljamo sve cifre na 0
    for (int i = 0; i < MAX_DUZINA; i++){
        broj1[i] = 0;
        broj2[i] = 0;
    }

    cout << "Unesite broj cifara prvog broja pa njegove cifre sa leva na desno: " << endl;
    cin >> brcif1;
    for (int i = MAX_DUZINA - brcif1; i < MAX_DUZINA; i++)
        cin >> broj1[i];

    cout << "Uneli ste: " << endl;
    for (int i = 0; i < MAX_DUZINA; i++)
            cout << broj1[i] << " ";
    cout << endl;


    cout << "Unesite broj cifara drugog broja pa njegove cifre sa leva na desno: " << endl;
    cin >> brcif2;
    for (int i = MAX_DUZINA - brcif2; i < MAX_DUZINA; i++)
        cin >> broj2[i];

    cout << "Uneli ste: " << endl;
    for (int i = 0; i < MAX_DUZINA; i++)
            cout << broj2[i] << " ";
    cout << endl;


    // racunamo zbir pri cemu vodimo racuna o prenosu
    // rezultat smestamo u broj1
    int prenos = 0;

    for (int i = MAX_DUZINA-1; i >= 0; i--){
        int zbir = broj1[i] + broj2[i] + prenos;
        prenos = zbir / 10;
        broj1[i] = zbir % 10;
    }

    cout << "Ispis preko niza: " << endl;
    for (int i = 0; i < MAX_DUZINA; i++)
        cout << broj1[i] << " ";
    cout << endl;


    cout << "Rezultat zbira: " << endl;
    // uvodimo indikator koji vodi racuna da ne ispisemo vodece nule
    bool pisi = false;

    for (int i = 0; i < MAX_DUZINA; i++){
        if (broj1[i] != 0)
              pisi = true;

        if (pisi)
            cout << broj1[i];
    }

    cout << endl;



    // Funkcije
    // Poziv funkcije koja racuna faktorijal

    int f;
    cout << "Unesite broj ciji faktorijal zelite da izracunate: " << endl;
    cin >> f;
    cout << "Vrednost " << f << "! = " << faktorijal(f) << endl;
    cout << "Rekurzivno " << f << "! = " << rek_fakt(f) << endl;


    return 0;
}