信息学奥赛一本通:1316:【例4.6】数的计数(Noip2001)

这篇具有很好参考价值的文章主要介绍了信息学奥赛一本通:1316:【例4.6】数的计数(Noip2001)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【题目描述】

我们要求找出具有下列性质数的个数(包括输入的自然数nn)。先输入一个自然数n(n≤1000)n(n≤1000),然后对此自然数按照如下方法进行处理:

不作任何处理;

在它的左边加上一个自然数,但该自然数不能超过原数的一半;

加上数后,继续按此规则进行处理,直到不能再加自然数为止。

【输入】

自然数n(n≤1000)n(n≤1000)。

【输出】

满足条件的数。

【输入样例】

6

【输出样例】

6

【提示】

【样例解释】

满足条件的数为如下所示:

   6
  16
  26
 126
  36
 136

【题目分析】

1 2 3 4 5 6 7 8
1 2 12 3 13 4 14 24 124 5 15 25 125 6 16 26 126 36 136 7 17 27 127 37 137 8 18 28 128 38 138 48 148 248 1248
a(n) 1 2 2 4 4 6 6 10
1+a(1) 1+a(1) 1+a(1)+a(2) 1+a(1)+a(2) 1+a(1)+a(2)+a(3) 1+a(1)+a(2)+a(3) 1+a(1)+a(2)+a(3)+a(4)

方法1:递推

#include <bits/stdc++.h>
using namespace std;
long long  a[1001];
int main(){
   a[1]=1;
   int n;
   cin>>n;
   for(int i=2;i<=n;i++){
    a[i]=1;//不做任何处理,本身是1种
    for(int j=1;j<=i/2;j++)
        a[i]+=a[j];//1到i/2的和
   }
    cout<<a[n]<<endl;
   return 0;
}

方法2:递归(测试最后一个超时)
(1)、定义f(n)为数n的方法数
(2)、边界条件:n=1时,只有一种方法
(3)、当n大于1时,f(n)=1+f(1)+f(2)…+f(n/2)

#include <bits/stdc++.h>
using namespace std;
int f(int n){
    if (n==1) return 1;
    int s=1;
    for(int i=1;i<=n/2;i++){
        s+=f(i);
    }
    return s;

}
int main()
{
    int n;
    cin>>n;
    cout<<f(n)<<endl;
	return 0;
}

方法3:优化递归,缓存中间结果。文章来源地址https://www.toymoban.com/news/detail-682755.html

#include <bits/stdc++.h>
using namespace std;
int a[1001];
int f(int n){
    if (n==1) return 1;
    if(a[n]) return a[n];
    a[n]=1;
    for(int i=1;i<=n/2;i++){
        a[n]+=f(i);
    }
    return a[n];

}
int main()
{
    int n;
    cin>>n;
    a[1]=1;
    cout<<f(n)<<endl;
	return 0;
}

