было думал подствпомнить Си ну и начал с простеньких задачек. задачка значит: найти n-ое число фибоначчи за log(n). Суть алгоритма не важна. Реализация специально раздутая для того чтобы непосредственно вспомнить как оно работает. Я было думал написать эту простенькую программку, потом создать тему а попросить чтобы мне указали что где я делаю неправильно и как сделать лучьше, но... Начинался третий день, моя самооценка валяется под столом, руки опущены ниже пола, мечты о работе программистом разбиты в прах. Вот код Code: #include <stdio.h> #include <stdlib.h> struct sDimension { int rows; int columns; }; int matrixPow(int**, const int**, const struct sDimension*, const int); int matrixMulti(int**, const struct sDimension*, const int**, const struct sDimension*, const int**, const struct sDimension*); int matrixCopy(const int**, const struct sDimension*, int**, const struct sDimension*); int** matrixMalloc(const struct sDimension*); void matrixFree(int**, const struct sDimension*); void matrixDisplay(const int**, const struct sDimension*); int fibN(int); int main() { int n = 4; // n-ое число Фибоначчи printf("F%d = %d", n, fibN(n)); return 0; } int fibN(int n) { const struct sDimension dimC = {1, 2}; const struct sDimension dimP = {2, 2}; int **P = matrixMalloc(&dimP); P[0][0] = 0; P[0][1] = 1; P[1][0] = 1; P[1][1] = 1; int **Ppow = matrixMalloc(&dimP); // matrixFree(Ppow, &dimP); matrixPow(Ppow, P, &dimP, n); int **C = matrixMalloc(&dimC); C[0][0] = 0; C[0][1] = 1; int **Fn = matrixMalloc(&dimC); matrixPow(Ppow, P, &dimP, n); //matrixDisplay(Ppow, &dimP); matrixMulti(Fn, &dimC, C, &dimC, Ppow, &dimP); //matrixDisplay(Fn, &dimC); int fib = Fn[0][0]; printf("2---\n"); matrixFree(Ppow, &dimP); matrixFree(Fn, &dimC); matrixFree(C, &dimC); matrixFree(P, &dimP); return fib; } int matrixPow(int **Ppow, const int **P, const struct sDimension *dimP, const int _pow) /* C[m][n] = A[m][n] ^ pow error status: 0 - good 1 - pow < 0; 2 - not a square matrix */ { if(_pow < 0) return 1; if(dimP->columns != dimP->rows) return 2; int pow = _pow; //Ppow = matrixMalloc(dimP); matrixCopy(P, dimP, Ppow, dimP); --pow; int **temp = matrixMalloc(dimP); int **localP = matrixMalloc(dimP); matrixCopy(P, dimP, localP, dimP); while(pow) { if(pow&1) { matrixMulti(temp, dimP, Ppow, dimP, localP, dimP); matrixCopy(temp, dimP, Ppow, dimP); --pow; } else { matrixMulti(temp, dimP, localP, dimP, localP, dimP); matrixCopy(temp, dimP, localP, dimP); pow>>=1; } } matrixFree(localP, dimP); matrixFree(temp, dimP); return 0; } int matrixMulti(int **C, const struct sDimension* dimC, const int **A, const struct sDimension* dimA, const int **B, const struct sDimension* dimB) { /* A[m][n] * B[p][q] = C[m][q] error status: 0 - good 1 - matrix's is not co-ordinated */ int Am = dimA->columns, Bq = dimB->rows; if(Am != Bq || dimC->rows != dimA->rows || dimC->columns != dimB->columns) return 1; int i, j, r; for(i=0; i<Am; i++) { for(j=0; j<Bq; j++) { C[i][j]=0; for(r=0; r<Am; r++) C[i][j] += A[i][r]*B[r][j]; } } return 0; } int matrixCopy(const int **from, const struct sDimension *dimFrom, int **to, const struct sDimension *dimTo) /* copy from -> to error status: 0 - good copy 1 - dimensions do not match (размерности не совпадают) */ { if ((*dimFrom).columns != (*dimTo).columns || (*dimFrom).rows != (*dimTo).rows) return 1; int i, j; for(i = 0; i < dimTo->rows; i++) for(j = 0; j < dimTo->columns; j++){ to[i][j] = from[i][j]; //printf("IJ = %d:%d\n", i, j); } return 0; } int** matrixMalloc(const struct sDimension *dim) { //printf("%d:%d\n", dim->rows, dim->columns); int** matrix = (int**)malloc(dim->rows * sizeof(int*)); int i; for(i=0; i<(*dim).rows; i++) matrix[i] = (int*)malloc((*dim).columns * sizeof(int)); return matrix; } void matrixFree(int** matrix, const struct sDimension* dim) { int i; printf("matrixFree rows = %d\n", dim->rows); for(i=dim->rows - 1; i>=0; i--) { //printf("[%d]\n", i); //matrixDisplay(matrix, dim); free(matrix[i]); } free(matrix); } void matrixDisplay(const int **matrix, const struct sDimension* dim) { int i,j; //printf("matrixDisplay [%d:%d]\n", dim->rows, dim->columns); for(i=0; i<dim->rows; i++) { for(j=0; j<dim->columns; j++) { printf("%d \t", matrix[i][j]); } printf("\n"); } //printf("end matrixDisplay\n"); } проблемма которую я не могу понять в вызове деструкторов в них на функции free() обламывается работа. при это если вызвать эту функции деструторы вот тут Code: int **Ppow = matrixMalloc(&dimP); matrixFree(Ppow, &dimP); matrixPow(Ppow, P, &dimP, n); т.е. после создание но перед вызовом любой из функций в которых изменяется значения массива, то все РАБОТАЕТ. Я догадываюсь что я тупо не знаю какихто основ Си, но понять каких я не могу. Подскажите в чем может быть проблема ? PS. ну и по коду если есть какие замечание высказывайте, нужно больше мнений со стороны (только не по поводу высосаности кода из пальца)
пздц, ниодного комментария... без них разбираться не буду, но крах free() означает, что при использовании памяти, выделенной malloc(), ты вылазишь за ее пределы. Ставим breakpoint, F5 и ползи по коду на пузе.
да какие комменты, код же банален. Ползал брюхом, не в дебагере а с помощью printf, тоже думал что где то удаляю что то не то, но вставлял распечатку массива перед напосредственно free(), оно сцуко все есть. Притом он два раза отрабатывает нормально для второстепенных массивово в matrixPow, а вот при вызове для Ppow все блин аналогично но сразу же на удалении последней строчки (начинаю с конца) на free падает. Хотя точно таки еже (тоже размерности) второстепенные массивы нормально удаляет.
Просто для интереса провел его через gcc, и результат вот такой : Code: test.c: In function ‘fibN’: test.c:36: warning: passing argument 2 of ‘matrixPow’ from incompatible pointer type test.c:10: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:41: warning: passing argument 2 of ‘matrixPow’ from incompatible pointer type test.c:10: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:43: warning: passing argument 3 of ‘matrixMulti’ from incompatible pointer type test.c:11: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:43: warning: passing argument 5 of ‘matrixMulti’ from incompatible pointer type test.c:11: note: expected ‘const int **’ but argument is of type ‘int **’ test.c: In function ‘matrixPow’: test.c:82: warning: passing argument 3 of ‘matrixMulti’ from incompatible pointer type test.c:11: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:82: warning: passing argument 5 of ‘matrixMulti’ from incompatible pointer type test.c:11: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:83: warning: passing argument 1 of ‘matrixCopy’ from incompatible pointer type test.c:14: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:88: warning: passing argument 3 of ‘matrixMulti’ from incompatible pointer type test.c:11: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:88: warning: passing argument 5 of ‘matrixMulti’ from incompatible pointer type test.c:11: note: expected ‘const int **’ but argument is of type ‘int **’ test.c:89: warning: passing argument 1 of ‘matrixCopy’ from incompatible pointer type test.c:14: note: expected ‘const int **’ but argument is of type ‘int **’ короче, гиморой с указателями у тебя мужик, мне пока лень копаться в нем
внутри вызова ф-ции matrixMulti(Fn, &dimC, C, &dimC, (const int **)Ppow, &dimP); срабатывает такой код PHP: for(i=0; i<Am; i++) { for(j=0; j<Bq; j++) { C[i][j]=0; for(r=0; r<Am; r++) C[i][j] += A[i][r]*B[r][j]; } } На втором круге, когда j=1 тут C[j]=0; ошибка чтото с памятью
однако вы правы, ошибка не там где я предпологал. P.S. как всегда, потрачена куча сил и время но поиск ошибки не там где нужно. ошибка глупая была, не по тем индексам пробегал матрицы при умножении вот так верно Code: int matrixMulti(int **C, const struct sDimension* dimC, const int **A, const struct sDimension* dimA, const int **B, const struct sDimension* dimB) { /* A[m][n] * B[p][q] = C[m][q] error status: 0 - good 1 - matrix's is not co-ordinated */ int Am = dimA->columns, Bq = dimB->rows; if(Am != Bq || dimC->rows != dimA->rows || dimC->columns != dimB->columns) return 1; int i, j, r; for(i=0; i<dimA->rows; i++) { for(j=0; j<dimB->columns; j++) { C[i][j]=0; for(r=0; r<Am; r++) C[i][j] += A[i][r]*B[r][j]; } } return 0; } PPS. и чтоб совсем все правильно было вместо Code: int pow = _pow; нужно Code: int pow = _pow - 1;
