正文
打印 1 到最大的 n 位数（C++ 和 Python 实现）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
（说明：本博客中的 题目 、 题目详细说明 及 参考代码 均摘自 “何海涛《 剑指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 = ; 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 <iostream>
#include <string>
// Check if the string contains illegal characters
bool checkDigitString(std::string numeric_str)
{
bool isLegal = true;
std::basic_string<char>::iterator iter = numeric_str.begin();
for (; iter != numeric_str.end(); ++ iter) {
char ch = *iter;
if (ch < '' || ch > '') {
isLegal = false;
break;
}
}
return isLegal;
}
// Remove the leading zeros in a numeric string
std::string removeLeadingZeros(std::string numeric_str)
{
int i = ;
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] == ''))
break;
}
if (i >= len) {
numeric_str = "";
} else {
numeric_str = numeric_str.substr(i);
}
return numeric_str;
}
// Simulate the numeric operation that numeric string adds one
std::string incrementByOne(std::string& numeric_str)
{
size_t len = numeric_str.size();
std::string output_str(numeric_str);
if (len <= )
return output_str;
int carry = ;
bool lowest_bit = true;
std::basic_string<char>::reverse_iterator riter = output_str.rbegin();
for (; riter != output_str.rend(); ++ riter) {
int value = *riter - '';
if (lowest_bit) {
lowest_bit = false;
value ++;
}
value += carry;
carry = ; // clear carry
if (value > ) {
carry = ;
value -= ;
}
*riter = '' + value; // update correspondent characters
if (carry <= ) break;
}
// pass the length of number string
if (carry > ) {
output_str = std::string("") + output_str;
}
return output_str;
}
// Compare the two numeric strings
// Return value: int,
// 1 when s1 > s2; 0 when s1 == s2; -1 when s1 < s2
int compare(std::string s1, std::string s2)
{
int result = ;
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 = ;
} else if (len_1 < len_2) {
result = -;
} else {
std::basic_string<char>::iterator iter1 = valid_s1.begin();
std::basic_string<char>::iterator iter2 = valid_s2.begin();
for (; iter1 != valid_s1.end(); ++iter1, ++iter2 ) {
if (*iter1 == *iter2) {
continue;
} else if (*iter1 > *iter2) {
result = ;
} else {
result = -;
}
break;
}
}
return result;
}
// Print the digits without the leading zeros
void printDigits(std::string digits)
{
std::string out_str = removeLeadingZeros(digits);
if (out_str != "") {
std::cout << out_str << std::endl;
}
}
// Print N digits of length `length` starting from index start
void 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 = ; i < ; ++ i) {
digits[start] = i + '';
printNDigitsRecursively(digits, length, start+);
}
}
// print digits from 1 to maximum
void printNDigits(int n, int method=)
{
if (n <= ) {
std::cout << "ERROR: Illegal parameters n <= 0!" << std::endl;
return;
}
if (method == ) {
// Recursive method
std::cout << "\nUse the recursive method to print the numbers from 1 to maximum n digits: " << std::endl;
int start = ;
char* digits = new char[n+];
digits[n] = '\0'; // easy to forget to add the '\0' to the C string
for (int i = ; i < ; ++i) {
digits[] = i + ''; // 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 = ; i < n; ++i)
maxNdigits += "";
std::string cur_num = "";
do {
std::cout << cur_num << std::endl;
cur_num = incrementByOne(cur_num);
} while (compare(maxNdigits, cur_num) >= );
std::cout << std::endl;
}
}
void unitest()
{
int n = ;
printNDigits(n, ); // recursive method
printNDigits(n, ); // simulation method
}
int main()
{
unitest();
return ;
}
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 digits
def 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 = ["" 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 print
def print_n_digits_recursive(string, length, start):
if length == start:
output = remove_leading_zeros("".join(string))
if output != '':
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 print
def print_n_digits_simulation(n):
max_num = '' * n
curr_num = ''
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_num
def remove_leading_zeros(num):
i = 0
for ch in num[:-1]:
if '' == ch:
i += 1
else:
break
return num[i:]
# Compare two digits string
def 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(''):
carry = True
out_seq.append('')
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(''):
next_ = '' + 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 method
if __name__ == '__main__':
unitest()
参考代码
/*
* Author: klchang
* Date: 2018.2.26
* Description: Print digits from 1 to the maximum n digits.
*/
#include <iostream>
#include <string> // Check if the string contains illegal characters
bool checkDigitString(std::string numeric_str)
{
bool isLegal = true; std::basic_string<char>::iterator iter = numeric_str.begin();
for (; iter != numeric_str.end(); ++ iter) {
char ch = *iter;
if (ch < '' || ch > '') {
isLegal = false;
break;
}
}
return isLegal;
} // Remove the leading zeros in a numeric string
std::string removeLeadingZeros(std::string numeric_str)
{
int i = ;
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] == ''))
break;
}
if (i >= len) {
numeric_str = "";
} else {
numeric_str = numeric_str.substr(i);
} return numeric_str;
} // Simulate the numeric operation that numeric string adds one
std::string incrementByOne(std::string& numeric_str)
{
size_t len = numeric_str.size();
std::string output_str(numeric_str); if (len <= )
return output_str; int carry = ;
bool lowest_bit = true;
std::basic_string<char>::reverse_iterator riter = output_str.rbegin();
for (; riter != output_str.rend(); ++ riter) {
int value = *riter - '';
if (lowest_bit) {
lowest_bit = false;
value ++;
}
value += carry;
carry = ; // clear carry
if (value > ) {
carry = ;
value -= ;
}
*riter = '' + value; // update correspondent characters
if (carry <= ) break;
}
// pass the length of number string
if (carry > ) {
output_str = std::string("") + output_str;
} return output_str;
} // Compare the two numeric strings
// Return value: int,
// 1 when s1 > s2; 0 when s1 == s2; -1 when s1 < s2
int compare(std::string s1, std::string s2)
{
int result = ;
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 = ;
} else if (len_1 < len_2) {
result = -;
} else {
std::basic_string<char>::iterator iter1 = valid_s1.begin();
std::basic_string<char>::iterator iter2 = valid_s2.begin();
for (; iter1 != valid_s1.end(); ++iter1, ++iter2 ) {
if (*iter1 == *iter2) {
continue;
} else if (*iter1 > *iter2) {
result = ;
} else {
result = -;
}
break;
}
} return result;
} // Print the digits without the leading zeros
void printDigits(std::string digits)
{
std::string out_str = removeLeadingZeros(digits);
if (out_str != "") {
std::cout << out_str << std::endl;
}
} // Print N digits of length `length` starting from index start
void 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 = ; i < ; ++ i) {
digits[start] = i + '';
printNDigitsRecursively(digits, length, start+);
}
} // print digits from 1 to maximum
void printNDigits(int n, int method=)
{
if (n <= ) {
std::cout << "ERROR: Illegal parameters n <= 0!" << std::endl;
return;
} if (method == ) {
// Recursive method
std::cout << "\nUse the recursive method to print the numbers from 1 to maximum n digits: " << std::endl;
int start = ;
char* digits = new char[n+];
digits[n] = '\0'; // easy to forget to add the '\0' to the C string for (int i = ; i < ; ++i) {
digits[] = i + ''; // 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 = ; i < n; ++i)
maxNdigits += ""; std::string cur_num = "";
do {
std::cout << cur_num << std::endl;
cur_num = incrementByOne(cur_num);
} while (compare(maxNdigits, cur_num) >= ); std::cout << std::endl;
}
} void unitest()
{
int n = ;
printNDigits(n, ); // recursive method
printNDigits(n, ); // simulation method
} int main()
{
unitest(); return ;
}
#!/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 digits
def 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 = ["" 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 print
def print_n_digits_recursive(string, length, start):
if length == start:
output = remove_leading_zeros("".join(string))
if output != '':
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 print
def print_n_digits_simulation(n):
max_num = '' * n
curr_num = ''
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_num def remove_leading_zeros(num):
i = 0
for ch in num[:-1]:
if '' == ch:
i += 1
else:
break
return num[i:] # Compare two digits string
def 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(''):
carry = True
out_seq.append('')
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(''):
next_ = '' + 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 method if __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 <stdio.h>
#include <tchar.h> // 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"
#include <memory> void PrintNumber(char* number);
bool Increment(char* number);
void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index); // ====================方法一====================
void Print1ToMaxOfNDigits_1(int n)
{
if(n <= )
return; char *number = new char[n + ];
memset(number, '', n);
number[n] = '\0'; while(!Increment(number))
{
PrintNumber(number);
} delete []number;
} // 字符串number表示一个数字，在 number上增加1
// 如果做加法溢出，则返回true；否则为false
bool Increment(char* number)
{
bool isOverflow = false;
int nTakeOver = ;
int nLength = strlen(number); for(int i = nLength - ; i >= ; i --)
{
int nSum = number[i] - '' + nTakeOver;
if(i == nLength - )
nSum ++; if(nSum >= )
{
if(i == )
isOverflow = true;
else
{
nSum -= ;
nTakeOver = ;
number[i] = '' + nSum;
}
}
else
{
number[i] = '' + nSum;
break;
}
} return isOverflow;
} // ====================方法二====================
void Print1ToMaxOfNDigits_2(int n)
{
if(n <= )
return; char* number = new char[n + ];
number[n] = '\0'; for(int i = ; i < ; ++i)
{
number[] = i + '';
Print1ToMaxOfNDigitsRecursively(number, n, );
} delete[] number;
} void Print1ToMaxOfNDigitsRecursively(char* number, int length, int index)
{
if(index == length - )
{
PrintNumber(number);
return;
} for(int i = ; i < ; ++i)
{
number[index + ] = i + '';
Print1ToMaxOfNDigitsRecursively(number, length, index + );
}
} // ====================公共函数====================
// 字符串number表示一个数字，数字有若干个0开头
// 打印出这个数字，并忽略开头的0
void PrintNumber(char* number)
{
bool isBeginning0 = true;
int nLength = strlen(number); for(int i = ; i < nLength; ++ i)
{
if(isBeginning0 && number[i] != '')
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();
Test();
Test();
Test();
Test(-); return ;
}
5. 参考代码下载
项目 12_Print1ToMaxOfNDigits 下载： 百度网盘
何海涛《 剑指Offer：名企面试官精讲典型编程题 》 所有参考代码下载：百度网盘
参考资料
[1] 何海涛. 剑指 Offer：名企面试官精讲典型编程题 [M]. 北京：电子工业出版社，2012. 94-99.
