Создать серию / вернуть n-й член в серии
Мне нужно сгенерировать такую последовательность, чтобы ее члены содержали только цифры 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 или представляет собой комбинации этих цифр в виде числа, как объясняется в последовательности, как и в нашей обычной системе счисления.
да, для того же самого я вывел так много терминов, но после этого запутался. Можете ли вы упростить это для меня, так как я новичок в программировании.
Поскольку N может быть максимум до 10 ^ 18 членов, я думаю, что если мы вычислим его при вводе данных, это может быть не так эффективно с точки зрения конкурентного программирования.
Ответы 2
Это просто система нумерации с основанием 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
Напишите два метода:
- digit (n): вычисляет крайнюю правую цифру для данного
n. Некоторые тестовые примеры: цифра (4) = 1, цифра (5) = 2, цифра (15) = 3. - leftover (n): вычисляет число, которое представляет n, но с обрезанной самой правой цифрой. Некоторые тестовые случаи: оставшиеся (4) = 1, оставшиеся (15) = 4, оставшиеся (23) = 7.
Теперь объедините два метода в решение вашей проблемы, которое многократно отрезает самую правую цифру, пока ничего не останется. Возможно, вам будет проще сделать это рекурсивно.
Последовательность, которую вы уже упомянули, известна как Числа, состоящие только из 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, вам необходимо использовать класс Java BigInteger.
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
Сколько элементов длины k в последовательности? Исходя из этого, можете ли вы написать эффективную программу, которая определяет длину n-го элемента в последовательности? Если вы зайдете так далеко, вы окажетесь на пути к полному решению.