Función Spt o función de partes más pequeñas de un número dado

Dado un número entero N, la tarea es encontrar la Función Spt del número N.

La función spt (función de partes más pequeñas) es una función en teoría de números que cuenta la suma del número de partes más pequeñas en cada partición de un entero positivo. Está relacionado con la función de partición. 
Por ejemplo, las particiones de 4 son [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]. 1 aparece 4 veces en la primera, 1 dos veces en la segunda, 2 dos veces en la tercera, etc.; así spt(4) = 4 + 2 + 2 + 1 + 1 = 10. 

Ejemplos: 

Entrada: N = 4
Salida: 10
Explicación: Las
particiones de 4 son [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]. 
1 aparece 4 veces en la primera, 1 dos veces en la segunda, 2 dos veces en la tercera, etc.
Así, spt(4) = 4 + 2 + 2 + 1 + 1 = 10 

Entrada: 5
Salida: 14

 

Enfoque : la idea es considerar cada número entero de 1 a N y agregarlo en un vector de respuesta y nuevamente repetir para los elementos restantes con suma reducida. Para evitar volver a imprimir las mismas representaciones, cada representación se construirá en orden ascendente. Si se alcanza la representación de N , encontraremos la frecuencia del elemento mínimo presente en el vector de respuesta y lo agregaremos a la variable de valor Spt e imprimiremos el valor de la variable Spt al final.

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

C++

// C++ implementation to find the
// Spt Function to given number
 
#include <bits/stdc++.h>
using namespace std;
 
// variable to store spt
// function of a number
int spt = 0;
 
// Function to add value
// of frequency of minimum element
// among all representations of n
void printVector(vector<int>& arr)
{
    int min_i = INT_MAX;
    for (int i = 0; i < arr.size(); i++)
        min_i = min(min_i, arr[i]);
 
    // find the value of frequency
    // of minimum element
    int freq = count(arr.begin(),
                     arr.end(),
                     min_i);
 
    // calculate spt
    spt += freq;
}
 
// Recursive function to find
// different ways in which
// n can be written as a sum of
// at one or more positive integers
void findWays(vector<int>& arr,
              int i, int n)
{
    // if sum becomes n,
    // consider this representation
    if (n == 0)
        printVector(arr);
 
    // start from previous element
    // in the representation till n
    for (int j = i; j <= n; j++) {
 
        // include current element
        // from representation
        arr.push_back(j);
 
        // call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // backtrack - remove current
        // element from representation
        arr.pop_back();
    }
}
 
// Function to find
// the spt function
void spt_function(int n)
{
 
    vector<int> arr;
 
    // Using recurrence find
    // different ways in which
    // n can be written as a sum of
    // at 1 or more positive integers
    findWays(arr, 1, n);
 
    cout << spt;
}
 
// Driver Code
int main()
{
    int N = 4;
    spt_function(N);
    return 0;
}

Java

// Java implementation to find the
// Spt Function to given number
import java.util.*;
 
