蓝桥杯模拟赛:奇怪的捐赠(dfs)

傷城~ 2022-06-18 10:00 217阅读 0赞

地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。  
麻烦的是，他有个很奇怪的要求：

1.  100万元必须被正好分成若干份（不能剩余）。每份必须是7的若干次方元。  
    比如：1元, 7元，49元，343元，…
2.  相同金额的份数不能超过5份。
3.  在满足上述要求的情况下，分成的份数越多越好！
4.  请你帮忙计算一下，最多可以分为多少份？

注意：只需要填写一个整数，就是分成的份数，不要填写任何多余的内容。比如说明文字。

分析:  
dfs  
因为相同金额可以有5份 所以递归的时候有两种情况  
1.当前次方元+1 visit\[step\]+1  
2.下一次方元+1 visit\[step+1\]+1  
通过份数不能超过5份和金额不能大于100万条件退出递归

#include <iostream>
    #include <cmath>
    using namespace std;
    int count = 0;
    int visit[10] = {
       0};
    int num;
    void dfs(int step,int count) {  //step代表7的几次方 
        if(visit[step] > 5) {   //相同金额的份数不能超过5份
            return;
        }
        if(count > 1000000) {
            return;
        } else if(count == 1000000){
            num = 0;
            for(int i = 0; i < 10; i++) {
                num += visit[i];
            }
            cout<< num;
            exit(0);
        }        
        count += pow(7,step);
        visit[step]++;
        dfs(step, count);    //两种路 visit[step]+1
        dfs(step+1, count);   //visit[step+1]+1
        visit[step]--;
        count -= pow(7,step);
    } 
    int main()
    {   
        dfs(0,0);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯2014省赛——奇怪的分式（Java）

问题描述：上小学的时候，小明经常自己发明新算法。一次，老师出的题目是： 1/4 乘以 8/5 小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参见下图.

秒速五厘米/ 2023年09月29日 10:16/ 0 赞/ 19 阅读

相关蓝桥杯模拟赛

蓝桥杯模拟赛图的边数合法括号序列内存单词反倍数

旧城等待，/ 2023年05月21日 13:57/ 0 赞/ 27 阅读

相关 2020蓝桥杯省赛模拟赛

目录第一题：第二题：第三题：第四题：第五题：第六题：第七题：第八题：第九题：第十题：

电玩女神/ 2022年12月13日 11:27/ 0 赞/ 204 阅读

相关蓝桥杯模拟赛:滑动解锁

参考了这位大牛:[http://blog.csdn.net/qq\_36238595/article/details/63254554][http_blog.csdn.net_

妖狐艹你老母/ 2022年06月18日 11:40/ 0 赞/ 251 阅读

相关蓝桥杯模拟赛:奇怪的捐赠(dfs)

地产大亨Q先生临终的遗愿是：拿出100万元给X社区的居民抽奖，以稍慰藉心中愧疚。麻烦的是，他有个很奇怪的要求： 1. 100万元必须被正好分成若干份（不能剩余）。每份

傷城~/ 2022年06月18日 10:00/ 0 赞/ 218 阅读

相关蓝桥杯模拟赛:字符串比较

我们需要一个新的字符串比较函数compare(s1, s2). 对这个函数要求是： 1. 它返回一个整数，表示比较的结果。 2. 结果为正值，则前一个串大，为负值，

Bertha 。/ 2022年06月18日 09:48/ 0 赞/ 256 阅读

相关蓝桥杯模拟赛:猜算式

你一定还记得小学学习过的乘法计算过程，比如：请你观察如下的乘法算式 ![这里写图片描述][SouthEast] 星号代表某位数字，注意这些星号中， 0~9中的每个数

Myth丶恋晨/ 2022年06月18日 09:48/ 0 赞/ 272 阅读

相关蓝桥杯模拟赛B组

![SouthEast][] ![SouthEast 1][] 推理过程：由题意可知：2\A1=A0+A2-2\C1;(A2 = 2 \ A1 - A0 -> A2里

爱被打了一巴掌/ 2022年06月01日 05:41/ 0 赞/ 282 阅读

相关 2017 蓝桥杯模拟赛

1. 算年龄 2. 猜算式 3. 排列序数 4. 字符串比较 5. 报

た入场券/ 2022年05月29日 13:57/ 0 赞/ 322 阅读

相关蓝桥杯奇怪的分式

上小学的时候，小明经常自己发明新算法。一次，老师出的题目是： 1/4 乘以8/5 小明居然把分子拼接在一起，分母拼接在一起，答案是：18/45 （参

逃离我推掉我的手/ 2022年03月07日 11:05/ 0 赞/ 214 阅读