面试题17：打印从1到最大的n位数

本题考查大数问题。大数一般用字符串或者数组表示。注意，strlen()函数返回的值是数组' '前元素的个数，并不包括' '。

C++版本

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

bool increment(char number[]){
    // 记录是否到达计数尽头
    bool isOverFlow = false;
    // 第n个位置的进位
    int nTakeOver = 0;
    int nLength = strlen(number);
    for(int i = nLength-1; i>=0; i--){
        // 计算第n个位置的十进制值
        int nSum = number[i] - '0' + nTakeOver;
        // 如果是最后一位数，则加1
        if(i == nLength - 1)
            nSum++;
        // 如果产生了进位
        if(nSum > 9){
            // 如果是首位产生了进位
            if(i == 0)
                isOverFlow = true;
            else{
                // 当前位置0
                number[i] = '0';
                // 将下一次的进位置一
                nTakeOver = 1;
            }
        }
        // 没有产生进位，则接下来不需要再计算
        else{
            number[i] = '0' + nSum;
            break;
        }
    }
    return isOverFlow;
}

void printNumber(char number[]){
    bool isBeginning0 = true;
    int nLength = strlen(number);
    for(int i = 0; i < nLength; i++){
        if(isBeginning0 && number[i] != '0')
            isBeginning0 = false;
        if(!isBeginning0)
            printf("%c", number[i]);
    }
    printf("	");
}

void printf1ToMaxOfDigits(int num){
    if(num < 0)
        return ;
    char number[num+1];
    memset(number, '0', num);
    number[num] = ' ';
    while(!increment(number)){
        printNumber(number);
    }
}


int main()
{
    printf1ToMaxOfDigits(2);
    return 0;
}