首页>少儿编程>在自然数的左边加上一个自然数,但该自然数不能超过原数的一半

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

NOIP2001普及组复赛题

输入一个自然数n,然后对此自然数按照如下方法进行处理:
(1)不作任何处理;
(2)在它的左边加上一个自然数,但该自然数不能超过原数的一半;(3)加上数后继续按此规则进行处理,直到不能再加自然数为止。

请找出以上操作能得到的数的个数,例如,n=6时,满足条件的数为6个,分别为6、16、26、126、36、136.

输入格式

一行一个正整数n,n≤1000。

输出格式

一行一个整数,表示满足条件的数的个数。

输入样例

6

输出样例

6

完整程序

#include<iostream>

using namespace std;

int sum=1;

int chai(int n){
    if(n == 1){
        return 0;
    }else{
        for(int i=0;i<n/2;i++){
            sum++;
        chai(n/2-i);
        }
    }    
}

int main(){
    chai(8);
    cout<<sum<<endl;
}

程序思路

add_a_natural_number_to_the_left

假设该自然数为8,那么不超过一半的数就是从1到4,也就是后续的10位允许有1,2,3,4这四种可能,除1之外,2、3、4都可以继续被拆分,所以我们实际解题的步骤是,取其一半,整理从1到该自然数一半的值,统计结果,继续取结果中的数(如还可以继续拆分),取其一半,统计结果。如果n为1,则程序返回。这里利用了一个循环,让递归产生了多路的分支,每一路分支依次sum++,程序运行完毕后的最终值,即可能产生结果的总和。

输出具体结果

上述的程序只是输出了统计结果,那么落实到实际数据究竟是哪几个结果呢,我们可以尝试在递归函数中定义一个用于存储的string变量result,利用它来直接输出结果:

#include<iostream>
using namespace std;

int digui(int n,string result){
    cout << result << endl;
    if(n/2==0)return 0;
    for(int i=1;i<=n/2;i++){
        digui(i,char(i+'0')+result);
    }
    return 0;
}


int main(){
    int a;
    string b;
    cin >> a;
    b=char(a+'0');
    digui(a,b);
}

标签: c++

移动端可扫我直达哦~

推荐阅读

cpp 2024-10-26

宁波地区选手csp-j复赛一日游

2024年的CSP-J/S复赛依旧没有杭州以外的考点,全省的OIER齐聚杭州,也是盛况空前。我们家是被分到了杭州师范大学的下沙校区,全程约140+公里,高德导航显示2小时能到。考虑考试当天可能拥堵,过早起床也怕孩子考场犯困,所以订了前...

少儿编程 c++

cpp 2024-09-27

2024年 csp-j 以及 csp-s 初赛复赛分数查询接口

链接只是跳转到noi官网,并不是什么第三方的数据库,所以需要预先登陆noi官方网站哦。2024年复赛(2024年10月27日)成绩还没有出,仅尝试放链接备用。csp-j复赛查分接口csp-s复赛查分接口2024年初赛(2024年9月2...

少儿编程 c++

cpp 2024-09-24

图解动态规划(一)-01背包和变体

在oiwiki学习01背包,虽然完成并通过了题目(洛谷P2871),但总感觉似懂非懂,干脆在画图软件上推演了一下,于是就有了这篇笔记。所谓01背包,一般是给定一个固定容量的容器(背包),并提供固定件数的物品,每件物品有各自的体积(或称...

少儿编程 c++

cpp 2024-09-17

c++中相爱相杀的cin与getline

在洛谷刷题,会遇到各种各种的输入情况,有的时候需要按个输入,而有时则需要按行输入,偶尔也有前一行按个输入,后一行按行输入这样的需求。Windows系统中,换行是由两个字符\r\n组成的。 \r为回车,其ASCII码是13,作用是回到当...

少儿编程 c++

cpp 2024-08-23

c++中的集合----set的使用方法

在C++中,set 是一个容器,用于存储唯一元素,且按特定顺序排序。其具备自动排序,快速查找,去重,插入效率高的特点。以下是定义和使用 set 的基本方法:#include<iostream> #include<se...

少儿编程 c++

cpp 2024-08-23

c++中的map库与它的遍历方式

map与unordered_mapC+提供 map 与unordered_map 两种关联容器,可以将key与value关联起来。 map 与unordered_map 区别:1.底层实现原理map:map内部实现了一个红黑树,该结构...

少儿编程 c++

cpp 2024-08-23

C++利用递归求全排列的笔记

这是一篇洛谷题号P1157题目的题解笔记,该题解的作者是feecle6418,自己写了一大段程序之后看到这么简洁的方式求组合,感觉还是挺挫败的。关键是,看完了题解还看不太懂......#include<bits/stdc++.h...

少儿编程 c++

cpp 2024-07-22

C++位运算的习题解析与若干技巧

洛谷刷题的时候遇到了一些位运算的题目,看得一头雾水,于是临时起意,单独开一篇习题集,用来记录刷题过程中遇到的位运算相关习题。文章准备分为两部分,前半部分为一些常用技巧,后半部分为习题记录,随时补充。位运算的若干技巧位运算的习题集习题部...

少儿编程 c++

cpp 2024-07-21

C++中的变量类型与常用数据类型

常用数据类型不同的数据类型,在不同的说明方式下,其长度和表示数据的范围也都有所不同,可以用sizeof函数来打印不同数据类型所占字节的大小:#include <iostream> using namespace std; ...

少儿编程 c++