////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE ConversioneDiBase.java
////////////////////////////////////////////////////////////////////////////////

import java.util.Scanner;

public class ConversioneDiBase {
    
    public static int cifraEsadecimale(char c) {
    	if('0' <= c && c <= '9') 
    	    return c - '0';
    	else // 'A' <= c && c <= 'F'
    	    return c - 'A' + 10;
    }
    
    public static int base16ToBase10(String s) {
	int ris = 0;
	
	for(int i = 0; i < s.length(); i++) {
	    int c = cifraEsadecimale(s.charAt(i));
	    ris = ris * 16 + c;
	}
	
	return ris;
    }
    
    public static void main(String[] args) {
	System.out.println("Conversione da base 16 a base 10");

	Scanner input = new Scanner(System.in);
	
	System.out.print("Numero da convertire: ");
	String s = input.next().toUpperCase();
	int n = base16ToBase10(s);
	System.out.println("[" + s + "]_16 = [" + n + "]_10");
    }
    
}


////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE FunzioneRicorsiva1.java
////////////////////////////////////////////////////////////////////////////////


/*
 * Implementare una funzione f(i) ricorsiva che riceve un intero e restituisce un razionale.
 * Per i=0 la funzione restituisce 1/2, per i>0 restituisce f(i-1)/2, ovvero f(i-1) diviso 2.
 * 
 * Implementare inoltre un main che stampi la somma dei primi N razionali della sequenza,
 * per ogni N = 0, ..., 9.
 * 
 * Fare uso della classe Razionale.
 */

public class FunzioneRicorsiva1 {

    public static Razionale f(int i) {
	if(i == 0)
	    return new Razionale(1, 2);
	
	Razionale f1 = f(i-1);
	f1.moltiplica(new Razionale(1, 2));
	return f1;	
    }
    
    public static void main(String[] args) {
	Razionale s = new Razionale();
	for(int i = 0; i < 10; i++) {
	    s.somma(f(i));
	    System.out.println(i + ": " + s + " = " + s.toDouble());
	}
    }
    
}



////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE MediaRazionali.java
////////////////////////////////////////////////////////////////////////////////

/*
 * Implementare un programma che determini la media di una sequenza di numeri razionali
 * terminata da un numero razionale negativo.
 * 
 * Fare uso della classe Razionale.
 * 
 * ATTENZIONE: I metodi setNumeratore(int) e setDenominatore(int) della classe Razionale 
 * invocano il metodo semplifica(). Pertanto, la media deve essere calcolata dividendo
 * la somma dei valori per il numero di elementi nella sequenza (come di consueto).
 */

import java.util.Scanner;

public class MediaRazionali {

    public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	
	Razionale media = new Razionale();
	int count = 0;
	
	System.out.println("Inserisci una sequenza di numeri razionali (coppie di interi) terminata da un numero razionale negativo.");
	Razionale x = Razionale.leggi(input);
	while(x.maggioreDiOUgualeA(new Razionale())) {
	    media.somma(x);
	    count++;
	    
	    x = Razionale.leggi(input);
	}
	
	media.dividi(new Razionale(count));
	System.out.println("La media e': " + media + " = " + media.toDouble());
    }
    
}


////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE OperazioniPolinomi.java
////////////////////////////////////////////////////////////////////////////////

import java.util.Scanner;

public class OperazioniPolinomi {
    
    public static void main(String[] args) {
    	Scanner input = new Scanner(System.in);
    	PolinomioCoefficienteRazionali p1 = PolinomioCoefficienteRazionali.leggi(input);
    	System.out.println("Il PolinomioCoefficienteRazionali inserito e': " + p1);
    	PolinomioCoefficienteRazionali p2 = PolinomioCoefficienteRazionali.leggi(input);
    	System.out.println("Il PolinomioCoefficienteRazionali inserito e': " + p2);
    	
    	if(p1.equals(p2))
    	   	System.out.println("I due polinomi sono uguali");
    	else
    	   	System.out.println("I due polinomi sono diversi");

     	PolinomioCoefficienteRazionali p3 = p1.somma(p2);
    	System.out.println("Il PolinomioCoefficienteRazionali risultante dalla loro somma e': " + p3);

     	PolinomioCoefficienteRazionali p4 = p1.sottrai(p2);
    	System.out.println("Il PolinomioCoefficienteRazionali risultante dalla loro differenza e': " + p4);
    	
    	System.out.println("Inserisci un valore intero per l'incognita x:");
    	Razionale x = Razionale.leggi(input);
    	System.out.println("Il valore del primo PolinomioCoefficienteRazionali per x=" + x + " e': " + p1.valuta(x));
    	
    	System.out.println("Inserisci un intervallo in cui cercare eventuali radici (intere) del primo PolinomioCoefficienteRazionali:");
    	System.out.print("Estremo iniziale: ");
    	int inizio = input.nextInt();
    	System.out.print("Estremo finale: ");
    	int fine = input.nextInt();
    	boolean esisteRadice = false;
    	for(int i=inizio; i<=fine; i++)
    		if(p1.eRadice(new Razionale(i))){
    			System.out.println("L'intero " + i + " e' una radice del PolinomioCoefficienteRazionali " + p1);
    			esisteRadice = true;
    		}
    	if(!esisteRadice)
			System.out.println("Nessuna radice (intera) nell'intervallo considerato");

    }
    
}


////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE OrdinaFrase.java
////////////////////////////////////////////////////////////////////////////////


import java.util.Scanner;


public class OrdinaFrase {

    public static int contaParole(String frase) {
	int count = 0;
	for(int i = 0; i < frase.length(); i++)
	    if(frase.charAt(i) == '-')
		count++;
	return count + 1;
    }
    
    public static String prossimaParola(String frase, int start) {
	String ris = "";
	while(start < frase.length() && frase.charAt(start) != '-') {
	    ris += frase.charAt(start);
	    start++;
	}
	return ris;
    }
    
    public static String[] separaParole(String frase) {
	int n = contaParole(frase);
	String[] parole = new String[n];
	
	int j = 0;
	for(int i = 0; i < n; i++) {
	    parole[i] = prossimaParola(frase, j);
	    j += parole[i].length() + 1;
	}
	
	return parole;
    }
    
    public static void merge(String[] a, int inf, int mid, int sup) {
	String[] tmp = new String[a.length];
	
	int i = inf;   // a[inf] ... a[mid]
	int m = mid+1; // a[mid+1] ... a[sup]
	int t = inf;   // tmp[inf] ... tmp[sup]
	
	while(i <= mid && m <= sup) {
	    if(a[i].compareTo(a[m]) <= 0) {
		tmp[t] = a[i];
		t++;
		i++;
	    }
	    else {
		tmp[t] = a[m];
		t++;
		m++;
	    }
	}
	
	while(i <= mid) {
	    tmp[t] = a[i];
	    t++;
	    i++;
	}
	
	while(m <= sup) {
	    tmp[t] = a[m];
	    t++;
	    m++;
	}
	
	for(i = inf; i <= sup; i++)
	    a[i] = tmp[i];
    }
    
    public static void mergeSort(String[] a, int inf, int sup) {
	if(inf < sup) {
	    int mid = (inf + sup) / 2;
	    mergeSort(a, inf, mid);
	    mergeSort(a, mid+1, sup);
	    merge(a, inf, mid, sup);
	}
    }
    
    public static String concatena(String[] parole) {
	String ris = parole[0];
	for(int i = 1; i < parole.length; i++)
	    ris += '-' + parole[i];
	return ris;
    }
    
    public static String ordina(String frase) {
	String[] parole = separaParole(frase);
	mergeSort(parole, 0, parole.length - 1);
	
	String ris = concatena(parole);
	return ris;
    }
    
    public static void main(String[] args) {
	System.out.println("Ordinamento frase");

	Scanner input = new Scanner(System.in);
	
	System.out.print("Frase da ordinare (piu' parole separate da un trattino): ");
	String frase = input.next();
	String fraseOrdinata = ordina(frase);
	System.out.println("La frase ordinata e': " + fraseOrdinata);
    }
    
}


////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE PolinomioCoefficienteRazionali.java
////////////////////////////////////////////////////////////////////////////////

import java.util.Scanner;

public class PolinomioCoefficienteRazionali {

    private int grado;
    private Razionale coeff[];

    private PolinomioCoefficienteRazionali(int g) {
	   grado = g;
	   coeff = new Razionale[g+1];
    }

    public PolinomioCoefficienteRazionali(PolinomioCoefficienteRazionali p) {
		grado = p.grado;
		coeff = new Razionale[grado+1];
		for(int i=0; i<coeff.length; i++)
			coeff[i].set(p.coeff[i]);
    }
    
