/* =============================================================== */
/*   CORSO DI PROGRAMMAZIONE IN C (C89)                            */
/*   Claudio Fornaro                                               */
/*   Ver. 3 - 2021                                                 */
/*   23-Ricorsione_Soluzioni.txt                                   */
/* =============================================================== */

/* =============================================================== */
/*   1                                                             */
/* =============================================================== */

/* NON TAIL */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSTR 100

int palin(char *s, int lung);

int main()
{
   char stringa[MAXSTR];

   printf("Inserire la stringa: ");
   gets(stringa);

   if (palin(stringa, strlen(stringa)))
      printf("La stringa e' palindroma\n");
   else
      printf("La stringa non e' palindroma\n");
      
   return EXIT_SUCCESS;
}

int palin(char *s, int lung)
{
   if (lung <=1 )  /* caso di base */
      return 1;    /* e' palindroma */
   return *s == *(s+lung-1) && palin(++s, lung-2) ;
   /* da' 1 se palindroma, 0 altrimenti se i chr estremi sono uguali
      e la stringa centrale rimanente e' palindroma (riduz. della 
      complessita') restituisce 1 */
}


/* Altra soluzione */
/* TAIL */

int palin(char *s, int lung)
{
   if (lung <=1 )              /* caso di base 1: e' palindroma */
      return 1;
   else if (*s != *(s+lung-1)) /* caso di base 2: non palindroma */
      return 0;
   return palin(++s, lung-2) ; /* se i chr estremi sono uguali e la
                                  stringa centrale rimanente e' 
                                  palindroma (riduz. complessita' */
}


/* =============================================================== */
/*   2                                                             */
/* =============================================================== */

/* NON TAIL */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSTR 100

void stampa(char *s);

int main()
{
   char stringa[MAXSTR];

   printf("Inserire la stringa: ");
   gets(stringa);

   stampa(stringa);
      
   return EXIT_SUCCESS;
}

void stampa(char *s)
{
   if (*s == '\0')
      return;      /* caso di base */
   else            
   {
      stampa(s+1); /* stampa il primo carattere di s+1 */
      putchar(*s); /* e poi quello di s */
      return;
   }
}


/* Altra soluzione (piu' compatta, ma identica) */
/* NON TAIL */

void stampa(char *s) 
{
   if (*s != '\0')
   {
      stampa(s+1); /* stampa il primo carattere di s+1 */
      putchar(*s); /* e poi quello di s */
   }
}


/* =============================================================== */
/*   3                                                             */
/* =============================================================== */

/* NON TAIL */

#include <stdio.h>
#include <stdlib.h>
#define LEN 10

#define min(A,B) ((A)<(B))?(A):(B)

int cercaMin(int v[], int len);

int main()
{
   int vett[LEN], i;

   for (i=0; i<LEN; i++)
   {
      printf("Inserire il %do valore: ", i+1);
      scanf("%d", &vett[i]);
   }

   printf("Il minimo vale: %d\n", cercaMin(vett,LEN));
      
   return EXIT_SUCCESS;
}

int cercaMin(int v[], int len)
{
   int m;  /* serve la variabile m perche' chiama una macro */

   if (len==1)
      return v[0];
   else
   {
      m = cercaMin(v+1, len-1);
      return min( v[0], m );
   }
}


/* =============================================================== */
/*   4                                                             */
/* =============================================================== */

/* NON TAIL */

#include <stdio.h>
#include <stdlib.h>

void muovi(int n, int from, int to, int temp);

int main()
{
   int quanti;
   printf("Quanti dischi? ");
   scanf("%d", &quanti);
   muovi(quanti,1,2,3); /* sposta i dischi da 1 a 2 usando 3*/
   return EXIT_SUCCESS;
}

void muovi(int n, int from, int to, int temp)
{
   if (n>0)
   {
      muovi(n-1, from, temp, to);
      printf("%d -> %d\n", from, to);
      muovi(n-1, temp, to, from);
   }
}

/*
################ OUTPUT #####################
Quanti dischi? 3
1 -> 2
1 -> 3
2 -> 3
1 -> 2
3 -> 1
3 -> 2
1 -> 2
*/


/* Altra soluzione con visualizzazione delle chiamate */

#include <stdio.h>
#include <stdlib.h>
#define spazi(N) spaz+41-2*(N)
/* spazi(N) restituisce il puntatore ad una stringa di 2N spazi */

void muovi(int n, int from, int to, int temp);
char spaz[41]="                                           ";
int quanti;	

int main()
{
   printf("Quanti dischi? ");
   scanf("%d", &quanti);
   printf("spost|chiam| \n");
   muovi(quanti,1,2,3); /* sposta i dischi da 1 a 2 usando 3*/
   return EXIT_SUCCESS;
}


