Предположим в качестве входных данных имеется двоичная комбинация, каждый разряд хранится в соответствующем элементе массива (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
29.04.2009 5:07
Чтобы это реализовать, надо сначала правильно сделать это столбиком на бумаге. Ты этого не сделала. Потому что проверяется деление полиномов чем? Угу, именно умножением. Умножаем полученное в твоем примере частное на делитель, и прибавляем остаток. Должны получить делимое:
Нашелся вот такой "делитель полиномов", написанный очень давно, еще под ДОС-овским ТурбоС:
#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"); }
, ответ, который он выдает: частное = (x3+x2-x-1), остаток = (2x+1). Вот если это проверить умножением, то получаем исходное делимое...
18192123
29.04.2009 15:18
Надо было мне сразу уточнять, что требуется несколько иное... Такое "деление полиномов", как в прикреплённом мною документе в посте #1, используется при циклическом кодировании, соответственно, если проверять полученное мною умножением (вместо обычного сложения использовать суммирование по модулю два, т.е. исключающее ИЛИ), то всё сходится: