您说的J复位到1的错误,我去更改了,思路就是不复位到1,只是减1,相当于从上一种
跳法的尾巴回缩1位,目前程序是对的了。因为我的对跳步约定了不允许大于剩余台阶,
所以也没有用到break语句,没有剪枝那一步。
但是我代码的执行效率偏低,比如20级台阶,最大2步的跳法
我要执行12秒,您那个只需要8秒。
不过我是执行了两次递归算法(函数FJ一次,函数FR一次),我如果只用函数FR,用re
alloc的方式按需扩充“储存数组”,不知道能不能快一些。
#include <stdlib.h>
#include <stdio.h>
int BZ=0;//全局变量,统计一共有多少种跳法,当剩余级数每1次变零,这个数加1
int I=0;//记录跳法的数组的行坐标
int J=1;//记录跳法的数组的列坐标,第1列记录第几种方法,所以从第2列开始记录
void FJ(int RS,int MS) //FJ:Frog Jump;RS:Remain Steps;MS:青蛙可以跳的最大步数,小于RS
{ int i;//青蛙每次可能跳的步数
for(i=1;i<=__min(RS,MS);i++) //第一次跳无需考虑跳的最大级数大于剩余阶数的问题
{
if (RS-i>0) //未跳尽剩余台阶
{
FJ(RS-i,MS);
}
else//跳尽剩余台阶了
BZ=BZ+1;
}
}
void FR(int **p,int RS,int MS) //RS:Remain Steps;MS:青蛙可以跳的最大步数,小于RS
//这个FR函数只为记录每一种跳法的各跳级数
{ int i;//青蛙每次可能跳的步数
int j;
for(i=1;i<=__min(RS,MS);i++) //第一次跳无需考虑跳的最大级数大于剩余阶数的问题
{
if (RS-i>0)//未跳尽剩余台阶
{
p[I][J]=i;
J=J+1;
FR(p,RS-i,MS);
//函数回归后,记录分叉点之后的新跳法
J=J-1;//因为尝试的跳法比上一次多1步,
//所以新一行的记录点从上一行的队尾回退1
//下面是把老跳法的前几步填补新跳法的分叉点之前
for(j=1;j<J;j++)
{
p[I][j]=p[I-1][j];
}
}
else//跳尽剩余台阶了
{
p[I][J]=i;//记录跳尽时最后一跳的级数
I=I+1;//每次跳尽,记录完后就换行记录一种新的跳法
}
p[I-1][0]=I;//数组第一列记录是第几种跳法
}
}
int main()
{
int r;
int m;
printf("请输入台阶级数后按下回车键:\n");
scanf("%d",&r);
printf("请输入青蛙一次最多能跳几级台阶:\n");
scanf("%d",&m);
//下面4行是避免输入错误
if (m==0)
printf("青蛙可跳跃的最大步数必须大于等于1\n");
else if (m>r)
m=r;
FJ(r,m);//调用之前定义的函数
printf("%d 级台阶一次最多跳 %d 级的跳法一共 %d 种:\n",r,m,BZ);
//下面要记录 每一种跳法的各跳级数了
int **p;//准备通过二级指针创建全0二维数组,用于存放每一种跳法
int j;
p=(int**)calloc(BZ+1,sizeof(int*));
for(j=0;j<BZ+1;j++)
{
p[j]=(int*)calloc(r+1,sizeof(int));//创建一级指针,多搞1列,
}
FR(p,r,m); //调用填写函数,将每一种跳法存进数组
int i;
int k;
int L7=r+1; //临时变量,打印到第几列
for(i=0;i<BZ;i++)//打印出所有跳法组合
{
for(j=0;j<L7;j++)
{
printf("%4d",p[i][j]);
if ((j!=0)&(j%(L7-1)==0) )
printf("\n");
}
}
}
【 在 z16166 的大作中提到: 】
: 有两处错误
: 1、(RS - i)和0比较是三种情况,不是两种。
: 你的代码会导致(RS - i) < 0这种无解的情况下,也会执行BZ = BZ + 1,这样解的总数BZ是错的。(但这个题里正好没有错)
: ...................
--
修改:sqsl FROM 111.193.229.*
FROM 111.193.229.*