BackTracking lab.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");
}

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

using namespace std;


int n = 5;
int sol[20];

bool valid(int k) {
    int i;
    //cout << k << endl;
    for (i = 1; i < k; i++) {

        if (sol[i] == sol[k]) {
            return false;
        }
    }
    if (k<(n / 2 + 1)) {
        for (int i = 1; i < k; i++) {
            if (sol[i] > sol[i + 1]) {
                return false;
            }
        }

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

void afis(int sol[], int n) {
    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(sol, n);
            else BKT(k + 1);
        }
    }

}

void main() {

    BKT(1);

    _getch();
}

//###############################################################################################33
//GREEDY MAN
#include <stdio.h>
#include <conio.h>
#include <iostream>

using namespace std;

int ban(int n ,int s, int e);

void main() {
    int s, n, e, b, nr = 0;
    //s = suma de bani , n = puteri ale lui e;
    cout << "s = ";
    cin >> s;

    cout << "n = ";
    cin >> n;

    cout << "e  = ";
    cin >> e;

    while (s > 0) {
        b = ban(s, n, e);
        printf("%d bancnote de %d lei\n", s / b, b);
        nr += s / b;
        s = s % b;
    }
    _getch();
}

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


    return p;
}

//######################################################################################################
//BUBLE SORT
#include <stdio.h>
#include <conio.h>
#include <iostream>

using namespace std;

void main() {
    int n = 7;
    int glass;

    int v1[7] = { 2,8,5,5,3,7,9 };
    int v2[7] = { 4,11,6,8,7,8,12 };

    //BUBLE SORT

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (v1[i] > v1[j]) {
                glass = v1[i];
                v1[i] = v1[j];
                v1[j] = glass;

                glass = v2[i];
                v2[i] = v2[j];
                v2[j] = glass;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        printf("%d  ", v1[i]);
    }

    printf("\n");

    for (int i = 0; i < n; i++) {
        printf("%d  ", v2[i]);
    }

    _getch();
}