Jump to content
xtrm0

Problema com divisão de polinómios

Recommended Posts

xtrm0

Boas, estou a fazer um CAS, no entanto estou com problemas com a divisao de polinomios. Estou a utilizar o algoritmo da divisao longa de polinomis. Ja fiz o seguinte, no entanto o programa tende a entrar num loop infinito.

Podem-me ajudar, sff?

typedef struct{
   int num, den;
   int pos;// casos possiveis: -1 -> negativo, 1-> positivo.
}fract ;
typedef struct {
   fract quof[MAXS+1]; //os quoficientes por ordem: quof[0]-> x^0, quof[50]->x^50, ...
}poly ;
void div_poly(poly * a, poly * b, poly * c) { // c=(a/b)
poly resto, tmp2;
fract tmp, tmp1, tmp3;
int i, j, k, g;
init_poly(&resto);
init_poly(c);
init_fract(&tmp);
for (g=MAXS; g>=0; g--) {
	if (b->quof[g].num!=0) break;
}
while(1) {
	for (k=MAXS; k>=0; k--) {
		if (a->quof[k].num!=0) break;
	}
	if (k<g) break;
	div_fract(&(a->quof[k]), &(b->quof[g]), &tmp);
	c->quof[g-k] = tmp;
	for (i=g; i>=0; i--) {
		mult_fract(&(b->quof[i]), &tmp, &tmp1); //c=a*b)
		subtr_fract(&(a->quof[i]), &tmp1, &(resto.quof[i+k-g])); //c=a-b
	}
	for (i=0; i<=MAXS; i++) {
		a->quof[i].num=resto.quof[i].num;
		a->quof[i].den=resto.quof[i].den;
		a->quof[i].pos=resto.quof[i].pos;
	}
}
return;
}
 

Cumprimentos,

Xtrm0


<Signature goes here>

Share this post


Link to post
Share on other sites
pmg

No último ciclo for estás a alterar a variável "a". Parece-me errado, mas não sei se tem influência para fazer um loop infinito.

De qualquer maneira sugiro que adiciones uns const na definição da função

// c = a / b
// return 0: ok
// return 1: erro
int div_poly(const poly *a, const poly *b, poly *c);


What have you tried?

Não respondo a dúvidas por PM

A minha bola de cristal está para compor; deve ficar pronta para a semana.

Torna os teus tópicos mais atractivos e legíveis usando a tag CODE para colorir o código!

Share this post


Link to post
Share on other sites
bsccara

A alteração que o pmg sugeriu não tem nada a ver com a ciclo infinito; apenas é boa prática quando se trabalha com ponteiros para conteúdos imutáveis.

O motivo óbvio para o ciclo infinito é que a variável 'k' nunca é menor que a 'g'. Como a variável 'g' é imutável dentro do ciclo o teu problema será um de dois: a variável 'g' deveria mudar dentro do ciclo ou a variável 'k' está a ser mal actualizada, por erro no algoritmo. Como a variável 'k' é um índice para o primeiro numerador de coeficiente do polinómio 'a' com valor diferente de 0, podes ter algum erro envolvendo a actualização desse polinómio.

Share this post


Link to post
Share on other sites
xtrm0

Obrigado. Ja corrigi. O erro estava em alterar isto:

               c->quof[g-k] = tmp;
               for (i=g; i>=0; i--) {
                       mult_fract(&(b->quof[i]), &tmp, &tmp1); //c=a*b)
                       subtr_fract(&(a->quof[i]), &tmp1, &(resto.quof[i+k-g])); //c=a-b
               }
               for (i=0; i<=MAXS; i++) {
                       a->quof[i].num=resto.quof[i].num;
                       a->quof[i].den=resto.quof[i].den;
                       a->quof[i].pos=resto.quof[i].pos;
               }

Para isto:

	c->quof[k-g] = tmp;
	for (i=g; i>=0; i--) {
		mult_fract(&(b->quof[i]), &tmp, &tmp1);
		subtr_fract(&(a->quof[i+k-g]), &tmp1, &(resto.quof[i+k-g]));
	}
               for (i=k; i>=k-g; i--) {
                       a->quof[i].num=resto.quof[i].num;
                       a->quof[i].den=resto.quof[i].den;
                       a->quof[i].pos=resto.quof[i].pos;
               }

Obrigado pela ajuda.

Cumprimentos,

Xtrm0


<Signature goes here>

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.