标题：李白打酒

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

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

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

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

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

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

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

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

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

答案提供代码~~

#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编辑过]

得出结果的所用的时间……执行过程中似乎要比参考答案的迟了一点~嗯,或者我可以对比下递归次数~

既然有帮忙顶贴的我就再说一下~
这题计算过上楼递归两千多次感觉是不是多了一点?~
我4楼手算都可以算出14次~

优化一点应该是:
不要疯狂连续设置商店买酒啊(这样难免会被人说是发酒疯的)~
递归的时候应该是以人见人爱的花为主~当剩下一壶酒的时候再开个店~
然后回溯的时候试图开个店再不断赏花,如果花赏完了还有酒则不要进店了(都不够花了,还疯狂买酒干嘛)~

相对于喝酒,我还是喜欢吃瓜~