/* Class: COP3530
 * Date: Jan 20, 2006
 * Instructor: Arup Guha
 * TA: Adam Campbell
 *
 * Recitation #2, Problem #1
 **/

import java.util.Arrays;

public class Rec2Prob1{

	/* I have main throw exception so I don't need the try/catch blocks everywhere when reading in from the file.
	 * In general, this is not good programming practice, but for these simple problems we are more interested in the
	 *   algorithm.
	 **/
	public static void main(String[] args) throws Exception{

		int[] counter = new int[16];
		int max = 1000; // the max value our counter will go up to
		int flips; // keeps track of the total number of flips for a particular value of n
		double average; // average number of flips that occur per successor call

		// loop through different values of n
		for(int n = 1; n < max; n++){

			// initialize the counter to all 0's
			Arrays.fill(counter, 0);

			// initialize flips
			flips = 0;

			// call successor n times
			for(int count = 0; count < n; count++){
				flips += successor(counter);
			}

			average = (double)flips / n;

			System.out.println(n + " " + average);

		}

	}

	// This function treats counter as a 16 bit binary number, and adds one to that number
	// It returns the number of bits that were flipped during the addition operation
	public static int successor(int[] counter){

		int totalFlips = 0;
		int currentBit = 0;

		while(currentBit < counter.length){

			totalFlips++;

			if(counter[currentBit] == 0){
				counter[currentBit] = 1;
				break;
			}else{
				counter[currentBit] = 0;
				currentBit++;
			}

		}

		return totalFlips;

	}

}