Esta pregunta se basa en el paradigma de programación dinámica y se puede resolver con conocimientos básicos de teoría de números.
La explicación irá mejor con un ejemplo:
Suponga que desea calcular la suma de dígitos de todos los números del 1 al 282.
Concepto:
Suma de números del 1 al 9 = 45.
Ahora 10 puede escribirse como 10 + 0, 11 como 10 + 1, 12 como 10 + 2 y también 20 puede escribirse como 20 + 0, 21 como 20 + 1 y así sucesivamente …
Entonces suma de dígitos de 1–99 = suma (9) + ((10 + 1) + (10 + 2) + (10 + 3)…. (10 + 9)) + ((20 + 0) + (20 +1) + (20 + 2) ……)) +…. (90 + 9))
- ¿Cuál es la diferencia entre el algoritmo de firma y el algoritmo hash de firma en un certificado SSL?
- ¿Es más difícil probar la corrección de algoritmos codiciosos que probar la corrección de cualquier otra clase de algoritmos?
- Cómo paralelizar un método recursivo en Java
- Después de que termina el programa de programación (estructuras de datos y algoritmo), ¿qué se les enseña a los estudiantes en CSE después de eso?
- ¿Por qué encontrar el trabajo múltiple menos común?
resolviendo: suma (99) = suma (9) + 9 * (1 + 2 + 3… + 9) + 10 * (1 + 2 + 3… 9)
sum (99) = sum (9) * 10 + 10 * 45;
generalizando:
sum (10 ^ d-1) = sum ((10 ^ d-1) -1) * 10 + 45 * (10 ^ d-1);
Como se puede ver, esta es una relación de recurrencia.
Para continuar:
Por ejemplo: 282
sum (282) = sum (99) * 2 + (1 * 100) + 2 * (82 + 1) + sum (82);
Esta es la solución final de recurrencia:
generalizando:
msd = número más significativo
d = no. de dígitos-1
sum (n) = [sum ((10 ^ d) -1) * d] + [(1 +…. + d-1) * 10 ^ d] + [msd * ((n% (10 ^ d)) +1)] + [suma (n% 10 ^ d)];
El caso base es cuando n <10 y podemos calcular la suma directamente.
Puede parecer complejo, pero créeme si entiendes los conceptos correctamente y conoces DP básico, entonces es un juego de niños.
Aquí hay un enlace para el tutorial:
Calcular la suma de dígitos en todos los números del 1 al n – GeeksforGeeks
Editaré si encuentro algunos problemas relacionados con él.
