PAT A1049计算1的个数

题意

输入N，从1~N求有几个1。

简单思路

枚举，先用子函数求出每一个数中出现1的次数，然后在主函数中循环从1-N。

#include<iostream> #include<algorithm> using namespace std; int get_one(int n){ int a,sum=0; while(n){ a=n%10; //循环每一位 if(a==1) sum++; n=n/10; } return sum; } int main(){ int n,sum=0; scanf("%d",&n); for(int i=1;i<=n;i++){ sum+=get_one(i); } printf("%d",sum); return 0; }

虽然超时了两个测试点，但是我感觉这个还是可以拿分的。

更正

#include<cstdio> #include<cstdlib> using namespace std; int main(){ int n,a=1,ans=0; int left,right,now; scanf("%d",&n); while(n/a){ //从低到高枚举n的每一位 left=n/(a*10); //left是高位 now=n/a%10; //now是当前处理位 right=n%a; //right是低位 if(now==0) ans+=left*a; //如果当前处理位是0的话，1的个数就是高位*当前的数位 else if(now==1) ans+=left*a+right+1; //如果当前处理位为是1的话，1的个数就是高位*当前数位+低位+1 else ans+=(left+1)*a; //如果当前位>=2的话，1的个数就是（高位+1）*当前数位 a*=10; //从低到高循环数位 } printf("%d",ans); system("pause"); return 0; }

看了一下算法笔记，这个找规律也太麻烦惹。 而且因为我用的是VS2010，所以需要system(“pause”)让测试黑框不要一闪而过