gistfile1.txt

// Test.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>     // std::cout
#include <algorithm>    // std::random_shuffle
#include <vector>       // std::vector
#include <ctime>        // std::time
#include <cstdlib>      // std::rand, std::srand

void dark_helper(std::vector<int> &myvector)
{
    for (int i = 0; i < 100; i++)
    {
        bool bFound = false;
        int currentNumber = i;
        int previousNumber = -1;
        for (int j = 0; j < 50; j++)
        {
            if (myvector[currentNumber] == i)
            {
                bFound = true;
                break;
            }
            previousNumber = currentNumber;
            currentNumber  = myvector[currentNumber];
        }

        if (bFound == false) {
            std::swap(myvector[currentNumber], myvector[previousNumber]);
        }
    }
}

bool experiment()
{
    std::vector<int> myvector;

    for (int i=0; i<100; ++i) myvector.push_back(i);
    std::random_shuffle ( myvector.begin(), myvector.end() );

    // dark friend
    dark_helper(myvector);

    for (int i=0; i <100;i++)
    {
        bool bFound = false;
        int currentNumber = i;
        for (int j = 0; j < 50; j++)
        {
            if (myvector[currentNumber] == i)
            {
                bFound = true;
                break;
            }
            currentNumber = myvector[currentNumber];
        }

        if (bFound == false)
            return false;
    }

    return true;
}

int _tmain(int argc, _TCHAR* argv[])
{
	std::srand ( unsigned ( std::time(0) ) );
	
	long experiments = 0;
	long succeededExperiments = 0;

	for(;;)
	{
		experiments++;
		if (experiment())
			succeededExperiments++;

		if (experiments % 10000 == 0)
			std::cout << experiments << " - " << (double)succeededExperiments / experiments << std::endl;
	}

	return 0;
}