打印1到最大的n位数

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

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


解题思路:


1、求出3位数字的最大数,再逐个打印


问题是:不能打印大数,原因是定义的int或者long型有限。


void PrintToMaxOfDigits(int n)

{

int number = 1;

int i = 0;

while (i++ < n)

 number *= 10;

for (i = 1; i < number; ++i)

 cout << i << ", ";

}

2、使用字符串模拟加法(以解决大数问题)


1)3位,每一位代表一个0-9的字符。

2)最低位加1,逢10进1

3)最高位也即是第0位若产生进位位,则溢出标志置1

4)打印部分,上述每次累加1,则对于3位字符串,依次从高位打印到低位


需要注意的问题是若前面的高位部分若为0,则进行判断,高位部分无效的0不打印


参考代码:


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;否则为false

bool 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;

}

上述的length为打印的最大位数。 注意一个数累加完成则break出循环,若是产生进位则循环到没有进位产生。


3、使用递归的方法实现


思路:


1)3位数(012),每一位看成是0-9的位数,即是3个从0-9的全排列

2)从高位(0位)开始递归,然后是1位,再是2位。每一位递归10次 ,则总共是1000次

3)并在第1000次时结束递归,并依次从低位到高位依次返回,从001到002一直到999


参考代码


void Print1ToMaxOfDigits(int n)

{

if (n <= 0)

 return;

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

number[n] = '\0';

for (int i = 0; i < 10; ++i)//递归1

{

 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)//递归2 这部分嵌套两次

{

 number[index + 1] = i + '0';

 Print1ToMaxOfNDigitsRecursively(number, length, index + 1);

}

}

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("\t");

}

参考:【1】https://blog.csdn.net/sinat_36161667/article/details/80786754


【2】剑指


后续问题:

2fbdf30cb4ef2568f3ec0462ab7ad177_20190211221150882.png

或者是两个没有定义大小的数相加(同样属于大数问题)


目录
相关文章
|
5月前
|
存储
从键盘输入10个整数,输出最大值
从键盘输入10个整数,输出最大值
|
5月前
|
数据安全/隐私保护
微机原理||十进制输入、数组中负数个数、字符串比较程序
微机原理||十进制输入、数组中负数个数、字符串比较程序
打印0~1000的水仙花数
打印0~1000的水仙花数
60 0
|
6月前
|
C++
『C/C++』Eg2:简单输出整数
『C/C++』Eg2:简单输出整数
|
11月前
统计两个整数所对应的二进制数中的不同位数的个数
统计两个整数所对应的二进制数中的不同位数的个数
41 0
打印1到最大的n位数
1.题目概述 2.题解
49 0
打印3的倍数的数
打印3的倍数的数
71 0
打印水仙花数
打印水仙花数
76 0
判断数字位数
判断数字位数
67 0
|
人工智能 Python
打印完全数
打印完全数
76 0