/**
 * Ternäres Suchen
 * 
 * @author (Ulrich Kiesmüller) 
 * @version (1.2 - 18.11.2010)
 */

import java.io.*;

public class Suche
{
    // Variablen
    private int grenze1;
    private int grenze2;
    private int min;
    private int max;
    private int[] feld;
    private int zahl;
    private int tipp;

    /**
     * Konstruktor
     */
    public Suche()
    {
        // Initialisierung
        grenze1 = 0;
        grenze2 = 0;
    }

    /**
     * Methoden - zuerst grundlegende, allgemeine dann für die Zahlensuche spezifische, zuletzt die main()-Methode für einen Durchgang des Zahlensuchspiels
     */
    
    static int eingabe () 
    {        
        String zeile= "";
        int wert;   
        BufferedReader in= new BufferedReader(new InputStreamReader(System.in) );
        try {
            zeile= in.readLine();
            } catch (IOException ioe) {}
      wert= Integer.parseInt(zeile);
      return wert;
    }
    
    public void ausgabe(int l)
    {
        for (int i = 0; i < l; i++)
        {
            System.out.print(feld[i] + " ");
        }
        System.out.println();
    }
    
    public void spielenMensch()
    {
        min = (int) (Math.random()*200+1);
        max = (int) (Math.random()*200+1);
        if (max < min)
        {
            int temp = max;
            max = min;
            min = temp;
        }
        System.out.println();
        feld = new int[max-min+1];
        for (int i = min; i <= max; i++)
        {
            feld[i-min] = i;
        }
        zahl = (int) (Math.random()*(max-min)+1+min);
        System.out.println("Ich habe mir eine Zahl im Bereich von " + min + " bis " + max + " gedacht.");
        while (fragenMensch(0) == 1)
        {
            System.out.println("Ich habe mir eine Zahl im Bereich von " + min + " bis " + max + " gedacht.");
        }
        System.out.println("Richtig, ich hatte mir die Zahl " + zahl + " gedacht.");
    }
    
    public int fragenMensch(int kennung)
    {
        tipp = -1;
        while (tipp < 0)
        {
            System.out.print("Wissen Sie die Zahl schon (0) oder wollen Sie den Bereich einschränken (1) ? ");
            tipp = eingabe();
            if (tipp > 1) tipp = -1;
        }
        if (tipp == 0)
        {
            tipp = -1;
            while (tipp < 0)
            {
                System.out.print("Welche Zahl habe ich mir gedacht? ");
                tipp = eingabe();
                if ((tipp < min) || (tipp > max)) tipp = -1;
            }
            if (tipp == zahl) return 0;
            else
            {
                System.out.println("Leider ist " + tipp + " die falsche Zahl.");
                return 1;
            }
        }
        else 
        {
            System.out.println("In welchem Bereich vermuten Sie meine Zahl?");
            grenze1 = -1;
            while (grenze1 < 0)
            {
                System.out.print("Wie lautet die untere Grenze dieses Zahlenbereichs? ");
                grenze1 = eingabe();
                if ((grenze1 < min) || (grenze1 > max)) grenze1 = -1;
            }
            grenze2 = -1;
            while (grenze2 < 0)
            {
                System.out.print("Wie lautet die obere Grenze dieses Zahlenbereichs? ");
                grenze2 = eingabe();
                if ((grenze2 < min) || (grenze2 > max)) grenze2 = -1;
            }
            if (grenze2 < grenze1)
            {
                int temp = grenze2;
                grenze2 = grenze1;
                grenze1 = temp;
            }
            if (zahl <= grenze2 && zahl >= grenze1)
            {
                System.out.println();
                System.out.println("Prima - Sie haben den richtigen Bereich gefunden!");
                min = grenze1;
                max = grenze2;
            }                
            else if (zahl < grenze1)
            {           
                System.out.println();
                System.out.println("Meine Zahl liegt links von dem von Ihnen genannten Bereich!");
                max = grenze1 - 1;
            }
            else
            {
                System.out.println();
                System.out.println("Meine Zahl liegt rechts von dem von Ihnen genannten Bereich!");
                min = grenze2 + 1;
            }
            return 1;           
        }
    }
    
    public void spielenComputer()
    {
        min = -1;
        while (min < 0)
        {
            System.out.print("Wie lautet die untere Grenze Ihres Zahlenbereichs? ");
            min = eingabe();
        }
        max = -1;
        while (max < 0)
        {
            System.out.print("Wie lautet die obere Grenze Ihres Zahlenbereichs? ");
            max = eingabe();
        }
        if (max < min)
        {
            int temp = max;
            max = min;
            min = temp;
        }
        System.out.println();
        feld = new int[max-min+1];
        for (int i = min; i <= max; i++)
        {
            feld[i-min] = i;
        }
       System.out.println("Die von Ihnen gedachte Zahl lautet " + ternaersucheComputer(min,max) + ".");
    }
    
    public int ternaersucheComputer(int links, int rechts)
    {
        tipp = -1;
        if (rechts - links <= 2)
        {
            while (tipp < 0)
            {
                System.out.print("Ist Ihre Zahl die " + (links+1) + " (0 = ja, 1 = nein) ? ");
                tipp = eingabe();
                if (tipp > 1) tipp = -1;
            }
            if (tipp == 0) return links+1;
            else if ((tipp == 1) && (rechts - links == 1)) return links;
            else
            {
                tipp = -1;
                while (tipp < 0)
                {
                    System.out.print("Ist Ihre Zahl kleiner oder größer als " + (links+1) + " (0 = kleiner, 1 = größer) ? ");
                    tipp = eingabe();
                    if (tipp > 1) tipp = -1;
                }
                if (tipp == 0) return links;
                else return rechts;
            }
        }
        
        System.out.println("Aus diesem Zahlenbereich greife ich nun einen Teilbereich heraus.");
        grenze1 = links + (rechts - links - 1) / 3;
        grenze2 = links + 2 * (rechts - links - 1) / 3;
        System.out.println(links + " --- " + grenze1 + " --- " + grenze2 + " --- " + rechts);
        System.out.println();
        tipp = -1;
        while (tipp < 0)
        {
            System.out.print("Liegt Ihre Zahl im Bereich von " + grenze1 + " bis " + grenze2 + " (0 = ja, 1 = nein) ? ");
            tipp = eingabe();
            if (tipp > 1) tipp = -1;
        }
        if ((tipp == 0) && (grenze1 != grenze2)) return ternaersucheComputer(grenze1, grenze2);
        else if ((tipp == 0) && (grenze1 == grenze2)) return grenze1;
        else 
        {
            tipp = -1;
            while (tipp < 0)
            {
                System.out.print("Liegt Ihre Zahl links oder rechts des Bereichs von " + grenze1 + " bis " + grenze2 + " (0 = links, 1 = rechts) ? ");
                tipp = eingabe();
                if (tipp > 1) tipp = -1;
            }
            if (tipp == 0 && links != grenze1) return ternaersucheComputer(links, grenze1 - 1);
            else if ((tipp == 0) && (links == grenze1)) return grenze1;
            else if ((tipp == 1) && (grenze2 == rechts)) return grenze2;
            else return ternaersucheComputer(grenze2 + 1, rechts);
        }
    }
    
    public void main()
    {
        int frage = -1;
        while (frage < 0)
            {
                System.out.print("Wollen Sie eine von mir gedachte Zahl erraten (0) oder soll ich eine von Ihnen gedachte Zahl finden (1) ? ");
                frage = eingabe();
                if (frage > 1) frage = -1;
            }
        if (frage == 1) spielenComputer();
        else spielenMensch();
    }   
}
