| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 1303 人关注过本帖, 2 人收藏
标题:2014年南桥杯竞赛第三题:李白打酒~
只看楼主 加入收藏
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:50
帖 子:4975
专家分:13940
注 册:2016-10-22
  得分:0 
回复 10楼 炎天
得出结果的所用的时间……执行过程中似乎要比参考答案的迟了一点~嗯,或者我可以对比下递归次数~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-10-13 04:18
书生牛犊
Rank: 13Rank: 13Rank: 13Rank: 13
来 自:星夜征程
等 级:蒙面侠
威 望:8
帖 子:1052
专家分:4993
注 册:2015-10-27
  得分:0 
以下是引用炎天在2017-10-12 21:41:17的发言:

#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;
}

也贴一个我的代码,稍作修改。在实际应用中并不如二楼@炎天的来着简洁明了。
程序代码:
/**
2014年南桥杯竞赛第三题:李白打酒~
标题:李白打酒

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

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

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

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

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

    注意:通过浏览器提交答案。答案是个整数。不要书写任何多余的内容。
   
*/
#include <stdio.h>
#include <stdlib.h>
int times=0;

int func(int Add,int Drink,int Wine);
int main() {
    int a=5;
    int b=8;/*已知最后一次遇到的是花,他正好把酒喝光了。而且倒数第二次遇到的肯定也不是店,而是花*/

    printf("%d",func(a,b,2));
    printf("\n递归次数[%d]",times);
    return 0;
}
int func(int Add,int Drink,int Wine) {
    ++times;
    int Plan;


    if(Add==0)//当遇酒家的机会Add用完,直接计算此时酒的存量Wine减去饮酒的机会Drink,是否等于两壶
        if(Wine-Drink==2)return 1;
        else return 0;
    if(Drink==0)//当饮酒的机会用完,若 遇酒家的次数Add!=1,或者酒的存量Wine!=2 ,均可断定此方案不可行
        if(Add==1&&Wine==1)return 1;
        else return 0;


    {
        //递归
        Plan=func(Add-1,Drink,Wine*2);
        Plan+=func(Add,Drink-1,Wine-1);
    }

    return Plan;
}


φ(゜▽゜*)♪
2018-01-08 13:22
九转星河
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:长长久久
等 级:版主
威 望:50
帖 子:4975
专家分:13940
注 册:2016-10-22
  得分:0 
既然有帮忙顶贴的我就再说一下~
这题计算过上楼递归两千多次感觉是不是多了一点?~
我4楼手算都可以算出14次~

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

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

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-01-08 18:03







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.028301 second(s), 9 queries.
Copyright©2004-2018, BCCN.NET, All Rights Reserved