标题：李白打酒

    话说大诗人李白，一生好饮。幸好他从不开车。

    一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱：

    无事街上走，提壶去打酒。
    逢店加一倍，遇花喝一斗。

    这一路上，他一共遇到店5次，遇到花10次，已知最后一次遇到的是花，他正好把酒喝光了。

    请你计算李白遇到店和花的次序，可以把遇店记为a，遇花记为b。则：babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？请你计算出所有可能方案的个数（包含题目给出的）。

    注意：通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。

某同学说要弄一段代码看看怎么理解不过我感觉自己腾不出时间了……这个我感觉要弄也比较耗时的~在这里发个帖委托一下顺便看看各位有啥看法~

重新算过一下~手工也能算得答案是14~

[此贴子已经被作者于2017-10-12 22:50编辑过]

#include <stdio.h>

int count = 0;

void func(int a,int b,int d)
{
    if (d == 1 && a == 0 && b == 0)
    {
        count++;
        return;
    }
    
    if (a > 0)
        func(a - 1, b, d*2);

    if (b > 0)
        func(a, b - 1, d-1);

}


int main()
{
    func(5, 9, 2);   //进店5次，遇花9次(加最后的一次共10次), 初始2斗酒
    printf("%d", count);

    return 0;
}

答案提供代码~~

#include <cstdio>
using namespace std;
int sum = 0;
char str[100];
int Fun(int now, int i, int a, int b)
{
    if(now < 0 || i > 16 || (now == 0 && i < 16))
        return 0;
    if(now == 0)
    {
        if(i == 16 && a == 5 && b == 10)
        {
            sum++;
            for(int j = 0; j < 15; j++)
                putchar(str[j]);
            putchar(10);
        }
    }
    str[i - 1] = 'a';
    Fun(now * 2, i + 1, a + 1, b);
    str[i - 1] = 'b';
    Fun(now - 1, i + 1, a, b + 1);
}
int main()
{
    str[15] = '\0';
    Fun(2, 1, 0, 0);
    printf("sum = %d\n", sum);
    return 0;
}

自己思考的~重点是总共5次买了8壶酒~
标记第N次遇见店时的酒数目~
这样剪枝效率就高很多了~
注意a1<=2;
a(n+1)<=an*2;

手工得出结果是14~

1--8=1+1+1+2+3;
2--8=1+1+2+1+2;
3--8=1+1+2+2+1;
4--8=1+2+1+2+2;
5--8=1+2+2+1+2;
6--8=1+2+2+2+1;
7--8=1+2+3+1+1;
8--8=2+1+1+2+2;
9--8=2+1+2+1+2;
10--8=2+1+2+2+1;
11--8=2+2+1+1+2;
12--8=2+2+1+2+1;
13--8=2+2+2+1+1;
14--8=2+3+1+1+1;

~

[此贴子已经被作者于2017-10-13 04:19编辑过]

小天提供的运算效率似乎比参考答案慢了一个档次(估计是剪枝方面还需优化)~不过嘛&总体还是挺简洁容易理解的哈~

[此贴子已经被作者于2017-10-12 23:14编辑过]

大神，是根据题意信手拈来？还是有什么思路？我也想到了用递归但是具体的递归条件根本想不到，进了里面就转圈了。看您的代码就像只根据题目条件来？想不到啊，我试着单步调试前40多次对变量的监控还能知道怎么来，后来就和我写的不一样了，然后就没心思看了，您有什么思路吗？

太过简洁理解了。。。不可思议。。。

您觉得出题方是想让怎么做，，递归执行了8007次。。。

排列组合,总共15个位置,每个位置不是a就是b, 最后两个还要都是b, 剩下13位置要剩下2斗

久久说的运算效率指什么？