Problema com divisão de polinómios

[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

[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);

[xtrm0]

Já alterei como disseste e o loop infinito continua. 😛

[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.

[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