Ошибка в рекурсивной функции, связанная с использованием "чужой" памяти.

@Morgan1189 · Регистрация: 12.02.2010

Студворк — интернет-сервис помощи студентам

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

Я столкнулся с одной проблемой при реализации некоторой задачи. Мой проект - программа, которая должна показывать все методы прохода шахматного коня по доске N*M, при том, что конь должен побывать на каждой клетке только один раз. Предлагалось реализовать задачу при помощи рекурсивной функции. Программа написана на C.

Программу я написал, и она работает почти для всех досок. Почти... При запуске ее на доске 6*6 она через некоторое время обнуляет глобальную переменную (VAR), отвечающую за кол-во вариантов. Полагаю, что функция "залезает" не в свою память, но уже месяц не могу найти где... Прошу помочь.

Сюда я выложу лишь часть кода, отвечающую за рекурсивную функцию, во вложениях будут все файлы, относящиеся к программе.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
long int VAR=0;
int n = 4, g = 0, l = 0, d = 0, d1=0, num = 0, step = 0, s = 0, RET=-1, TOTAL=0, LENGTH=0;
int *arr;
int brr[16][16];
int dn[8] = {-1,1,2,2,1,-1,-2,-2};
int dm[8] = {2,2,1,-1,-2,-2,-1,1};
int N=6;//кол-во столбцов
int M=6;//кол-во строк
int STARTN=0;//стартовая позиция коня по столбцам
int STARTM=0;//стартовая позиция коня по строкам
char stroka[100];
char stroka1[100];
char number[225];
 
arr = (int *)malloc(sizeof(int) * 100000 * N * M);
for (VAR=0; VAR<100000; VAR++) {
    for (i=0; i<N; i++) {
        for (j=0; j<M; j++) {
            *(arr + N * M * VAR + i * M + j)=-1;
        }
    }
}
VAR=0;
 
for (d=0; d<16; d++) {
    for (d1=0; d1<16; d1++) {
        brr[d][d1]=-1;
    }
}
brr[STARTN][STARTM]=1;
move(brr, 2, STARTN, STARTM);
 
int move(int crr[][16] , int k, int nt0, int mt0)
{
    int z,nt,mt,i,j;
    int * test;
    if (k==M*N+1) {
        if (VAR>=100000) {
            if (VAR%50000==0) {
                test = (int *)realloc(arr, sizeof(int)*(VAR+50000)*N*M);
                if (test==NULL) {
                    MessageBox(NULL, "Не хватило памяти", "Attention", MB_OK);
                    return 10;
                } else {
                    /*_snprintf(stroka1, sizeof(stroka1)-1, "VAR = %d", VAR);
                    MessageBox(NULL, stroka1, "Realloc here", MB_OK);*/ 
                    arr=test;
                }
            }
        }
        /*if (VAR%100000==0) {
            _snprintf(stroka1, sizeof(stroka1)-1, "VAR = %d", VAR);
            MessageBox(NULL, stroka1, "Number of variants", MB_OK);
        }*/
        for (i=0; i<N; i++) {
            for (j=0; j<M; j++) {
                *(arr + N * M * VAR + i * M + j)=crr[i][j];
            }
        }
        if (VAR==0) {
            _snprintf(stroka, sizeof(stroka)-1, "Все опять обнулилось...");
            MessageBox(NULL, stroka, "Attention", MB_OK);
        }
        VAR++;
        return 0;
    }
    for (z=0; z<8; z++) {
        nt=nt0+dn[z];
        if (nt<0 || nt>=N) {
            continue;
        }
        mt=mt0+dm[z];
        if (mt<0 || mt>=M) {
            continue;
        }
        if (crr[nt][mt]==-1) {
            crr[nt][mt]=k;
            if ( move(crr, k+1, nt, mt) == 10 )
                return 10;
            crr[nt][mt]=-1;
        }
    }
    return 0;
}

P.S. Программа написана в Visual Studio 6.0. Во время работы программы debug никаких ошибок не выдает.

@Patch · 24.03.2010, 16:28

закомментируй код нормально.
я в этом алгоритме ничего не понимаю.
кроме того, в приложении код не тот, что выложен.

у меня при VAR>100000 идет вылет с сообщением об ошибке доступа к памяти на строке
*(arr + 16 * 16 * VAR + i * 16 + j)=crr[i][j];

@Morgan1189 · 24.03.2010, 16:46 **[ТС]**

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
long int VAR=0;//кол-во вариантов
int n = 4, g = 0, l = 0, d = 0, d1=0, num = 0, step = 0, s = 0, RET=-1, TOTAL=0, LENGTH=0;
int *arr; //указатель на место в памяти, где хранятся все варианты прохода коня по данной доске
int brr[16][16];//глобальный массив, используемый для передачи его рекурсивной функции
int dn[8] = {-1,1,2,2,1,-1,-2,-2};//массив возможных ходов коня (по столбцам)
int dm[8] = {2,2,1,-1,-2,-2,-1,1};//массив возможных ходов коня (по строкам)
int N=6;//кол-во столбцов
int M=6;//кол-во строк
int STARTN=0;//стартовая позиция коня по столбцам
int STARTM=0;//стартовая позиция коня по строкам
char stroka[100];
char stroka1[100];
char number[225];
 
