Transformar N al valor mínimo posible

Dados dos números y N y D . Aplique cualquiera de las dos operaciones siguientes a N :

añadir D a N
cambie N a digitsum(N) , donde digitsum(N) es la suma de los dígitos de N

La tarea es transformar N al mínimo valor posible. Imprime el valor mínimo posible de N y el número de veces que se aplicaron las operaciones dadas (cualquiera de ellas). El número de operaciones debe ser mínimo.
Ejemplos:

Entrada: N = 2, D = 1
Salida: 1 9
Realice la operación Tipo 1 8 veces y la operación Tipo 2 1 vez
Entrada: N = 9, D = 3
Salida: 3, 2
Aplique una operación Tipo 1 primero y luego la operación Tipo 2

Prerrequisitos:
1. Raíz digital (suma digital repetida) del entero grande dado
2. Números en un rango con raíz digital dada
Enfoque:
Sea Dr(x) una función definida para el entero x como:

Dr(x) = x, si 0 <= x <= 9
de lo contrario, Dr(x) = Dr(Suma-de-dígitos(x))

La función Dr(x) es la raíz digital de un número x.

Dr(a+b) = Dr(Dr(a) + Dr(b))
Dr(ab) = Dr(Dr(a) * Dr(b))

Observación importante: El valor mínimo es siempre el mínimo sobre: Dr(N + kD) para algún número entero no negativo k.

Dr(N + kD) = Dr(Dr(N) + Dr(kD))          (1)

Ahora, Dr(kd) = Dr(Dr(k) * Dr(D))
Los posibles valores de Dr(k) son 0, 1, 2…9, dados por los números k=0, 1, 2…9

Dr(x) = Dr(Sum-of-digits(x))             (2)

El valor mínimo de N es igual al valor mínimo de Suma de dígitos (N). Si reducimos esta respuesta una vez y le sumamos D, el valor mínimo que se puede obtener no cambiaría. Entonces, si se requiere realizar una operación de reducción y luego una operación de suma, entonces podemos hacer la operación de suma y luego la operación de reducción sin afectar las posibles raíces que podemos alcanzar. Esto es evidente a partir de la combinación de las fórmulas (1) y (2)
Entonces, podemos hacer todas las operaciones de suma primero, todas las operaciones de reducción después y llegar a cualquier número que pueda ser alcanzado por cualquier conjunto de operaciones. Utilizando las afirmaciones anteriores, podemos probar que el valor mínimo posible es el mínimo de Dr(N + kD) donde 0 <= k <= 9.
Para encontrar el número mínimo de pasos, tenga en cuenta que el orden relativo de las operaciones de suma y suma de dígitos afecta la respuesta. Además, tenga en cuenta que la función Suma de dígitos disminuye extremadamente rápido.
Cualquier número <= 10 ¹⁰ se convierte en un número <= 90, cualquier número <= 90 se convierte en algo <= 18 y así sucesivamente. En resumen, cualquier número se puede reducir a su raíz digital en <= 5 pasos.
A través de esto, podemos probar que el valor de los pasos mínimos nunca puede ser superior a 15. Este es un límite superior flexible, no el exacto.
Use el algoritmo de recursión de fuerza bruta, que en cada paso se bifurca en 2 direcciones diferentes, una x = suma de dígitos (x), la otra es x = x + D, pero solo hasta una profundidad de recursión de 15. De esta manera, nos detenemos después de explorar 2 ¹⁵ formas diferentes.

A continuación se muestra la implementación del enfoque anterior:

C++

// CPP program to transform N to the minimum value
#include <bits/stdc++.h>
using namespace std;
 
// Initialising the answer
int min_val = INT_MAX;
int min_steps = 0;
 
// Function to find the digitsum
int sumOfDigits(int n)
{
    string s = to_string(n);
 
    int sum = 0;
 
    // Iterate over all digits and add them
    for (int i = 0; i < s.length(); i++) {
        sum += (s[i] - '0');
    }
     
    // Return the digit su,
    return sum;
}
 
// Function to transform N to the minimum value
void Transform(int n, int d, int steps)
{
    // If the final value is lesser than least value
    if (n < min_val) {
        min_val = n;
        min_steps = steps;
    }
 
    // If final value is equal to least value then check
    // for lesser number of steps to reach this value
    else if (n == min_val) {
        min_steps = min(min_steps, steps);
    }
 
    // The value will be obtained in less than 15 steps as
    // proved so applying normal recursive operations
    if (steps < 15) {
        Transform(sumOfDigits(n), d, steps + 1);
        Transform(n + d, d, steps + 1);
    }
}
 
// Driver code
int main()
{
    int N = 9, D = 3;
     
    // Function call
    Transform(N, D, 0);
     
    // Print the answers
    cout << min_val << " " << min_steps;
     
    return 0;
}

Java

// JAVA program to transform N to the minimum value
import java.util.*;
 
