分类： C/C++
2012-03-23 14:42:17
Q:
给定一个十进制整数N，写下从1到N的所有整数，然后数一下其中出现的所有的“1”的个数，如10: 1、2、3、4、5、6、7、8、9、10，其中“1”的个数为2。
（1） 写一个函数，返回1到N之间出现的 “1”的个数，如f(10) = 2；
（2） 满足条件”f(N) = N”的最大的N是多少？
A：
（1） 解法1：
从1到N遍历，计算每个数中出现的”1”的个数，算法复杂度为O(N)*计算一个数中1的个数的复杂度=O(N*lgN).
unsigned long count1InAnInteger(unsigned long N)
{
unsigned long num = 0;
while(N)
{
num += (N%10==1) ? 1 : 0;
N /= 10;
}
return num;
}
unsigned long count1InSerial(unsigned long n)
{
unsigned long iCount = 0;
for(unsigned long i=1; i<=n; i++)
{
iCount += count1InAnInteger(i);
}
return iCount;
}
解法2：
归纳法寻找N的各位中包含1的规律：
如果当前位上的数字为0，则在该位上出现1的次数由更高位决定，等于更高位乘以当前位数（十位为10，百位为100）；
如果当前位上的数字为等于1，则该位上出现1的次数由高位和低位共同决定：等于高位乘以当前位数加上低位数字加1；
如果当前位上的数字大于1，则该位上出现1的次数由高位决定：等于高位数字加1然后乘以当前的位数。
typedef unsigned long TYPE;
TYPE sum1s(TYPE n)
{
TYPE iCount = 0;
TYPE iFactor = 1;
TYPE iLowerNum = 0;
TYPE iCurrNum = 0;
TYPE iHigherNum = 0;
while(n/iFactor != 0)
{
iLowerNum = n - (n/iFactor) * iFactor;
iCurrNum = n/iFactor % 10;
iHigherNum = n/(iFactor*10);
switch(iCurrNum)
{
case 0:
iCount += iHigherNum*iFactor;
break;
case 1:
iCount += iHigherNum*iFactor + iLowerNum+1;
break;
default:
iCount += (iHigherNum+1)*iFactor;
break;
}
iFactor *= 10;
}
return iCount;
}
（2）
解：略。
