写点什么

算法题每日一练 --- 第 6 天:李白打酒

作者:知心宝贝
  • 2022 年 7 月 23 日
  • 本文字数:923 字

    阅读完需:约 3 分钟

算法题每日一练---第6天:李白打酒

一、问题描述

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


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


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


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


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

二、题目要求

考察

1.全排列公式、循环判断2.建议用时10~20min
复制代码


运行限制


  • 最大运行时间:1s

  • 最大运行内存: 128M

三、问题分析

对于这一题,我们可以使用贪心算法、dfs 深度搜索以及全排列解决。


首先,题目已知,酒壶中一开始有酒 2 斗,路上总共有 5 个店记作 a,有 10 朵花记作 b,其中最后一次出现的是花。使用 c++中的 string 类进行存储,因为第十五个一定是 b 所以可以不需要存储,只需要在最后一次判断酒壶里面的酒是不是还剩下一斗。


题目的规模不是很大,我们可以使用全排列计算出所有可能的结果。


  do   {
} while(next_permutation(s.begin(),s.end()));
复制代码


全排列头文件 algorithm,next_permutation(s.begin(),s.end())里面对于非 string 类的,比如一个 int 型以为数组 a[10],数组大小为 10。


写成 next_permutation(a,a+10)。全排列在循环中求解出,每一次的结果。我们只需要判断值为 a,sum 变成 2 倍,值为 b,sum--, 找到符合值为 1 就行。

四、编码实现

#include<iostream>#include<algorithm>//全排列头文件using namespace std;int main(){  string s="aaaaabbbbbbbbb";//定义初始值   int n=s.size(),ans=0,i;//把s的大小赋值给n   do  {    int sum=2;//因为初始值为2     for(i=0;i<n;i++)//循环判断     {      if(s[i]=='a')  sum=sum*2;//值为a,sum变成2倍       if(s[i]=='b')   sum--;//值为b,sum--     }      if(sum==1)//最后一种不要计算,符合值为1的特点     {      ans++;    }  }  while(next_permutation(s.begin(),s.end()));//计算出每一种可能的结构   cout<<ans;//输出符合条件的结果   return 0;}
复制代码

五、输出结果


输出结果为 14,如果要求输出具体步骤,在全排列里面加入一个输出就行。

发布于: 1 小时前阅读数: 8
用户头像

知心宝贝

关注

公众号:穿越计算机的迷雾 2022.03.07 加入

生于尘埃 溺于人海 死于理想高台

评论

发布
暂无评论
算法题每日一练---第6天:李白打酒_算法_知心宝贝_InfoQ写作社区