Los resultados para cualquier base N y número de etiquetas por dígito por DVD "S" son:
N\S ] 1 | 2 | 3 | 4 | 5 | S?
===================================================================
2 ] 2 | 14 | 62 | 254 | 1022 | 4^S - 2
----+--------+----------+------------+-----------+------+----------
3 ] 12 | 363 | 9840 | 265719 | (27^S - 3)/2
----+--------+----------+------------+-----------+-----------------
4 ] 28 | 7672 | 1965558 | 503184885 |
----+--------+----------+------------+-----------+
5 ] 181 | 571865 | 1787099985 |
----+--------+----------+------------+
6 ] 426 | 19968756 |
----+--------+----------+
7 ] 3930 | (≥ 2^31) |
----+--------+----------+
8 ] 8184 |
----+--------+
9 ] 102780 |
----+--------+
10 ] 199990 |
----+--------+
No puedo ver ningún patrón.
Alternativamente, si la etiqueta se inicia desde 0 en lugar de 1,
N\S ] 1 | 2 | 3 | 4 | 5 | S?
======================================================================
2 ] 4 | 20 | 84 | 340 | 1364 | (4^S-1)*4/3
----+---------+----------+------------+-----------+------+------------
3 ] 12 | 363 | 9840 | 265719 | (27^S - 3)/2
----+---------+----------+------------+-----------+-------------------
4 ] 84 | 7764 | 1965652 | 503184980 |
----+---------+----------+------------+-----------+
5 ] 182 | 571875 | 1787100182 |
----+---------+----------+------------+
6 ] 1728 | 19970496 |
----+---------+----------+
7 ] 3931 | (≥ 2^31) |
----+---------+----------+
8 ] 49152 |
----+---------+
9 ] 102789 |
----+---------+
10 ] 1600000 |
----+---------+
de asumen que es el “1” etiqueta acabando primero vamos - que es de hecho el caso para la mayoría de otra información computada
Supongamos que estamos en la base N y que habrá S nuevas pegatinas por dígito por DVD.
En el DVD #X, habrá etiquetas totalmente "0" X × S, usadas o no.
El número de pegatinas "1" utilizadas es solo el número de "1" en los dígitos del 1 al X en la expansión de la base N.
Por lo tanto, solo tenemos que encontrar el punto de cruce de X × S y el conteo total de dígitos "1".
- N = 2: 1,2,4,5,7,9,12,13,15,17,20,22,25,28,32,33,35,37,40,42,45,48,52,54,57,…
- N = 3: 1,1,2,4,5,5,6,6,7,9,10,12,15,17,18,20, 21,21,22,22,23,25,26,26,27, ...
- N = 10: 1,1,1,1,1,1,1,1,1,2,4,5,6,7,8,9,10,11,12,12,13,13,13,13,13,…
no parece ser un cerrado de todas estas secuencias, por lo que un bucle proporcional X iteraciones es necesario. Los dígitos se pueden extraer en tiempo log X, por lo que, en principio, el algoritmo puede finalizar en tiempo O (X log X).
Esto no es mejor que el otro algoritmo, pero al menos se pueden eliminar muchos cálculos. Un código de ejemplo C:
#include <stdio.h>
static inline int ones_in_digit(int X, int N) {
int res = 0;
while (X) {
if (X % N == 1)
++ res;
X /= N;
}
return res;
}
int main() {
int N, S, X;
printf("Base N? ");
scanf("%d", &N);
printf("Stickers? ");
scanf("%d", &S);
int count_of_1 = 0;
X = 0;
do {
++ X;
count_of_1 += S - ones_in_digit(X, N);
if (X % 10000000 == 0)
printf("%d -> %d\n", X/10000000, count_of_1);
} while (count_of_1 >= 0);
printf("%d\n", X-1);
return 0;
}
¿Es esta tarea? – Oded
para que siempre obtenga +20 pegatinas con cada DVD en blanco? – knittl
Suponiendo que desea numerar secuencialmente, podrá contar hasta 10 DVD con 2 o 3 calcomanías por dígito (spd), 11 con 4 spd, 20 con 12 calcomanías por dígito, 30 con 13, y así sucesivamente. La razón principal es que te quedarás sin 1 bastante temprano. –