用递归方式解决滑雪问题
滑雪问题是一个算法逻辑题, 就是像滑雪一样,只能往上下左右比自己低的地方走,问有几种方式或者最长的滑道,本来想用二叉树实现, 但需要定义父节点和4个上下左右的子节点,比较麻烦就放弃了,今天聊天时突然想起来了可以递归解决,就迅速写了代码,稍微修改下也可以处理走迷宫问题#include <stdio.h>
//定义滑雪场,各个数值代表高度,坐标代表位置
int are = {{ 1,2,3,4, 5},
{16, 17, 18, 19, 6},
{15, 24, 25, 20, 7},
{14, 23, 22, 21, 8},
{13, 12, 11, 10, 9}};
void int_add(int *a, int n , int d)
{
int i = 0;
for (i = 0; i< n ; i++)
{
if (a == 0)
{
a = d;
break;
}
}
}
void int_pri(int *a, int n)
{
int i = 0;
while (a != 0)
{
printf("%d ", a);
i++;
}
printf("\n");
}
void digui(int a, int b, int *his)
{
int top = 99, bot = 99, left = 99, right = 99, i = 0;
int len = sizeof(are)/sizeof(int);
int high = sizeof(are)/sizeof(are);
int lj = {0};
//加入到滑雪路径中
for (i = 0; i < 32; i++)
{
int_add(lj, 32, his);
}
int_add(lj, 32, are);
//判断上下左右
if (a > 0 )
{
top = are;
if (top < are)
{
//开始递归
digui(a-1, b, lj);
}
}
if (a < high - 1)
{
bot = are;
if (bot < are)
{
//开始递归
digui(a+1, b, lj);
}
}
if (b > 0 )
{
left = are;
if (left < are)
{
//开始递归
digui(a, b-1, lj);
}
}
if (b < len-1 )
{
right = are;
if (right < are)
{
//开始递归
digui(a, b+1, lj);
}
}
//如果此处是最低,就打印此滑道
if (top > are && bot > are && left >are && right >are )
{
int_pri(lj, 32);
}
}
int main()
{
int lj = {0};
//输入滑雪起始位置,lj是记录滑雪路径
digui(2, 2, lj);
return 0;
}
亲~这边建议上洛谷多多练习呢~
页:
[1]