public class TriangleApp {
  private static int theNumber;

  public static void main(String[] args) throws IOException {
    System.out.println("Enter a number: ");
    theNumber = getInt();
    int answer = triangle(theNumber);
    System.out.println("Answer: Triangle=" + answer);
  }

  public static int triangle(int n) {
    System.out.println("Entering: n=" + n);
    if (n == 1) {
      System.out.println("Returning 1");
      return 1;
    } else {
      int temp = n + triangle(n - 1);
      System.out.println("Returning " + temp);
      return temp;
    }
  }

  public static String getString() throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    String s = br.readLine();
    return s;
  }

  public static int getInt() throws IOException {
    String s = getString();
    return Integer.parseInt(s);
  }
}

public class AnagramApp {
  private static int size;
  private static int count;
  private static char[] arrChar = new char[100];

  public static void main(String[] args) throws IOException {
    System.out.println("Enter a word: ");
    String word = getString(); // get word
    size = word.length(); // find its size
    count = 0;
    for (int j = 0; j < size; j++) {
      arrChar[j] = word.charAt(j); // put it in array
    }
    doAnagram(size); // anagram it
  }

  /**
   * anagram [ˈænəɡræm] 相同字母异序词，易位构词，变位词
   * @param newSize
   */
  public static void doAnagram(int newSize) {
    if (newSize == 1) { // if innermost
      displayWord(); // display
      return;
    }
    for (int j = 0; j < newSize; j++) { // for each position
      doAnagram(newSize - 1); // anagram remaining
      rotate(newSize); // rotate word
    }
    System.out.print(""); // for debug
  }

  /**
   * rotate [ˈroʊteɪt] 旋转；循环
   */
  public static void rotate(int newSize) {
    int j;
    int position = size - newSize;
    char temp = arrChar[position]; // save first letter
    for (j = position + 1; j < size; j++) { // shift others left
      arrChar[j - 1] = arrChar[j]; // put first on right
    }
    arrChar[j - 1] = temp;
    System.out.print(""); // for debug
  }

  public static void displayWord() {
    if (count < 9) { // 对齐
      System.out.print(" ");
    }
    System.out.print(++count + " ");
    for (int j = 0; j < size; j++) {
      System.out.print(arrChar[j]);
    }
    System.out.flush();
    if (count % 6 == 0) {
      System.out.println();
    } else {
      System.out.print("   ");
    }
  }

  public static String getString() throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    String s = br.readLine();
    return s;
  }
}

public class BinarySearch {
  private int[] a; // ref to array a
  private int nElem;  // number for data items

  public BinarySearch(int max) {
    a = new int[max];
    nElem = 0;
  }

  public int size() {
    return nElem;
  }

  public int find(int key) {
    return recFind(key, 0, nElem - 1);
  }

  public int recFind(int key, int lowerBound, int upperBound) {
    int curIn = (lowerBound + upperBound) / 2;
    if (a[curIn] == key) {
      return curIn; // found it
    } else if (lowerBound > upperBound) {
      return nElem; // can't find it
    } else { // divide range
      if (a[curIn] < key) {
        return recFind(key, curIn + 1, upperBound);
      } else {
        return recFind(key, lowerBound, curIn - 1);
      }
    }
  }

  public void insert(int val) {
    int j;
    for (j = 0; j < nElem; j++) {
      if (a[j] > val) {
        break;
      }
    }
    for (int k = nElem; k > j; k--) {
      a[k] = a[k - 1];
    }
    a[j] = val;
    nElem++;
  }

  public void display() {
    for (int j = 0; j < nElem; j++) {
      System.out.print(a[j] + " ");
    }
    System.out.println();
  }
}

public class BinarySearchApp {
  public static void main(String[] args) {
    int maxSize = 100;
    BinarySearch arr = new BinarySearch(maxSize);
    arr.insert(72);
    arr.insert(90);
    arr.insert(45);
    arr.insert(126);
    arr.insert(54);
    arr.insert(99);
    arr.insert(144);
    arr.insert(27);
    arr.insert(135);
    arr.insert(81);
    arr.insert(18);
    arr.insert(108);
    arr.insert(9);
    arr.insert(117);
    arr.insert(63);
    arr.insert(36);
    arr.display();

    int key = 9;
    if (arr.find(key) != arr.size()) {
      System.out.println("Found " + key);
    } else {
      System.out.println("Can't find " + key);
    }
  }
}