Minimice el costo de convertir todos los elementos de la array a números de Fibonacci

Dada una array arr[] que consta de N enteros, la tarea es minimizar el costo de convertir todos los elementos de la array en un número de Fibonacci , donde el costo de convertir un número A en B es la diferencia absoluta entre A y B.

Ejemplos:

Entrada: arr[] = {56, 34, 23, 98, 7}
Salida: 13
Explicación:
A continuación se muestra la conversión de los elementos necesarios para convertir todos los elementos de la array en números de Fibonacci:

Convierta arr[0](= 56) a 55. Costo = | 56 – 55| = 1.

Convierta arr[1](= 34) a 34. Costo = |34 – 34| = 0.

Convierta arr[2](= 23) a 21. Costo = |23 – 21| = 2

Convierta arr[3](= 98) a 89. Costo = |98 – 89| = 9.

Convierta arr[4](= 7) a 8. Costo = |7 – 8| = 1.

Por lo tanto, el costo total de cambiar todos los elementos de la array a números de Fibonacci = 1 + 0 + 2 + 9 + 1 = 13.

Entrada: {543, 32, 7, 23, 641}
Salida: 103

Enfoque: el problema dado se puede resolver reemplazando cada elemento de la array con su número de Fibonacci más cercano para obtener el costo mínimo de cambiar todos los elementos de la array al número de Fibonacci . Siga el siguiente paso para resolver el problema dado:

Inicialice una variable, digamos, costo que almacene el costo mínimo de cambiar todos los elementos de la array al número de Fibonacci.
Recorra la array dada arr[] y realice los siguientes pasos:
- Para encontrar el número de Fibonacci más cercano a arr[i] , primero, encuentre el valor de N tal que el número N de Fibonacci sea ^arr [i] usando la fórmula $N = \frac {\log(\sqrt 5*arr[i])}{\log \frac{1 + \sqrt 5}{2}}$
- Ahora, encuentre el N ^-ésimo y (N + 1) ^-ésimo Número de Fibonacci , digamos X e Y respectivamente y agregue el mínimo de los valores absolutos de (X – arr[i]) y (Y – arr[i]) al costo .
Después de completar los pasos anteriores, imprima el valor del costo como el costo mínimo resultante.

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

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the
// N-th Fibonacci Number
int nthFibo(int n)
{
     
    // Find the value of a, b, and r
    double a = (pow(5, 0.5) + 1) / 2;
    double b = (-1*(pow(5, 0.5) ) + 1) / 2;
    double r = pow(5, 0.5);
 
    // Find the N-th Fibonacci
    double ans = (pow(a, n) - pow(b, n)) / r;
 
    // Return the result
    return int(ans);
}
 
// Function to find the Fibonacci
// number which is nearest to X
int nearFibo(int X)
{
    double a = (pow(5, 0.5) + 1) / 2;
 
    // Calculate the value of n for X
    int n = int(log((pow(5, 0.5)) * X) / log(a));
 
    int nth = nthFibo(n);
    int nplus = nthFibo(n + 1);
 
    // Return the nearest
    // Fibonacci Number
    if (abs(X - nth) < abs(X - nplus))
        return nth;
    else
        return nplus;
}
 
// Function to find the minimum
// cost to convert all array
// elements to Fibonacci Numbers
int getCost(int arr[], int n)
{
 
    // Stores the total minimum cost
    int cost = 0;
 
    // Traverse the given array arr[]
    for(int i = 0; i < n; i++)
    {
         
        // Find the nearest
        // Fibonacci Number
        int fibo = nearFibo(arr[i]);
 
        // Add the cost
        cost += abs(arr[i] - fibo);
    }
     
    // Return the final cost
    return cost;
}
 
