吃饱没事做之——爬楼梯题复杂化(1)

吃饱没事做之——爬楼梯题复杂化(1)

上一个爬楼梯复杂化，通过数学公式来写代码得出了答案。

然后我发了个朋友圈，有个朋友在下面留言：为什么不用递归？

我稍加思考，发现有道理，然后就开始了，写递归。

代码先贴上

//此代码是为了更难的完成爬楼梯的题的代码
#include 
#define c_MAX(x,y) (x)>(y)?(x):(y)
#define c_MIN(x,y) (x)<(y)?(x):(y)

//字符转整型
int char_int(char i);
//字符串转整型
int string_int(char *s);
//求C（a,b）的值，即C a 取 b
int C_l(int a,int b);
//整型转字符串
char * int_string(int in);

int main(int arg_len, char* arg[]) {
    //长度不够，直接退出
    if(arg_len != 2 )return 0;
    //递归到了第一层，退出
    if(string_int(arg[1]) <= 0)return 0;
    int z = string_int(arg[1]); //楼梯值
    //对下部分传递进行赋值
    char **p1 = new char*[2];
    p1[1] = new char[10];
    //p1[0] = new char[2];
    p1[1] = int_string(z-1);

    main(arg_len,p1);

    {
        //int z = string_int(arg[1]); //楼梯值
        int n = z/2;
        int c = 0;
        for(int i = n; i >= 0; i--)
        {
            c += C_l(i + (z - (2 * i)), i);
        }
        std::cout << c << std::endl;
    }
}

int char_int(char i)
{
    return (int)i - 48;
}

int string_int(char *s)
{
    int num = 0;
    bool flag = false;
    int c = 10 , n = 0;
    while(*s != '')
    {
        if(*s == '-' && flag == false)
        {
            flag = true;
            s++;
            continue;
        }
        n = char_int(*s);
        //std::cout << n  << " n"  << std::endl;
        if(n < 0 || n > 9)break;
        num = num * c + n;
        //std::cout << num  << " 123 n"  << std::endl;
        s++;
    }
    return flag?-num:num;
}

int C_l(int a,int b)
{
    int x = 1,y = 1,z = 1;
    if(b == 0)return 1;
    if(b == 1)return a;
    if(a == b)return 1;
    if(a - b == 1)return a;
    
    return C_l(a-1,b) + C_l(a-1,b-1);
}

char * int_string(int in)
{
    char s[10],*p = s;
    int c = 0, i = 0 ;
    if(in == 0)return "0";
    for(int d = in; d != 0 ;i++)
    {
        d /= 10;
    }
    s[i] = '';
    i--;
    for(;in != 0;i--)
    {
        c = in%10;
        in /= 10;
        s[i] = c + 48;
    }
    //std::cout << s << std::endl;
    return p;
}

运行结果：

通过正常代码验算，正常人都这样写。多简单的题啊

#include 

int main()
{
	int i,j = 1,z = 1,d;
	for(i = 1;i < 40;i++)
	{
		d = j;
		j = j + z;
		z = d;
		printf("%dt%dn",j,i);
	}
   return 0;
}

答案一模一样没有问题

在写这个我遇到了一些问题，比如main函数的递归，arg数组要怎么传，就这一部分我搞了好久。

	char **p1 = new char*[2];
    p1[1] = new char[10];
    //p1[0] = new char[2];
    p1[1] = int_string(z-1);

因为不会嘛，在这里可以看到，main函数递归可以新建一个指针，由于一般第一个位置是放程序名，第二个才是参数，所以在这里先新建两个内存地址位来，存放两个字符串的地址，通过对第二个字符串的地址进行建立，然后进行赋值。

第一个的话，可以不用建立内存，或者建立多少内存都无所谓。

我感觉应该是

这样的。

然后在进行下一步的时候，发现后面的数字出现了错误，然后就知道是int空间不够了，此时的我，就是不想递归。然后……

int C_l(int a,int b)
{
    int x = 1,y = 1,z = 1;
    if(b == 0)return 1;
    if(b == 1)return a;
    if(a == b)return 1;
    if(a - b == 1)return a;
    for(int i = b+1;i <= a; i++)
    {
        x *= i;
    }
    for(int i = 1;i <= (a-b); i++)
    {
        z *= i;
    }
    return  x / z;
}

就写了这个，但问题没有解决，只要先乘后除就一定会int空间不够，然后就接受现实

int C_l(int a,int b)
{
    if(b == 0)return 1;
    if(b == 1)return a;
    if(a == b)return 1;
    if(a - b == 1)return a;
    return C_l(a-1,b) + C_l(a-1,b-1);
}

使用递归解决问题。

于是乎，爬楼梯题复杂化，到这里就结束了。