//Здесь происходит заполнение памяти под варианты прохода коня. при этом -1 означает, что в этой //клетке конь еще не побывал
 
arr = (int *)malloc(sizeof(int) * 100000 * N * M);
for (VAR=0; VAR<100000; VAR++) {
        for (i=0; i<N; i++) {
                for (j=0; j<M; j++) {
                        *(arr + N * M * VAR + i * M + j)=-1;
                }
        }
}
VAR=0;
 
//Здесь глобальный массив заполняется -1, чтобы затем быть переданным рекурсивной функции 
for (d=0; d<16; d++) {
        for (d1=0; d1<16; d1++) {
                brr[d][d1]=-1;
        }
}
brr[STARTN][STARTM]=1;
move(brr, 2, STARTN, STARTM);
 
//Сама рекурсивная функция
//crr[][16] - локальный массив (выполняет функцию доски, по которой ходит конь)
//k - номер хода коня (1,2 и т.п.)
//nt0 - текущая позиция коня по стобцам
//mt0 - текущая позиция коня по строкам
int move(int crr[][16] , int k, int nt0, int mt0)
{
        int z,nt,mt,i,j;
        int * test;
//Блок, при входе в который функция уже заполнила один вариант прохода, и переписывает его из //локального массива в место, на которое указывает arr
        if (k==M*N+1) {
                if (VAR>=100000) {
                        if (VAR%50000==0) {
                                test = (int *)realloc(arr, sizeof(int)*(VAR+50000)*N*M);
                                if (test==NULL) {
                                        MessageBox(NULL, "Не хватило памяти", "Attention", MB_OK);
                                        return 10;
                                } else {
                                        /*_snprintf(stroka1, sizeof(stroka1)-1, "VAR = %d", VAR);
                                        MessageBox(NULL, stroka1, "Realloc here", MB_OK);*/ 
                                        arr=test;
                                }
                        }
                }
                /*if (VAR%100000==0) {
                        _snprintf(stroka1, sizeof(stroka1)-1, "VAR = %d", VAR);
                        MessageBox(NULL, stroka1, "Number of variants", MB_OK);
                }*/
                for (i=0; i<N; i++) {
                        for (j=0; j<M; j++) {
                                *(arr + N * M * VAR + i * M + j)=crr[i][j];
                        }
                }
                if (VAR==0) {
                        _snprintf(stroka, sizeof(stroka)-1, "Все опять обнулилось...");
                        MessageBox(NULL, stroka, "Attention", MB_OK);
                }
                VAR++;
                return 0;
        }
//Цикл, который выполняет попытку постановки коня в какую-либо клетку
        for (z=0; z<8; z++) {
                nt=nt0+dn[z];
                if (nt<0 || nt>=N) {
                        continue;
                }
                mt=mt0+dm[z];
                if (mt<0 || mt>=M) {
                        continue;
                }
                if (crr[nt][mt]==-1) {
                        crr[nt][mt]=k;
                        if ( move(crr, k+1, nt, mt) == 10 )
                                return 10;
                        crr[nt][mt]=-1;
                }
        }
        return 0;
}

Так лучше? Что еще непонятно в коде, я объясню.

@Patch · 24.03.2010, 18:42

Сообщение от Morgan1189

Так лучше?

не очень.
в этом коде НЕТ строки, которая вызывает ошибку доступа к памяти.
а в приложенном проекте на MSVS 6.0 она ЕСТЬ.

а вообще - код немного индусский...

какие-то странные выделения памяти с фантастической размерностью...

вот смотри, я прикинул, как это должно выглядеть:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//инициализация
//при первом запуске массив полей заполнен 0,
//cStep = 1 - номер хода
//Vars = 0 - счетчик найденных вариантов
//алгоритм:
//перебор всех полей, слева направо и сверху вниз
//незаполненным считается поле, у которого записанный номер хода больше текущего
//для каждого незаполненного поля проверяется соответствие на "ход коня" - можно ли с него попасть в текущую
//если возможно - проверяется, не равен ли номер текущего хода максимальному(длина*ширина поля)
//если равен - значит найден еще один вариант прохода коня, счетчик вариантов увеличивается, массив полей копируется.
//если не равен - текущее поле заполняется текущим номером хода, и рекурсивно вызывается функция new_move, c cStep+=1
void new_move(int cxPos, int cyPos, int cStep)
{
    int xPos, yPos; 
    for(xPos = 0; xPos < N; xPos++)                 //перебор колонок
        for(yPos = 0; yPos < M; yPos++)             //перебор строк
            if(*(lpCell+yPos*N+xPos) < cStep)           //если поле не заполнено
            {
                if(checkpos(cxPos, cyPos, xPos, yPos))  //проверяем, можно ли с этого поля попасть в текущее
                {
                    if(cStep == N*M-1)          //если номер хода уже максимальный - вариант найден
                    {
                        Vars++;             //увеличиваем счетчик найденных вариантов
                        CopyVar();          //копируем найденный вариант
                        return;             //и выходим из функции
                    }
                    *(lpCell+yPos*N+xPos) = cStep;  //иначе  - пишем номер хода в текущую клетку и вызываем функцию
                    new_move(xPos, yPos, cStep+1);
                }
 
            }
}
 