void muovi(int n, int from, int to, int temp)
{
   static int count=0;

   if (n>0)
   {
      printf("     | %3d | ", quanti-n+1);
      printf("%s(muovi %d disc%s da %d a %d usando %d)\n", 
             spazi(quanti-n), n, n==1?"o":"hi", from, to, temp);
      muovi(n-1, from, temp, to);

      printf(" %-4d| %3d | ", ++count, quanti-n+1);
      printf("%s%d -> %d\n", spazi(quanti-n), from, to);
      muovi(n-1, temp, to, from);
   }
}


/* Altra soluzione con animazione degli spostamenti */

#include <stdio.h>
#include <stdlib.h>
#define RITARDO 10000000   /* modificare a seconda della macchina */
void muovi(int,int,int,int);
void visualizza(void);
void sleep(void);

/* palo[i][0] tiene il conto di quanti sono i dischi nel palo i*/
int palo[3][70] = {0}; 
int quanti;
int chiamate = 0;

int main()
{
   int i;
  
   printf("Quanti dischi? ");
   scanf("%d", &quanti);
   palo[0][0] = quanti;
   palo[1][0] = palo[2][0] = 0;  /* sono gia' impostate a 0 */
   for (i=1; i<= quanti; i++)
      palo[0][i] = quanti - i + 1;
   visualizza();
   muovi(quanti, 0, 1, 2);
   visualizza();
   return EXIT_SUCCESS;
}

void muovi(int n, int pi, int pf, int pt)
{
   chiamate++;
   visualizza();
   if (n == 1)
   {
      /* printf ("%d -> %d\n", pi, pf); */
      /* toglie da testa di palo[pi] e mette in testa a palo[pf] */
        palo[pf][palo[pf][0]+1]=palo[pi][palo[pi][0]];
        palo[pf][0]++;
        palo[pi][0]--;
   }
   else
   {
      muovi(n-1, pi, pt, pf);
      /* printf ("%d -> %d\n", pi, pf); */
      /* toglie da testa di palo[pi] e mette in testa a palo[pf] */
        palo[pf][palo[pf][0]+1]=palo[pi][palo[pi][0]];
        palo[pf][0]++;
        palo[pi][0]--;
      muovi(n-1, pt, pf, pi);
   }
   chiamate--;
   visualizza();
}


void sleep(void)
{
  long j;
  for (j=RITARDO; j>0; j--)
  {
    j=-j;  /* deve solo perdere tempo... */
    j=-j;
  }
}

void visualizza()
{
   static int cont = 0;
   int p, i;
   system("CLS");   /* per Windows */
   /* system("clear"); per Unix/Linux */
   printf("Passo: %3d (chiamate aperte: %3d)\n", cont++, chiamate);
   for (p=0; p<=2; p++)
   {
      printf("%d>", p+1);
      for (i=1; i<=palo[p][0]; i++)
         printf("%2d ", palo[p][i]);
      printf("\n");
   }
   sleep();
}


/* =============================================================== */
/*   5                                                             */
/* =============================================================== */

/* TAIL */

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int cercaLin(int v[], int x, int len);

int main()
{
   int vett[MAX], x, i;

   for (i=0; i<MAX; i++)
   {
      printf("Inserire il %do valore: ", i+1);
      scanf("%d", &vett[i]);
   }

   printf("Valore da cercare: ");
   scanf("%d", &x);

   if (cercaLin(vett, x, MAX) >= 0)
      printf("Trovato\n");
   else
      printf("Non trovato\n");
      
   return EXIT_SUCCESS;
}

/* cerca dalla fine del vettore */
int cercaLin(int v[], int x, int len)
{
   if (len == 0)           /* caso di base: non trovato */
      return -1;
   else if (v[len-1] == x) /* caso di base: l'ultimo carattere e' 
                              quello cercato */
      return len-1;
   else                    /* altrimenti accorcia la stringa, 
                              riducendo la complessita' */
      return cercaLin(v, x, len-1); 
}

/* versione con accumulatore static */
/* cerca dall'inizio del vettore */
/* notare che non c'e' l'accumulatore start tra i parametri */
int cercaLin(int v[], int x, int len)
{
   static int start = 0;   /* accumulatore static */
   if (start == len)       /* caso di base: non trovato */
      return -1;
   else if (v[start] == x) /* caso di base: il carattere e' quello 
                              cercato in pos */
      return start;
   else                    /* altrimenti parte da start+1, riducendo
                              la complessita' */
   {
      start++;
      return cercaLin(v, x, len);   /* sempre uguali in tutte */
   }                                /*  le chiamate */   
}

/* Altra soluzione */

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

int cercaLin(int v[], int x, int len, int start);

int main()
{
   int vett[MAX], x, i;

   for (i=0; i<MAX; i++)
   {
      printf("Inserire il %do valore: ", i+1);
      scanf("%d", &vett[i]);
   }

   printf("Valore da cercare: ");
   scanf("%d", &x);

   if (cercaLin(vett, x, MAX, 1) >= 0)
      printf("Trovato\n");
   else
      printf("Non trovato\n");
      
   return EXIT_SUCCESS;
}

