#include <iostream>
#include <deque>
#include <numeric>
using namespace std;

//
// This program prints out some of the probabilities
// of seeing k consecutive heads in n tosses at for probabilities
// of 90%, 99%, 99.9%, and so on.
//
// Author: Mark Nelson
//
// See http://marknelson.us/2011/02/13/a-big-problem-that-doesnt-need-a-bignum
//
int main() {
	const int k = 20;

	//
	// Before the loop is entered, the deque is set
	// to the correct values for n=0 - that is, it
	// contains F(2) divided by 2^0. Each time
	// through the loop n is incremented by 1.
	//
	deque<double> q(k, 0);
	q[0] = 1.0;
	q[1] = 1.0;
	double seeking = 0.1;
	for ( int i = 1 ; ; i++ ) {
	    q.push_front( 0.0 );
	    for ( int j = 1 ; j <= k ; j++ ) {
	    	q[ j ] /= 2.0;
	    	q[0] += q[j];
	    }
		q.pop_back();
		if ( q[0] < seeking ) {
			cout << "There is a " << 100*(1-seeking)
			     << "% probability of seeing " << k
			     << " consecutive heads in " << i
			     << " tosses of a fair coin"<< endl;
			seeking /= 10;
			if ( seeking < .00001 )
				return 0;
		}
	}
	return 0;
}