class GFG{
  
// Initialising the answer
static int min_val = Integer.MAX_VALUE;
static int min_steps = 0;
  
// Function to find the digitsum
static int sumOfDigits(int n)
{
    String s = String.valueOf(n);
  
    int sum = 0;
  
    // Iterate over all digits and add them
    for (int i = 0; i < s.length(); i++) {
        sum += (s.charAt(i) - '0');
    }
      
    // Return the digit su,
    return sum;
}
  
// Function to transform N to the minimum value
static void Transform(int n, int d, int steps)
{
    // If the final value is lesser than least value
    if (n < min_val) {
        min_val = n;
        min_steps = steps;
    }
  
    // If final value is equal to least value then check
    // for lesser number of steps to reach this value
    else if (n == min_val) {
        min_steps = Math.min(min_steps, steps);
    }
  
    // The value will be obtained in less than 15 steps as
    // proved so applying normal recursive operations
    if (steps < 15) {
        Transform(sumOfDigits(n), d, steps + 1);
        Transform(n + d, d, steps + 1);
    }
}
  
// Driver code
public static void main(String[] args)
{
    int N = 9, D = 3;
      
    // Function call
    Transform(N, D, 0);
      
    // Print the answers
    System.out.print(min_val+ " " +  min_steps);
      
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program to transform N to the minimum value
import sys;
 
# Initialising the answer
min_val = sys.maxsize;
min_steps = 0;
 
# Function to find the digitsum
def sumOfDigits(n) :
 
    s = str(n);
 
    sum = 0;
 
    # Iterate over all digits and add them
    for i in range(len(s)) :
        sum += (ord(s[i]) - ord('0'));
     
    # Return the digit su,
    return sum;
 
# Function to transform N to the minimum value
def Transform(n, d, steps) :
    global min_val;global min_steps;
     
    # If the final value is lesser than least value
    if (n < min_val) :
        min_val = n;
        min_steps = steps;
 
    # If final value is equal to least value then check
    # for lesser number of steps to reach this value
    elif (n == min_val) :
        min_steps = min(min_steps, steps);
     
    # The value will be obtained in less than 15 steps as
    # proved so applying normal recursive operations
    if (steps < 15) :
        Transform(sumOfDigits(n), d, steps + 1);
        Transform(n + d, d, steps + 1);
 
# Driver code
if __name__ == "__main__" :
 
    N = 9; D = 3;
     
    # Function call
    Transform(N, D, 0);
     
    # Print the answers
    print(min_val, min_steps);
     
# This code is contributed by Yash_R

C#

// C# program to transform N to the minimum value
using System;
 
class GFG{
  
// Initialising the answer
static int min_val = int.MaxValue;
static int min_steps = 0;
  
// Function to find the digitsum
static int sumOfDigits(int n)
{
    string s = n.ToString();
  
    int sum = 0;
  
    // Iterate over all digits and add them
    for (int i = 0; i < s.Length; i++) {
        sum += (s[i] - '0');
    }
      
    // Return the digit su,
    return sum;
}
  
// Function to transform N to the minimum value
static void Transform(int n, int d, int steps)
{
    // If the final value is lesser than least value
    if (n < min_val) {
        min_val = n;
        min_steps = steps;
    }
  
    // If final value is equal to least value then check
    // for lesser number of steps to reach this value
    else if (n == min_val) {
        min_steps = Math.Min(min_steps, steps);
    }
  
    // The value will be obtained in less than 15 steps as
    // proved so applying normal recursive operations
    if (steps < 15) {
        Transform(sumOfDigits(n), d, steps + 1);
        Transform(n + d, d, steps + 1);
    }
}
  
// Driver code
public static void Main(string[] args)
{
    int N = 9, D = 3;
      
    // Function call
    Transform(N, D, 0);
      
    // Print the answers
    Console.Write(min_val+ " " +  min_steps);
}
}
 
// This code is contributed by Yash_R

Javascript

<script>
// Javascript program to transform N to the minimum value
 
// Let initialising the answer
let min_val = Number.MAX_VALUE;
let min_steps = 0;
  
// Function to find the digitsum
function sumOfDigits(n)
{
    let s = n.toString();
  
    let sum = 0;
  
    // Iterate over all digits and add them
    for (let i = 0; i < s.length; i++) {
        sum += (s[i] - '0');
    }
      
    // Return the digit su,
    return sum;
}
  
// Function to transform N to the minimum value
function Transform(n, d, steps)
{
    // If the final value is lesser than least value
    if (n < min_val) {
        min_val = n;
        min_steps = steps;
    }
  
    // If final value is equal to least value then check
    // for lesser number of steps to reach this value
    else if (n == min_val) {
        min_steps = Math.min(min_steps, steps);
    }
  
    // The value will be obtained in less than 15 steps as
    // proved so applying normal recursive operations
    if (steps < 15) {
        Transform(sumOfDigits(n), d, steps + 1);
        Transform(n + d, d, steps + 1);
    }
}
 
// Driver Code
     
    let N = 9, D = 3;
      
    // Function call
    Transform(N, D, 0);
      
    // Print the answers
    document.write(min_val+ " " +  min_steps);
     
</script>

Producción:

3 2

Complejidad del tiempo: $O(T \cdot 2^{15} \cdot log_{10} N )$

Publicación traducida automáticamente

Artículo escrito por king_tsar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta