数据结构与算法

打印1到最大的n位数

略

题目：输入数字n，按顺序打印出从1最大的n位数。比如输入3，则打印1、2、3一直到最大3位数即是999。

分析

耿直的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void Print1ToMaxOfNDigits_1(int n)
{
    int number = 1;
    int i = 0;
    while(i++ < n)
    {
        number *= 10;
    }
    for(i = 0 ; i < number ; i++)
    {
        System.out.println(i + "\t");
    }
    
}

  乍一看代码并没什么错误，但是却忽略了一个因素，就是当n特别大时会导致溢出。

在字符串上模拟数字加法的解法

  首先把字符串上的每一个数字都初始化为0，然后每一次为字符串表示的数字加一，再打印出来。因此需要做两件事，一是字符串上模拟加法，二是把字符串表示的数字打印出来。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public static void Print1ToMaxOfNDigits(int n)
{
    if(n < 0 )
    {
        return;
    }
    char[] number = new char[n]; 
    
    //给number数组赋初值0
    for(int i = 0 ; i < n ; i++)
    {
        number[i] = '0';
    }
    
    
    while(!Increment(number))
    {
        PrintNumber(number);
    }
}

  其中Increment(char[] number)方法是用来实现字符串上模拟加法，PrintNumber(char[] number)方法是用来实现输出的。

Increment方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
    * 实现数字数组加1的功能
    * @param number 数字数组
    * @return 是否溢出，即是否已经打印完所有1到n位最大数，是返回true
    */
   public static Boolean Increment(char[] number)
   {
       Boolean isOverflow = false;
       int nTakeOver = 0;
       int nLength = number.length;
       for(int i = nLength - 1 ; i >= 0 ; i--)
       {
           int nSum = number[i] - '0' + nTakeOver;
           if(i == nLength -1) //数字的最低位 
           {
               nSum ++;
           }
           
           if(10 <= nSum) //产生进位
           {
               if(0 == i)  //产生进位的是最高位，证明已经打印完所有数了
               {
                   isOverflow = true;
               }
               else   //产生进位的不是最高位
               {
                   nSum -= 10;
                   nTakeOver = 1;  //高一位要加1
                   number[i] = (char) ('0' + nSum);
               }
               
           }
           else
           {
               number[i] = (char) ('0' +nSum);
               break;
           }
       }
       return isOverflow;
   }

PrintNumber方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
    * 打印出数组，去掉数组前面的0
    * @param number 要打印的数组
    */
   public static void PrintNumber(char[] number)
   {
       Boolean isBeginning0 = true;
       int nLength = number.length;
       
       for(int i = 0 ; i < nLength ; i++)
       {
           if(isBeginning0 && '0' != number[i])   //用于判断是否是0开头
           {
               isBeginning0 = false;
           }
           if(!isBeginning0)
           {
               System.out.print(number[i]);
           }
       }
       System.out.println("");
   }

总结

  1. 对于大数问题的处理，可以用数组来实现。
  2. 输出数字时，要考虑头几位可能是0的情况，为了符合阅读习惯，所以需要不输入开头的0。