-4
Моя программа отлично работает, когда я использую массив элементов 81, но когда я общаюсь с массивом из 256 блоков, он падает, и я не знаю, почему он это делает. Я представляю вам весь исходный код и текст ввода, который вы можете использовать в TXT-файле с последним возвратом каретки.Почему моя программа падает с переполнением стека?
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <windows.h>
#include <malloc.h>
int grille[256];
int domaine[256][17]; /* indique les valeurs possib pour case donnee */
int domaine_taille[256]; /* nombre de valeurs possibles une case donnee */
int compteur_noeuds;
void restreindre_domaines(int);
int backtrack(int imite_limite_par_ton_nez);
#define PERR(bSuccess, api) \
{if (!(bSuccess)) perr(__FILE__, __LINE__,api, GetLastError());}
#define INCONNU -1
void lire_grille()
{
int k = 0;
while (k < 256) {
char c = getchar();
if (c >= '0' && c <= '9') //0 a 9
grille[k++] = c-48;
if(c >= 'a' && c <= 'f') // a a f
grille[k++] = c-87;
if (c == '.' || c == ' ' || c== '+') // espace + ou .
grille[k++] = INCONNU;
if (c == EOF)
{
fprintf(stderr, "Lecture de la grille : mauvais format\n");
exit(1);
} }}
void afficher_grille() /* afficher la grille courante sur stdout */
{
int c, l;
for (l = 0; l < 16; l++) {
for (c = 0; c < 16; c++) {
int k = l*16+c;
if (grille[k] == INCONNU) printf(".");
if (grille[k] >= 0 && grille[k] <= 9) //0 a 9
printf("%c", grille[k]+48);
if(grille[k] >= 10 && grille[k] <= 15) // a a f
printf("%c", grille[k]+87);
}
printf("\n");
}
printf("\n");
}
void init_domaines() /* en fonction grille,initialiser domaines */
{
int i, v;
for (i = 0; i < 256; i++)
{
domaine_taille[i] = 16;
for (v = 0; v <= 16; v++)
domaine[i][v] = 1;
}
for (i = 0; i < 256; i++) /* restreindre domaines cases remplies */
if (grille[i] != INCONNU) restreindre_domaines(i);
}
/*oter valeurs des domaines incompatibles avec valeur case i */
void restreindre_domaines(int i)
{
int l = i/16; //ligne
int c = i % 16; //colonne
int lb = l/4; //
int cb = c/4; //
int l2, c2, lr2, cr2, i2;
/* contraintes de la colonne contenant la case i */
for (l2 = 0; l2 < 16; l2++) {
i2 = l2*16+c;
if (domaine[i2][grille[i]]!=0) {
domaine[i2][grille[i]] = 0;
domaine_taille[i2]--;
}
}
/* contraintes de la ligne contenant la case i */
for (c2 = 0; c2 < 16; c2++) {
i2 = l*16+c2;
if (domaine[i2][grille[i]]) {
domaine[i2][grille[i]] = 0;
domaine_taille[i2]--;
}
}
/* verifier la region contenant la case i */
for (lr2 = 0; lr2 < 4; lr2++)
for (cr2 = 0; cr2 < 4; cr2++) {
i2 = (lb*4+lr2)*16+(cb*4+cr2);
if (domaine[i2][grille[i]]) {
domaine[i2][grille[i]] = 0;
domaine_taille[i2]--;
}}}
int main()
{
lire_grille();
afficher_grille();
init_domaines();
backtrack(0);
printf("%d noeuds cherches\n", compteur_noeuds);
printf(" \n");
_getch();
return 0;
}
int backtrack(int uz)
{
if (uz==-99) return(uz);
int i, i_min = -1,aa=0;
int taille_min = 17;
int domaine2[256][17];
int domaine_taille2[256];
static int toc,Toc;
int iz,zzz=0;
toc++;
static int xu;
xu=true;
int lnum[16];
lnum[0]=0;
lnum[1]=15;
lnum[2]=14;
lnum[3]=13;
lnum[4]=12;
lnum[5]=11;
lnum[6]=4;
lnum[7]=3;
lnum[8]=2;
lnum[9]=1;
lnum[10]=5;
lnum[11]=10;
lnum[12]=9;
lnum[13]=8;
lnum[14]=7;
lnum[15]=6;
int tst=0;
for (iz = 0; iz < 256; iz++)
{
if (grille[iz] != INCONNU)tst++;
}
if(tst==256)
{ /*fin:*/
// printf("\n%d 2 valeur tst\n", tst);
afficher_grille();
xu=0;
return xu;
}
/* chercher la case avec le domaine le plus petit */
for (i = 0; i < 256; i++)
{
if (grille[i] == INCONNU && domaine_taille[i] < taille_min)
{
i_min = i;
taille_min = domaine_taille[i];
//printf("i %d *do_tail[i] %d *tail_min %d \n",i,domaine_taille[i],taille_min);
}
if(toc >10000)
{
toc=0;
afficher_grille();
printf("\n%d noeuds cherches\n", compteur_noeuds);
printf(" toc %d et Toc %d \n",toc,Toc);
Toc++;
printf("-------------------------------------------\n");
}
}
compteur_noeuds++;
// for (grille[i_min] = lnum[aa]; grille[i_min] <= lnum[aa+15]; grille[i_min]++,aa++)
for (grille[i_min] = 0; grille[i_min] <= 15; grille[i_min]++,aa++)
{
if (domaine[i_min][grille[i_min]] == 0)
continue;
/* on sauvegarde l'etat courant de domaine
et domaine_taille pour les retablir apres l'appel recursif */
memcpy (domaine2, domaine, sizeof(domaine));
memcpy (domaine_taille2, domaine_taille, sizeof(domaine_taille));
restreindre_domaines(i_min);
backtrack(uz);
if (xu==0)return xu;
memcpy (domaine, domaine2, sizeof(domaine));
memcpy (domaine_taille, domaine_taille2, sizeof(domaine_taille));
}
grille[i_min] = INCONNU;
return 0;
}
Vademecum: prog.exe < inp.txt
вот inp.txt текст с хорошим форматом (16х16 1-F количество и для случая поиска.)
.ae692...0..5.8d
5....4.12.37.bc6
..f.....5......4
.b.8e5f..9.d..01
.42b.17.3.......
.3.52....bf0...c
.......a.1..042b
....4.cb8...1..a
....f.4eb...3..8
.......5.3..acef
.7.2d....51f...9
.e3c.ab.0.......
.0.a58e..7.1..63
..1.....d......2
4....d.26.59.eb0
.6b7c9...4..d.15
Итак, если вы можете мне помочь.
Рекомендовать это: http://stackoverflow.com/help/how-to-ask и этот http://stackoverflow.com/help/mcve. Также рекомендуем попробовать отладить. Еще хуже, что в вашей программе есть некоторые ОС. Если вы хотите, чтобы люди помогали вам, обязательно укажите минимальный код, который воспроизводит ваши ошибки. И имена переменных должны быть на английском, а не на французском;) – LBes
[Как отлаживать небольшие программы] (http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) –
'backtrack' требует приблизительно 20 КБ стека * за рекурсивный вызов *. Для меня не очевидно, насколько глубока рекурсия, но если вы работаете в Windows (как подсказывает ваш код), вы получаете только 2 МБ стека, и этого достаточно только для глубины рекурсии 100 или около того. Подумайте об использовании 'unsigned short' или, возможно, даже' unsigned char', если все необходимые значения будут соответствовать всем массивам. Если это не достаточно хорошо, вам придется избавиться от рекурсии и/или переключиться на кучу выделенных массивов царапин. – zwol