backtracking lab. 4 (ex 2) (Irina #4)

// EX 1

#include <stdio.h>
#include <conio.h>

int n = 5;
int sol[20];

void BackTracking(int k);
bool valid(int k);
void afis();


void main() {
    //int k = 1;

    BackTracking(1);

    _getch();
}

void BackTracking(int k) {
    for (int i = 1; i <= n; i++) {
        sol[k] = i;
        if (valid(k)) {
            if (k == n) {
                afis();
            }
            else {
                BackTracking(k + 1);
            }
        }
    }
}

bool valid(int k) {
    for (int i = 1; i < k; i++)
        if (sol[i] == sol[k])
            return false;

    if (k % 2 == 0 && sol[k] != k)
        return false;

    return true;
}

void afis() {
    for (int i = 1; i <= n; i++) {
        printf("%d ", sol[i]);
    }
    printf("\n");
}
//#####################################################################################################
// EX 2
#include <stdio.h>
#include <conio.h>
#include <iostream>

using namespace std;
int sol[20], n = 5;

bool valid(int k) {
    int juma = (n / 2) + 1;

    for (int i = 1; i < k; i++) {

        if (sol[i] == sol[k]) {
            return false;
        }
    }


    if (k<juma) {
        for (int i = 1; i < k; i++) {
            if (sol[i] > sol[i + 1]) {
                return false;
            }
        }
    }
    else {
        for (int i = juma; i < k; i++) {
            if (sol[i] < sol[i + 1]) {
                return false;
            }
        }
    }
    return true;
}

void afis() {
    for (int i = 1; i <= n; i++) {
        cout << sol[i] << " ";

    }
    cout << endl;
}

void BKT(int k) {
    for (int i = 1; i <= n; i++) {
        sol[k] = i;
        if (valid(k)) {
            if (k == n)
                afis();
            else BKT(k + 1);
        }
    }

}

void main() {
    BKT(1);
    _getch();
}
//####################################################################################################
// ex 3 ceva cu bani bancnote // algoritmul greedy mai pe scurt

#include <stdio.h>
#include <conio.h>
#include <iostream>

using namespace std;

int ban(int S, int e, int n) {
    int p = 1, i = 0;
    while (p*e <= S &&  i < n) {
        p *= e;
        i++;
    }
    return p;
}


void main() {
    int s, n, e, b, nr = 0;
    s = 444; // suma de bani
    e = 2; //(asta e exponentul, adica 2 la puterea n , ala de mai jos)
    n = 5;//reprezinta cea mai mare bancnota (2 la puterea 5 , 32, daca pui 6 cea mai mare bancnota e 64 lei)
    while (s > 0) {
        b = ban(s, e, n);
        cout << s / b << " bancnota de " << b << " lei" << endl;
        nr += s / b;
        s %= b;
    }
    cout << nr << " bancnote";

    _getch();
}

// s = suma de bani . trebuie platita folosind bancnote folosind puteri.... e e^0,e^1;



//############################################################################
// ex versiunea 1 cu sali/ore

#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;

void Afisare(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
        if (a[i] < 10)
            cout << " ";
    }
    cout << endl;
}

void SortCresc(int a[], int b[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int aux;
                aux = a[i]; // metoda bulelor si pt "a" , si "b" in acelasi timp , ca sa sortezi 2 vectori deodata
                a[i] = a[j];
                a[j] = aux;

                aux = b[i];
                b[i] = b[j];
                b[j] = aux;
            }
        }
    }
}

void main() {
    // e problema cu salile alea si cu orele(curs), incepe cursu sa zicem la ora "5" cursu nu are cum sa se termine
    // mai devreme de "5" , de asta te asiguri ca dureaza minim o ora,
    // vectorul "a" contine de la "1" la "11" ore , iar b contine de la "1" la "12"
    srand(time(NULL));
    int n = 7, a[7], b[7];
    for (int i = 0; i < n; i++) {
        a[i] = rand() % 11 + 1; // se pune random numer de la 1 la 11
        b[i] = rand() % 12 + 1; // se pune random numar de la 1 la 12
        while (b[i] <= a[i]) { //daca numarul din b[i] e mai mic decat cel din a[i] (adica ora de terminare trebuie sa fie mai mare decat ora de incepere)
            b[i] = rand() % 12 + 1; // repeta random pana cand b[i] devine mai mare decat a[i]
        }
    }
    Afisare(a, n);
    Afisare(b, n);

    SortCresc(a, b, n);
    //  SortCresc(b, n);

    Afisare(a, n);
    Afisare(b, n);

    _getch();
}

