学步园

我的思路1 的话 就是用空间换时间吧。输入为n然后分配一个n为几位数 分配一个n*位数的字符串，然后sprintf(str,“%d”,num)往字符串输入，最后

从头到为遍历字符串就能求出1的个数。代码如下：

#include "stdio.h"
#include "stdlib.h"

int main()
{
	int n;
	int num;
	int digit=0,index=0;
	char *str;
	int total;
	scanf("%d",&n);
	num=n;
	while(n)
	{
		n/=10;
		++digit;
	}
        str = calloc(digit*num+1,1);
	memset(str,0,digit*num);
	str[0]='\0';
	for(index=1;index<=num;index++)
	{
		sprintf(str+strlen(str),"%d",index);
	}
	index=0;
	total=0;
	while(str[index]!='\0')
	{
		if(str[index]=='1')
			total++;
		index++;
	}
	printf("%d\n",total);
	free(str);
	return 0;
}

这道题目的解法

1 面试宝典有 不过过于复杂，没时间分析，而且变量名给的相当难以明白

2 海涛的书上也有相关的解法，还要用什么递归之类的，感觉好复杂啊。

直到遇见了一位博客园的网友文章，我才是豁然开朗，如释重负啊。

思路怎样的呢。

假如输入 的数 为21356

如何计算呢？ 当然从低位开始咯

低位为6 :  >1  那么 1的数目  就为高于它的数字 加1，然后乘以该位的加权。

                        （2135+1）*1

十位为5 ：（213+1）*10

百位为3： （21+1）*100

千位为1：当为1的时候，需要考虑高位和低位，显然如果有高位不为0的话 X1999--- X1000这种情况还是有的吧，同时还要考虑低位就是 1000-1xxx这里面的数字当然

                   就为 xxx+1

万位为2：（0+1）*10000

还有一种情况没有说明 即当该位为0时 如何处理。

此时 只需处理高位就行了 比如   10xx 显然 为（1+0）*100。为什么不考虑低位呢，因为把高位去掉，那么百位就为0，不需要考虑后面的了。

好了上代码吧

#include "stdio.h"
#include "stdlib.h"


int main()
{
  int n;
  int factor=1;
  int lower=0;
  int current=0;
  int higher=0;
  int sum =0;
  scanf("%d",&n);
  while(n/factor!=0)
  {
	lower=n-(n/factor)*factor;
	current = (n/factor)%10;
	higher =(n/factor)/10;
	switch(current)
	{
		case 0: sum+=higher*factor;
				break;
		case 1: sum+=(higher*factor+lower+1);
				break;
		default:sum+=((higher+1)*factor);
				break;
	}
	factor*=10;
  }
  printf("%d",sum);
 return 0;
}

这个方法很牛叉，有木有啊，有木有~