【C/C++练习题】打印1到最大的n位数

《剑指Offer》面试题17：打印1到最大的n位数

1 题目

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

2 问题分析

由于n的值不确定，也就无法确定用什么数据类型来表示最大的数字。如果n很大的话，可能没有足够大的数据类型来支持。这里采用字符串来模拟数值计算，来解决大数问题。

3 代码分析

在Increment()函数中，将字符串模拟数值加法运算

1. 将字符转换成对应的数值，参与'位运算'，加法运算要考虑进位
2. 计算方向是从底位到高位，依次判断
   1. 如果产生进位，则继续计算高位部分
   2. 如果没有进位，较高位部分保持不变，直接返回
   3. 如果最高位产生进位，则达到最大值，返回结果
3. 在将计算后的数值，写回原来的字符串中(对应字符位置)

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     

      #include <cstdio>
     
    
   

    

     

    
    

     

      #include <cstring>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //问题：打印从1到最大的n位数
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      bool Increment(char* number);
     
    
   

    

     

    
    

     

      void Print_number(char* number);
     
    
   

    

     

    
    

     

      bool Show_nubmer(int n);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void test01()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	Show_nubmer(3);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(int argc, char const *argv[])
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	test01();
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //输入：n最大数值的位数
     
    
   

    

     

    
    

     

      //返回：false 失败， true 成功
     
    
   

    

     

    
    

     

      bool Show_nubmer(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (n <= 0) return false;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//1.构造一个长度为n的存储空间，初始化字符串
     
    
   

    

     

    
    

     
	char* number = new char [n+1];
     
    
   

    

     

    
    

     
	memset(number,'0',n);
     
    
   

    

     

    
    

     

      	number[n] = '\0';
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//3.模拟数字加法，并打印每次计算的结果
     
    
   

    

     

    
    

     
	while (!Increment(number))
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		Print_number(number);
     
    
   

    

     

    
    

     
		// cout << number << endl;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//2.释放堆内存
     
    
   

    

     

    
    

     
	delete [] number;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：字符串上模拟数字加法
     
    
   

    

     

    
    

     

      //输入：number 指向堆内存的地址
     
    
   

    

     

    
    

     

      //返回：false 未溢出， true 溢出了
     
    
   

    

     

    
    

     

      bool Increment(char* number)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	bool all_overflag = false;	//溢出标志
     
    
   

    

     

    
    

     
	int n_overflag = 0;			//进位标志
     
    
   

    

     

    
    

     
	int length = strlen(number);	//字符串长度
     
    
   

    

     

    
    

     
	int value = 0;			//数值
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	//从最底位开始进行计算
     
    
   

    

     

    
    

     
	for (int i = length-1;i >= 0;i--)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		//1.字符 -> 数值
     
    
   

    

     

    
    

     

      		value = number[i] - '0' + n_overflag;	//转换成对应的数值(考虑进位)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		//2.加法运算
     
    
   

    

     

    
    

     
		if (i == length-1)
     
    
   

    

     

    
    

     

      		{//
     
    
   

    

     

    
    

     

      			++value;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		//3.判断进位
     
    
   

    

     

    
    

     
		if (value >= 10)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if (i == 0)
     
    
   

    

     

    
    

     

      			{//溢出，计算完成，返回
     
    
   

    

     

    
    

     

      				all_overflag = true;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			//其他位进位,继续向高位判断
     
    
   

    

     

    
    

     

      			n_overflag = 1;
     
    
   

    

     

    
    

     

      			value -= 10;
     
    
   

    

     

    
    

     

      			number[i] = value + '0';	//4.数值 -> 字符
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{//没有进位，计算完成
     
    
   

    

     

    
    

     

      			n_overflag = 0;
     
    
   

    

     

    
    

     

      			number[i] = value + '0';	//4.数值 -> 字符
     
    
   

    

     

    
    

     

      			all_overflag = false;
     
    
   

    

     

    
    

     
			break;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return all_overflag;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //功能：从第一个非零字符开始打印字符串数字
     
    
   

    

     

    
    

     

      //输入：number 指向堆内存的地址
     
    
   

    

     

    
    

     

      //输出：打印结果
     
    
   

    

     

    
    

     

      void Print_number(char* number)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	bool isbegining = false;	//起始打印标志
     
    
   

    

     

    
    

     
	int length = strlen(number);	//字符串长度
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
	for (int i = 0; i < length;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (!isbegining && number[i] != 0)
     
    
   

    

     

    
    

     

      		{//遇到非零字符
     
    
   

    

     

    
    

     

      			isbegining = true;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
		printf("%c", number[i]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("\t");
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/98501851