/* ******************************************************************************
* Autor: Marlene E.Vásquez C
* Descripción: Programa que realiza el cálculo de número de combinaciones,
* sin repeticiones y con repetición de n en k.
* Fecha: 22-12 2011
*********************************************************************************/
/**
* @file combinaciones.cpp
* @brief Programa que realiza el cálculo de número de combinaciones,
* sin repetición y con repetición, de n en k.
*
* El programa pide un par de valores positivos y el segundo no debe ser mayor.
*
* Salida: escribir el número de combinaciones de n en k, con repeticiones y sin
* repeticiones.
*/
#include <iostream> // biblioteca para uso de cout
#include <cmath>//utilizar sqrt
#include <vector> //Para utilizar vectores
using namespace std;
// Funciones
void leerDatos(int &m,int &p);
bool EsPrimo(int n);//
bool esCalculable(vector <int> x,int &p);
vector <int> FactoresPrimos(int numero);
vector <int> ProductoComponentes(vector <int> v, vector <int> c);
vector <int> Factorial(int numero);
vector <int> eliminarElementos(vector<int> v) ;// funcion necesaria para la funcion Simplificar Nº2 comentada.
void Simplificar(vector <int> &primosNumerador,vector <int> &primosDenominador);
void Producto(vector <int> v);
void imprimirVector(vector <int> v);
void CombinacionesConRepeticiones(int n , int k);
void CombinacionesSinRepeticiones(int n , int k);
void C(int m , int p);
int main()
{
cout << "------ Programa de Cálculo de Combinaciones ------" << endl;
int m, p ;
leerDatos(m,p);
C(m,p);
}
/**
* @brief lee dos valores
* @param n primer parametro pasado por referencia.
* @param k segundo parametro pasado por referencia.
* @pre carga @a n y @a k > 0 y @a k es menor que @a n
*/
void leerDatos( int &n , int &k )
{
cout << "Introduzca n y k : ";
cin >> n >> k ;
while (n<0 || k<0 || k>n)
{
cout << "No puede ser negativo y el segundo no puede ser mayor"<<endl;
cout << "Introduzca de nuevo: ";
cin >> n >> k;
}
}
/**
* @brief
* @param n
* @return si es primo.
*/
bool EsPrimo( int n )
{
int raiz = sqrt(n);
bool esprimo = true;
for(int i = 2; i <= raiz && esprimo; ++i)
{
if(n%i == 0)
esprimo = false;//es divisible
}
return esprimo;
}
/**
* @brief Módulo para calcular la descomposición en factores primos. Este módulo
* convierte un
* valor entero (int) a un vector con la descomposición en números primos.
* @param numero
* @return @a primos vector con los factores primos de @a numero
*/
vector <int> FactoresPrimos( int numero )
{
vector <int> primos;
int i = 2;
if ( EsPrimo(numero)== false)
{
do
{
if (!(numero % i))
{
numero = numero / i;
primos.push_back(i);
}
else
i++;
}while(i <= numero);
}
else
primos.push_back(numero);
return primos;
}
/**
* @brief Módulo para multiplicar “enteros”. Obtiene el vector resultado de
* multiplicar dos
* vectores que corresponden a descomposiciones de números en primos.
* @param a primer "vector" parametro.
* @param b segundo "vector" parametro.
* @return @a c vector resultante de unir los vectores v y c.
*/
vector <int> ProductoComponentes(vector <int> a ,vector <int> b)
{
vector<int> c;
int i= 0,j= 0;
while( i < a.size() && j < b.size())
{
if(a.at(i) < b.at(j))
{
c.push_back(a.at(i));
i++;
}
else
{
c.push_back(b.at(j));
j++;
}
}
if (i < a.size())
{
while(i < a.size())
{
c.push_back(a.at(i));
++i;
}
}
if(j<b.size())
{
while(j < b.size())
{
c.push_back(b.at(j));
j++;
}
return c;
}
}
/**
* @brief Módulo para calcular el factorial. realiza el calculo factorial de un
* numero.
* @param numero
* @return @a nuevo vector que contiene el factorial de @a numero descompuesto en
* factores primos .
*/
vector <int> Factorial(int numero)
{
vector <int> nuevo;
for (int i=2; i<=numero ; ++i)
{
nuevo = ProductoComponentes(nuevo,FactoresPrimos(i));
}
return nuevo;
}
/**
* @brief Módulo para determinar si el entero es calculable.
* @param v "vector".
* @return si es calculable .
*/
bool esCalculable(vector <int> v,int &p)
{
int u = 1,n;
bool calc = false;
for ( int i=0;i<v.size(); ++i )
{
n = u * v.at(i);
if (i == v.size()-1 && n/v.at(i) == u )
{
calc = true;
p=n;
}
else
if( n/v.at(i) != u)
{
calc = false;
break;
}
u = n ;
}
return calc;
}
/**
* @brief Módulo para dividir enteros. Obtiene el vector resultado de dividir dos * vectores que corresponden a descomposiciones de números en primos. Dado que el * resultado no tiene por qué ser un entero, este modulo esta implementado para
* que transforme el numerador y el denominador mediante la simplificación
* "eliminacion" de primos comunes.
* @param primosNumerador "vector" primer argumento pasado por referencia.
* @param primosDenominador "vector" segundo argumento pasado por referencia. */
//----------------------Funciones para simplificar------------------------
//------------------------Funcion Simplificar---------------------------
void Simplificar(vector <int> &primosNumerador, vector <int> &primosDenominador)
{
int i=0,j=0;
vector<int> numerador;
vector<int> denominador;
while( i < primosNumerador.size() && j < primosDenominador.size())
{
if(primosNumerador.at(i) < primosDenominador.at(j))
{
numerador.push_back(primosNumerador.at(i));
i++;
}
else if (primosNumerador.at(i) == primosDenominador.at(j))
{
i++;
j++;
}else if(primosNumerador.at(i) > primosDenominador.at(j))
{
denominador.push_back(primosDenominador.at(j));
j++;
}
}
if (i<primosNumerador.size())
{
while(i < primosNumerador.size())
{
numerador.push_back(primosNumerador.at(i));
i++;
}
}
if(j < primosDenominador.size())
{
while(j < primosDenominador.size())
{
denominador.push_back(primosDenominador.at(j));
j++;
}
}
if(numerador.empty()) numerador.push_back(1);
if(denominador.empty()) denominador.push_back(1);
primosNumerador=numerador;
primosDenominador=denominador;
}
//------------------------Funcion Simplificar Nº2----------------------------
//void Simplificar(vector <int> &primosNumerador, vector <int> &primosDenominador)
//{
// // Elimina de cada vector los factores primos repetidos
//
// // reemplazandolos por 1
// for(int i=0;i < primosNumerador.size();++i)
// {
// for (int j=0;j < primosDenominador.size();++j)
// {
// if (primosNumerador.at(i) == primosDenominador.at(j))
// {
// primosNumerador.at(i) = 1;
// primosDenominador.at(j) = 1;
// }
// }
// }
//
// primosNumerador= eliminarElementos(primosNumerador);
// primosDenominador=eliminarElementos(primosDenominador);
//}
// /**
// * @brief Módulo para eliminar elementos del vector que sean igual a 1
// * @param v "vector".
// * @return resultado "vector" con elementos !=1
// */
//vector <int> eliminarElementos(vector<int> v)
//{
// vector<int> resultado;
// for (int i=0; i<v.size();++i)
// {
// if (v.at(i)!=1)// si el valor del vector es diferente de 1 se escribe en el vector resultado
// resultado.push_back(v.at(i));
// }
// if (resultado.empty())// si el vector resultado es vacio
// resultado.push_back(1);
//
// return resultado;
//}
//------------------------------------------------------------------------------------------------------------------
/**
* @brief Módulo para calcular el producto de los elemento de un vector
* @param v "vector".
* @post esCalculable(v)==true;
*
*/
void Producto(vector <int> v)
{
int p;
if((esCalculable(v,p) == false))// llama a la funcion esCalculable();
cout <<" = Entero Indeterminado" << endl;
else
if (p !=1 )
cout << " = "<< p << endl;
else
cout << endl;
}
/**
* @brief Módulo para mostrar datos que contiene un vector y
* el resultado de multiplicar cada uno de sus elementos.
*
* @param v "vector".
*/
void imprimirVector(vector <int> v)
{
int i=0, m=v.size();
while(i < m)
{
if(i < m-1)
cout << v.at(i) << " * ";
else
cout << v.at(i);
++i;
}
Producto(v);
}
/**
* @brief Módulo para calcular la ecuacion c = n! / k!*(n-k)!
*
* @param n primer parametro
* @param k segundo parametro
*/
void CombinacionesSinRepeticiones(int n, int k)
{
//(El numero combinatorio n sobre k calculado de la forma:
/*
n n! -> numerador
c(n,k)=( )=(----------- )
k k!*(n-k)! -> denominador
*/
vector <int> numerador;
vector <int> denominador;
numerador = Factorial(n);
denominador = ProductoComponentes(Factorial(k),Factorial(n-k));
cout << "Combinaciones sin repeticiones de n en k" <<endl;
Simplificar(numerador,denominador);
cout << "Numerador: ";
imprimirVector(numerador);
cout << "Denominador: ";
imprimirVector(denominador);
}
/**
* @brief Módulo para calcular la ecuacion c = (n+k-1)! / k!*(n-1)!
*
* @param n primer parametro
* @param k segundo parametro
*/
void CombinacionesConRepeticiones(int n, int k)
{
//(El numero combinatorio n sobre k calculado de la :
/*
n+k-1 (n+k-1)! -> numerador
c(n+k-1,k)=( )= -----------
k k!*(n-1)! -> denominador
*/
vector <int> numerador;
vector <int> denominador;
numerador = Factorial(n+k-1);
denominador = ProductoComponentes(Factorial(k),Factorial(n-1));
cout << "Combinaciones con repeticiones de n en k" << endl;
Simplificar(numerador,denominador);
cout << "Numerador: ";
imprimirVector(numerador);
cout << "Denominador: ";
imprimirVector(denominador);
}
/**
* @brief Módulo que simplifica la llamada a las dos funciones
* que calculan la ecuaciones y presentan los resultados de las dos ecuaciones
* calculadas independientemente.
* @param m primer parametro
* @param p segundo parametro
*/
void C(int m, int p)
{
CombinacionesSinRepeticiones(m,p);
cout << "-----------------------" << endl;
CombinacionesConRepeticiones(m,p);
}
No hay comentarios:
Publicar un comentario