打印1到最大的n位数(Java)
题目:
输入数字n,按顺序打印出从1到最大的n位十进制数。比如输入3,则打印出1、2、3一直到最大的3位数即999。
第一思路:
首先计算出n位数的最大十进制数,然后利用循环输出从1到最大的n位数。
实现代码:
public void printToMaxOfNDigits(int n){
long number = 1;
int i = 0;
while(i < n){ //利用while循环计算出比n位十进制多1的数
number *= 10;
++i;
}
for (long j = 1; j < number; j++) { //利用for循环输出从1到最大的n位数
System.out.print(j + " ");
if(j%5 == 0){
System.out.println();
}
}
}
分析:
上面的代码考虑的问题很简单,默认为最大数值为long型,没有考虑长整型也会溢出的情况。故上面的代码鲁棒性很差。
鲁棒性好的思路:
因为上面分析可知我们在遇到比长整型还大的数时,上面的代码是不能成功执行的,即基本类型已经存储不下的数字。这时我们需要考虑用字符串或者数组来表示大数。
用字符串表示数字的时候,最直观的方法就是字符串里每个字符都是‘0’到‘9’之间的某一个字符,用来表示数字中的一位。因为最大的是n位的,因此我们需要一个长度为n+1的字符串(字符串中最后一个是结束符号‘\0’。当实际数字不够n位的时候,在字符串的前半部分补0)。
首先我们把字符串中的每一个数字都初始化为‘0’,然后每一次为字符串表示的数字加1,再打印出来。故我们只需要做两件事:一是在字符串表达数字上模拟加法,二是把字符串表达的数字打印出来。
在字符串表达数字上模拟加法,我们首先设置是否溢出标识,是否进位标识,以及取得字符数组长度,遍历这个字符数组,在末尾进行+1操作,如果末尾字符在+1后变为不小于10的数字,我们将末尾减去10加上‘0’字符赋值为末位,进位标识设置为1,在循环次位时+1,然后再判断是否为不小于10,是的话重复上面的步骤。直到判断高位是不是不小于10,是的话字符数组溢出;如果末尾字符在+1后是小于10的数字,直接加上‘0’赋值给末尾,跳出当前循环,返回没有溢出。
在字符串表达的数字打印出来方法时,没有什么特别,直接利用for循环遍历输出字符数组,但是要从高位第一个不是0的开始输出。
代码:
//打印1到最大的n位数
public void printToMaxOfDigits(int n){
if(n <= 0){
System.out.println("输入的n没有意义");
return;
}
//声明字符数组,用来存放一个大数
char number[] = new char[n];
for (int i = 0; i < number.length; ++i) { //放字符0进行初始化
number[i] = '0';
}
while(!incrementNumber(number)){ //如果大数自加,直到自溢退出
printNumber(number); //打印大数
}
}
//自加
private boolean incrementNumber(char[] number) {
boolean isOverflow = false; //判断是否溢出
int nTakeOver = 0; //判断是否进位
int nLength = number.length;
for (int i = nLength - 1; i >= 0 ; --i) {
int nSum = number[i] - '0' + nTakeOver; //取到第i位的字符转换为数字 +进位符
if(i == nLength - 1){ //末尾自加1
++nSum;
}
if(nSum >= 10){
if(i == 0){
isOverflow = true;
}else{
nSum -= 10;
nTakeOver = 1;
number[i] = (char) ('0' + nSum);
}
}else{
number[i] = (char) (nSum + '0');
break;
}
}
return isOverflow;
}
//打印数字
private void printNumber(char[] number) {
boolean isBeginning0 = true;
int nLength = number.length;
for (int i = 0; i < nLength; ++i) {
if(isBeginning0 && number[i]!='0'){
isBeginning0 = false;
}
if(!isBeginning0){
System.out.print(number[i]);
}
}
System.out.println();
}
测试用例:
public static void main(String[] args) {
Main m1 = new Main();
m1.printToMaxOfDigits(-10);
m1.printToMaxOfDigits(0);
m1.printToMaxOfDigits(10);
m1.printToMaxOfDigits(100);
}
小思:
把问题转化为数字排列的解法,使用递归可以使代码简洁明了。即:如果在所有的数字前面补0的话,就会发现n位所有的十进制数其实就是n个从0到9的全排列。也就是说,我们把数字的每一位都从0到9排列一遍,就得到了所有的十进制数。在打印时,数字排在前面的0不打印。
全排列递归实现最容易。数字的每一位都可能是0到9的一个数,然后设置下一位。递归结束的条件就是我们已经设置了数字的最后一位。
代码:
//打印1到最大的n位数的主方法
public void printToMaxOfDigits(int n){
if(n <= 0){
System.out.println("输入的n没有意义");
return;
}
char number[] = new char[n];
for (int i = 0; i < number.length; i++) {
number[i] = '0';
}
for (int i = 0; i < 10; ++i) {
number[0] = (char) (i + '0');
printToMaxOfNDigitsRecursively(number, n, 0);
}
}
//利用递归实现1到最大的n位数的全排列
public void printToMaxOfNDigitsRecursively(char[] number, int n, int index) {
if(index == n - 1){
printNumber(number);
return;
}
for (int i = 0; i < 10; ++i) {
number[index + 1] = (char) (i + '0');
printToMaxOfNDigitsRecursively(number, n, index + 1);
}
}
//输出
private void printNumber(char[] number) {
boolean isBeginning0 = true;
int nLength = number.length;
for (int i = 0; i < nLength; ++i) {
if(isBeginning0 && number[i]!='0'){
isBeginning0 = false;
}
if(!isBeginning0){
System.out.print(number[i]);
}
}
System.out.println();
}
测试方法同上。
小结:
这是一个大数问题,考查我们怎么定义这个大数,以及对大数进行+1操作,以及定义完成怎么输出这个大数。另外递归使问题简单使我们谨记。
下一篇: 碰撞检测
推荐阅读
-
1.java小作业-计算1到100的整合-指定输入多少行输出就打印多少行-打印24小时60分钟每一分钟-重载基础练习-面向java编程初学者
-
for循环练习 打印4面三角形,99乘法表 ,打印1-100内整数 数字包含9跳过 每行输出5个 用空格分隔,按照从大到小的顺序输出4位数中的个位+百位=十位+千位的数字及个数
-
剑指offer 打印从1到最大的n位数
-
1.java小作业-计算1到100的整合-指定输入多少行输出就打印多少行-打印24小时60分钟每一分钟-重载基础练习-面向java编程初学者
-
Java_冒泡排序|获取数组最大值和最小值操作,编写函数得到0到n之间的随机数,并找出产生m个这样的随机数中最大的、最小的数,并统计其中>=60的有多少个
-
剑指offer 打印从1到最大的n位数
-
打印1到最大的n位数(Java)
-
剑指offer-----打印1到最大的n位数