//возвращает 1, если из позиции cxPos, cyPos можно ходом коня попасть в позицию xPos, yPos
bool checkpos(cxPos, cyPos, xPos, yPos)
{
    if(abs(cxPos - xPos) == 1)
        if(abs(cyPos-yPos) == 2)
            return 1;
    if(abs(cxPos - xPos) == 2)
        if(abs(cyPos-yPos) == 1)
            return 1;
    return 0;
}

а для хранения найденных вариантов лучше использовать список.

итого, комментариев получилось едва ли не больше, чем кода.

@Morgan1189 · 24.03.2010, 19:21 **[ТС]**

Спасибо.

А по поводу моего кода можете сказать, чем может быть вызвана ошибка, или там все-таки сам черт ногу сломит?

+ я не знаю, что такое список, и как с ним работать... Можете показать реализацию через malloc-realloc (просто я не совсем уверен, что все делаю верно)?

@Patch · 24.03.2010, 19:31

еще раз покурил твой код.

у тебя основной массив - на 100000 досок:

C
1
arr = (int *)malloc(sizeof(int) * 100000 * N * M);

а проверка превышения этого размера идет, только если текущий ход = максимальный:

C
1
2
3
        if (k==M*N+1) {
                if (VAR>=100000) {
                        if (VAR%50000==0) {

а кто сказал, что 100000 досок кончатся именно тогда, когда k==M*N+1 ?
вот и вылазит обращение к данным за пределы этого массива.

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

@Morgan1189 · 24.03.2010, 19:43 **[ТС]**

Ну там вроде как k==M*N+1 - это и есть индикатор того, что доска полностью забита. То есть у нас 36 клеток и последний экземпляр функции захочет найти место, куда можно будет сделать 37 ход. Ну вот тут и ставится ограничение, что, мол, пора бы место в памяти расширять и тому подобное.

Я чего-то недопонимаю?

@Patch · 25.03.2010, 10:14

Сообщение от Morgan1189

Я чего-то недопонимаю?

я тоже в этом коде много чего недопонимаю.

извини, у меня завал, со списками сам разбирайся, если все-же понадобятся.

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

я вынес функцию копирования доски, изменил выделение памяти под размер N*M, вместо 16*16, и убрал копирование текущей доски в стек при каждом вызове move().
и еще немного по мелочи.
сам посмотришь...
делал логи - все нормально посчиталось.
возможно, ты просто забивал весь стек этими досками.

у процесса по-умолчанию всего 2Mb памяти на стек выделено, а у тебя получалось... примерно 1MB только досок в стеке, при размере массива 16*16 и NM = 8.
а еще там должны быть и другие локальные переменные, адреса функций и т.д.

@Morgan1189 · 25.03.2010, 14:03 **[ТС]**

Блин, только сейчас обнаружил, что сюда залил старую версию, самую баговую. Сорри.

Спасибо большое, сейчас потестю.

Добавлено через 1 час 59 минут
Patch, не знаю, как и благодарить, все работает, спасибо тебе огромное за потраченное время!

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Patch 2343 / 499 / 22 Регистрация: 01.04.2009 Сообщений: 2,200
	24.03.2010, 16:28
	закомментируй код нормально. я в этом алгоритме ничего не понимаю. кроме того, в приложении код не тот, что выложен. у меня при VAR>100000 идет вылет с сообщением об ошибке доступа к памяти на строке (arr + 16 16 * VAR + i * 16 + j)=crr[i][j]; 0

@Morgan1189 0 / 0 / 0 Регистрация: 12.02.2010 Сообщений: 5
	24.03.2010, 19:21 [ТС]
	Спасибо. А по поводу моего кода можете сказать, чем может быть вызвана ошибка, или там все-таки сам черт ногу сломит? + я не знаю, что такое список, и как с ним работать... Можете показать реализацию через malloc-realloc (просто я не совсем уверен, что все делаю верно)? 0

@Morgan1189 0 / 0 / 0 Регистрация: 12.02.2010 Сообщений: 5
	24.03.2010, 19:43 [ТС]
	Ну там вроде как k==M*N+1 - это и есть индикатор того, что доска полностью забита. То есть у нас 36 клеток и последний экземпляр функции захочет найти место, куда можно будет сделать 37 ход. Ну вот тут и ставится ограничение, что, мол, пора бы место в памяти расширять и тому подобное. Я чего-то недопонимаю? 0

@Morgan1189 0 / 0 / 0 Регистрация: 12.02.2010 Сообщений: 5
	25.03.2010, 14:03 [ТС]
	Блин, только сейчас обнаружил, что сюда залил старую версию, самую баговую. Сорри. Спасибо большое, сейчас потестю. Добавлено через 1 час 59 минут Patch, не знаю, как и благодарить, все работает, спасибо тебе огромное за потраченное время! 0