// Driver Code
int main()
{
    int arr[] = { 56, 34, 23, 98, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << (getCost(arr, n));
}
 
// This code is contributed by ukasp

Java

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG
{
   
// Function to find the
// N-th Fibonacci Number
static int nthFibo(int n)
{
     
    // Find the value of a, b, and r
    double a = (Math.pow(5, 0.5) + 1) / 2;
    double b = (-1*(Math.pow(5, 0.5) ) + 1) / 2;
    double r = Math.pow(5, 0.5);
 
    // Find the N-th Fibonacci
    double ans = (Math.pow(a, n) - Math.pow(b, n)) / r;
 
    // Return the result
    return (int)ans;
}
 
// Function to find the Fibonacci
// number which is nearest to X
static int nearFibo(int X)
{
    double a = (Math.pow(5, 0.5) + 1) / 2;
 
    // Calculate the value of n for X
    int n = (int)(Math.log((Math.pow(5, 0.5)) * X) / Math.log(a));
 
    int nth = nthFibo(n);
    int nplus = nthFibo(n + 1);
 
    // Return the nearest
    // Fibonacci Number
    if (Math.abs(X - nth) < Math.abs(X - nplus))
        return nth;
    else
        return nplus;
}
 
// Function to find the minimum
// cost to convert all array
// elements to Fibonacci Numbers
static int getCost(int arr[], int n)
{
 
    // Stores the total minimum cost
    int cost = 0;
 
    // Traverse the given array arr[]
    for(int i = 0; i < n; i++)
    {
         
        // Find the nearest
        // Fibonacci Number
        int fibo = nearFibo(arr[i]);
 
        // Add the cost
        cost += Math.abs(arr[i] - fibo);
    }
     
    // Return the final cost
    return cost;
}
 
// Driver code
public static void main (String[] args)
{
 int arr[] = { 56, 34, 23, 98, 7 };
    int n = arr.length;
 System.out.print(getCost(arr, n));
    }
}
 
// This code is contributed by offbeat

Python3

# Python program for the above approach
 
import math
 
# Function to find the
# N-th Fibonacci Number
def nthFibo(n):
   
    # Find the value of a, b, and r
    a = (5**(1 / 2) +1)/2
    b = (-5**(1 / 2) +1)/2
    r = 5**(1 / 2)
 
 
    # Find the N-th Fibonacci
    ans = (a**n - b**n)/r
 
    # Return the result
    return int(ans)
 
# Function to find the Fibonacci
# number which is nearest to X
def nearFibo(X):
   
    a = (5**(1 / 2)+1)/2
     
    # Calculate the value of n for X
    n = int(math.log((5**(1 / 2))*X) / math.log(a))
 
    nth = nthFibo(n)
    nplus = nthFibo(n + 1)
 
    # Return the nearest
    # Fibonacci Number
    if abs(X - nth) < abs(X - nplus):
        return nth
    else:
        return nplus
 
# Function to find the minimum
# cost to convert all array
# elements to Fibonacci Numbers
def getCost(arr):
   
    # Stores the total minimum cost
    cost = 0
     
    # Traverse the given array arr[]
    for i in arr:
       
        # Find the nearest
        # Fibonacci Number
        fibo = nearFibo(i)
         
        # Add the cost
        cost += abs(i-fibo)
 
    # Return the final cost
    return cost
 
# Driver Code
 
arr = [56, 34, 23, 98, 7]
 
print(getCost(arr))

C#

// C# program to count frequencies of array items
using System;
 
class GFG{
     
// Function to find the
// N-th Fibonacci Number
static int nthFibo(int n)
{
     
    // Find the value of a, b, and r
    double a = (Math.Pow(5, 0.5) + 1) / 2;
    double b = (-1*(Math.Pow(5, 0.5) ) + 1) / 2;
    double r = Math.Pow(5, 0.5);
 
    // Find the N-th Fibonacci
    double ans = (Math.Pow(a, n) -
                  Math.Pow(b, n)) / r;
 
    // Return the result
    return (int)ans;
}
 
// Function to find the Fibonacci
// number which is nearest to X
static int nearFibo(int X)
{
    double a = (Math.Pow(5, 0.5) + 1) / 2;
 
    // Calculate the value of n for X
    int n = (int)(Math.Log((Math.Pow(5, 0.5)) * X) /
                            Math.Log(a));
 
    int nth = nthFibo(n);
    int nplus = nthFibo(n + 1);
 
    // Return the nearest
    // Fibonacci Number
    if (Math.Abs(X - nth) < Math.Abs(X - nplus))
        return nth;
    else
        return nplus;
}
 
// Function to find the minimum
// cost to convert all array
// elements to Fibonacci Numbers
static int getCost(int []arr, int n)
{
 
    // Stores the total minimum cost
    int cost = 0;
 
    // Traverse the given array arr[]
    for(int i = 0; i < n; i++)
    {
         
        // Find the nearest
        // Fibonacci Number
        int fibo = nearFibo(arr[i]);
 
        // Add the cost
        cost += Math.Abs(arr[i] - fibo);
    }
     
    // Return the final cost
    return cost;
}   
 
// Driver code
public static void Main(String []args)
{
    int []arr = { 56, 34, 23, 98, 7 };
    int n = arr.Length;
     
    Console.WriteLine(getCost(arr, n));
}
}
 
// This code is contributed by jana_sayantan

Javascript

<script>
// Javascript program for the above approach
 
// Function to find the
// N-th Fibonacci Number
function nthFibo(n)
{
     
    // Find the value of a, b, and r
    let a = (Math.pow(5, 0.5) + 1) / 2;
    let b = (-1*(Math.pow(5, 0.5) ) + 1) / 2;
    let r = Math.pow(5, 0.5);
 
    // Find the N-th Fibonacci
    let ans = (Math.pow(a, n) - Math.pow(b, n)) / r;
 
    // Return the result
    return Math.floor(ans);
}
 
// Function to find the Fibonacci
// number which is nearest to X
function nearFibo(X)
{
    let a = (Math.pow(5, 0.5) + 1) / 2;
 
    // Calculate the value of n for X
    let n = Math.floor(Math.log((Math.pow(5, 0.5)) * X) / Math.log(a));
 
    let nth = nthFibo(n);
    let nplus = nthFibo(n + 1);
 
    // Return the nearest
    // Fibonacci Number
    if (Math.abs(X - nth) < Math.abs(X - nplus))
        return nth;
    else
        return nplus;
}
 
// Function to find the minimum
// cost to convert all array
// elements to Fibonacci Numbers
function getCost(arr, n)
{
 
    // Stores the total minimum cost
    let cost = 0;
 
    // Traverse the given array arr[]
    for(let i = 0; i < n; i++)
    {
         
        // Find the nearest
        // Fibonacci Number
        let fibo = nearFibo(arr[i]);
 
        // Add the cost
        cost += Math.abs(arr[i] - fibo);
    }
     
    // Return the final cost
    return cost;
}
 
// Driver Code
 
    let arr = [ 56, 34, 23, 98, 7 ];
    let n = arr.length;
    document.write(getCost(arr, n));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Producción:

Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.

Publicación traducida automáticamente

Artículo escrito por rohitsingh07052 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