Ricorsione Avanzata

#include <stdio.h>

// Potenza in O(log n) invece di O(n)
double potenza(double base, int esp) {
    if (esp == 0) return 1.0;
    if (esp % 2 == 0) {
        double meta = potenza(base, esp/2);
        return meta * meta;            // Divide a metà
    }
    return base * potenza(base, esp-1);
}

// Massimo sottoarray (Kadane modificato con D&C)
int max_crossing_subarray(int arr[], int sx, int mid, int dx) {
    int sx_max = arr[mid], sx_sum = arr[mid];
    for (int i=mid-1; i>=sx; i--) {
        sx_sum += arr[i];
        if (sx_sum > sx_max) sx_max = sx_sum;
    }
    int dx_max = arr[mid+1], dx_sum = arr[mid+1];
    for (int i=mid+2; i<=dx; i++) {
        dx_sum += arr[i];
        if (dx_sum > dx_max) dx_max = dx_sum;
    }
    return sx_max + dx_max;
}

int max_subarray_dc(int arr[], int sx, int dx) {
    if (sx == dx) return arr[sx];
    int mid = (sx+dx)/2;
    int sx_max  = max_subarray_dc(arr, sx, mid);
    int dx_max  = max_subarray_dc(arr, mid+1, dx);
    int cross   = max_crossing_subarray(arr, sx, mid, dx);
    return sx_max > dx_max ? (sx_max > cross ? sx_max : cross)
                           : (dx_max > cross ? dx_max : cross);
}

// Contare le inversioni (D&C durante merge sort)
long long conta_inversioni(int arr[], int tmp[], int sx, int dx) {
    if (sx >= dx) return 0;
    int mid = (sx+dx)/2;
    long long inv = 0;
    inv += conta_inversioni(arr, tmp, sx, mid);
    inv += conta_inversioni(arr, tmp, mid+1, dx);

    // Merge e conta inversioni
    int i=sx, j=mid+1, k=sx;
    while (i<=mid && j<=dx) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else { tmp[k++] = arr[j++]; inv += (mid-i+1); }
    }
    while (i<=mid) tmp[k++]=arr[i++];
    while (j<=dx)  tmp[k++]=arr[j++];
    for(int l=sx;l<=dx;l++) arr[l]=tmp[l];
    return inv;
}

int main() {
    printf("2^10 = %.0f\n", potenza(2.0, 10));
    printf("3^20 = %.0f\n", potenza(3.0, 20));

    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n=9;
    printf("Max sottoarray: %d\n", max_subarray_dc(arr, 0, n-1));  // 6

    int arr2[] = {5,3,1,2,4};
    int tmp[5];
    printf("Inversioni in [5,3,1,2,4]: %lld\n",
           conta_inversioni(arr2, tmp, 0, 4));  // 7
    return 0;
}

#include <stdio.h>
#include <string.h>

#define MAX_N 12

int board[MAX_N];  // board[i] = colonna della regina nella riga i
int soluzioni = 0;

int valido(int riga, int col, int n) {
    for (int r=0; r<riga; r++) {
        if (board[r] == col) return 0;             // Stessa colonna
        if (abs(board[r]-col) == abs(r-riga)) return 0;  // Stessa diagonale
    }
    return 1;
}

void stampa_board(int n) {
    printf("Soluzione %d:\n", ++soluzioni);
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++)
            printf("%s ", j==board[i] ? "Q" : ".");
        printf("\n");
    }
    printf("\n");
}

void n_queens(int riga, int n, int stampa) {
    if (riga == n) {
        if (stampa) stampa_board(n);
        else soluzioni++;
        return;
    }
    for (int col=0; col<n; col++) {
        if (valido(riga, col, n)) {
            board[riga] = col;
            n_queens(riga+1, n, stampa);
            // Backtrack: la prossima iterazione sovrascrive board[riga]
        }
    }
}

int main() {
    // Mostra tutte le soluzioni per N=4
    soluzioni = 0;
    n_queens(0, 4, 1);
    printf("N=4: %d soluzioni\n\n", soluzioni);

    // Solo conta per N maggiori
    for (int n=1; n<=10; n++) {
        soluzioni = 0;
        n_queens(0, n, 0);
        printf("N=%2d: %5d soluzioni\n", n, soluzioni);
    }
    return 0;
}

#include <stdio.h>

#define N 9

int board[N][N] = {
    {5,3,0, 0,7,0, 0,0,0},
    {6,0,0, 1,9,5, 0,0,0},
    {0,9,8, 0,0,0, 0,6,0},
    {8,0,0, 0,6,0, 0,0,3},
    {4,0,0, 8,0,3, 0,0,1},
    {7,0,0, 0,2,0, 0,0,6},
    {0,6,0, 0,0,0, 2,8,0},
    {0,0,0, 4,1,9, 0,0,5},
    {0,0,0, 0,8,0, 0,7,9}
};

int valido_sudoku(int riga, int col, int num) {
    for(int i=0;i<N;i++) if(board[riga][i]==num || board[i][col]==num) return 0;
    int br=riga-riga%3, bc=col-col%3;
    for(int i=br;i<br+3;i++) for(int j=bc;j<bc+3;j++) if(board[i][j]==num) return 0;
    return 1;
}

