（说明：本博客中的题目、题目详细说明及参考代码均摘自 “何海涛《剑指Offer：名企面试官精讲典型编程题》2012年”）
题目
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数．比如输入 3，则打印出 1,2,3 一直到最大的 3 位数即 999 .
算法设计思想
由于最大的 n 位十进制可能超过整型范围的限制，而成为大数问题．本题目的关键是如何实现大数的表示或运算．本博客采用参考书中的两种方法，将从 1 到最大 n 位数之间的所有数都看作 n 位数，实际的数若不足 n 位，则在前补 0．具体的设计思想如下 ：
1) 使用字符串模拟数字加法，从 1 开始递增到最大 n 位数． 在计算机中，n 位数可用包含 n 个指定字符（ '0' - '9' ）的字符串（所有字符均为 '0' 除外）表示．其可以想象为对字符串实现伪码：for ( i = 1; i < max_n_digits; i++ ) print i;
2) 将 n 位数看做是 n 个数（0 - 9）的排列问题．
n 位数的排列问题，即 n 位数的每一位都可取 10 个数（0 - 9）中任意一个数，对于 n 位数，共有 10^n 个选择，注意需要去掉所有位都是 0 的排列，与上一个方法的输出结果相同．易错点：在打印每个数时，打印前导零是没有意义的．其中，前导零是第一个非零元素的最高有效位之前的所有零．
C++实现
/** Author: klchang* Date: 2018.2.26* Description: Print digits from 1 to the maximum n digits.*/#include#include // Check if the string contains illegal charactersbool checkDigitString(std::string numeric_str){ bool isLegal = true; std::basic_string ::iterator iter = numeric_str.begin(); for (; iter != numeric_str.end(); ++ iter) { char ch = *iter; if (ch < '0' || ch > '9') { isLegal = false; break; } } return isLegal;}// Remove the leading zeros in a numeric stringstd::string removeLeadingZeros(std::string numeric_str){ int i = 0; size_t len = numeric_str.length(); // Return null string when including illegal characters if (!checkDigitString(numeric_str)) { std::cout << "Input string " << numeric_str << " contains at least an illegal character." << std::endl; return ""; } for (; i < len; ++i) { if (!(numeric_str[i] == '0')) break; } if (i >= len) { numeric_str = "0"; } else { numeric_str = numeric_str.substr(i); } return numeric_str;}// Simulate the numeric operation that numeric string adds onestd::string incrementByOne(std::string& numeric_str){ size_t len = numeric_str.size(); std::string output_str(numeric_str); if (len <= 0) return output_str; int carry = 0; bool lowest_bit = true; std::basic_string ::reverse_iterator riter = output_str.rbegin(); for (; riter != output_str.rend(); ++ riter) { int value = *riter - '0'; if (lowest_bit) { lowest_bit = false; value ++; } value += carry; carry = 0; // clear carry if (value > 9) { carry = 1; value -= 10; } *riter = '0' + value; // update correspondent characters if (carry <= 0) break; } // pass the length of number string if (carry > 0) { output_str = std::string("1") + output_str; } return output_str;}// Compare the two numeric strings// Return value: int, // 1 when s1 > s2; 0 when s1 == s2; -1 when s1 < s2int compare(std::string s1, std::string s2){ int result = 0; std::string valid_s1, valid_s2; valid_s1 = removeLeadingZeros(s1); valid_s2 = removeLeadingZeros(s2); size_t len_1 = valid_s1.size(); size_t len_2 = valid_s2.size(); if (len_1 > len_2) { result = 1; } else if (len_1 < len_2) { result = -1; } else { std::basic_string ::iterator iter1 = valid_s1.begin(); std::basic_string ::iterator iter2 = valid_s2.begin(); for (; iter1 != valid_s1.end(); ++iter1, ++iter2 ) { if (*iter1 == *iter2) { continue; } else if (*iter1 > *iter2) { result = 1; } else { result = -1; } break; } } return result;}// Print the digits without the leading zerosvoid printDigits(std::string digits){ std::string out_str = removeLeadingZeros(digits); if (out_str != "0") { std::cout << out_str << std::endl; }}// Print N digits of length `length` starting from index startvoid printNDigitsRecursively(char* digits, int length, int start){ if (length == start) { std::string cur_number = digits; printDigits(cur_number); return; } // Set the digit of the start index for (int i = 0; i < 10; ++ i) { digits[start] = i + '0'; printNDigitsRecursively(digits, length, start+1); }}// print digits from 1 to maximumvoid printNDigits(int n, int method=0){ if (n <= 0) { std::cout << "ERROR: Illegal parameters n <= 0!" << std::endl; return; } if (method == 1) { // Recursive method std::cout << "\nUse the recursive method to print the numbers from 1 to maximum n digits: " << std::endl; int start = 1; char* digits = new char[n+1]; digits[n] = '\0'; // easy to forget to add the '\0' to the C string for (int i = 0; i < 10; ++i) { digits[0] = i + '0'; // Convert digit to character digits printNDigitsRecursively(digits, n, start); } delete[] digits; } else { // Simulation of the integer self-incrementation operation method // for (i = 0; i < 10; ++i) print i std::cout << "\nSimulate the self incrementation of the integer: " << std::endl; // Construct maximum integer in string form std::string maxNdigits(""); for (int i = 0; i < n; ++i) maxNdigits += "9"; std::string cur_num = "1"; do { std::cout << cur_num << std::endl; cur_num = incrementByOne(cur_num); } while (compare(maxNdigits, cur_num) >= 0); std::cout << std::endl; }}void unitest(){ int n = 3; printNDigits(n, 1); // recursive method printNDigits(n, 0); // simulation method}int main(){ unitest(); return 0;}
Python 实现
#!/usr/bin/python#-*- coding: utf8 -*-"""# Author: klchang# Date: 2018.2.26# Description: Print digits from 1 to the maximum n digits."""# Generic interface to print numbers from 1 to the maximum of n digitsdef print_n_digits(n, method=0): if n <= 0: print("ERROR: Illegal parameters n <= 0!") return if method == 1: print("\nUse the recursive method to print the numbers from 1 to maximum n digits: ") string = ["0" for i in range(n)] print_n_digits_recursive(string, n, 0) else: print("\nSimulate the self incrementation of the integer: ") print_n_digits_simulation(n) # Use the recursive method to printdef print_n_digits_recursive(string, length, start): if length == start: output = remove_leading_zeros("".join(string)) if output != '0': print(output) return for i in range(0,10): string[start] = repr(i) print_n_digits_recursive(string, length, start+1) # Use the simulation method to printdef print_n_digits_simulation(n): max_num = '9' * n curr_num = '1' while True: print(curr_num) next_num = increment_by_one(curr_num) # add by 1 function: i += 1 # Check if next_num > max_num if compare(next_num, max_num) > 0: # compare function: i > , <, or == some_number break else: curr_num = next_numdef remove_leading_zeros(num): i = 0 for ch in num[:-1]: if '0' == ch: i += 1 else: break return num[i:] # Compare two digits stringdef compare(num_1, num_2): result = 0 real_num_1 = remove_leading_zeros(num_1) real_num_2 = remove_leading_zeros(num_2) len_1 = len(real_num_1) len_2 = len(real_num_2) if len_1 == len_2: if real_num_1 > real_num_2: result = 1 elif real_num_1 < real_num_2: result = -1 else: result = 0 else: if len_1 > len_2: result = 1 elif len_1 < len_2: result = -1 else: result = 0 return result def check_digits_string(num): is_legal = True # Check if the input num string is legal or not # Check the type if not isinstance(num, str): is_legal = False print("Input param is not str type!") # Check the length num_length = len(num) if num_length <= 0: is_legal = False print('Illegal String: null str') # Check the characters contained legal_chars = set([repr(i) for i in range(10)]) for ch in num: if ch not in legal_chars: print("Input number string includes non-digit character") is_legal = False break return is_legal def increment_by_one(num): next_ = '' num = remove_leading_zeros(num) # First, check that it is a legal input number string. if not check_digits_string(num): return next_ # The effective length of num num_length = len(num) # The Least Significant Bit carry = False char_code = ord(num[-1]) + 1 out_seq, index = [], 0 for i in range(num_length-2, -1, -1): if char_code > ord('9'): carry = True out_seq.append('0') else: out_seq.append(chr(char_code)) index = i + 1 break # Process the case with carry char_code = ord(num[i]) + 1 carry = False # Reverse the output sequence out_seq.reverse() next_ = ''.join(out_seq) if char_code > ord('9'): next_ = '10' + next_ # Overflow elif index == 0: next_ = chr(char_code) + next_ else: next_ = num[:index] + next_ return next_ def unitest(): n = 3 print_n_digits(n, 1) # recursive method print_n_digits(n, 0) # simulation methodif __name__ == '__main__': unitest()
参考代码
1. targetver.h
#pragma once// The following macros define the minimum required platform. The minimum required platform// is the earliest version of Windows, Internet Explorer etc. that has the necessary features to run // your application. The macros work by enabling all features available on platform versions up to and // including the version specified.// Modify the following defines if you have to target a platform prior to the ones specified below.// Refer to MSDN for the latest info on corresponding values for different platforms.#ifndef _WIN32_WINNT // Specifies that the minimum required platform is Windows Vista.#define _WIN32_WINNT 0x0600 // Change this to the appropriate value to target other versions of Windows.#endif
2. stdafx.h
// stdafx.h : include file for standard system include files,// or project specific include files that are used frequently, but// are changed infrequently//#pragma once#include "targetver.h"#include#include // TODO: reference additional headers your program requires here
3. stdafx.cpp
// stdafx.cpp : source file that includes just the standard includes// Print1ToMaxOfNDigits.pch will be the pre-compiled header// stdafx.obj will contain the pre-compiled type information#include "stdafx.h"// TODO: reference any additional headers you need in STDAFX.H// and not in this file
4. Print1ToMaxOfNDigits.cpp
// Print1ToMaxOfNDigits.cpp : Defines the entry point for the console application.//// 《剑指Offer――名企面试官精讲典型编程题》代码// 著作权所有者：何海涛#include "stdafx.h"#includevoid PrintNumber(char* number);bool Increment(char* number);void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index);// ====================方法一====================void Print1ToMaxOfNDigits_1(int n){ if(n <= 0) return; char *number = new char[n + 1]; memset(number, '0', n); number[n] = '\0'; while(!Increment(number)) { PrintNumber(number); } delete []number;} // 字符串number表示一个数字，在 number上增加1// 如果做加法溢出，则返回true；否则为falsebool Increment(char* number){ bool isOverflow = false; int nTakeOver = 0; int nLength = strlen(number); for(int i = nLength - 1; i >= 0; i --) { int nSum = number[i] - '0' + nTakeOver; if(i == nLength - 1) nSum ++; if(nSum >= 10) { if(i == 0) isOverflow = true; else { nSum -= 10; nTakeOver = 1; number[i] = '0' + nSum; } } else { number[i] = '0' + nSum; break; } } return isOverflow;}// ====================方法二====================void Print1ToMaxOfNDigits_2(int n){ if(n <= 0) return; char* number = new char[n + 1]; number[n] = '\0'; for(int i = 0; i < 10; ++i) { number[0] = i + '0'; Print1ToMaxOfNDigitsRecursively(number, n, 0); } delete[] number;} void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index){ if(index == length - 1) { PrintNumber(number); return; } for(int i = 0; i < 10; ++i) { number[index + 1] = i + '0'; Print1ToMaxOfNDigitsRecursively(number, length, index + 1); }}// ====================公共函数====================// 字符串number表示一个数字，数字有若干个0开头// 打印出这个数字，并忽略开头的0void 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("\t");}// ====================测试代码====================void Test(int n){ printf("Test for %d begins:\n", n); Print1ToMaxOfNDigits_1(n); Print1ToMaxOfNDigits_2(n); printf("Test for %d ends.\n", n);}int _tmain(int argc, _TCHAR* argv[]){ Test(1); Test(2); Test(3); Test(0); Test(-1); return 0;}
5. 参考代码下载
项目 12_Print1ToMaxOfNDigits 下载：
何海涛《剑指Offer：名企面试官精讲典型编程题》 所有参考代码下载：
参考资料
[1] 何海涛. 剑指 Offer：名企面试官精讲典型编程题 [M]. 北京：电子工业出版社，2012. 94-99.