Некорректная работа программы при формировании массива

[@Manya@]

Здравствуйте!
Имеется массив p_Q_v[q*(deg-1)+1][deg]. Он заполнен какими-то данными до строки deg-1 включительно. Нужно найти след строки по следующему правилу:
Например:
известная часть массива p_Q_v
1 2 3
1 2 1
1 4 1 <- (deg-1)
к примеру, массив p_cut[deg-1] имеет вид {1, 2, 3}
тогда строка deg в искомом массиве p_Q_v будет иметь вид :
1*1+1*2+3*1 = 6 <- 1 элемент
2*1+2*2+4*3 <- 2 элемент
3*1+2*1+1*3 <- 3 элемент
строка deg+1 будет получена тем же способом, но уже в качестве первой строки будет взята не 1 2 3, а 1 2 1, а в качестве последней - полученная на предыдущем шаге.

 
for (a = deg; a < q*(deg-1)+1; a++)
        {
                for (j = 0; j < deg; j++)
                {
                        sum = 0;
                        for (k = 0; k < deg-1; k++)
                        {
                                sum += this->p_Q_v[a-k-1][j]*this->p_cut[k];
                        }
                        this->p_Q_v[a][j] = sum;
                }
        }

работает некорректно, начиная с определенной строки, исправить не получается(

[silent_1991]

Т.е. он считает некоторое количество строк правильно, и вдруг с какой-то определённо начинает работать неверно? Если так, то надо посмотреть весь код, т.к. описанный алгоритм простой и вроде реализован правильно, скорее всего проблемы в другом месте.

[@Manya@]

Спасибо, что помогаете)
Это, собственно говоря, не реализованный пока алгоритм Берлекэмпа по разложению многочленов над полями GF(q), где q=2 или q=3

#define SIZE 10
#include <stdio.h>
#include <stdlib.h>
class Vector{
private :
	int *p;// сам по себе многочлен
	int deg;// степень многочлена
	int *p_cut;// тот же p, только без старшего коэффициента
	int **p_Q_v;// матрица, которая формируется указанными действиями + еще кое-чем, что описано в методе класса make_Q
	int **p_Q;// то, что получается из p_Q_v, копированием каждой q-ой строки
public :
	Vector(int s);
	void in(); // ввод
	~Vector();
	void print(); // печать многочлена p
	void print_cut(); // вывод на экран p_cut
	friend int check( Vector );// проверка, не равна ли 0 степень p
	int get_deg(); // получение степени многочлена p
	void print_Q(); // печать p_Q
	void make_Q(int ); // формирование p_Q
	void Core(); // алгоритм ядра, пока еще не реализованный
};
int input(); //еще 1 ввод

void main(){
	printf("Input degree -> ");
	int deg = input();
	Vector a(deg);
	a.in();
	a.make_Q(2); 
	a.print_Q();
}
Vector :: Vector(int s){
	deg = s;
	p = new int [deg+1];
}
void Vector :: in(){
	for (int i = 0; i<= deg; i++){
		printf("Input the coefficient before %d -> ", i);
		p [i] = input();
	}
	p_cut = new int [deg];
	for (int i = 0; i < deg; i++)
		p_cut [i] = p [i];
}
Vector :: ~Vector(){
	if (p != 0){
		delete [] p;
	}
	if (p_cut !=0)
		delete [] p_cut;
}
void Vector :: print(){
	printf("The vector is -> ");
	for (int i = 0; i <= this->deg; i++){
		printf("%d ", this->p [i]);
	}
}
void Vector :: print_cut(){
	printf("The cut_vector is -> ");
	for (int i = 0; i < this->deg; i++){
		printf("%d ", this->p_cut [i]);
	}
}
int check( Vector a ){
	if ( a.deg == 0)
		return 0;
	else
		return 1;
}
int Vector ::get_deg(){
	int d = this->deg;
	return d;
}
void Vector :: print_Q(){
	int deg = get_deg();
	for (int i = 0; i < deg; i++){
		for(int j=0; j < deg; j++)
			printf("%d ",this->p_Q[i][j]);
		printf("\n");
	}
}
void Vector :: make_Q(int q){
	int i, j, sum, l, c, k, a;
	i=j=sum=0;
	a=0;
	int deg = get_deg();
	this->p_Q_v = new int * [q*(deg-1)+1];// выделяем память
	for (int k=0; k<q*(deg-1)+1; k++)
		this->p_Q_v[k] = new int [deg];
	this->p_Q = new int * [deg]; 
	for (int k=0; k<deg; k++)
		this->p_Q[k]=new int [deg];// выделяем память
	for (i=0; i<=q*(deg-1); i++){ // заполняем нулями p_Q_v на всякий пожарный
		for (j=0; j<deg; j++)
			this->p_Q_v[i][j]=0;
	}
	for (i=0; i<deg; i++){ // создаем у p_Q_v часть, которая будет единичной матрицей
		for (j=0; j<deg; j++){
			if (i==j)
				this->p_Q_v[i][j]=1;
		}
	}
	for (a = deg; a < q*(deg-1)+1; a++)// начало глючного куска
	{
		for (j = 0; j < deg; j++)
		{
			sum = 0;
			for (k = 0; k < deg-1; k++)
			{
				sum += this->p_Q_v[a-k-1][j]*this->p_cut[k];
			}
			this->p_Q_v[a][j] = sum %q;
		}
	}// конец глючного куска
	for (c=0, l=0; (c<deg)&&( l<=q*(deg-1)); c++, l+=q){ // матрица p_Q получена копированием q-ой строки p_Q_v
		for (j=0; j<deg; j++)
		{
			this->p_Q[c][j]=this->p_Q_v[l][j];
		}
	}
	if (q==2){ // приведение коэффициентов p_Q над полем GF(2) или GF(3), зависит от q
	for (i=0; i<deg; i++)
		for (j=0; j<deg; j++)
			if (i==j){
				this->p_Q[i][j]+=(-1);
				this->p_Q[i][j]=abs(this->p_Q[i][j]);
			}
	}
	if (q==3){
		for (i=0; i<deg; i++)
			for (j=0; j<deg; j++)
				if (i==j)
					this->p_Q[i][j]+=(-1);
		for(i=0; i<deg; i++)
			for (j=0; j<deg; j++){
				if (this->p_Q[i][j]==-1)
					this->p_Q[i][j]=2;
				if (this->p_Q[i][j]==-2)
					this->p_Q[i][j]=1;
			}
	}
}
void Vector :: Core(){// нечто, пока еще не дописанное и не влияющее пока ни на что
	int * c = new int [deg];
	int i, j, r, k;
	for (i=0; i<deg; i++)
		c[i]=-1;
	r=0;
	for (k=0; k<deg; k++){
		for (j=0; j<deg; j++){

		}
	}
}
int input(){// ввод
	int m[SIZE];
	int c;
	int i = 0;
	int j = 0;
	int d,k,t,z = 0;
	do{
		c = getchar();
		if(c != '.' && c != ' ' && c != '\n' && c != '-'){
			m[i] = c;
			i ++;
		}
		else if(c == '-')
			z = 1;
		else{
			d = 0;
			t = 1;
			for(k = j+1; k <= i-1;t = t*10, k++);
			for(k = j;k <= i-1; k++){
				d+=(m[k]-48)*t;
				t/=10;
			}
			m[j]=d;
			if (z==1)
				m[j]=-m[j];
			i=++j;
		}
	}
	while(c!='\n' && c!=' ' && c!='.');
	return m[0];
}

