Деление полиномов, C++ Builder6 Опции

[18192123]

Здравствуйте!

Предположим в качестве входных данных имеется двоичная комбинация, каждый разряд хранится в соответствующем элементе массива (char m[7]={0x1, 0x1, 0x0, 0x1, 0x0, 0x0, 0x0).
И будем ассоциировать для себя этот массив с полиномом x^6 + x^5 + x^3.
Будет ещё один фиксированный полином: char g[4]={0x1, 0x0, 0x1, 0x1} (g=x^3 + x + 1).

Задача заключается в делении m на g..Интересует остаток от деления, который в данном примере будет
char r[3]={0x0, 0x0, 0x1} (r = 1).

пример деления я привела в прикреплённом документе..

Затрудняюсь с тем, как это реализовать..объясните пожалуйста!

[volvo]

Чтобы это реализовать, надо сначала правильно сделать это столбиком на бумаге. Ты этого не сделала. Потому что проверяется деление полиномов чем? Угу, именно умножением. Умножаем полученное в твоем примере частное на делитель, и прибавляем остаток. Должны получить делимое:

(x³+x+1)*(x³+x²+x+1) + 1 = ?
Раскрываем скобки, приводим подобные, получаем: x⁶+x⁵+2x⁴+3x³+2x²+2x+2. Неверно.

Нашелся вот такой "делитель полиномов", написанный очень давно, еще под ДОС-овским ТурбоС:

#include <stdlib.h>
#include <stdio.h>

int p1[]={0x1, 0x1, 0x0, 0x1, 0x0, 0x0, 0x0};
int p2[]={0x1, 0x0, 0x1, 0x1};

int main() {
       int *ptr1=p1;

       int del;
       int i;
       int s1 = sizeof(p1)/sizeof(int);
       int s2 = sizeof(p2)/sizeof(int);
       int *result = (int*)malloc(sizeof(int)*(s1));
       int sresult =0;

       while (1) {

               del = (int)(*ptr1 / *p2);
               result[sresult]=del;
               sresult++;
               for (i=0; i<s2; i++) {
                       *(ptr1+i) -= del * p2[i];
               }


               ptr1++;
               s1--;
               if (s1<s2) break;

       }

       printf("Частное: ");
       for (i=0; i<sresult; i++) {
               if (result[i] >= 0 && i != 0) printf(" + ");
               if (sresult-i-1 !=0) {
                       if (sresult-i-1 != 1) {
                               printf(" %d*x^%d ",result[i],sresult-i-1);
                       } else {
                               printf(" %d*x ",result[i]);
                       }
               } else {
                       printf(" %d ",result[i]);
               }
       }

       printf("\n");
       s1=sizeof(p1)/4;
       printf("Остаток: ");
       for (i=0; i<s1; i++) {
               if (p1[i]!=0) {
                       if (p1[i]>0) printf(" + ");
                       if (s1-i-1 !=0) {
                               printf(" %d*x^%d",p1[i],s1-i-1);
                       } else {
                               printf(" %d ",p1[i]);
                       }
               }
       }
       printf("\n");
}

, ответ, который он выдает: частное = (x³+x²-x-1), остаток = (2x+1). Вот если это проверить умножением, то получаем исходное делимое...

[18192123]

Надо было мне сразу уточнять, что требуется несколько иное...
Такое "деление полиномов", как в прикреплённом мною документе в посте #1, используется при циклическом кодировании, соответственно, если проверять полученное мною умножением (вместо обычного сложения использовать суммирование по модулю два, т.е. исключающее ИЛИ), то всё сходится:

(x^3 + x^2 + x + 1)(x^3 + x + 1) + 1 =
x^6 + x^4 + x^3 + x^5 + x^3 + x^2 + x^4 + x^2 + x + x^3 + x + 1 + 1 =
x^6 + x^5 + x^3

(т.е. х с одинаковыми степенями взаимоуничтожились)..

Вот тут так же есть пример того, что мне нужно реализовать..
INTUIT.ru

[18192123]

#include <stdlib.h>
#include <stdio.h>

int p1[]={0x1, 0x1, 0x0, 0x1, 0x0, 0x0, 0x0};
int p2[]={0x1, 0x0, 0x1, 0x1};

int main() {
       int *ptr1=p1;

       int del;
       int i;
       int s1 = sizeof(p1)/sizeof(int);
       int s2 = sizeof(p2)/sizeof(int);
       int *result = (int*)malloc(sizeof(int)*(s1));
       int sresult =0;

       while (1) {

               del = (int)(*ptr1 / *p2);
               result[sresult]=del;
               sresult++;
               for (i=0; i<s2; i++) {
                       *(ptr1+i) ^= del * p2[i]; //вот здесь XOR
               }
               ptr1++;
               s1--;
               if (s1<s2) break;

       }

       printf("Частное: ");
       for (i=0; i<sresult; i++) {
               if (result[i] >= 0 && i != 0) printf(" + ");
               if (sresult-i-1 !=0) {
                       if (sresult-i-1 != 1) {
                               printf(" %d*x^%d ",result[i],sresult-i-1);
                       } else {
                               printf(" %d*x ",result[i]);
                       }
               } else {
                       printf(" %d ",result[i]);
               }
       }

       printf("\n");
       s1=sizeof(p1)/4;
       printf("Остаток: ");
       for (i=0; i<s1; i++) {
               if (p1[i]!=0) {
                       if (p1[i]>0) printf(" + ");
                       if (s1-i-1 !=0) {
                               printf(" %d*x^%d",p1[i],s1-i-1);
                       } else {
                               printf(" %d ",p1[i]);
                       }
               }
       }
       printf("\n");
}

Заменила вычитание на XOR - вроде получается результат, который мне нужен.

Сообщение отредактировано: 18192123 - 29.04.2009 13:43

[volvo]

Ну, так замени в 23-ей строке той программы, что я привел, вычитание на сложение по модулю 2:

               for (i=0; i<s2; i++) {
                       *(ptr1+i) ^= del * p2[i]; // <--- Вот так
               }

и получишь частное = 1*x^3 + 1*x^2 + 1*x + 1, и остаток = + 1