做营销网站公司,网络推广文案招聘,wordpress 登录菜单,怎么注册公司企业邮箱1316#xff1a;【例4.6】数的计数(Noip2001) 【题目描述】 我们要求找出具有下列性质数的个数#xff08;包括输入的自然数n #xff09;。先输入一个自然数n(n≤1000)#xff0c;然后对此自然数按照如下方法进行处理#xff1a;不作任何处理#xff1b;在它的左边加上一…1316【例4.6】数的计数(Noip2001) 【题目描述】 我们要求找出具有下列性质数的个数包括输入的自然数n 。先输入一个自然数n(n≤1000)然后对此自然数按照如下方法进行处理不作任何处理在它的左边加上一个自然数但该自然数不能超过原数的一半加上数后继续按此规则进行处理直到不能再加自然数为止。 【输入】 自然数n(n≤1000)。 【输出】 满足条件的数。
【输入样例】 6 【输出样例】 6 【提示】 【样例解释】
满足条件的数为如下所示
6 16 26 126 36 136
思路
首先分析: 一个自然数左边加上一个自然数举例-100左边加上后可以为5010025504910024100所以他的数量为1~50这五十个自然数的每次计数之和由于每个自然数独一无二左边加上一个自然数就多了该自然数的排列方式所以可以理解为前n/2个自然数不同排列组成的数的个数之和由于数据庞大在使用递归式时可以考虑该数组的值是否已经求了如果已求则可以直接跳过节省运行时间记忆搜索如果采用一层for循环的递归方式则会超时用一个变量去存由于每次都要从1开始计算所以会超时
#includebits/stdc.h
using namespace std;
//由于直接每次num(i)只是用sum记忆次数则会超时所以选择用记忆的方式每次计算后存起来
//记忆搜索一个if判断数组值是否为0递归
int sum 0,a[1001];
//定义计数的函数
void num(int m) ;
int main(){int n;cinn;num(n);couta[n];return 0;
}
void num(int m){if(a[m]0) return;//表示该数值已经求到了a[m]1;// 自身也是一种情况 for(int i1;im/2;i){num(i);//每次都递归一下(避免前面的数未计数) a[m]a[i];}
}
