Dados dos enteros positivos N y K , la tarea es encontrar la media del mínimo de todos los subconjuntos posibles de tamaño K de los primeros N números naturales .
Ejemplos:
Entrada: N = 3, K = 2
Salida: 1,33333
Explicación:
Todos los subconjuntos posibles de tamaño K son {1, 2}, {1, 3}, {2, 3}. Los valores mínimos en todos los subconjuntos son 1, 1 y 2 respectivamente. La media de todos los valores mínimos es (1 + 1 + 2)/3 = 1,3333.Entrada: N = 3, K = 1
Salida: 2,00000
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar todos los subconjuntos formados a partir de elementos [1, N] y encontrar la media de todos los elementos mínimos de los subconjuntos de tamaño K.
Complejidad temporal: O(N*2 N )
Espacio auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar observando el hecho de que el número total de subconjuntos formados de tamaño K está dado por N C K y cada elemento dice i ocurre (N – i) C (K – 1) número de veces como elemento mínimo.
Por lo tanto, la idea es encontrar la suma de ( N – i C K – 1) )*i sobre todos los valores posibles de i y dividirla por el número total de subconjuntos formados, es decir, N C K .
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 value of nCr
int nCr(int n, int r, int f[])
{
// Base Case
if (n < r) {
return 0;
}
// Find nCr recursively
return f[n] / (f[r] * f[n - r]);
}
// Function to find the expected minimum
// values of all the subsets of size K
int findMean(int N, int X)
{
// Find the factorials that will
// be used later
int f[N + 1];
f[0] = 1;
// Find the factorials
for (int i = 1; i <= N; i++) {
f[i] = f[i - 1] * i;
}
// Total number of subsets
int total = nCr(N, X, f);
// Stores the sum of minimum over
// all possible subsets
int count = 0;
// Iterate over all possible minimum
for (int i = 1; i <= N; i++) {
count += nCr(N - i, X - 1, f) * i;
}
// Find the mean over all subsets
double E_X = double(count) / double(total);
cout << setprecision(10) << E_X;
return 0;
}
// Driver Code
int main()
{
int N = 3, X = 2;
findMean(N, X);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the value of nCr
static int nCr(int n, int r, int f[]) {
// Base Case
if (n < r) {
return 0;
}
// Find nCr recursively
return f[n] / (f[r] * f[n - r]);
}
// Function to find the expected minimum
// values of all the subsets of size K
static int findMean(int N, int X) {
// Find the factorials that will
// be used later
int[] f = new int[N + 1];
f[0] = 1;
// Find the factorials
for (int i = 1; i <= N; i++) {
f[i] = f[i - 1] * i;
}
// Total number of subsets
int total = nCr(N, X, f);
// Stores the sum of minimum over
// all possible subsets
int count = 0;
// Iterate over all possible minimum
for (int i = 1; i <= N; i++) {
count += nCr(N - i, X - 1, f) * i;
}
// Find the mean over all subsets
double E_X = (double) (count) / (double) (total);
System.out.print(String.format("%.6f", E_X));
return 0;
}
// Driver Code
public static void main(String[] args) {
int N = 3, X = 2;
findMean(N, X);
}
}
// This code contributed by Princi Singh
Python3
# Python 3 program for the above approach
# Function to find the value of nCr
def nCr(n, r, f):
# Base Case
if (n < r):
return 0
# Find nCr recursively
return f[n] / (f[r] * f[n - r])
# Function to find the expected minimum
# values of all the subsets of size K
def findMean(N, X):
# Find the factorials that will
# be used later
f = [0 for i in range(N + 1)]
f[0] = 1
# Find the factorials
for i in range(1,N+1,1):
f[i] = f[i - 1] * i
# Total number of subsets
total = nCr(N, X, f)
# Stores the sum of minimum over
# all possible subsets
count = 0
# Iterate over all possible minimum
for i in range(1,N+1,1):
count += nCr(N - i, X - 1, f) * i
# Find the mean over all subsets
E_X = (count) / (total)
print("{0:.9f}".format(E_X))
return 0
# Driver Code
if __name__ == '__main__':
N = 3
X = 2
findMean(N, X)
# This code is contributed by ipg201607.
C#
// C# code for the above approach
using System;
public class GFG
{
// Function to find the value of nCr
static int nCr(int n, int r, int[] f)
{
// Base Case
if (n < r) {
return 0;
}
// Find nCr recursively
return f[n] / (f[r] * f[n - r]);
}
// Function to find the expected minimum
// values of all the subsets of size K
static int findMean(int N, int X)
{
// Find the factorials that will
// be used later
int[] f = new int[N + 1];
f[0] = 1;
// Find the factorials
for (int i = 1; i <= N; i++) {
f[i] = f[i - 1] * i;
}
// Total number of subsets
int total = nCr(N, X, f);
// Stores the sum of minimum over
// all possible subsets
int count = 0;
// Iterate over all possible minimum
for (int i = 1; i <= N; i++) {
count += nCr(N - i, X - 1, f) * i;
}
// Find the mean over all subsets
double E_X = (double) (count) / (double) (total);
Console.Write("{0:F9}", E_X);
return 0;
}
// Driver Code
static public void Main (){
// Code
int N = 3, X = 2;
findMean(N, X);
}
}
// This code is contributed by Potta Lokesh
Javascript
<script>
// Javascript program for the above approach
// Function to find the value of nCr
function nCr(n, r, f) {
// Base Case
if (n < r) {
return 0;
}
// Find nCr recursively
return f[n] / (f[r] * f[n - r]);
}
// Function to find the expected minimum
// values of all the subsets of size K
function findMean(N, X) {
// Find the factorials that will
// be used later
let f = new Array(N + 1).fill(0);
f[0] = 1;
// Find the factorials
for (let i = 1; i <= N; i++) {
f[i] = f[i - 1] * i;
}
// Total number of subsets
let total = nCr(N, X, f);
// Stores the sum of minimum over
// all possible subsets
let count = 0;
// Iterate over all possible minimum
for (let i = 1; i <= N; i++) {
count += nCr(N - i, X - 1, f) * i;
}
// Find the mean over all subsets
let E_X = count / total;
document.write(parseFloat(E_X).toFixed(9));
return 0;
}
// Driver Code
let N = 3,
X = 2;
findMean(N, X);
// This code is contributed by gfgking.
</script>
1.333333333
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA