全国软件设计大赛题，求解释！该怎么处理

全国软件设计大赛题，求解释！
某游戏规则中，甲乙双方每个回合的战斗总是有一方胜利，一方失败。游戏规定：失败的一方要把自己的体力值的1/4加给胜利的一方。例如：如果双方体力值当前都是4，则经过一轮战斗后，双方的体力值会变为：5，3。
现在已知：双方开始时的体力值甲：1000，乙：2000。
假设战斗中，甲乙获胜的概率都是50%
求解：双方经过4个回合的战斗，体力值之差小于1000的理论概率。

答案为：
#include<stdio.h>
#include<math.h>
void f(double a,double b,int* m,int* n,int k)
{
if(k==0)
{
(*n)++;
if(fabs(a-b)<1000)
(*m)++;
return;
}
double ta=a,tb=b;
ta*=3.0/4.0;
tb+=ta*1.0/4.0;
f(ta,tb,m,n,k-1);
b*=3.0/4.0;
a+=b*3.0/4.0;
f(a,b,m,n,k-1);
}
void main()
{
double a=1000,b=2000;
int m=0,n=0;
f(a,b,&m,&n,4);
printf("m=%d n=%d\n",m,n);
printf("%f\n",(float)m/(float)n);
}
1，假设战斗中，甲乙获胜的概率都是50%，代码是如何满足这一点的？
2，失败的一方要把自己的体力值的1/4加给胜利的一方。代码中是怎样体现的？
3，如果不用递归该怎样做？求思路？

------解决方案--------------------
1、下面的代码分别代表甲胜和乙胜的两种状态，每一轮递归里都分别考虑两种状况。
2、同样注释在下面：

C/C++ code


 ta*=3.0/4.0;            //  甲减1/4
  tb+=ta*1.0/4.0;    //  乙加1/4
  f(ta,tb,m,n,k-1);    //  乙胜了，递归看下面的情况   
  b*=3.0/4.0;       //  乙减1/4
  a+=b*3.0/4.0;       //  甲加1/4
  f(a,b,m,n,k-1);  //  甲胜了，递归看下面的情况

------解决方案--------------------
#include<stdio.h>
#include<math.h>

double  dfs(int n,double A ,double B)            //递归形式的写法
{
	if(n==0)
	{
		if(fabs(A-B)>1000)
			return 0.0625;
		return 0;
	}
	return dfs(n-1,A+B*0.25,B*0.75)+dfs(n-1,A*0.75,B+A*0.25);
}

int main(void)
{
	printf("%lf\n",dfs(4,1000,2000));
	return 0;
}  

这段代码更神奇...

------解决方案--------------------
// 递归搜一下..

C/C++ code

#include<stdio.h>
#include<math.h>
struct point{
    int a,b;
}p[30];
int n;
void DFS(double a,double b,int count)
{
    if(count == 4)
    {
        p[n].a = a;
        p[n++].b = b;
        return ;    
    }
    // a win 
        DFS(a+b/4.0,b-b/4.0,count+1);
    //b win
        DFS(a-b/4.0+a/4.0,b+b/4.0+a/4.0,count+1);
}
int main()
{
    int a=1000,b=2000,mac=0;
    n=0;
    DFS(a,b,1);
    for(int i=0;i<n;i++)
        if(fabs(p[i].a-p[i].b)>1000)
                mac++;
        printf("%lf\n",1.0*mac/n);
    return 0;    
}

------解决方案--------------------

C/C++ code

#include <iostream>
#include <cmath>
using namespace std;

bool func(float number1,float number2,int state)
{
    int i=3;
    float temp;
    while (i>=0)
    {
        if (state&(1<<i))
        {
            temp=number2/4;
            number1+=temp;
            number2-=temp;
        } 
        else
        {
            temp=number1/4;
            number1-=temp;
            number2+=temp;
        }
        i--;
    }

    if (fabs(number1-number2)<1000)
    {
        return true;
    }
    else
    {
        return false;
    }
}


int main()
{
    int count=0;
    int state;
    float number1=1000,number2=2000;
    state=0;
    while (state<=15)
    {
        if (func(number1,number2,state))
        {
            count++;
        }
        state++;
    }

    printf("%.2f",count/(float)16);//count 最后是10

    return 0;
}

全国软件设计大赛题，求解释！该怎么处理

相关推荐