Witam.
Bazuje na kodzie i podpowiedziach użytkownika Crizz z tego tematu: 168448.htm
Ukryta treść:
Kod:
bool konik(int **T, int i, int j, int N, int pole)
{
T[j]=pole;
if(pole==N*N) return true;
if(T[i-2][j-1]==0 AND konik(T,i-2,j-1,int N, pole+1)) return true;
if(T[i-2][j+1]==0 AND konik(T,i-2,j+1,int N, pole+1)) return true;
if(T[i+2][j-1]==0 AND konik(T,i+2,j-1,int N, pole+1)) return true;
if(T[i+2][j+1]==0 AND konik(T,i+2,j+1,int N, pole+1)) return true;
if(T[i+1][j-2]==0 AND konik(T,i+1,j-2,int N, pole+1)) return true;
if(T[i+1][j+2]==0 AND konik(T,i+1,j+2,int N, pole+1)) return true;
if(T[i-1][j+2]==0 AND konik(T,i-1,j+2,int N, pole+1)) return true;
if(T[i-1][j-2]==0 AND konik(T,i-1,j-2,int N, pole+1)) return true;
T[k]=0;
return false;
}
To, co widzisz powyżej, to pseudokod, trzeba go minimalnie zmodyfikować, żeby otrzymać kod napisany w C.
Powyższa funkcja sprawdza, czy istnieje taka sekwencja ruchów konika szachowego dla szachownicy NxN, w której konik startuje z pola odpowiadającego elementowi tablicy T[j].
Jako argument należy przekazać funkcji tablicę T (N+4)x(N+4), w której pierwsze dwa i ostatnie dwa rzędy, oraz pierwsze dwie i ostatnie dwie kolumny, wypełnione są wartością -1, a pozostałe pola tablicy wypełnione są zerami (minus jedynki to pola kontrolne, służą do tego, żeby konik nie wyskoczył poza zakres tablicy).
Funkcja konik w przypadku, kiedy prawidłowa sekwencja zostanie znaleziona, nie tylko zwraca wartość true, ale pozostawia tablicę T wypełnioną liczbami całkowitymi, które wyznaczają kolejne pola, na które powinien skoczyć konik (jeśli wywoła się ją dla N=8, tablica zostanie wypełniona liczbami 1,2,3,...,64).
Musisz jeszcze napisać drugą funkcję, która:
*dostaje jako argument tablicę T (12x12)
*wypełnia odpowiednie pola minus jedynkami oraz zerami
*dla (w jakiś sposób) kolejnych "ważnych" par i,j (tzn. 2 le i,j le 9) będzie sprawdzała, czy funkcja konik(T,i,j,8,1) zwraca prawdę (jeśli zwróci prawdę, to twoja funkcja też ma zwrócić prawdę i zakończyć się; zastanów się, którą część spośród "ważnych" pól tablicy trzeba sprawdzić, dla niektórych pól sytuacja jest symetryczna - podpowiedź: którą jedną czwartą)
Mam nadzieję, ze pomogłem, w razie wątpliwości pytaj
skleiłem coś takiego (funkcja wypelniacz jest rozpisana dalej i działa poprawnie);
#include<stdio.h>
int konik(int (T)[][12], int i, int j, int N, int pole)
{
printf("A");
T[i][j]=pole;
if(pole==N*N) return 1;
if(T[i-2][j-1]==0 && konik(T,i-2,j-1, N, pole+1)){ return 1;}
if(T[i-2][j+1]==0 && konik(T,i-2,j+1, N, pole+1)){ return 1;}
if(T[i+2][j-1]==0 && konik(T,i+2,j-1, N, pole+1)){ return 1;}
if(T[i+2][j+1]==0 && konik(T,i+2,j+1, N, pole+1)){ return 1;}
if(T[i+1][j-2]==0 && konik(T,i+1,j-2, N, pole+1)){ return 1;}
if(T[i+1][j+2]==0 && konik(T,i+1,j+2, N, pole+1)){ return 1;}
if(T[i-1][j+2]==0 && konik(T,i-1,j+2, N, pole+1)){ return 1;}
if(T[i-1][j-2]==0 && konik(T,i-1,j-2, N, pole+1)){ return 1;}
T[i][j]=0;
return 0;
}
void wypelniacz(int tab[],int size);
int main()
{
int size=8;
int tab[size+4][size+4];
tab[0][0]=10;
wypelniacz(tab,size);
int i=2,j=2,pole=1;
int konik( tab, i, j, size, pole);
/*for(int i=0;i<size+4;i++)
{
for(int j=0;j<size+4;j++)
{
printf("%d ",tab[i][j]);
}
printf("
");
}*/
return 0;
}
Mam kilka pytań bo program kompletnie nie działa. Zdaje sobie sprawę że jest już trochę pogmatwane ponieważ sporo zmieniałem i kombinowałem.
1.Czemu program nawet nie wchodzi do funkcji konik (nie wypisuje się "A")?
2.Z posta Crizz nie rozumiem:
Ukryta treść:
*dla (w jakiś sposób) kolejnych "ważnych" par i,j (tzn. 2 le i,j le 9) będzie sprawdzała, czy funkcja konik(T,i,j,8,1) zwraca prawdę (jeśli zwróci prawdę, to twoja funkcja też ma zwrócić prawdę i zakończyć się; zastanów się, którą część spośród "ważnych" pól tablicy trzeba sprawdzić, dla niektórych pól sytuacja jest symetryczna - podpowiedź: którą jedną czwartą)
3. Co jeszcze zrobić aby program zaczał działać poprawnie.
Dziekuje za wszystkie wskazówki.
Pozdrawiam.
Ostatnio zmieniony 17 lis 2015, o 06:56 przez Afish, łącznie zmieniany 1 raz.
Powód:Poprawa wiadomości.