《编程之美》284页,问题4.6:桶中取黑白球。
有一个桶,里面有白球、黑球各100个,人们必须按照以下规则把球取出来:
1. 每次从桶中拿两个球;
2. 如果两球同色,再放入一个黑球;
3. 如果两球异色,再放入一个白球;
问:最后桶里面只剩下一个黑球的概率是多少?
于是我开始分析,桶里装球,每次摸球是随机的,所以不能用队列和栈,那就用万能的动态列表来做桶吧。按照题目描述的顺序,写出取球的过程,最后剩的是黑球返回1,白球返回2,其他情况(没球了)返回3,然后根据概率在大数据量下将会趋于稳定的性质无限取球,最后趋于稳定的那个数就是答案。
代码如下(注释的部分为调试程序过程中用到的测试代码,用来显示操作过程中取球、放球、以及桶中球的详细变化过程):
using System;
using System.Collections.Generic;
using System.Linq;
namespace BucketBall
{
class Program
{
static void Main(string[] args)
{
int count = 0;
int targetCount = 0;
int result;
double probability;
while (true)
{
List<string> bucketBalls = new List<string>();
result = Play(bucketBalls);
//Console.WriteLine("result:" + result);
if (result == 1)
{
targetCount++;
//Console.WriteLine("targetCount:" + targetCount);
}
count++;
//Console.WriteLine("count:" + count);
probability = Math.Round((double)1.0 * targetCount / count, 2);
Console.WriteLine(probability);
//Console.Read();
}
} private static int Play(List<string> bucketBalls)
{
for (int i = 1; i <= 2; i++)
{
bucketBalls.Add("BlackBall");
bucketBalls.Add("WhiteBall");
}
//PrintList(bucketBalls);
Random ran = new Random();
while (bucketBalls.Count() > 1)
{
var balls = Take(bucketBalls, 2, ran);
//Console.WriteLine("Take the balls " + balls[0] + " " + balls[1]);
//PrintList(bucketBalls);
if (balls[0] == balls[1])
{
Put(bucketBalls, "BlackBall");
//Console.WriteLine("Put the BlackBall");
//PrintList(bucketBalls);
}
else
{
Put(bucketBalls, "WhiteBall");
//Console.WriteLine("Put WhiteBall over!");
//PrintList(bucketBalls);
}
//Console.WriteLine(bucketBalls.Count());
}
if (bucketBalls.Count() == 1)
{
//Console.WriteLine("result is " + bucketBalls[0]);
return bucketBalls[0] == "BlackBall" ? 1 : 2;
}
else
{
return 0;
}
}
private static void PrintList(List<string> bucketBalls)
{
Console.WriteLine();
foreach (var ball in bucketBalls)
{
Console.Write(ball + " ");
}
Console.WriteLine();
}
private static void Put(List<string> bucketBalls, string v)
{
bucketBalls.Add(v);
}
private static List<string> Take(List<string> bucketBalls, int v, Random ran)
{
List<string> balls = new List<string>();
int pos;
for (int i = 1; i <= v; i++)
{
pos = ran.Next(0, bucketBalls.Count());
balls.Add(bucketBalls[pos]);
bucketBalls.RemoveAt(pos);
}
return balls;
}
}
}
我因为不小心将一处的“WhiteBall”写成了“WhileBall”而一度修改却得不到正确的答案,最终一步一步的通过上面的测试代码,才将出错范围最终锁定在了初始化bucketBalls的for循环内,最终发现我将“WhiteBall”写成了“WhileBall”。改过来以后,运行结果终于正确了。下面是去掉测试代码的最终版:
using System;
using System.Collections.Generic;
using System.Linq;
namespace BucketBall
{
class Program
{
static void Main(string[] args)
{
int count = 0;
int targetCount = 0;
int result;
double probability;
while (true)
{
List<string> bucketBalls = new List<string>();
result = Play(bucketBalls);
if (result == 1)
{
targetCount++;
}
count++;
probability = Math.Round((double)1.0 * targetCount / count, 2);
Console.WriteLine(probability);
}
} private static int Play(List<string> bucketBalls)
{
for (int i = 1; i <= 100; i++)
{
bucketBalls.Add("BlackBall");
bucketBalls.Add("WhiteBall");
}
Random ran = new Random();
while (bucketBalls.Count() > 1)
{
var balls = Take(bucketBalls, 2, ran);
if (balls[0] == balls[1])
{
Put(bucketBalls, "BlackBall");
}
else
{
Put(bucketBalls, "WhiteBall");
}
}
if (bucketBalls.Count() == 1)
{
return bucketBalls[0] == "BlackBall" ? 1 : 2;
}
else
{
return 0;
}
}
private static void Put(List<string> bucketBalls, string v)
{
bucketBalls.Add(v);
}
private static List<string> Take(List<string> bucketBalls, int v, Random ran)
{
List<string> balls = new List<string>();
int pos;
for (int i = 1; i <= v; i++)
{
pos = ran.Next(0, bucketBalls.Count());
balls.Add(bucketBalls[pos]);
bucketBalls.RemoveAt(pos);
}
return balls;
}
}
}
通过运行结果可以看出来,概率一直很稳定,为1:
所以答案是在白球和黑球各100个的前提下取球放球,最后都只剩下黑球,概率为1。
修改程序中的初始化参数还可以用来求解课后题中的拓展情况,不用动脑。大家可以试试。
总结过程中遇到的问题:
1、字符串赋值的时候一定要仔细,别写错了!
2、Random.Next()函数返回值的范围包括 minValue 但不包括 maxValue。如果 minValue 等于 maxValue,则返回 minValue。
|
请发表评论