xnow - 巧解一道ACM的计数题

也是暑假时候的事了，买了一本ACM程序设计的基础教程，下面是这本书的第一道题目，看了解答，一直没看明白，不知道是用的什么公式还是啥的！！！当然，可能是本人智商的问题！！！但是，通过一些小技巧，我发现如果从另一个想法入手，其实这道题还有一个更加想得明白的解法。大晚上的刚刚把自己的方法实现了一遍，结果是完全正确的！！！题目如下：

给定两个数a和b，计算出1在a和b之间出现的次数，例如，如果a=1024，b=1032，那么a和b之间的数就是： 1024,1025,1026,1027,1028,1029,1030,1031,1032
则有10个1出现在这些数中。输入：输入不会超过500行。每一行有两个数a和b，a和b的范围是0<a,b<100 000 000。官方解答如下，研究了很久也没明白，有看明白的请给个指教！！！

#include<iostream>
using namespace std;

const int N=11;
int d[N];
int value;

void deal(int n)
{
	if(n<=0) return ;
	int one,ten;
	one=n%10;
	n/=10;
	ten=n;
	
	for(int i=0;i<=one;i++)
 		d[i]+=value;
	while(ten)
	{
		d[ten%10]+=(one+1)*value;
		ten/=10;
	}
	for(int i=0;i<10;i++)
		d[i]+=value*n;
	d[0]-=value;
	value*=10;
	deal(n-1);
}

int main()
{
	int a,b;
	while(cin>>a>>b)
	{
		if(a==0&&b==0)break;
		if(a<b){int tmp=b;b=a;a=tmp;}
		for(int i=0;i<10;i++)
			d[i]=0;
		value=1;
		deal(a);
		value=-1;
		deal(b-1);
		cout<<d[1]<<endl;
	}
	return 0;
}

看不懂这个答案的同学就接下来看看我的方法吧！！！思路如下：从第一个数开始，先把数字转换成字符串，数出字符串里面1的个数，然后，再将下一个数字转换成字符串，并加上以前的1的个数，直到最后的一个数。上代码：

#include<iostream>
#include<string.h>
using namespace std;

int cnt(char str[])
{
	int d=0,i=0;
	for(char c=str[i];i<strlen(str);c=str[i])
	{
		if(str[i]=='1')
		{
			d++;
		}	
		i++;
	}
	return d;
}

int main()
{
	int a,b,count;
	while(cin>>a>>b)
	{
		count=0;
		if(a==0&&b==0)break;
		if(a<b){int tmp=b;b=a;a=tmp;}
		for(int i=b;i<=a;i++)
		{
			char str[10];
			itoa(i,str,10);
			count=count+cnt(str);
		}
		cout<<count<<endl;
	}
	return 0;	
}

我的这个答案也算是巧解了吧，说到巧解，想起来以前在《疯狂的程序员》这本书看到的一个故事。问，怎么样计算出未来某个年月日是星期几？这个计算貌似是有公式的，但是，作者的解法是这样的。先把计算机的当前时间存起来，在修改系统时间设置为未来所要求的那个时间，然后得到这个日子的星期数，并存下来，然后将系统时间还原为当前时间，并返回存起来的那个星期数！！！

昔我往矣

巧解一道ACM的计数题