从1到n整数中1出现的次数 代码(C)

本文地址: http://blog.csdn.net/caroline_wendy

题目: 输入一个整数n, 求从1到n这n个整数的十进制表示中1出现的次数.

把拆分为最高位数字, 其余数字, 最后数字求解.

21345 -> 1346-21345[10000-19999, 最高位 + 1346-x1345其余位数] + 1-1345;

代码:

/*
 * main.cpp
 *
 *  Created on: 2014年6月29日
 *      Author: wang
 */

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; int PowerBase10(size_t n) { int result = 1; for (size_t i=0; i
      
       '9' || *strN == '\n') return 0; int first = *strN - '0'; size_t length = strlen(strN); if (length == 1 && first == 0) return 0; if (length == 1 && first > 0) return 1; //最高位数字 int numFirstDight = 0; if (first > 1) numFirstDight = PowerBase10(length-1); else if (first == 1) numFirstDight = atoi(strN+1) + 1; //+1去除最高位, 在加1 //其余数字 int numOtherDights = first*(length-1)*PowerBase10(length-2); //最后剩余 int numRecursive = NumberOf1(strN + 1); return numFirstDight + numOtherDights + numRecursive; } int NumberOf1Between1AndN (int n) { if (n<=0) return 0; char strN[50]; sprintf(strN, "%d", n); return NumberOf1(strN); } int main(void) { int result = NumberOf1Between1AndN(12); printf("result = %d\n", result); return 0; } 
      
     
    
   
  

result = 5