Estoy tratando de agregar dos funciones polinómicas y almacenar la respuesta en la primera. Hasta ahora tengo esto:

// co = coefficient, ex = exponent
void add_polynom(int co1[], int ex1[], int co2[], int ex2[])
{
    int i, j;
    for (i = 0; i < dataSize; i++)
    {
        for (j = 0; j < dataSize; j++)
        {
            if (ex1[i] == ex2[j])
            {
                co1[i] = co1[i] + co2[i];
                co2[i] = 0;
            }
        }
    }
}

¿Estoy en el camino correcto?

c
0
user2962635 26 oct. 2017 a las 20:50

3 respuestas

La mejor respuesta

Su representación de polinomios no es práctica:

  • itera en 2 bucles anidados (complejidad cuadrática) para tratar de hacer coincidir los términos correspondientes de ambos polinomios, pero si el segundo tiene un poder que el primero no tiene, faltará en la suma.

  • pasa el grado como una variable global dataSize que puede tener un valor inapropiado.

En su lugar, debe usar una matriz de coeficientes para todos los exponentes desde 0 hasta el grado del polinomio y pasar el polinomio de destino y su grado de esta manera:

/* add 2 polynomials into a destination array.
 * count variables are the sizes of the arrays,
 *   ie 1 more than the degree of the polynomials.
 * return the size of the resulting polynomial,
 *   potentially larger than the size of the destination array.
 */
int add_polynomials(int dest[], int dest_count,
                    const int co1[], int count1,
                    const int co2[], int count2) {
    /* compute the result coefficients */
    int i, count;
    for (i = count = 0; i < dest_count; i++) {
        int coef = 0;
        if (i < count1)
            coef += co1[i];
        if (i < count2)
            coef += co2[i];
        dest[i] = coef;
        if (coef != 0)
            count = i + 1;
    }
    /* determine the result count */
    for (; i < count1 && i < count2; i++) {
        if (co1[i] + co2[i] != 0)
            count = i + 1;
    }
    for (; i < count1; i++) {
        if (co1[i] != 0)
            count = i + 1;
    }
    for (; i < count2; i++) {
        if (co2[i] != 0)
            count = i + 1;
    }
    return count;
}

Si debe usar el prototipo y la definición global dados para dataSize, podría usar 2 bucles anidados, pero dependiendo de cómo se usen los exponentes en ambos polinomios, podría ser imposible ajustar el resultado en la matriz de destino:

  • los polinomios de origen pueden tener hasta dataSize términos con cualquier rango de exponentes. El polinomio resultante puede tener un número total de términos que excede dataSize y, por lo tanto, no es representable en una matriz de tamaño dataSize.

  • su código falla porque escribió co1[i] = co1[i] + co2[i]; en lugar de co1[i] = co1[i] + co2[j];, pero también modifica co2[i], lo cual es inapropiado y omite los términos que solo están presentes en co2 / {{ X4}}.

Si podemos suponer que el exponente máximo es menor que dataSize, aquí hay un enfoque eficiente (tiempo lineal) que generará un resultado en forma normalizada:

#define dataSize  50

// co = coefficients, ex = exponents
void add_polynom(int co1[], int ex1[], int co2[], int ex2[]) {
    int res[dataSize] = { 0 };
    int i, j;
    for (i = 0; i < dataSize; i++) {
        res[ex1[i]] += co1[i];
        res[ex2[i]] += co2[i];
    }
    j = 0;
    for (i = dataSize; i-- > 0;) {
        if (res[i] != 0) {
            co1[j] = res[i];
            ex1[j] = i;
            j++;
        }
    }
    while (j < dataSize) {
        co1[j] = ex1[j] = 0;
    }
}
0
chqrlie 26 oct. 2017 a las 19:19

Su interfaz es "subóptima". Obliga a hacer garantías para que funcione en absoluto.

  • Use la opción 1 si puede garantizar que todos los valores de exs1 y exs2 están en [0 .. ( DATASIZE -1)].

  • Use la opción 2 si simplemente puede garantizar que hay menos de DATASIZE valores diferentes en exs1 y exs2 combinados.

