首页 > 其他 > 详细

编程算法 - 从1到n整数中1出现的次数 代码(C)

时间:2014-07-01 11:10:17      阅读:278      评论:0      收藏:0      [点我收藏+]

从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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

using namespace std;

int PowerBase10(size_t n) {
	int result = 1;
	for (size_t i=0; i<n; ++i)
		result *= 10;
	return result;
}

int NumberOf1(const char* strN) {
	if (!strN || *strN<‘0‘ || *strN>‘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






bubuko.com,布布扣

编程算法 - 从1到n整数中1出现的次数 代码(C),布布扣,bubuko.com

编程算法 - 从1到n整数中1出现的次数 代码(C)

原文:http://blog.csdn.net/caroline_wendy/article/details/36058085

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!