• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

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

    二、解题思路

    ①使用一个n位的数组来存储每一位的元素。例如n位3,则000表示为[0,0,0]。

    使用递归的方式,存放每一位元素值。

    ②同上,使用一个n位的数组来存储每一位的元素。然后循环执行加1运算,并在数组中进行模拟进位,直到最高位需要进位,则表示循环结束。

    三、解题代码

    1. public class Test {
    2. /**
    3. * 输入数字n,按顺序打印出从1最大的n位十进制数。比如输入3,则打印出1、2、3 一直到最大的3位数即999。
    4. *
    5. * @param n 数字的最大位数
    6. */
    7. public static void printOneToNthDigits(int n) {
    8. // 输入的数字不能为小于1
    9. if (n < 1) {
    10. throw new RuntimeException("The input number must larger than 0");
    11. }
    12. // 创建一个数组用于打存放值
    13. int[] arr = new int[n];
    14. printOneToNthDigits(0, arr);
    15. }
    16. /**
    17. * 输入数字n,按顺序打印出从1最大的n位十进制数。
    18. *
    19. * @param n 当前处理的是第个元素,从0开始计数
    20. * @param arr 存放结果的数组
    21. */
    22. public static void printOneToNthDigits(int n, int[] arr) {
    23. // 说明数组已经装满元素
    24. if (n >= arr.length) {
    25. // 可以输出数组的值
    26. printArray(arr);
    27. } else {
    28. for (int i = 0; i <= 9; i++) {
    29. arr[n] = i;
    30. printOneToNthDigits(n + 1, arr);
    31. }
    32. }
    33. }
    34. /**
    35. * 输入数组的元素,从左到右,从第一个非0值到开始输出到最后的元素。
    36. *
    37. * @param arr 要输出的数组
    38. */
    39. public static void printArray(int[] arr) {
    40. // 找第一个非0的元素
    41. int index = 0;
    42. while (index < arr.length && arr[index] == 0) {
    43. index++;
    44. }
    45. // 从第一个非0值到开始输出到最后的元素。
    46. for (int i = index; i < arr.length; i++) {
    47. System.out.print(arr[i]);
    48. }
    49. // 条件成立说明数组中有非零元素,所以需要换行
    50. if (index < arr.length) {
    51. System.out.println();
    52. }
    53. }
    54. /**
    55. * 输入数字n,按顺序打印出从1最大的n位十进制数。比如输入3,则打印出1、2、3 一直到最大的3位数即999。
    56. * 【第二种方法,比上一种少用内存空间】
    57. *
    58. * @param n 数字的最大位数
    59. */
    60. public static void printOneToNthDigits2(int n) {
    61. // 输入值必须大于0
    62. if (n < 1) {
    63. throw new RuntimeException("The input number must larger than 0");
    64. }
    65. // 创建一个长度为n的数组
    66. int[] arr = new int[n];
    67. // 为数组元素赋初始值
    68. for (int i = 0; i < arr.length; i++) {
    69. arr[i] = 0;
    70. }
    71. // 求结果,如果最高位没有进位就一直进行处理
    72. while (addOne(arr) == 0) {
    73. printArray(arr);
    74. }
    75. }
    76. /**
    77. * 对arr表示的数组的最低位加1 arr中的每个数都不能超过9不能小于0,每个位置模拟一个数位
    78. *
    79. * @param arr 待加数组
    80. * @return 判断最高位是否有进位,如果有进位就返回1,否则返回0
    81. */
    82. public static int addOne(int[] arr) {
    83. // 保存进位值,因为每次最低位加1
    84. int carry = 1;
    85. // 最低位的位置的后一位
    86. int index = arr.length;
    87. do {
    88. // 指向上一个处理位置
    89. index--;
    90. // 处理位置的值加上进位的值
    91. arr[index] += carry;
    92. // 求处理位置的进位
    93. carry = arr[index] / 10;
    94. // 求处理位置的值
    95. arr[index] %= 10;
    96. } while (carry != 0 && index > 0);
    97. // 如果index=0说明已经处理了最高位,carry>0说明最高位有进位,返回1
    98. if (carry > 0 && index == 0) {
    99. return 1;
    100. }
    101. // 无进位返回0
    102. return 0;
    103. }
    104. }