    // Versione semplice
/*    public String toString() {
    	String output = "";
    	for(int i=grado; i>=0; i--)
    		if(coeff[i] != 0) {
    			if(coeff[i] > 0)
    				output += "+";
   				output += coeff[i] + "x^" + i;
    		}
    	return output;
    }
*/
    // Versione + sofisticata
    public String toString() {
    	String output = "";
    	for(int i=grado; i>=0; i--)
    		if(coeff[i].diversoDa(new Razionale())) {
    			if(coeff[i].maggioreDi(new Razionale()) && i < grado)
    				output += "+";
    			if(coeff[i].equals(new Razionale(-1)) && i > 0)
    				output += "-";
    			else
    				if(coeff[i].diversoDa(new Razionale(1)) || i == 0)
    					output += coeff[i];
    			if(i > 0)
    				output += "x";
    			if(i > 1)
    				output += "^" + i;;
    		}
    	return output;
    }
    
    public int getGrado() {
        return grado;
    }
    
    public Razionale getTermine(int g) {
    	if(g < coeff.length)
    		return coeff[g];
    	else
    		return new Razionale();
    }
    
    public void setTermine(int g, Razionale t) {
    	if(g < coeff.length)
    		coeff[g].set(t);
    }
    
    public boolean equals(PolinomioCoefficienteRazionali p) {
    	if(grado != p.grado)
    		return false;
    	for(int i=0; i<coeff.length; i++)
    		if(coeff[i].diversoDa(p.coeff[i]))
    			return false;
    	return true;
    }
    
    public PolinomioCoefficienteRazionali perCostante(Razionale c) {
    	PolinomioCoefficienteRazionali ris = new PolinomioCoefficienteRazionali(grado);
    	for(int i=0; i<=grado; i++) {
    		ris.coeff[i] = new Razionale(coeff[i]);
    		ris.coeff[i].moltiplica(c);
    	}
    	return ris;
    }
    
    public PolinomioCoefficienteRazionali somma(PolinomioCoefficienteRazionali p) {
    	PolinomioCoefficienteRazionali somma;
    	if(grado > p.grado)
    		somma = new PolinomioCoefficienteRazionali(grado);
    	else
    		somma = new PolinomioCoefficienteRazionali(p.grado);

    	int i = 0;
    	while(i<=grado && i<=p.grado) {
    		somma.coeff[i] = new Razionale(coeff[i]);
    		somma.coeff[i].somma(p.coeff[i]);
    		i++;
    	}
    	while(i<=grado) {
    		somma.coeff[i] = new Razionale(coeff[i]);
    		i++;
    	}
    	while(i<=p.grado) {
    		somma.coeff[i] = new Razionale(p.coeff[i]);
    		i++;
    	}
    	return somma;
    }
    
    public PolinomioCoefficienteRazionali sottrai(PolinomioCoefficienteRazionali p) {
    	return somma(p.perCostante(new Razionale(-1)));
    }
    
    public Razionale valuta(Razionale x) {
    	Razionale val = new Razionale();
    	for(int i=0; i<=grado; i++) {
    	    Razionale tmp = new Razionale(1);
    	    for(int j = 0; j < i; j++)
    		tmp.moltiplica(x);
    	    
    	    tmp.moltiplica(coeff[i]);
    	    val.somma(tmp);
    	}
    	return val;
    }
    
    public boolean eRadice (Razionale x) {
    	return valuta(x).ugualeA(new Razionale());
    }
    
    public static PolinomioCoefficienteRazionali leggi(Scanner input) {
    	int g;
    	do {
    		System.out.print("Grado del polinomio: ");
    		g = input.nextInt();
    		if(g < 0)
    			System.out.println("Il grado di un polinomio non pu? essere un numero negativo!!!");
    	} while(g < 0);
    	PolinomioCoefficienteRazionali pol = new PolinomioCoefficienteRazionali(g);
    	System.out.println("Inserisci i coefficienti del polinomio per grado decrescente. ");
    	for (int i=g; i>=0; i--) {
    		System.out.print("Grado " + i + ": ");
    		pol.coeff[i] = Razionale.leggi(input);
    		}
    	return pol;
    }
    
}


////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE ProdottoRazionali.java
////////////////////////////////////////////////////////////////////////////////