class GFG{
 
// Variable to store spt
// function of a number
static int spt = 0;
 
// Find the value of frequency
// of minimum element
static int count(Vector<Integer> arr, int min_i)
{
    int count = 0;
     
    for(int i = 0; i < arr.size(); i++)
        if(min_i == arr.get(i))
        count++;
         
    return count;
}
 
// Function to add value of
// frequency of minimum element
// among all representations of n
static void printVector(Vector<Integer> arr)
{
    int min_i = Integer.MAX_VALUE;
    for(int i = 0; i < arr.size(); i++)
        min_i = Math.min(min_i, arr.elementAt(i));
 
    // Find the value of frequency
    // of minimum element
    int freq = count(arr, min_i);
 
    // Calculate spt
    spt += freq;
}
 
// Recursive function to find
// different ways in which
// n can be written as a sum of
// at one or more positive integers
static void findWays(Vector<Integer> arr,
                     int i, int n)
{
     
    // If sum becomes n, consider
    // this representation
    if (n == 0)
        printVector(arr);
 
    // Start from previous element
    // in the representation till n
    for(int j = i; j <= n; j++)
    {
         
        // Include current element
        // from representation
        arr.add(j);
 
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // backtrack - remove current
        // element from representation
        arr.remove(arr.size() - 1);
    }
}
 
// Function to find
// the spt function
static void spt_function(int n)
{
    Vector<Integer> arr = new Vector<>();
 
    // Using recurrence find
    // different ways in which
    // n can be written as a sum of
    // at 1 or more positive integers
    findWays(arr, 1, n);
 
    System.out.print(spt);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 4;
     
    spt_function(N);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 implementation to find the
# Spt Function to given number
import sys
 
# Variable to store spt
# function of a number
spt = 0
 
# Function to add value
# of frequency of minimum element
# among all representations of n
def printVector(arr):
   
    global spt
     
    min_i = sys.maxsize
    for i in range(len(arr)):
        min_i = min(min_i, arr[i])
 
    # Find the value of frequency
    # of minimum element
    freq = arr.count(min_i)
 
    # Calculate spt
    spt += freq
 
# Recursive function to find
# different ways in which
# n can be written as a sum of
# at one or more positive integers
def findWays(arr, i, n):
   
    # If sum becomes n,
    # consider this representation
    if (n == 0):
        printVector(arr)
 
    # Start from previous element
    # in the representation till n
    for j in range(i, n + 1):
 
        # Include current element
        # from representation
        arr.append(j)
 
        # Call function again
        # with reduced sum
        findWays(arr, j, n - j)
 
        # Backtrack - remove current
        # element from representation
        del arr[-1]
 
# Function to find
# the spt function
def spt_function(n):
 
    arr = []
 
    # Using recurrence find
    # different ways in which
    # n can be written as a sum of
    # at 1 or more positive integers
    findWays(arr, 1, n)
 
    print(spt)
 
# Driver Code
if __name__ == '__main__':
   
    N = 4
    spt_function(N)
 
# This code is contributed by mohit kumar 29

C#

// C# implementation to find the
// Spt Function to given number
using System;
using System.Collections.Generic;
 
class GFG{
 
// Variable to store spt
// function of a number
static int spt = 0;
 
// Find the value of frequency
// of minimum element
static int count(List<int> arr, int min_i)
{
    int count = 0;
 
    for(int i = 0; i < arr.Count; i++)
        if (min_i == arr[i])
            count++;
 
    return count;
}
 
// Function to add value of
// frequency of minimum element
// among all representations of n
static void printList(List<int> arr)
{
    int min_i = int.MaxValue;
    for(int i = 0; i < arr.Count; i++)
        min_i = Math.Min(min_i, arr[i]);
 
    // Find the value of frequency
    // of minimum element
    int freq = count(arr, min_i);
 
    // Calculate spt
    spt += freq;
}
 
// Recursive function to find
// different ways in which
// n can be written as a sum of
// at one or more positive integers
static void findWays(List<int> arr,
                          int i, int n)
{
 
    // If sum becomes n, consider
    // this representation
    if (n == 0)
        printList(arr);
 
    // Start from previous element
    // in the representation till n
    for(int j = i; j <= n; j++)
    {
         
        // Include current element
        // from representation
        arr.Add(j);
 
        // Call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // backtrack - remove current
        // element from representation
        arr.RemoveAt(arr.Count - 1);
    }
}
 
// Function to find
// the spt function
static void spt_function(int n)
{
    List<int> arr = new List<int>();
 
    // Using recurrence find
    // different ways in which
    // n can be written as a sum of
    // at 1 or more positive integers
    findWays(arr, 1, n);
 
    Console.Write(spt);
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 4;
 
    spt_function(N);
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
 
// Javascript implementation to find the
// Spt Function to given number
 
// variable to store spt
// function of a number
var spt = 0;
 
// Function to add value
// of frequency of minimum element
// among all representations of n
function printVector(arr)
{
    var min_i = 1000000000;
    for (var i = 0; i < arr.length; i++)
        min_i = Math.min(min_i, arr[i]);
 
    // find the value of frequency
    // of minimum element
    var freq = 0;
 
    for(var i =0;i<arr.length; i++)
    {
       if( arr[i] == min_i)
          freq++;
    }
 
    // calculate spt
    spt += freq;
}
 
// Recursive function to find
// different ways in which
// n can be written as a sum of
// at one or more positive integers
function findWays(arr, i, n)
{
    // if sum becomes n,
    // consider this representation
    if (n == 0)
        printVector(arr);
 
    // start from previous element
    // in the representation till n
    for (var j = i; j <= n; j++) {
 
        // include current element
        // from representation
        arr.push(j);
 
        // call function again
        // with reduced sum
        findWays(arr, j, n - j);
 
        // backtrack - remove current
        // element from representation
        arr.pop();
    }
}
 
// Function to find
// the spt function
function spt_function( n)
{
 
    var arr = [];
 
    // Using recurrence find
    // different ways in which
    // n can be written as a sum of
    // at 1 or more positive integers
    findWays(arr, 1, n);
 
    document.write( spt);
}
 
// Driver Code
var N = 4;
spt_function(N);
 
// This code is contributed by rutvik_56.
</script>
Producción: 

10

 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *