編程算法 - 從1到n整數中1出現的次數 代碼(C)

從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