到了这里,关于信息学奥赛一本通:1316:【例4.6】数的计数(Noip2001)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • HOJ 系统常用功能介绍 OJ部署定制快速入门 c++ python Java编程在线自动评测判题 信息奥赛一本通 USACO G E S P 蓝桥 CSP NOIP 蓝桥等考题库 常见问题

    技术支持微  makytony   终身更新维护 功能类似洛谷和信息奥赛一本通,支持CSP复赛中的freopen文件输入输出方式提交,模拟真实考试环境,防止出现 本地  AC 比赛  WA  PA TLE  爆零 的惨剧。 组织比赛作业,创建题目、查看用户提交代码、下载评测数据等都没限制。 约  328

    2024年01月25日
    浏览(37)
  • 《信息学奥赛一本通 提高篇》

    提高篇 第一部分 基础算法 第1章 贪心算法 提高篇 第一部分 基础算法 第1章 贪心算法_青少年趣味编程-CSDN博客 提高篇 第一部分 基础算法 第1章 贪心算法 提高篇 第一部分 基础算法 第1章 贪心算法_青少年趣味编程-CSDN博客 信息学奥赛一本通 提高篇 第一部分 基础算法 第2章

    2024年02月16日
    浏览(46)
  • 信息学奥赛一本通(1398:短信计费)

    1398:短信计费 时间限制: 1000 ms         内存限制: 65536 KB 提交数: 22811     通过数: 10561 【题目描述】 用手机发短信,一条短信资费为0.1元,但限定一条短信的内容在70个字以内(包括70个字)。如果你一次所发送的短信超过了70个字,则会按照每70个字一条短信的限制把它分

    2023年04月08日
    浏览(77)
  • 信息学奥赛一本通【1302】股票买卖

    信息学奥赛一本通1302 1302:股票买卖 时间限制: 1000 ms 内存限制: 65536 KB   【题目描述】 最近越来越多的人都投身股市,阿福也有点心动了。谨记着“股市有风险,入市需谨慎”,阿福决定先来研究一下简化版的股票买卖问题。 假设阿福已经准确预测出了某只股票在未来N天的

    2024年02月05日
    浏览(39)
  • 信息学奥赛一本通习题答案(一)

    最近在给小学生做C++的入门培训,用的教程是信息学奥赛一本通,刷题网址为http://ybt.ssoier.cn:8088/index.php 现将部分习题的答案放在博客上,希望能给其他有需要的人带来帮助 篇幅有限,所以从分支结构开始,所有代码都可以正确提交,鉴于本人能力有限以及教学需要,部分代

    2024年02月16日
    浏览(39)
  • 信息学奥赛一本通 1376:信使(msner)

    ybt 1376:信使(msner) 1. 图论:最短路径 每个哨所是一个顶点,哨所与哨所之间的通信线路为边,两哨所间通讯花费的时间为边的权值。 记第一个哨所为顶点s,信息从第一个哨所传递到表示为顶点x的某哨所可能有多条路径,每条传送路径有一个花费的时间,自然要选择花费时

    2024年02月14日
    浏览(77)
  • 信息学奥赛一本通 1384:珍珠(bead)

    ybt 1384:珍珠(bead) 1. 图论:floyd 求传递闭包 传递闭包:二维数组e, e[i][j] 表示顶点i到顶点j是否有路径。 这是个有向图。每颗珍珠是一个顶点,初始情况下,如果i比j重,那么i到j有一条弧。 设布尔类型数组e,为该图的传递闭包,即 e[i][j] 表示i是否比j重。 先输入已知的相

    2024年01月24日
    浏览(41)
  • 信息学奥赛一本通:1119:矩阵交换行

    【题目描述】 给定一个5×5的矩阵(数学上,一个r×c的矩阵是一个由r行c列元素排列成的矩形阵列),将第n行和第m行交换,输出交换后的结果。 【输入】 输入共6行,前5行为矩阵的每一行元素,元素与元素之间以一个空格分开。 第6行包含两个整数m、n,以一个空格分开(1≤m,

    2024年02月22日
    浏览(41)
  • 信息学奥赛一本通 1352 【例4-13】奖金

    ybt 1352 【例4-13】奖金 1. 图论:拓扑排序 解法1:拓扑排序 每个人是一个顶点。 如果a奖金比b高,应该先确定b的奖金数,再确定a的奖金。 因此可以这样定义边:如果b的奖金比a高,那么存在有向边a, b。 设数组money,顶点i的奖金为 money[i] 。 图中入度为0的顶点的奖金为100。

    2024年02月16日
    浏览(44)
  • 信息学奥赛一本通(1162:字符串逆序)

    1162:字符串逆序 时间限制: 1000 ms         内存限制: 65536 KB 提交数: 14027     通过数: 10525 【题目描述】 输入一串以‘!’结束的字符,按逆序输出。 【输入】 如题述。 【输出】 如题述。 【输入样例】 【输出样例】 【分析】         逆序输出字符串,本身不难,可以

    2023年04月17日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包