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 = 10Entrada: 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