Esercitazioni di algoritmi

Sultan problem (UVA 167)

N--;}return 0;}bool compareJob(job a,job b){double r1 = (double) a.fine/a.time;double r2 = (double) b.fine/b.time;if(r1 != r2) return r1 > r2;return a.pos < b.pos;}10) Sultan problem (UVA 167)#include <iostream>#include <vector>#include <algorithm>using namespace std;void printChessBoard(vector<vector<int>>);void printBitMap(vector<vector<bool>>);void fillChessBoard(vector<vector<int>>&);bool maxScore(vector<vector<int>>, int, vector<vector<bool>>,int&);int processSolution(vector<vector<int>>,vector<vector<bool>>);bool isSafe(vector<vector<bool>>,int,int);int main(int argc, const char * argv[]) {int n_chessBoard;int punteggio = 0;vector<vector<int>> chessBoards(8,vector<int>(8));vector<vector<bool>> bitmap(8,vector<bool>(8));cout<<"Quante scacchiere vuoi considerare ?

j<chessBoard[0].size();j++){chessBoard[i][j] = number_chessBoard;number_chessBoard++;}}}
bool maxScore(vector<vector<int>> chessBoard, int n_queen,vector<vector<bool>> bitmap,int&punteggio){
    if(n_queen == chessBoard.size()){
        int processed_score = processSolution(chessBoard, bitmap);
        if(punteggio<processed_score){
            punteggio = processed_score;
        }
        return true;
    }
    bool res = false;
    for(int i = 0; i<chessBoard.size();i++){
        if(isSafe(bitmap, i, n_queen)){
            bitmap[i][n_queen]= true;
            res = res||maxScore(chessBoard, n_queen+1, bitmap, punteggio);
            bitmap[i][n_queen] = false;
        }
    }
    return res;
}
int processSolution(vector<vector<int>> chessBoard,vector<vector<bool>>bitmap){
    //printBitMap(bitmap);
    int sum = 0;
    for(int i = 0; i<bitmap.size();i++){
        for(int j = 0; j<bitmap[0].size(); j++){
            if(bitmap[i][j] == true){
                sum += chessBoard[i][j];
            }
        }
    }
    return sum;
}
bool isSafe(vector<vector<bool>> chessBoard,int row,int col){
    //Nfunzionerà anche da colonna

di inserimento
if(chessBoard[row][col]){
    return false;
}
for(int i = 0; i<chessBoard[0].size();i++){
    if(chessBoard[row][i]){
        return false;
    }
}
for(int i = 0; i<chessBoard.size();i++){
    if(chessBoard[i][col]){
        return false;
    }
}
//Diagonale destra
for(int i = row, j = col; i>=0 && j >= 0; i--, j--){
    if(chessBoard[i][j]){
        return false;
    }
}
for(int i = row, j = col; i<chessBoard.size() && j < chessBoard.size(); i++,j++){
    if(chessBoard[i][j]){
        return false;
    }
}
//Diagonale sinistra
for(int i = row, j = col; i<chessBoard.size() && j >= 0; i++, j--){
    if(chessBoard[i][j]){
        return false;
    }
}
for(int i = row, j = col; i>=0 && j < chessBoard.size(); i--, j++){
    if(chessBoard[i][j]){
        return false;
    }
}
return true;
}

11) Sudoku

#include <iostream>
#define SUDOKU_SIZE 9
#define EMPTY 0

using namespace std;

void stampa_matrice(int[][SUDOKU_SIZE]);
bool isSafe(int[][SUDOKU_SIZE],int,int,int);
bool backtracking(int[][SUDOKU_SIZE],int,int);

int main(int argc, const char * argv[])

int grid[SUDOKU_SIZE][SUDOKU_SIZE] = {{3,EMPTY,6,5,EMPTY,8,4,EMPTY,EMPTY},{5,2,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY},{EMPTY,8,7,EMPTY,EMPTY,EMPTY,EMPTY,3,1},{EMPTY,EMPTY,3,EMPTY,1,EMPTY,EMPTY,8,EMPTY},{9,EMPTY,EMPTY,8,6,3,EMPTY,EMPTY,5},{EMPTY,5,EMPTY,EMPTY,9,EMPTY,6,EMPTY,EMPTY},{1,3,EMPTY,EMPTY,EMPTY,EMPTY,2,5,EMPTY},{EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,EMPTY,7,4},{EMPTY,EMPTY,5,2,EMPTY,6,3,EMPTY,EMPTY},};
cout<<"Il sudoku da risolvere è il seguente"<<endl;
stampa_matrice(grid);
if(backtracking(grid, 0, 0)){
    cout<<"Sudoku risolto"<<endl;
    stampa_matrice(grid);
}else{
    cout<<"Non sono riuscito a risolvere il Sudoku"<<endl;
}
return 0;
}

void stampa_matrice(int sudoku[][SUDOKU_SIZE]){
    for(int i=0; i<SUDOKU_SIZE;i++){
        for(int j = 0; j<SUDOKU_SIZE;j++){
            cout<<sudoku[i][j]<<" ";
        }
        cout<<endl;
    }
}

bool backtracking(int sudoku[][SUDOKU_SIZE],int row,int col){
    if(row == SUDOKU_SIZE-1 && col == SUDOKU_SIZE){
        //BASECASE,

ho finito
return true;
}
if(col == SUDOKU_SIZE){
    //Devo passare alla successiva riga (Avrei anche potuto riempire le colonne)
    row ++;
    col = 0;
}
if(sudoku[row][col] > 0){
    //Se nella posizione già c'è un numero, non devo fare nulla
    return backtracking(sudoku, row, col+1);
}
for(int num = 1; num <= 9; num ++){
    if(isSafe(sudoku, row, col,num)){
        sudoku[row][col] = num;
        if(backtracking(sudoku, row, col+1)){
            return true;
        }
        //Vedo se la mia soluzione mi porta ad un risultato
    }
    sudoku[row][col] = EMPTY; //ROLLBACK, nel caso la soluzione non mi porti a nulla
    /*Difatti per ogni caso ho vari punti di ritorno, dunque se mi trovo qui significa che la mia successione di soluzioni non funziona, e devo azzerare tutti i passi*/
}
return false;
}

bool isSafe(int sudoku[][SUDOKU_SIZE],int row,int col,int num){
    //Vediamo se troviamo il numero nella riga
    for(int i = 0; i<SUDOKU_SIZE;i++){
        if(sudoku[row][i] == num){
            return false;
        }
    }
    //Vediamo se lo trovo sulla colonna
    for(int i = 0; i<SUDOKU_SIZE;i++){
        if(sudoku[i][col] == num){
            return false;
        }
    }
    //Vediamo se lo trovo nella sottomatrice 3x3
    int startRow = row - row % 3;
    int startCol = col - col % 3;
    for(int i = 0; i<3;i++){
        for(int j = 0; j<3;j++){
            if(sudoku[i+startRow][j+startCol] == num){
                return false;
            }
        }
    }
    return true;
}

i<SUDOKU_SIZE;i++){
    if(sudoku[i][col] == num){
        return false;
    }
}

// Vediamo se lo troviamo nel quadrato 3x3
int startRow = row - row%3;
int startCol = col - col%3;
for(int i = 0; i<SUDOKU_SIZE/3;i++){
    for(int j = 0; j<SUDOKU_SIZE/3;j++){
        if(sudoku[startRow+i][startCol+j] == num){
            return false;
        }
    }
}

return true;
}

12) SubsetSum backtracking

#include <iostream>
using namespace std;

bool backtrack(int*,int*,int,int,int);
void processSolution(int*,int*,int);
bool accept_solution(int*,int*,int,int);

int main(int argc, const char * argv[]) {
    int *A;
    int n,k;
    int *S;

    cout<<"Quanti elementi vuoi inserire nell'insieme A ?"<<endl;
    cin>>n;
    A = new int[n];
    S = new int[n];

    for(int i = 0; i<n;i++){
        cout<<"Inserire l'elemento "<<i<<"-esimo"<<endl;
        cin>>A[i];
    }

    cout<<"Quale e l'ammontare ? "<<endl;
    cin>>k;

    if(backtrack(A, S, k, 1, n)){
        cout<<"Abbiamo delle soluzioni."<<endl;
    } else {
        cout<<"Non abbiamo soluzioni."<<endl;
    }

    return 0;
}

soluzioni<<"<<endl;
}
else{
    cout<<"Non ci sono soluzioni"<<endl;
}
delete[] A;
delete[] S;
return 0;
}

bool backtrack(int* A_array, int* S_array, int k, int i, int n){
    bool there_are_solution = false;
    if(i>n){
        there_are_solution = false;
    }
    else if(accept_solution(S_array, A_array, n, k)){
        processSolution(S_array, A_array, n);
        there_are_solution = true;
    }
    else{
        int C[2] = {0,1};
        for(int j=0; j<2; j++){
            S_array[i] = C[j];
            if(backtrack(A_array, S_array, k, i+1, n)){
                there_are_solution = true;
            }
        }
    }
    return there_are_solution;
}

bool accept_solution(int* Sol, int* Values, int n, int k){
    int sum = 0;
    for(int j=0; j<n; j++){
        if(Sol[j] == 1){
            sum += Values[j];
        }
    }
    if(sum > k || sum < k){
        return false;
    }
    else{
        return true;
    }
}

void processSolution(int* Solution, int* Values, int n){
    cout<<"Insieme: ";
    int sum = 0;
    for(int j=0; j<n; j++){
        if(Solution[j] == 1){
            cout<<Values[j];
            sum += Values[j];
        }
    }
    cout<<" Con somma: "<<sum<<endl;
}

13) Homework 1.1
#include

<pre><code>&lt;iostream&gt;
#include &lt;cstring&gt;
using namespace std;

#define STRING_LEN 100

struct Node{
    char stringa[STRING_LEN];
    struct Node *next;
};

void buildLinkedList(Node**,int &amp;); //costruisce una lista
void invertLinkedList(Node*,Node **); //Inverte una lista
Node *invertLinkedList_2(Node*); //Inverte una lista modo 2
void printLinkedList(Node*,int); //Stampa una lista
void buildInCoda(Node**,int &amp;);

int main(int argc, const char * argv[]) {
    Node *head = NULL;
    int size;
    //buildLinkedList(&amp;head, size);
    buildInCoda(&amp;head, size);
    printLinkedList(head, size);
    Node *Shead = head;
    for(int i=0;i&lt;(size/2)-1;i++){
        Shead = Shead-&gt;next;
    }
    //Modo iterativo con puntatori inseguitori
    //invertLinkedList((Shead-&gt;next),&amp;(Shead));
    //Uso della ricorsione
    Shead-&gt;next = invertLinkedList_2(Shead-&gt;next);
    printLinkedList(head, size);
    return 0;
}

void buildLinkedList(Node**head,int &amp;n){
    //Chiaramente devo modificare il valore effettivo della head, dunque devo passare un riferimento int
</code></pre>

size_n;
cout<<"Inserire la lunghezza n della lista (la lista sarà poi di lunghezza 2n"<<endl;
cin>>size_n;
n = 2*size_n;
for(int i = 0; i<n;i++){
    Node *newNode = new Node;
    cin>> newNode->stringa;
    newNode->next = (*head);
    (*head) = newNode;
}
}

void buildInCoda(Node**head,int &n){
    int size_n;
    cout<<"Inserire la lunghezza n della lista (la lista sarà poi di lunghezza 2n"<<endl;
    cin>>size_n;
    n = 2*size_n;
    Node *tmp = (*head);
    for(int i = 0; i<n; i++){
        Node *elem = new Node;
        elem->next = NULL;
        cin>>elem->stringa;
        if(tmp == NULL){
            tmp = elem;
            (*head) = tmp;
        }else{
t