词条 | 半数集 |
释义 | 定义给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下: (1) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (2)按此规则进行处理,直到不能再添加自然数为止。 举例以自然数6为例,首先包括其本身{6},然后包括6与其约数构成的2位数集合{16,26,36},最后还有两个3位数集合{126,136}。 汇总之后得出6的半数集set(6)={6,16,26,36,126,136}. 同法可得8的半数集set(8)={8,18,28,38,48,128,138,148,248,1248} 元素总数元素总数计算公式: 代码实现计算元素总数递归代码(效率较低)#include<iostream> using namespace std; int set(int i) { if(i>=2) { return set(i / 2) + set(i - 2); } else return 1; } void main(){ int s; cin>>s; cout<<set(s)<<endl; } 动态规划(效率较高)#include<iostream> using namespace std; #define N 1001 int asd[N]; void main() { int i, j; for(i = 2,asd[1]=1;i < N; i++) { j = i / 2; asd[i] = asd[j * 2 - 1] + asd[j]; } cout<<"--"<<endl; int n = 0; while(n >= 0) { cin>>n; cout<<asd[n]<<endl; } } |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。