/* cerca dall'inizio del vettore */
/* start e' l'accumulatore */
int cercaLin(int v[], int x, int len, int start)
{
   if (start == len)       /* caso di base: non trovato */
      return -1;
   else if (v[start] == x) /* caso di base: il carattere e' quello
                              cercato in start */
      return start;
   else                    /* altrimenti parte da start+1, riducendo
                              la complessita' */
      return cercaLin(v, x, len, start+1); 
}


/* =============================================================== */
/*   6                                                             */
/* =============================================================== */

/* TAIL */

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

void ordina(int v[], int l);
int cercaDicot(int v[], int x, int left, int right);

int main()
{
   int vett[MAX], y, i;

   for (i=0; i<MAX; i++)
   {
      printf("Inserire il %do valore: ", i+1);
      scanf("%d", &vett[i]);
   }

   ordina(vett, MAX);

   printf("Valore da cercare: ");
   scanf("%d", &y);

   if (cercaDicot(vett, y, 0, MAX-1) >= 0)
      printf("Trovato\n");
   else
      printf("Non trovato\n");
      
   return EXIT_SUCCESS;
}

void ordina(int v[], int len)
{
   int i, j, jmin;
   char t;
   
   for (i=0; i<len-1; i++)
   {
      jmin = i;
      for (j=i+1; j<len; j++)
         if (v[j] < v[jmin])
            jmin = j;
         
         t=v[jmin];
         v[jmin]=v[i];
         v[i]=t;
   }
}

int cercaDicot(int v[], int x, int left, int right)
{
   int c;

   if (left > right)
      return -1;
   else
   {
      c=(left+right)/2;
      if (x > v[c])
         /* cerca nella meta' destra */
         return cercaDicot(v, x, c+1, right); 
      else if (x < v[c])
         /* cerca nella meta' destra */
         return cercaDicot(v, x, left, c-1);
      else
         /* trovato */
         return c;
   }
}


/* =============================================================== */
/*   7                                                             */
/* =============================================================== */

/* TAIL */

#include <stdio.h>
#include <stdlib.h>
#define LEN 10

#define swap(A,B) do{ static int t; t=A; A=B; B=t; }while(0)

void selectionSort(int v[], int len);

int main()
{
   int vett[LEN], i;

   for (i=0; i<LEN; i++)
   {
      printf("Inserire il %do valore: ", i+1);
      scanf("%d", &vett[i]);
   }

   printf("VALORI INTRODOTTI\n");
   for (i=0; i<LEN; i++)
      printf("%d ", vett[i]);

   selectionSort(vett, LEN);

   printf("VALORI RIORDINATI\n");
   for (i=0; i<LEN; i++)
      printf("%d ", vett[i]);

   return EXIT_SUCCESS;
}

void selectionSort(int v[], int len)
{
   int i, minIndex;

   if (len > 1)
   {
      minIndex = 0;
      for (i=1; i<len; i++) /* cerca il minimo */
         if (v[i] < v[minIndex])
            minIndex = i;

      if (v[minIndex] < v[0]) /* e lo mette al primo posto */
         swap(v[minIndex], v[0]);

      selectionSort(v+1, len-1);
   }
  return;    /* caso di base */
}


/* =============================================================== */
/*   8                                                             */
/* =============================================================== */

/* ITERATIVA */
/* relativa alla prima soluzione */
int cercaLin(int v[], int x, int len)
{

   while (!(len == 0 || v[len-1] == x)) /* (1) */
      len = len-1;  /* accorcia la stringa: riduce la complessita' */
      
   if (len == 0)
      return -1;
   else
      return len-1;
}

/* Nota
   Usando il teorema di De Morgan si puo' riscrivere senza i NOT:
   (len != 0 && v[len-1] != x)
*/


/* =============================================================== */
/*   9                                                             */
/* =============================================================== */

/* ITERATIVA */

int cercaDicot(int v[], int x, int left, int right)
{
   int c;

   while (!(left > right))
   {
      c=(left+right)/2;
      if (x > v[c])
         /* cerca nella meta' destra, riduz complessita' */
         left = c+1;
      else if (x < v[c])
         /* cerca nella meta' destra, riduce la complessita' */
         right = c-1;
      else
          /* trovato */
         return c;
   }
   return -1;
}


/* =============================================================== */
/*  10                                                             */
/* =============================================================== */

/* ITERATIVA */

void selectionSort(int v[], int len)
{
   int i, minIndex;

   while ((len > 1))
   {
      minIndex = 0;
      for (i=1; i<len; i++)         /* cerca il minimo */
         if (v[i] < v[minIndex])
            minIndex = i;

      if (v[minIndex] < v[0])       /* e lo mette al primo posto */
         swap(v[minIndex], v[0]);

      v++; len--;
   }
}