[@Manya@]

сам по себе алгоритм вообще не важен, зачатки моего кода реализовывают его по логике правильно, а возможное место глюка помечено соответствующими комментариями

[silent_1991]

Хм... А при каких входных данных наблюдаются глюки? И с какой строки начинаются? И если ввести идентичные входные данные, начиная с той же самой строки появляются глюки? И вообще, в чём они проявляются?

[@Manya@]

Матрица p_Q всегда формируется неверно, это как раз скорее всего из-за того места, которое обозвано глючным куском)) Это в методе make_Q, там комментарий соответствующий у начала этой строки. Ошибок нет, вылетов тоже. Это скорее всего не глюк, а не корректная работа вот сего:

for (a = deg; a < q*(deg-1)+1; a++)// начало глючного куска
	{
		for (j = 0; j < deg; j++)
		{
			sum = 0;
			for (k = 0; k < deg-1; k++)
			{
				sum += this->p_Q_v[a-k-1][j]*this->p_cut[k];
			}
			this->p_Q_v[a][j] = sum %q;
		}
	}// конец глючного куска

При любом введенном многочлене матрица p_Q всегда неверна из-за того, что неверна p_Q_v, а она в свою очередь такая из-за куска кода, приведенного выше, который и послужил причиной моего самого первого сообщения))
Ну вот, например, если ввести многочлен 12 степени 1010001110001, то матрица p_Q должна иметь вид , а она такая . Это происходит как раз из-за того куска, который обозван "глючным" в комментариях. В нем по идее должно все строиться так, как написано в 1 сообщении, но еще добавлено приведение по модулю q

[silent_1991]

Если я правильно понял условие, то q - длина строки в матрице p_Q_v (а также длина вектора p_cut), deg - номер искомой строки (которую надо вычислить). Тогда, мне кажется, правильный алгоритм такой:

for (i = 0; i < q; i++)
    {
        sum = 0;
        
        for (j = deg - q - 1, k = 0; j < deg - 1; j++, k++)
        {
            sum += Q[j][i] * p[k];
        }

        Q[deg][i] = sum;
    }

Т.е. счётчик i пробегает по столбцам (на каждой итерации внешнего цикла вычисляется один (а именно - i-й) элемент строки с номером deg матрицы Q). Счётчик j пробегает по каждому элементу столбца, а счётчик k - по соответствующему элементу вектора p.
Почему то у меня нехорошее чувство, что я недопонял условие)))

[@Manya@]

Не))
q - это просто некоторая константа, которая может быть равна 2 или 3. Она тут в принципе вот в этой части кода большой роли не играет. Длина строки p_Q_v есть deg, длина вектора p_cut есть deg-1. А сам p_Q_v[q*(deg-1)+1][deg].
Ну а deg и правда номер искомой строки, но только на самом первом шаге, потом-то он увеличится на одЫн

[silent_1991]

А сколько изначально известно строк из матрицы p_Q_v? Тоже deg - 1?

[@Manya@]

Ага. Точно так