int risolvi() {
    for(int r=0;r<N;r++) for(int c=0;c<N;c++) {
        if(board[r][c]==0) {
            for(int num=1;num<=9;num++) {
                if(valido_sudoku(r,c,num)) {
                    board[r][c]=num;
                    if(risolvi()) return 1;
                    board[r][c]=0;  // Backtrack
                }
            }
            return 0;  // Nessun numero valido → torna indietro
        }
    }
    return 1;  // Tutti i campi riempiti
}

void stampa() {
    for(int i=0;i<N;i++) {
        if(i%3==0&&i) printf("------+-------+------\n");
        for(int j=0;j<N;j++) {
            if(j%3==0&&j) printf("| ");
            printf("%d ", board[i][j]);
        }
        printf("\n");
    }
}

int main() {
    printf("Sudoku da risolvere:\n"); stampa();
    if(risolvi()) { printf("\nSoluzione:\n"); stampa(); }
    else printf("Nessuna soluzione!\n");
    return 0;
}

#include <stdio.h>
#include <string.h>

// =========== 1. FIBONACCI con DP ===========
long long fib_dp(int n) {
    if (n <= 1) return n;
    long long dp[n+1];
    dp[0]=0; dp[1]=1;
    for (int i=2; i<=n; i++) dp[i] = dp[i-1] + dp[i-2];
    return dp[n];
}

// =========== 2. ZAINO 0/1 (Knapsack) ===========
// Oggetti con peso e valore, zaino con capacità W.
// Massimizza il valore totale senza superare W.
int zaino(int pesi[], int valori[], int n, int W) {
    int dp[n+1][W+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1; i<=n; i++) {
        for (int w=0; w<=W; w++) {
            dp[i][w] = dp[i-1][w];  // Non prendo l'oggetto i
            if (pesi[i-1] <= w) {
                int prendo = dp[i-1][w-pesi[i-1]] + valori[i-1];
                if (prendo > dp[i][w]) dp[i][w] = prendo;
            }
        }
    }
    return dp[n][W];
}

// =========== 3. LCS (Longest Common Subsequence) ===========
int lcs(const char *s1, const char *s2) {
    int m=strlen(s1), n=strlen(s2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));

    for (int i=1; i<=m; i++)
        for (int j=1; j<=n; j++)
            if (s1[i-1]==s2[j-1]) dp[i][j] = dp[i-1][j-1]+1;
            else dp[i][j] = dp[i-1][j]>dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];

    // Ricostruzione della LCS
    printf("LCS: ");
    int i=m, j=n;
    char result[100]; int ri=0;
    while (i>0 && j>0) {
        if (s1[i-1]==s2[j-1]) { result[ri++]=s1[i-1]; i--; j--; }
        else if (dp[i-1][j]>dp[i][j-1]) i--;
        else j--;
    }
    result[ri]='\0';
    // Inverti
    for(int a=0,b=ri-1;a<b;a++,b--){char t=result[a];result[a]=result[b];result[b]=t;}
    printf("%s (lunghezza %d)\n", result, ri);
    return dp[m][n];
}

// =========== 4. COIN CHANGE ===========
// Quante monete (minimo) per fare amount?
int coin_change(int monete[], int n, int amount) {
    int dp[amount+1];
    for(int i=0;i<=amount;i++) dp[i]=amount+1;  // "Infinito"
    dp[0]=0;
    for(int a=1;a<=amount;a++) {
        for(int i=0;i<n;i++) {
            if(monete[i]<=a && dp[a-monete[i]]+1 < dp[a])
                dp[a] = dp[a-monete[i]]+1;
        }
    }
    return dp[amount]>amount ? -1 : dp[amount];
}

int main() {
    printf("Fib(30) = %lld\n", fib_dp(30));

    int pesi[]   = {2, 3, 4, 5};
    int valori[] = {3, 4, 5, 6};
    printf("Zaino (cap=8): valore max = %d\n", zaino(pesi,valori,4,8));

    printf("LCS di 'ABCBDAB' e 'BDCAB': ");
    lcs("ABCBDAB", "BDCAB");

    int monete[] = {1, 5, 10, 25};
    printf("Monete per 36 centesimi: %d\n", coin_change(monete,4,36));
    return 0;
}

#include <stdio.h>
#include <string.h>

// Quante operazioni (insert, delete, replace) servono per trasformare s1 in s2?
int edit_distance(const char *s1, const char *s2) {
    int m=strlen(s1), n=strlen(s2);
    int dp[m+1][n+1];

    for(int i=0;i<=m;i++) dp[i][0]=i;  // Elimina tutti i char di s1
    for(int j=0;j<=n;j++) dp[0][j]=j;  // Inserisci tutti i char di s2

    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(s1[i-1]==s2[j-1]) dp[i][j]=dp[i-1][j-1];
            else {
                int ins=dp[i][j-1]+1, del=dp[i-1][j]+1, rep=dp[i-1][j-1]+1;
                dp[i][j]=ins<del?(ins<rep?ins:rep):(del<rep?del:rep);
            }
        }
    }
    return dp[m][n];
}

int main() {
    printf("Edit dist('kitten','sitting'): %d\n", edit_distance("kitten","sitting")); // 3
    printf("Edit dist('sunday','saturday'): %d\n", edit_distance("sunday","saturday")); // 3
    printf("Edit dist('abc','abc'): %d\n", edit_distance("abc","abc")); // 0
    return 0;
}