1677 - 数数
时间限制 : 1 秒
内存限制 : 32 MB
ACM俱乐部里的那些无聊家伙经常举行数数比赛- -。
比赛规则就是对于一个给出的正整数n，把1到n的正整数写在纸上，然后数里面数字1被写出来的次数。
题目输入
输入有多组数据。
每组数据一行，包含一个正整数n（小于等于2^26）。
题目输出
对应每组数据，输出所求的1的出现次数。
输入/输出样例
输入格式
11 20
输出格式
4 12
C语言解答
#include<stdio.h> long long int Count(long long int n){ //1的个数 long long int count = 0; //当前位 long long int Factor = 1; //低位数字 long long int LowerNum = 0; //当前位数字 long long int CurrNum = 0; //高位数字 long long int HigherNum = 0; if(n <= 0){ return 0; } while(n / Factor != 0){ //低位数字 LowerNum = n - (n / Factor) * Factor; //当前位数字 CurrNum = (n / Factor) % 10; //高位数字 HigherNum = n / (Factor * 10); //如果为0,出现1的次数由高位决定 if(CurrNum == 0){ //等于高位数字 * 当前位数 count += HigherNum * Factor; } //如果为1,出现1的次数由高位和低位决定 else if(CurrNum == 1){ //高位数字 * 当前位数 + 低位数字 + 1 count += HigherNum * Factor + LowerNum + 1; } //如果大于1,出现1的次数由高位决定 else{ //（高位数字+1）* 当前位数 count += (HigherNum + 1) * Factor; } //前移一位 Factor *= 10; } return count; } int main(){ long long int a; while(scanf("%lld",&a) != EOF){ printf("%lld\n",Count(a)); } return 0; }
C++解答
#include <stdio.h> #include <string.h> #include <stdlib.h> int NumberOf1(const char* strN); int PowerBase10(unsigned int n); ///////////////////////////////////////////////////////////////////////////// // Find the number of 1 in an integer with radix 10 // Input: n - an integer // Output: the number of 1 in n with radix ///////////////////////////////////////////////////////////////////////////// int NumberOf1BeforeBetween1AndN_Solution2(int n) { if(n <= 0) return 0; // convert the integer into a string char strN[50]; sprintf(strN, "%d", n); return NumberOf1(strN); } ///////////////////////////////////////////////////////////////////////////// // Find the number of 1 in an integer with radix 10 // Input: strN - a string, which represents an integer // Output: the number of 1 in n with radix ///////////////////////////////////////////////////////////////////////////// int NumberOf1(const char* strN) { if(!strN || *strN < '0' || *strN > '9' || *strN == '\0') return 0; int firstDigit = *strN - '0'; unsigned int length = static_cast<unsigned int>(strlen(strN)); // the integer contains only one digit if(length == 1 && firstDigit == 0) return 0; if(length == 1 && firstDigit > 0) return 1; // suppose the integer is 21345 // numFirstDigit is the number of 1 of 10000-19999 due to the first digit int numFirstDigit = 0; // numOtherDigits is the number of 1 01346-21345 due to all digits // except the first one int numOtherDigits = firstDigit * (length - 1) * PowerBase10(length - 2); // numRecursive is the number of 1 of integer 1345 int numRecursive = NumberOf1(strN + 1); // if the first digit is greater than 1, suppose in integer 21345 // number of 1 due to the first digit is 10^4. It's 10000-19999 if(firstDigit > 1) numFirstDigit = PowerBase10(length - 1); // if the first digit equals to 1, suppose in integer 12345 // number of 1 due to the first digit is 2346. It's 10000-12345 else if(firstDigit == 1) numFirstDigit = atoi(strN + 1) + 1; return numFirstDigit + numOtherDigits + numRecursive; } ///////////////////////////////////////////////////////////////////////////// // Calculate 10^n ///////////////////////////////////////////////////////////////////////////// int PowerBase10(unsigned int n) { int result = 1; for(unsigned int i = 0; i < n; ++ i) result *= 10; return result; } int main() { int n; while(scanf("%d",&n)!=EOF) printf("%d\n",NumberOf1BeforeBetween1AndN_Solution2(n)); return 0; }