/*
 * Implementare un programma che determini il prodotto di una sequenza di numeri razionali
 * terminata da un numero razionale negativo. Il programma deve inoltre stabilire se 
 * tale prodotto è minore di 12/7 (dodici settimi) o meno.
 * 
 * Fare uso della classe Razionale.
 */

import java.util.Scanner;

public class ProdottoRazionali {

    public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	
	Razionale p = new Razionale(1);
	
	System.out.println("Inserisci una sequenza di numeri razionali (coppie di interi) terminata da un numero razionale negativo.");
	Razionale x = Razionale.leggi(input);
	while(x.maggioreDiOUgualeA(new Razionale())) {
	    p.moltiplica(x);
	    
	    x = Razionale.leggi(input);
	}
	
	System.out.println("Il prodotto e': " + p + " = " + p.toDouble());
	
	Razionale r = new Razionale(12, 7);
	if(p.minoreDi(r))
	    System.out.println("Il prodotto e' minore di " + r + " = " + r.toDouble());
	else
	    System.out.println("Il prodotto non e' minore di " + r + " = " + r.toDouble());
     }
    
}


////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE Razionale.java
////////////////////////////////////////////////////////////////////////////////

import java.util.Scanner;


public class Razionale {

    private int numeratore;
    private int denominatore;

    public Razionale(int numeratore, int denominatore) {
	this.numeratore = numeratore;
	this.setDenominatore(denominatore);
    }

    public Razionale(int numeratore) {
	this.numeratore = numeratore;
	this.denominatore = 1;
    }
    
    public Razionale() {
	this.numeratore = 0;
	this.denominatore = 1;
    }
    
    public Razionale(Razionale r) {
	this.set(r);
    }
    
    public String toString() {
	return this.numeratore + "/" + this.denominatore;
    }
    
    public double toDouble() {
	return this.numeratore / (double) this.denominatore;
    }
    
    public int getNumeratore() {
        return numeratore;
    }
    
    public void setNumeratore(int numeratore) {
        this.numeratore = numeratore;
        this.semplifica();
    }
    
    public int getDenominatore() {
        return denominatore;
    }
    
    public void setDenominatore(int denominatore) {
	if(denominatore != 0) {
	    this.denominatore = denominatore;
	    this.semplifica();
	}
	else  // se denominatore e' 0 lo settiamo a 1 per evitare una divisione per zero 
	      // (ma l'utente dovrebbe evitare di settare il denominatore a zero)
	    this.denominatore = 1;
    }
    
    public void set(Razionale r) {
	this.numeratore = r.numeratore;
	this.denominatore = r.denominatore;
    }
    
    private void semplifica() {
	if(this.denominatore < 0) {
	    this.numeratore *= -1;
	    this.denominatore *= -1;
	}
	
	int d = Razionale.mcd(Math.abs(this.numeratore), denominatore);
	this.numeratore /= d;
	this.denominatore /= d;
    }
    
    private static int mcd(int a, int b) {
	while(true) {
	    if(a == 0)
		return b;
	    if(b == 0)
		return a;
	    
	    if(a > b)
		a -= b;
	    else
		b -= a;
	}
    }

    public boolean ugualeA(Razionale r) {
	return this.toDouble() == r.toDouble();
    }
    public boolean diversoDa(Razionale r) {
	return !this.ugualeA(r);
    }
    public boolean minoreDi(Razionale r) {
	return this.toDouble() < r.toDouble();
    }
    public boolean minoreDiOUgualeA(Razionale r) {
	return this.toDouble() <= r.toDouble();
    }
    public boolean maggioreDi(Razionale r) {
	return this.toDouble() > r.toDouble();
    }
    public boolean maggioreDiOUgualeA(Razionale r) {
	return this.toDouble() >= r.toDouble();
    }
    
    public void moltiplica(Razionale r) {
	this.numeratore *= r.numeratore;
	this.denominatore *= r.denominatore;
	this.semplifica();
    }
    
    public void dividi(Razionale r) {
	Razionale tmp = new Razionale(r);
	tmp.inverti();
	this.moltiplica(tmp);
    }
    
    public void inverti() {
	if(this.numeratore != 0) {
	    int tmp = this.numeratore;
	    this.numeratore = this.denominatore;
	    this.denominatore = tmp;
	    this.semplifica();
	}
    }

