当前位置：首页 → 问答吧 → 从X个球中取Y个球，统计各和值出现次数，寻找高手优化算法

从X个球中取Y个球，统计各和值出现次数，寻找高手优化算法

时间：2010-09-17

来源：互联网

需求：从X个球中取出Y个球为一组，计算该组球的和值，统计各个和值的出现次数，球号从1号开始，一组球中的各号码是不重复的。还不明白请去看北京快乐8的彩票玩法。

下面是我写的一个实现，这个算法是通过列出每一种可能，然后对得出的每组号码计算和值，再统计各和值的出现次数。代码如下：

复制代码

<?php
/*
* 计算球的和值
*/
function sum_balls($balls){
$sum = 0;
foreach ($balls as $a)
$sum += (int)$a;
return $sum;
}
/*
* 格式化$balls
*/
function format_balls($balls){
$str = "";
foreach ($balls as $ball){
$str = $str.($ball < 10 ? "0".$ball : $ball)." ";
}
return $str;
}
/*
* 从$total_ball_num个球中选出$select_ball_num个球，计算各和值出现的次数
*/
function calc_keno_sum_times($total_ball_num, $select_ball_num){
if($total_ball_num <= 0 || $select_ball_num <= 0 ||
$select_ball_num > $total_ball_num || $total_ball_num > 99){
echo "你输入的数字不符合要求，程序退出...";
exit;
}
$min_sum = ($select_ball_num + 1) * $select_ball_num / 2; //最小和值，高斯算法
$max_sum = $min_sum + ($total_ball_num - $select_ball_num) * $select_ball_num;//最大和值
echo "最小和值：${min_sum}，最大和值：${max_sum} ";
$result = array();//保存和值次数的结果
//初始化$result数组中的元素，后面就不需要再判断是否存在该元素了
for($i = $min_sum; $i <= $max_sum; $i++){
$result[$i] = 0;
}
$ball_sum = 0;
$balls = initBalls($select_ball_num);
echo "从{$total_ball_num}个球中选择{$select_ball_num}个球，各组合如下： ";
while($balls != null){
$ball_sum = sum_balls($balls);
$result[$ball_sum]++;
echo format_balls($balls)." ".$ball_sum." ";
$balls = getNextBalls($total_ball_num, $select_ball_num, $balls);
}
return $result;
}
/*
* 初始化第一组号码
*/
function initBalls($select_ball_num){
$balls = array();
for($i = 1; $i <= $select_ball_num; $i++){//balls下标从1开始
$balls[$i] = $i;
}
return $balls;
}
/*
* 获得下一组号码，如果已经是最后一组号码，则返回null
*/
function getNextBalls($total_ball_num, $select_ball_num, $balls){
$i = $select_ball_num;
while($i >= 1){
if(++$balls[$i] <= ($total_ball_num - $select_ball_num + $i)){
//小于或等于该位置允许的最大值时，中断循环
break;
} else {
$i--;
}
}
if($i >= 1){
//每个后面的球等于前面的球加1
while((++$i) <= $select_ball_num){
$balls[$i] = $balls[$i-1] + 1;
}
} else {
//已经没有其它组合了
return null;
}
return $balls;
}
/*
* 计算指定范围内和值数
*/
function calc_range_sum($result, $min, $max){
$count = 0;
for($i = $min; $i <= $max; $i++){
$count += $result[$i];
}
return $count;
}
/*
* 输出结果
*/
function print_result($result){
echo "各和值情况如下： ";
foreach ($result as $key => $value){
echo $key."\t".$value." ";
}
}
$result = calc_keno_sum_times(20, 7);
print_result($result);
?>