//----------------------------------------------------------------------
// Enigma1340.c (c) 2005 by Charles Petzold (www.charlespetzold.com)
//
// "Stairs and Sums" from New Scientist, 14 May 2005, page 49.
//
// This problem involves a game in which a teddy bear is placed on 
// the top step of 9 numbered steps, where 9 is the top step. 
// The landing is 0. Teddy is pushed off the 
// top step and lands on a step below (steps 0 through 8). He is 
// then repeatedly pushed off the step he lands on until he 
// finally lands on step 0. The score for each game is the sum of 
// the steps Teddy lands on, including the one he started on.
//
// The probability of Teddy landing on any step below the one he's
// pushed off is the same.
//
// This problem can be analyzed in a fairly straight-forward manner
// without a computer program involved.
//
// For a game played on 1 step, Teddy goes from 1 to 0, and the 
// average score (Si, where i is the number of steps) is always 1:
//
//	S1 = 1
//
// For 2 steps, Teddy can go from 2 to 0, or from 2 to 1 with equal 
// probability. In the first case, the score is 2. In the second, the
// score is 2 + S1. The average is:
//
//	S2 = (2 + 2 + S1) / 2
//
// or:
// 
// 	S2 = 2 + (1/2)S1
// 
// For 3 steps, Teddy can go from 3 to 0, from 3 to 1, or 3 to 2 
// with equal probability, for scores of 3, 3 + S1, and 3 + S2.
// The average is:
// 
// 	S3 = 3 + (1/3)(S1 + S2)
// 
// or:
// 
// 	S3 = 3 + (1/3)Sum(S1, S2)
// 
// In general,
// 
// 	Si = i + (1/i)Sum(S1 ... Si-1)
// 
// The one that we're really interested in is:
// 
// 	S9 = 9 + (1/9)(S1 + S2 + S3 + S4 + S5 + S6 + S7 + S8)
// 
// or:
// 
// 	S9 = 9 + (1/9)Sum(S1 ... S8)
// 
// Let's rearrange a bit to extract S8 from the sum:
// 
// 	S9 = 9 + (1/9)(S8 + Sum(S1 ... S7))
// 
// And substitute for S8:
// 
// 	S9 = 9 + (1/9)(8 + (1/8)Sum(S1 ... S7) + Sum(S1 ... S7))
// 
// So:
// 
// 	S9 = 9 + 8/9 + (1/8)Sum(S1 ... S7)
// 
// This time extract S7 from the sum:
// 
// 	S9 = 9 + 8/9 + (1/8)(S7 + Sum(S1 ... S6))
// 
// Substitute S7:
// 
// 	S9 = 9 + 8/9 + (1/8)(7 + (1/7)Sum(S1 ... S6) + Sum(S1 ... S6))
// 
// So:
// 
// 	S9 = 9 + 8/9 + 7/8 + (1/7)Sum(S1 ... S6)
// 
// Keep doing this and eventually you'll get:
// 
// 	S9 = 9 + 8/9 + 7/8 + 6/7 + 5/6 + 4/5 + 3/4 + 2/3 + 1/2
// 
// and that's about 15.17.
// 
// The program uses two methods. The first is a recursive function, 
// and the second is a simulation.
//
//----------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

// Returns the Average score for Teddy pushed off step number Step.

double AverageScore(int Step)
{
	int i;
	double Score = 0;

	if (Step == 0)
		return 0;

	for (i = 0; i < Step; i++)
		Score += Step + AverageScore(i);

	return Score / Step;
}

// Simulate the game Trials times and take the average.

double RandomPushes(int Trials)
{
	int i;
	double Total = 0;

	for (i = 0; i < Trials; i++)
	{
		int Step = 9, Score = 0;

		while (Step > 0)
		{
			Score += Step;
			Step = rand() % Step;
		}
		Total += Score;
	}

	return Total / Trials;
}

int main(void)
{
	printf("Average score using recursive function: %f\n", AverageScore(9));
	printf("Average score using 1,000,000 random kicks: %f\n", RandomPushes(1000000));
	return 0;
}