Hola todos, necesito un pequeño empujon con un problema que tengo que hacer, sobre la multiplicación de polinomios mediante la técnica de divide y vencerás.
Ya he echo algo, pero no funciona bien, podrías decirme porque no funciona.
Aqui os dejo el código
Gracias
#include <stdio.h>
#include <stdlib.h>
int multiplicar(int *, int *, int *, int, int *, int *);
void combinar(int, int *, int *);
int espotenciade2(int);
int main(int argc, char *argv[]){
int n;
int contador=0,i=0;
int *P; /*Arrays que contienen los coeficientes de los polinomios que hay
que multiplicar*/
int *Q;
int *PQ; /*Array donde se almacenará el resultado de la multiplicación*/
int *aux;
int *vectorr; /*Array para almacenar resultados parciales*/
char c=getche();
switch(argc){
case 2:
n=atoi(argv[1]);
if(espotenciade2(n)==-2){ /*Si n es potencia de 2 se mostrara un mensaje
de error por la salida de error estandar*/
fprintf(stderr,"Uso: ./pract2 <n>\nSiendo n un numero entero potencia de 2\n");
return -2;
}
P=(int *)malloc(n * sizeof(int));
Q=(int *)malloc(n * sizeof(int));
vectorr=(int *)malloc(((2*n)+1) * sizeof(int));
PQ=(int *)malloc(((2*n)) * sizeof(int));
/*Pedir al usuario datos de entrada para el polinomio P*/
while(contador < n){
printf("P[ %d] = ",contador);
scanf("%d", &(P[contador]));
contador++;
printf("\n");
}
char c=getche();
contador=0;
/*Pedir al usuario datos de entrada para el polinomio Q*/
while(contador < n){
printf("Q[ %d] = ",contador);
scanf("%d", &(Q[contador]));
contador++;
printf("\n");
}
c=getche();
for(i=0; i<(2*n)-1; i++)
PQ[i]=0;
aux=(int *)malloc(sizeof(int));
*aux=0;
printf("antes del multiplicar");
multiplicar(P,Q,PQ,n,aux,vectorr);
c=getche();
combinar(n,vectorr,PQ);
c=getche();
for(i=0; i<(2*n)-1; i++)
printf("%d ",PQ[i]);
break;
default:
fprintf(stderr,"Uso: ./pract2 <n>\nSiendo n un numero entero potencia de 2\n");
return -1;
}
printf("\n");
free(vectorr);
free(PQ);
free(P);
free(Q);
free(aux);
return 0;
c= getche();
}
/*Algoritmo para comprobar que n cumpla la restricción de ser potencia de
2*/
int espotenciade2(int n){
int aux;
while(1){
aux=n%2;
n/=2;
if(aux != 0)
return -2; /*No es potencia de 2*/
if(n == 1)
return 0; /*Es potencia de 2*/
}
}
/*Algoritmo para combinar las soluciones parciales siguiendo la fórmula*/
void combinar(int n, int *vectorr, int *PQ){
int RI[n-1];
int RH[n-1];
int RD[n-1];
int contador=0, i=0;
for(i=0; i<n-1; i++){
RI[i]=vectorr[contador];
contador++;
}
for(i=0; i<n-1; i++){
RD[i]=vectorr[contador];
contador++;
}
for(i=0; i<n-1; i++){
RH[i]=vectorr[contador];
contador++;
}
contador=0;
for(i=0; i<n/2; i++){
PQ[i]=RI[i];
contador++;
}
for(i=n/2; i<=n; i++){
if(contador<n-1)
PQ[contador]=RI[contador] + RH[contador-2] - RI[contador-2] -
RD[contador-2];
else if(contador == n-1)
PQ[contador]=RH[contador-2] - RI[contador-2] - RD[contador-2];
else
PQ[contador]=RH[n/2] - RI[n/2] - RD[n/2] + RD[contador-n];
contador++;
}
contador=1;
for(i=n+1; i<(2*n)-1; i++){
PQ[i]=RD[contador];
contador++;
}
}
/*Algoritmo basado en la tecnica Divide y Venceras*/
int multiplicar(int *P, int *Q, int *PQ, int n, int *aux, int *vectorr){
int i=0, j=0, producto;
int PI[n/2];
int PD[n/2];
int QI[n/2];
int QD[n/2];
int sumaP[n/2];
int sumaQ[n/2];
int *RI=(int *)malloc(sizeof(int));
int *RD=(int *)malloc(sizeof(int));
int *RH=(int *)malloc(sizeof(int));
if(n == 1){ /*Caso base de la recursividad. Operar con escalares.*/
producto = *P * *Q;
return producto;
}
/*Dividir los polinomios*/
else{
for(i=0; i<(n/2); i++)
PI[i]=P[i];
for(j=0; j<(n/2); j++){
PD[j]=P[i];
i++;
}
for(i=0; i<(n/2); i++)
QI[i]=Q[i];
for(j=0; j<(n/2); j++){
QD[j]=Q[i];
i++;
}
/*Aqui calcular las erres: RI, RD y RH*/
*RI=multiplicar(PI,QI,RI,n/2,aux,vectorr);
*RD=multiplicar(PD,QD,RD,n/2,aux,vectorr);
for(i=0; i<n/2; i++)
sumaP[i]=PI[i] + PD[i];
for(i=0; i<n/2; i++)
sumaQ[i]=QI[i] + QD[i];
*RH=multiplicar(sumaP,sumaQ,RH,n/2,aux,vectorr);
/*PQ = (RH - RI - RD)*/
*PQ = *RH - *RI - *RD;
vectorr[*aux]=*RI;
(*aux)++;
vectorr[*aux]=*PQ;
(*aux)++;
vectorr[*aux]=*RD;
(*aux)++;
}
free(RI); free(RD); free(RH);
return 0;
}
Este tema le ha gustado a 2 personas (incluyéndote)