一开始果断选择暴力做法,结果就炸了。
暴力代码:
#include<bits/stdc++.h>
using namespace std;
long long int ans=1;//因为后面不包括本身,所以计为1
void f(int a){
int mid=a/2;//取中间值
for(int i=1;i<=mid;i++)//将所有可以取的值枚举一遍
{
ans++;
f(i);//选取之后,再进行加数字
}
}
int main()
{
int a;
while(cin>>a){//输入数字
f(a);
cout<<ans<<endl;
ans=1;//重置
}
return 0;
}
如果仔细观察就知道,之前的数可选取的结果会重复出现.
比如6和12:
6的选取之后的数(因为经过选取,所以不包括本身)有16,26,36,126,136;
12如果前面选取6,即为612;
那么之后的结果就为1612,2612,3612,12612,13612;
其实如果当选取的数一样的话,结果是一样的
只要创建个数组,记录一下所选取的数的结果的多少就可以节约时间了
解题思路:创建个数组,记录一下所选取的数的结果,从1到1000,把所有数先算出来
参考代码:
#include<bits/stdc++.h>
using namespace std;
long long int ans=1;
int m[1000];
int f(int a){
int mid=a/2;//取中间数
for(int i=1;i<=mid;i++)
{
if(m[i]==0) ans++,f(i);//如果没有被记录
else ans+=m[i];
}
return ans;
}
int main()
{
int a;
memset(m,0,sizeof(m));
for(int i=1;i<=1000;i++)
{
m[i]=f(i);//记录下该数的半数集的元素个数
ans=1;//重置
}
while(cin>>a){
cout<<m[a]<<endl;
}
return 0;
}
0.0分
1 人评分
C语言训练-斐波纳契数列 (C语言代码)浏览:2826 |
printf基础练习2 (C语言代码)浏览:594 |
简单的a+b (C++语言代码)浏览:860 |
拆分位数 (C语言代码)浏览:1328 |
C语言程序设计教程(第三版)课后习题8.3 (C语言代码)浏览:717 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:542 |
【明明的随机数】 (C语言代码)浏览:787 |
a+b浏览:433 |
演讲大赛评分 (C语言代码)浏览:1638 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:509 |