分析与解法

【问题1的解法一】

这个问题看上去并不是一个困难的问题，因为不需要太多的思考，我想大家都能找到一个最简单的方法来计算f（N），那就是从1开始遍历到N，将其中每一个数中含有“1”的个数加起来，自然就得到了从1到N所有“1”的个数的和。写成程序如下：

代码清单2-9

这个方法很简单，只要学过一点编程知识的人都能想到，实现也很简单，容易理解。但是这个算法的致命问题是效率，它的时间复杂度是

O（N）×计算一个整数数字里面“1”的个数的复杂度 = O（N * log₂ N）

如果给定的N比较大，则需要很长的运算时间才能得到计算结果。比如在笔者的机器上，如果给定N=100 000 000，则算出f（N）大概需要40秒的时间，计算时间会随着N的增大而线性增长。

看起来要计算从1到N的数字中所有1的和，至少也得遍历1到N之间所有的数字才能得到。那么能不能找到快一点的方法来解决这个问题呢？要提高效率，必须摈弃这种遍历1到N所有数字来计算f（N）的方法，而应采用另外的思路来解决这个问题。

【问题1的解法二】

仔细分析这个问题，给定了N，似乎就可以通过分析“小于N的数在每一位上可能出现1的次数”之和来得到这个结果。让我们来分析一下对于一个特定的N，如何得到一个规律来分析在每一位上所有出现1的可能性，并求和得到最后的f（N）。

先从一些简单的情况开始观察，看看能不能总结出什么规律。

先看1位数的情况。

如果N = 3，那么从1到3的所有数字：1、2、3，只有个位数字上可能出现1，而且只出现1次，进一步可以发现如果N是个位数，如果N>=1，那么f（N）都等于1，如果N=0，则f（N）为0。

再看2位数的情况。

如果N=13，那么从1到13的所有数字：1、2、3、4、5、6、7、8、9、10、11、12、13，个位和十位的数字上都可能有1，我们可以将它们分开来考虑，个位出现1的次数有两次：1和11，十位出现1的次数有4次：10、11、12和13，所以f（N）=2+4=6。要注意的是11这个数字在十位和个位都出现了1，但是11恰好在个位为1和十位为1中被计算了两次，所以不用特殊处理，是对的。再考虑N=23的情况，它和N=13有点不同，十位出现1的次数为10次，从10到19，个位出现1的次数为1、11和21，所以f（N）=3+10=13。通过对两位数进行分析，我们发现，个位数出现1的次数不仅和个位数字有关，还和十位数有关：如果N的个位数大于等于1，则个位出现1的次数为十位数的数字加1；如果N的个位数为0，则个位出现1的次数等于十位数的数字。而十位数上出现1的次数不仅和十位数有关，还和个位数有关：如果十位数字等于1，则十位数上出现1的次数为个位数的数字加1；如果十位数大于1，则十位数上出现1的次数为10。

f(13) = 个位出现1的个数 + 十位出现1的个数 = 2 + 4 = 6；

f(23) = 个位出现1的个数 + 十位出现1的个数 = 3 + 10 = 13；

f(33) = 个位出现1的个数 + 十位出现1的个数 = 4 + 10 = 14；

…

f(93) = 个位出现1的个数 + 十位出现1的个数 = 10 + 10 = 20；

接着分析3位数。

如果N = 123：

个位出现1的个数为13：1, 11, 21, …, 91, 101, 111, 121

十位出现1的个数为20：10～19, 110～119

百位出现1的个数为24：100～123

f（23）= 个位出现1的个数 + 十位出现1的个数 + 百位出现1的次数 = 13 + 20 + 24 = 57；

同理我们可以再分析4位数、5位数。读者朋友们可以写一写，总结一下各种情况有什么不同。

根据上面的一些尝试，下面我们推导出一般情况下，从N得到f（N）的计算方法：

假设N=abcde，这里a、b、c、d、e分别是十进制数N的各个数位上的数字。如果要计算百位上出现1的次数，它将会受到三个因素的影响：百位上的数字，百位以下（低位）的数字，百位（更高位）以上的数字。

如果百位上的数字为0，则可以知道，百位上可能出现1的次数由更高位决定，比如12 013，则可以知道百位出现1的情况可能是100～199，1 100～1 199，2 100～2 199，…，11 100~11 199，一共有1 200个。也就是由更高位数字（12）决定，并且等于更高位数字（12）×当前位数（100）。

如果百位上的数字为1，则可以知道，百位上可能出现1的次数不仅受更高位影响，还受低位影响，也就是由更高位和低位共同决定。例如对于12 113，受更高位影响，百位出现1的情况是100～199，1 100～1 199，2 100～2 199，…，11 100~11 199，一共1 200个，和上面第一种情况一样，等于更高位数字（12）×当前位数（100）。但是它还受低位影响，百位出现1的情况是12 100～12 113，一共114个，等于低位数字（123）+1。

如果百位上数字大于1（即为2~9），则百位上可能出现1的次数也仅由更高位决定，比如12 213，则百位出现1的可能性为：100～199，1 100～1 199，2 100～2 199，…，11 100～11 199，12 100～12 199，一共有1 300个，并且等于更高位数字+1（12+1）×当前位数（100）。

通过上面的归纳和总结，我们可以写出如下的更高效算法来计算f（N）：

代码清单2-10

{

    ULONGLONG iCount = 0;

    ULONGLONG iFactor = 1;

    ULONGLONG iLowerNum = 0;

    ULONGLONG iCurrNum = 0;

    ULONGLONG 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;

这个方法只要分析N就可以得到f（N），避开了从1到N的遍历，输入长度为Len的数字N的时间复杂度为O（Len），即为O（ln（n）/ln（10）+1）。在笔者的计算机上，计算N=100 000 000，相对于第一种方法的40秒时间，这种算法不到1毫秒就可以返回结果，速度至少提高了40 000倍。

【问题2的解法】

要确定最大的数N，满足f（N）=N。我们通过简单的分析可以知道（仿照上面给出的方法来分析）：

                9以下为：                                           1个；

               99以下为：                      1×10+10×1=20个；

           999以下为：                 1×100+10×20=300个；

          9999以下为：           1×1000+10×300=4000个；

                   …

 999999999以下为：                          900000000个；

9999999999以下为：                          10000000000个。

容易从上面的式子归纳出：f（10^n-1）= n * 10^n-1。通过这个递推式，很容易看到，当n = 9时候，f（n）的开始值大于n，所以我们可以猜想，当n大于某一个数N时，f（n）会始终比n大，也就是说，最大满足条件在0～N之间，亦即N是最大满足条件f（n）= n的一个上界。如果能估计出这个N，那么只要让n从N往0递减，每个分别检查是否有f（n）= n，第一个满足条件的数就是我们要求的整数。

因此，问题转化为如何证明上界N确实存在，并估计出这个上界N。

证明满足条件f（n）= n的数存在一个上界

首先，用类似数学归纳法的思路来推理这个问题。很容易得到下面这些结论（读者朋友可以自己试着列举验证一下）：

当n增加10时，f（n）至少增加1；

当n增加100时，f（n）至少增加20；

当n增加1 000时，f（n）至少增加300；

当n增加10 000时，f（n）至少增加4 000；

……

当n增加10^k时，f（n）至少增加k*10^k-1。

首先，当k>=10时，k*10 ^k-1> 10 ^k，所以f（n）的增加量大于n的增加量。

其次，f（10^10-1）=10¹⁰>10^10-1。如果存在N，当n = N时，f（N）-N>10^10-1成立时，此时不管n增加多少，f（n）的值将始终大于n。

具体来说，设n的增加量为m：当m小于10^10-1时，由于f（N）-N>10^10-1，因此有f（N + m）> f（N）> N + 10^10-1 > N + m，即f（n）的值仍然比n的值大；当m大于等于10^10-1时，f （n）的增量始终比n的增量大，即f（N + m）- f（N）>（N+m）- N，也就是f（N + m）> f（N）+ m > N + 10^10-1+ m > N + m，即f（n）的值仍然比n的值大。

因此，对于满足f（N）- N > 10^10-1成立的N一定是所求该数的一个上界。

求出上界N

又由于f（10^10-1）= n *10^10-1，不妨设N = 10^K-1，有f（10 ^K-1）-（10 ^K-1）> 10^10-1，即K*10 ^K-1 -（10 ^K-1）> 10^10-1，易得K > =11时候均满足。所以，当K = 11时，N=10^11-1即为最小一个上界。

计算这个最大数n

令N = 10^11-1=99 999 999 999，让n从N往0递减，每个分别检查是否有f（n）= n，第一满足条件的就是我们要求的整数。很容易解出n = 1 111 111 110是满足f（n）= n的最大整数。

扩展问题

对于其他进制表达方式，也可以试一试，看看有什么规律。例如二进制：

f（1）= 1

f（10）= 10（因为01, 10有两个1）

f（11）= 100（因为01, 10, 11有四个1）

读者朋友可以模仿我们的分析方法，给出相应

int countone(int n)

{

  int t=1,temp=0;

  if(n==0) t=0;

  for(int i=10;i<=n;i*=10)

  {

    temp=int(n/i);

    if(temp>1)

    {

      t=t+temp+i;

    }

    if(temp==1)

    {

      t=t+(n-i)+1;

    }

  }

  return t+(n%10>0);

}

//--This is true----

int countone(int n)

{

  int t=0,temp=0;

  if(n==0) t=0;

  for(int i=10;i<=n;i*=10)

  {

    temp=int(n/i);

    if(temp>1)

    {

      t=t+temp+i;

    }

    if(temp==1)

    {

      t=t+(n-i+1)+1;

    }

  }

  return t+(n%10>0);

}

int countone(int n)

{

  int t=0;

  int lownum=0;

  int curnum=0;

  int hignum=0;

  for(int i=1,j=1;i<=n;i*=10)

  {

    lownum=n-(n/i)*i;

    curnum=(n/i)%10;

    hignum=n/(i*10);

    switch(curnum)

    {

    case 0:

      t+=hignum*i;

      break;

    case 1:

      t+=hignum*i+lownum+1;

      break;

    default:

      t+=(hignum+1)*i;

      break;

    }

  }

  return t;

}

我用VS.NET 2005 C# 写的最原始的实现方案:窗体中放一个文本框让用户输入一个整数,然后点击命令按扭时在一个多行文本框中显示所有的整数,同时统计出现1的次数并在另外一个文本框中显示出现的次数是多少.主要源代码如下:

int n = 0;

richTextBox1.Text = "";

//输入整数不为空并且第一个数不能为O

if (textBox1.Text != "" && textBox1.Text.Substring(0,1) != "0")

{

  n = Convert.ToInt32(textBox1.Text);

  //向多行文本框中写入数字

  for (int i = 1; i <= n; i++)

  {

    richTextBox1.Text = richTextBox1.Text + i.ToString() + "\n";

  }

  //统计出现1的个数

  int len = richTextBox1.Text.Length - 1;

  int one = 0;

  char[] sum = new char[len];

  sum = richTextBox1.Text.ToCharArray();

  for (int j = 0; j < len; j++)

  {

    if (sum[j] == Convert.ToChar("1"))

    {

      one++;

    }

  }

  textBox2.Text = one.ToString();

}

else

{

  MessageBox.Show("请输入要显示的整数且不能为0！", "提示", MessageBoxButtons.OK);

  textBox1.Focus();

}

先考虑这样的问题：求n位数中出现的“1”的个数g(n)，这里的n位数包括“0”填充高位的情形，例如“001”认为是3位数。

如果去掉n位数的最高位，则剩下的是一个n-1位数。于是我们可以固定住最高位，做成一个递归的形状，只需要找出g(n)和g(n-1)就可以解决这个问题。利用一点数数的知识，可以知道：最高位可以取从0到9的10个数字，每取定一个数字，对应的剩余n-1位都将出现g(n-1)个“1”，加上最高位出现的“1”，最后有g(n) = 10*g(n-1) + 10^(n-1)。

对于任给的正整数N，先计算其位数，然后利用上面问题的结论，简单处理可以得到函数f(N)。

要求满足条件“f(N) = N”的最大N值，需要注意：f(N) <= g(N的位数)。因此如果10^(N的位数-1) - 9 > g(N的位数)，那么N的位数的整数都是不满足条件的。

我倒是觉得 第一个问题的解释太复杂了 简单地说 f(x)= 1 ( 1<=x<=9) f(99) = 9*f(9) + f (9) + 10; f (256 ) = 2 * f(99) + f(56) + 100;