    public void somma(Razionale r) {
	this.numeratore = this.numeratore * r.denominatore + r.numeratore * this.denominatore;
	this.denominatore *= r.denominatore;
	this.semplifica();
    }
    
    public void sottrai(Razionale r) {
	Razionale tmp = new Razionale(r);
	tmp.moltiplica(new Razionale(-1));
	this.somma(tmp);
    }
    
    public static Razionale leggi(Scanner input) {
	System.out.print("Numeratore: ");
	int n = input.nextInt();
	System.out.print("Denominatore: ");
	int d = input.nextInt();
	System.out.println();
	return new Razionale(n, d);
    }
    
}



////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE SequenzaStrettmenteCrescente.java
////////////////////////////////////////////////////////////////////////////////

/*
 * Implementare un programma che determini se una sequenza di numeri razionali
 * terminata da un numero razionale negativo e' strettamente crescente o meno.
 * 
 * Fare uso della classe Razionale.
 */

import java.util.Scanner;

public class SequenzaStrettamenteCrescente {

    public static void main(String[] args) {
	Scanner input = new Scanner(System.in);

	System.out.println("Inserisci una sequenza di numeri razionali (coppie di interi) terminata da un numero razionale negativo.");
	
	boolean strettamenteCrescente = true;
	Razionale prec = Razionale.leggi(input);
	Razionale succ = Razionale.leggi(input);
	
	while(succ.maggioreDiOUgualeA(new Razionale())) {
	    if(!succ.maggioreDi(prec))
		strettamenteCrescente = false;
	    
	    prec = succ;
	    succ = Razionale.leggi(input);
	}

	if(strettamenteCrescente)  
	    System.out.println("Sequenza strettamente crescente");
	else
	    System.out.println("Sequenza non strettamente crescente");
    }
    
}



////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE VerificaSommaIntera.java
////////////////////////////////////////////////////////////////////////////////

/*
 * Implementare un programma che determini la somma di una sequenza di numeri razionali
 * terminata da un numero razionale negativo. Il programma deve inoltre stabilire se 
 * tale somma è un numero intero o meno.
 * 
 * Fare uso della classe Razionale.
 */

import java.util.Scanner;

public class VerificaSommaIntera {
    
    public static void main(String[] args) {
	Scanner input = new Scanner(System.in);
	
	Razionale s = new Razionale();
	
	System.out.println("Inserisci una sequenza di numeri razionali (coppie di interi) terminata da un numero razionale negativo.");
	Razionale x = Razionale.leggi(input);
	while(x.maggioreDiOUgualeA(new Razionale())) {
	    s.somma(x);
	    
	    x = Razionale.leggi(input);
	}
	
	if(s.getDenominatore() == 1)
	    System.out.println("La somma e': " + s.toDouble() + " (un numero intero)");
	else
	    System.out.println("La somma e': " + s + " (un numero non intero)");
     }
    
}



////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE FunzioneRicorsiva2.java
////////////////////////////////////////////////////////////////////////////////


/*
 * Implementare una funzione f(i) ricorsiva che riceve un intero e restituisce un razionale.
 * Per i=0 la funzione restituisce 0,
 * per i=1 la funzione restituisce 1,
 * per i>1 restituisce (f(i-2) + f(i-1))/2, ovvero la media fra f(i-2) e f(i-1).
 * 
 * Implementare inoltre un main che stampi i primi 10 razionali della sequenza.
 * 
 * Fare uso della classe Razionale.
 */

public class FunzioneRicorsiva2 {

}



////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE SequenzaStrettamenteDecrescente.java
////////////////////////////////////////////////////////////////////////////////

/*
 * Implementare un programma che determini se una sequenza di numeri razionali
 * terminata da un numero razionale negativo e' strettamente decrescente o meno.
 * 
 * Fare uso della classe Razionale.
 */

public class SequenzaStrettamenteDecrescente {

    public static void main(String[] args) {
	
    }
    
}



////////////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////////////
// FILE SequenzaSegnoAlterno.java
////////////////////////////////////////////////////////////////////////////////

/*
 * Implementare un programma che determini se una sequenza di N numeri razionali
 * e' a segni alterni (ogni numero positivo e' seguito da un numero negativo e viceversa).
 * Per semplicita', assumere che lo zero faccia parte dei numeri positivi.
 * 
 * Fare uso della classe Razionale.
 */

public class SequenzaSegnoAlterno {

    public static void main(String[] args) {
	
    }
    
}