Opción 1

El rendimiento de esta solución está sujeto a O (N).

#define DATASIZE 50

void panic(const char* msg) {
   fprintf(stderr, msg);
   exit(EXIT_FAILURE);
}

find_ex(ex, 

// Assumes all values in exs1 are in [0..49].
// Assumes all values in exs2 are in [0..49].
void add_polynom(int cos1[], int exs1[], int cos2[], int exs2[]) {
    int cos_sum[DATASIZE];
    size_t i;
    int exs1i, exs2i;

    for (i=DATASIZE; i--; )
       cos_sum[i] = 0;

    for (i=DATASIZE; i--; ) {
        if (exs1[i] < 0 || exs1[i] >= DATASIZE || exs2[i] < 0 || exs2[i] >= DATASIZE)
            panic("add_polynom: Exponent out of range\n");

        cos_sum[exs1[i]] += cos1[i];
        cos_sum[exs2[i]] += cos2[i];
    }

    for (i=DATASIZE; i--; ) {
        cos1[i] = cos_sum[i];
        exs1[i] = i;

        cos2[i] = 0;
        /* exs2[i] = i; */
    }
}

Opción 2

El rendimiento de esta solución está limitado por O (N 2 ). El límite se puede reducir a O (N) mediante el uso de una matriz asociativa en lugar de find_index_of_ex, pero eso es demasiado trabajo para esta respuesta.

#define DATASIZE 50

void panic(const char* msg) {
   fprintf(stderr, msg);
   exit(EXIT_FAILURE);
}

ssize_t find_index_of_ex(int ex, int cos[], int exs[], size_t size) {
    ssize_t i;
    for (i=0; i<size; ++i) {
        if (exs[i] == ex) {
            return i;
        }
    }

    return -1;
}

// Assumes there are fewer than DATASIZE different values in exs1 and exs2 combined.
void add_polynom(int cos1[], int exs1[], int cos2[], int exs2[]) {
    int cos_sum[];
    int exs_sum[];
    ssize_t lookup_is_by_ex[datasize];
    size_t i, sum_count;
    ssize_t i_sum;

    for (i=DATASIZE; i--; ) {
       cos_sum[i] = 0;
       exs_sum[i] = 0;
    }

    sum_count = 0;
    for (i=DATASIZE; i--; ) {
        if (cos1[i] == 0)
            continue;

        i_sum = find_index_of_ex(exs1[i], exs_sum, sum_count);
        if (i_sum >= 0)
           cos_sum[i_sum] += cos1[i];
           continue;
        }

        if (sum_count == DATASIZE)
            panic("add_polynom: Too many different exponents\n");

        cos_sum[sum_count] = cos1[i];
        exs_sum[sum_count] = exs1[i];
        ++sum_count;
    }

    for (i=DATASIZE; i--; ) {
        if (cos2[i] == 0)
            continue;

        i_sum = find_index_of_ex(exs2[i], exs_sum, sum_count);
        if (i_sum >= 0)
           cos_sum[i_sum] += cos2[i];
           continue;
        }

        if (sum_count == DATASIZE)
            panic("add_polynom: Too many different exponents\n");

        cos_sum[sum_count] = cos2[i];
        exs_sum[sum_count] = exs2[i];
        ++sum_count;
    }

    for (i=DATASIZE; i--; ) {
        cos1[i] = cos_sum[i];
        exs1[i] = exs_sum[i];

        cos2[i] = 0;
        /* exs2[i] = i; */
    }
}
0
ikegami 26 oct. 2017 a las 22:40

Tomemos, por ejemplo, 7x^3 + 2x + 1 como primer y 5x^4 + 9x^2 como segundo polinomio. Ahora dataSize se convierte en 5 (ya que el mayor grado de ambos es 4).

Ahora co1 sería {1, 2, 0, 7, 0} y co2 sería {0, 0, 9, 0, 5}.

       for (i = 0; i < dataSize; i++)
       {
            co1[i] += co2[i];
       }
0
Aditi Rawat 26 oct. 2017 a las 18:15