//###################################################
// esec v2

#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;

void Afisare(int a[], int n) {
    for (int i = 0;i < n;i++) {
        cout << a[i] <<" ";
        if (a[i] < 10)
            cout << " ";
    }
    cout << endl;
}

void SortCresc(int a[],int b[], int n) {
    for (int i = 0;i < n - 1;i++) {
        for (int j = i + 1;j < n;j++) {
            if (a[i] > a[j]) {
                int aux;
                aux  = a[i];
                a[i] = a[j];
                a[j] = aux;

                aux = b[i];
                b[i] = b[j];
                b[j] = aux;

            }
            if (a[i] == a[j]) {
                if (b[i] > b[j]) {
                    int aux;
                    aux = a[i];
                    a[i] = a[j];
                    a[j] = aux;

                    aux = b[i];
                    b[i] = b[j];
                    b[j] = aux;

                }
            }
        }
    }
}

void main(){
    srand(time(NULL));
    int n = 7,a[7],b[7];
    for (int i = 0;i < n;i++) {
        a[i] = rand() % 11 + 1;
        b[i] = rand() % 12 + 1;

        while (b[i] <= a[i]) {
            b[i] = rand() % 12 + 1;
        }

    }


    SortCresc(a,b, n);
//  SortCresc(b, n);

    Afisare(a, n);
    Afisare(b, n);

    _getch();
}

// s = suma de bani . trebuie platita folosind bancnote folosind puteri.... e e^0,e^1;
//#####################################################################################
//ideea lui David

#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <time.h>
using namespace std;

void Afisare(int a[], int n) {
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
        if (a[i] < 10)
            cout << " ";
    }
    cout << endl;
}

void SortCresc(int a[], int b[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                int aux;
                aux = a[i]; // metoda bulelor si pt "a" , si "b" in acelasi timp , ca sa sortezi 2 vectori deodata
                a[i] = a[j];
                a[j] = aux;

                aux = b[i];
                b[i] = b[j];
                b[j] = aux;
            }
        }
    }
}

void main() {
    // e problema cu salile alea si cu orele(curs), incepe cursu sa zicem la ora "5" cursu nu are cum sa se termine
    // mai devreme de "5" , de asta te asiguri ca dureaza minim o ora,
    // vectorul "a" contine de la "1" la "11" ore , iar b contine de la "1" la "12"
    srand(time(NULL));
    int n = 7, a[7], b[7], k = 0, retine_rand;
    for (int i = 0; i < n; i++) {
        if (i >= 1) {
            while (1) {
                retine_rand = rand() % 11 + 1;
                bool check = true;
                //int index;
                for (int index = 0; index < k; index++) {
                    if (a[index] == retine_rand) {
                        check = false;
                    }
                }
                if (check) {
                    a[i] = retine_rand;
                    break;
                }
            }
        }
        if (i == 0)
        a[i] = rand() % 11 + 1; // se pune random numer de la 1 la 11
        k++;

        if (a[i] == 11) {
            b[i] = 12;
        }
        else {
            b[i] = rand() % a[i] + 3; // se pune random numar de la 1 la 12
        }
        while (b[i] <= a[i]) { //daca numarul din b[i] e mai mic decat cel din a[i] (adica ora de terminare trebuie sa fie mai mare decat ora de incepere)
            b[i] = rand() % a[i] + 3; // repeta random pana cand b[i] devine mai mare decat a[i]
        }
    }
    Afisare(a, n);
    Afisare(b, n);

    SortCresc(a, b, n);

    cout << "\nDupa sortare\n";
    Afisare(a, n);
    Afisare(b, n);

    _getch();
}