C语言实验作业选做题
I-游戏问题（完全二叉树）
某游戏规则中，甲乙双方每回合的战斗总是有一方胜利，一方失败。失败后要把自己的体力值1/4交给胜利的一方。
现在已知双方开始时的体力值：甲1000，乙2000.假设双方战斗胜率各为p。双方经过4回合的战斗，双方体力值之差abs小于1000的概率
Sample Input
0.5
Sample Output
0.625
代码：
#include<stdio.h>
#include<math.h>
#define N 4
double p = 0.5;//p表示甲赢的概率是0.5
double fun(double x, double y, int cur, double k) {
double sum = 0;
if (cur == N) {
if (fabs(x - y) < 1000)
sum += k;
return sum;
}
sum += fun(x - x / 4, y + x / 4, cur + 1, k * (1 - p));//甲输掉比赛
sum += fun(x + y / 4, y - y / 4, cur + 1, k * p);
return sum;
}
int main() {
printf("%lf\n", fun(1000, 2000, 0, 1));
return 0;
}
每个结点封装了这些东西：层数，甲乙血量，从根节点到该结点的概率k，还有一个神秘的变量就叫做sum
上面的代码给出了一个深度搜索的示例，通过前序遍历来构建这个树：结点一进入Stack中就立刻对该结点进行搜索。搜索的结果存进一个叫做sum的变量里面，然后对sum进行汇总求和。
对于非叶结点：比如说上图第7号结点的sum=A结点sum+B结点sum
对于叶结点：A结点的sum就是做个判断，如果血量差满足题目要求：sum=概率k，如果不满足：sum=0
再看代码：
sum += fun(x – x / 4, y + x / 4, cur + 1, k * (1 – p));//甲输掉比赛
sum += fun(x + y / 4, y – y / 4, cur + 1, k * p);
这两行代码就是递归，每一次递归就开一层Stack，到叶结点就停止，弹栈，从左到右，遍历顺序我在这分析一下：
首先根节点进入左子树，再进入左子树的左子树，因为这个是完全二叉树，没到规定层数完全不担心子树指向NULL的情况。顺序是：1->3->7->A->B->8->C->D这样来的，到了叶结点就弹栈，就进入上一层根节点的右子树。右子树遍历完了就继续弹栈，到上上结点的右子树，如此循环。这也跟树的前序遍历差别
总之这是一个简单的数据结构的题目，当然这道题完全可以脱离树的结构来做，因为这个数据量较小，用暴力的方法也不会慢很多。
II-输出一列式子（简单哈希表）
题目：输入一个数字p然后输出abcde/fghij=p的式子，而且abcdefghij互不相同
Sample Input
32
Sample Output
75168/02349=32
代码：我这个方法比较蠢，看看有没有大佬能提供更好的方法
#include<stdio.h>
#include<math.h>
int main() {
int x;
scanf_s("%d", &x);
int tem,flag=1;
int HashSet[10] = { 0 };//标记0-9的HashSet
for (int i = 1000;i < 99999 / x; i++) {
flag = 1;
tem = x * i;//先构造a/b=x的式子
if (i < 10000) {
HashSet[0] = 1;//不足一万的，那肯定有个0，置0为1
}
for (int temp = i; temp > 0;) {
HashSet[temp % 10 ] = 1;//挨个把哈希表设置好，先遍历除数
temp /= 10;
}
for (int temp = tem; temp > 0;) {
HashSet[temp % 10] = 1;//再遍历被除数
temp /= 10;
}
for (int j = 0; j < 10; j++) {
if (!HashSet[j]) {//遍历哈希表，看有无0项
flag = 0; break;
}
}
for (int k = 0; k < 10; k++) {
HashSet[k] = 0;//哈希表置0，准备下一次循环
}
if (!flag) continue;
else printf("%5d/%5d=%d\n", tem, i, x);
}
}
III-迷宫（广度优先搜索）
题目：用0-1矩阵代表有无障碍，要输出一个从左上角到右下角的一个路线
Sample Input&Output
#include<stdio.h>
struct node{
int x; //x坐标
int y; //y坐标
int pre; //来到此点的出发点，大概是记录这是第几个的
};
int book[6][6]; //用来记录点是否访问过
int map[6][6]; //记录图
struct node queue[20]; //存储路径的队列
void print(struct node a) //实现路径输出的函数
{
if(a.pre==-1)
{
printf("(%d, %d)\n",a.x,a.y);
return ;
}
else
{
print(queue[a.pre]);//递归调用，类似于出队的感觉，最先入队的最晚出队
printf("(%d, %d)\n",a.x,a.y);
}
}
int main()
{
int i,j,k,m,n,x,y;
int head,tail;
for(i=0;i<5;i++)
{
for(j=0;j<5;j++)
{
scanf("%d",&map[i][j]);
}
}
head=0;
tail=0;
queue[tail].x=0;
queue[tail].y=0;
queue[tail].pre=-1;
book[0][0]=1;
tail++;//这个初始化
while(head<tail) //当队列为空时跳出，说明搜索没有找到可行路径
{
int next[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; //定义出四个方向
int flag=0;
for(i=0;i<4;i++) //从当前点往四周探索
{
int nextx=queue[head].x+next[i][0];
int nexty=queue[head].y+next[i][1]; //实现移动
if(nextx<0||nextx>5||nexty<0||nexty>5) //超出了边界则跳出
{
continue;
}
if(book[nextx][nexty]==0&&map[nextx][nexty]==0) //当点未被访问过且是可行点才入队
{
book[nextx][nexty]=1;
queue[tail].x=nextx;
queue[tail].y=nexty;
queue[tail].pre=head;
tail++;
}
if(nextx==4&&nexty==4) //到达了目的地，毫无疑问地跳出结束循环
{
flag=1;
break;
}
}
if(flag) //到达目的地后调用函数输出路径
{
print(queue[tail-1]);
break;
}
head++; //出队
}//到这里一直属于while循环
return 0;
}
我认为是这样的：
- 首先构造一个数组，这个数组储存一下每个点是不是都已经遍历过了
- 再构建一个队列，这个结构储存每一个经过的点的位置坐标以及类似于位置这样的东西
- 进入main函数，初始化一下：起点是肯定要经过的啦
- 好了还是进行搜索了首先构造head和tail这两个指针（类似的），如果head和tail一头一尾追上了直接结束，这波叫做没路走了
- tail可以向下走，那就可以走，并且把这个点的信息存储进去，
- 假如说有两个方向有路，那就很好，tail可以加2，代表着有更多的路可以走
- head和tail必须分别平均每次都能够+1，那就是有路的，我们可以这样理解，就是消耗与产生，tail就是产生路，head就是消耗路。每次读取head所对应的队列就是类似于找寻对应这个东西有没有路
- 遍历完毕了，假如说找到了，那就开始输出
- 这个时候queue的pre就可能是这样子的 -1 0 0 0 1 1 1 2 3 4 5 6 6这样的，该怎样找出适合我们的路径呢？
- 这时候这个queue我觉得可以看成一个树，tail对应的就是节点的编号而pre对应着上一个节点的节点的编号，我们就可以进行树的遍历
- 假如说能找到-1，也就是根节点，那可以说明我们找到了一条路了，这时候递归输出就好了
0 条评论