| 网站首页 | 业界新闻 | 群组 | 人才 | 技术文章 | 下载频道 | 博客 | 代码贴 | 编程论坛
共有 220 人关注过本帖
标题:2014年南桥杯竞赛第三题:李白打酒~
只看楼主 收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3650
专家分:10447
注 册:2016-10-22
结帖率:100%
  已结贴   问题点数:20  回复次数:10   
2014年南桥杯竞赛第三题:李白打酒~
标题:李白打酒

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

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

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

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

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

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

某同学说要弄一段代码看看怎么理解不过我感觉自己腾不出时间了……这个我感觉要弄也比较耗时的~在这里发个帖委托一下顺便看看各位有啥看法~
7 天前 20:37
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3650
专家分:10447
注 册:2016-10-22
  得分:0 
重新算过一下~手工也能算得答案是14~


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


[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
7 天前 20:38
炎天
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:桃花岛
等 级:版主
威 望:21
帖 子:1048
专家分:3852
注 册:2016-9-15
  得分:10 
程序代码:
#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;
}

一万年太久,只争朝夕
7 天前 21:41
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3650
专家分:10447
注 册:2016-10-22
  得分: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编辑过]


[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
7 天前 22:54
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:22
帖 子:3650
专家分:10447
注 册:2016-10-22
  得分:0 
回复 3楼 炎天
小天提供的运算效率似乎比参考答案慢了一个档次(估计是剪枝方面还需优化)~不过嘛&总体还是挺简洁容易理解的哈~

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


[code]/*~最近喜欢吃瓜和睡觉~2017-08-25更~*/[/code]
7 天前 23:01
LG隐
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:50
专家分:118
注 册:2016-4-20
  得分:10 
回复 3楼 炎天
大神,是根据题意信手拈来?还是有什么思路?我也想到了用递归但是具体的递归条件根本想不到,进了里面就转圈了。看您的代码就像只根据题目条件来?想不到啊,我试着单步调试前40多次对变量的监控还能知道怎么来,后来就和我写的不一样了,然后就没心思看了,您有什么思路吗?
7 天前 23:51
LG隐
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:50
专家分:118
注 册:2016-4-20
  得分:0 
回复 5楼 九转星河
太过简洁理解了。。。不可思议。。。
7 天前 23:52
LG隐
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:50
专家分:118
注 册:2016-4-20
  得分:0 
回复 5楼 九转星河
您觉得出题方是想让怎么做,,递归执行了8007次。。。
7 天前 23:58
炎天
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:桃花岛
等 级:版主
威 望:21
帖 子:1048
专家分:3852
注 册:2016-9-15
  得分:0 
回复 6楼 LG隐
排列组合,总共15个位置,每个位置不是a就是b, 最后两个还要都是b, 剩下13位置要剩下2斗

一万年太久,只争朝夕
6 天前 01:06
炎天
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
来 自:桃花岛
等 级:版主
威 望:21
帖 子:1048
专家分:3852
注 册:2016-9-15
  得分:0 
以下是引用九转星河在2017-10-12 23:01:26的发言:

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

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

一万年太久,只争朝夕
6 天前 01:40







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

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