создать серию / вернуть n-й член в серии - PullRequest
Новая
       12

создать серию / вернуть n-й член в серии

0 голосов
/ 05 мая 2018

Мне нужно сгенерировать последовательность так, чтобы ее члены содержали только 1, 2, 3 цифр. Например, 1 2 3 11 12 13 21 22 23 31 32 33 111 .... и т. Д. До 10^18th срока. Я не могу вывести какой-либо образец для этого. Кажется невозможным написать код до 10^18 номеров терминов в серии.

1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333, 1111, 1112, 1113, 1121, 1122, 1123, 1131, 1132, 1133, 1211, 1212, 1213, 1221 ...

Я ожидаю найти данный n-й член в ряду. Это система счисления, которая содержит только 1, 2, 3 или представляет собой комбинации этих цифр как числа, как описано в последовательности, как наша обычная система счисления.

Ответы [ 2 ]

0 голосов
/ 05 мая 2018

Упомянутая вами последовательность уже известна как Числа, содержащие только 1, 2 и 3 . Она сформулирована Иеронимом Фишером . 

a(n) = sum_{j=0..m-1} (1 + b(j) mod 3)*10^j,

where m = floor(log_3(2*n+1)), b(j) = floor((2*n+1-3^m)/(2*3^j)).

Вы можете ознакомиться с объяснением формулы по вышеуказанной ссылке выше. Я написал базовый уровень, используя long. Чтобы достичь 10^18th термина, вам нужно использовать BigInteger класс Java. 

class SequenceGeneratorWith123 {

    // Written by Soner

    private static double logOfBase(long base, long num) {
        return Math.log(num) / Math.log(base);
    }

    private static int mfunc(long n) {
        return (int) Math.floor(logOfBase(3, 2 * n + 1));
    }

    private static int b(int j, double m, long n) {
        return (int) Math.floor((2 * n + 1 - Math.pow(3, m)) / (2 * Math.pow(3, j)));
    }

    public static void main(String[] args) {

        for (int i = 0; i < 9; i++) {
            long n = (long) Math.pow(10, i);
            int m = mfunc(n);
            long sum = 0;

            for (int j = 0; j < m ; j++) {
                sum += ((1 + b(j, m, n) % 3) * Math.pow(10, j));
            }
            System.out.printf("a(10^%d) = %d\n", i, sum);
        }

        System.out.println("After the point, overflow will occur " +
                        "because of long type.");    
    }
}

Выход: 

a(10^0) = 1
a(10^1) = 31
a(10^2) = 3131
a(10^3) = 323231
a(10^4) = 111123331
a(10^5) = 11231311131
a(10^6) = 1212133131231
a(10^7) = 123133223331331
a(10^8) = 13221311111312132
After the point, overflow will occur because of long type.

Вам просто нужно поиграть с кодом, то есть мы можем получить ваше желание, просто немного изменив main(). 

long n = 1;
// How many terms you need you can alter it by pow() method.
// In this example 10^2 = 100 terms will be obtained.
int term = (int)Math.pow(10, 2);
for (int i = 0; i < term; i++) {

    int m = mfunc(n);
    long sum = 0;

    for (int j = 0; j < m ; j++) {
        sum += ((1 + b(j, m, n) % 3) * Math.pow(10, j));
    }
    System.out.printf("%d. term = %d\n", i + 1, sum);
    n++;
}

Вывод: 

1. term = 1
2. term = 2
3. term = 3
4. term = 11
5. term = 12
6. term = 13
7. term = 21
8. term = 22
9. term = 23
10. term = 31
11. term = 32
12. term = 33
13. term = 111
14. term = 112
15. term = 113
16. term = 121
17. term = 122
18. term = 123
19. term = 131
20. term = 132
21. term = 133
22. term = 211
23. term = 212
24. term = 213
25. term = 221
26. term = 222
27. term = 223
28. term = 231
29. term = 232
30. term = 233
31. term = 311
32. term = 312
33. term = 313
34. term = 321
35. term = 322
36. term = 323
37. term = 331
38. term = 332
39. term = 333
40. term = 1111
41. term = 1112
42. term = 1113
43. term = 1121
44. term = 1122
45. term = 1123
46. term = 1131
47. term = 1132
48. term = 1133
49. term = 1211
50. term = 1212
51. term = 1213
52. term = 1221
53. term = 1222
54. term = 1223
55. term = 1231
56. term = 1232
57. term = 1233
58. term = 1311
59. term = 1312
60. term = 1313
61. term = 1321
62. term = 1322
63. term = 1323
64. term = 1331
65. term = 1332
66. term = 1333
67. term = 2111
68. term = 2112
69. term = 2113
70. term = 2121
71. term = 2122
72. term = 2123
73. term = 2131
74. term = 2132
75. term = 2133
76. term = 2211
77. term = 2212
78. term = 2213
79. term = 2221
80. term = 2222
81. term = 2223
82. term = 2231
83. term = 2232
84. term = 2233
85. term = 2311
86. term = 2312
87. term = 2313
88. term = 2321
89. term = 2322
90. term = 2323
91. term = 2331
92. term = 2332
93. term = 2333
94. term = 3111
95. term = 3112
96. term = 3113
97. term = 3121
98. term = 3122
99. term = 3123
100. term = 3131
0 голосов
/ 05 мая 2018

Это просто система счисления с базой 3, только цифры идут от 1 до 3 вместо 0 до 2. Математика работает так же:

1 = 1 * 3 ^ 0
2 = 2 * 3 ^ 0
3 = 3 * 3 ^ 0
4 = 1 * 3 ^ 1 + 1 * 3 ^ 0
5 = 1 * 3 ^ 1 + 2 * 3 ^ 0
6 = 1 * 3 ^ 1 + 3 * 3 ^ 0
7 = 2 * 3 ^ 1 + 1 * 3 ^ 0
...
19 = 1 * 3 ^ 2 + 3 * 3 ^ 1 + 1 * 3 ^ 0

Напишите два метода:

  1. цифра (n): вычисляет крайнюю правую цифру для данного n. Некоторые тестовые случаи: цифра (4) = 1, цифра (5) = 2, цифра (15) = 3.
  2. Остаток (n): вычисляет число, которое представляет n, но с обрезанной крайней правой цифрой. Некоторые тестовые случаи: остаток (4) = 1, остаток (15) = 4, остаток (23) = 7.

Теперь объедините два метода в решение вашей проблемы, которое многократно отсекает самую правую цифру, пока ничего не останется. Возможно, вам будет проще сделать это рекурсивно.

...