—- Acesta e doar un exemplu dar conceptul în sine de backtracking e foarte maleabil, în acest caz se generează toate numerele de x cifre (x introdus de la tastatură), ia toate combinațiile posibile.
Odată înțeles(vă trebuie mult exercițiu) vă va fi extrem de util cum îmi este și mie.
fierarul: pentru o mare parte din cei de pe acest forum ESTE rocket science. Nu toată lumea a fost la liceul de informatică. In clasa a 10-a la Mate-Fizică unde am fost eu ne învățau “BEZIC” pe HC-uri.
trapper - dă mai multe detalii. Cum face omul obișnuit ca să ajungă de la scrierea cuneiformă din mesajul tău la cifre apărând în fereastra neagră ?
N-am spus că e rocket science, scopul acestui topic este să-i ajute pe micii programatori să învețe back-tracking deoarece e o metodă eficientă(timp de execuție scurt) de a genera și verifica toate posibilitățile. Dacă știai, mă bucur, dacă nu atunci nu critica pentru că am postat ceva ce știai deja.
psergiu: păi backtracking nu e chiar pentru începători => dacă nu ești începător înseamnă că știi să compilezi un program iar detaliile sunt mai mult decât suficiente.
Un program atât de mic și cu atâtea probleme… De unde să încep?
1) Nu faci nici un fel de bounds checking, ai array-ul ăla alocat static și limitat în dimensiune dar nu faci nici un fel de input validation și e trivial să faci un exploit pentru programul în cauză el suferind de buffer overflow.
2) Folosești variabilele alea globale absolut gratuit. Se recomandă a se minimiza program state, hence, variabilele globale, iar un program de dimensiunea asta nu are nevoie în nici un caz de variabile globale.
3) Funcțiile alea violează conceptul de programare procedurală pentru că nu sunt stateless și au side effects ascunse. (Asta e legat de (2)).
4) Structura programului este de asemenea haotică, fară nici un fel de separation of concerns inerente programării procedurale. Amesteci I/O în funcționarea algoritmilor. Nu există o separație clară între date și algoritmi, input și output la o funcție ce implementează algoritmul. Tot programul e monolitic și nu este scalabil.
5) main() e int main(), chiar și în C. În C tipul de retur default este int, dar în C++ este void, de asta ar trebui să ai int main() acolo, pentru a fi compatibil cu C++.
6) Recursivitatea e bună în teorie pentru că mulți algoritmi se înțeleg mai ușor în forma recursivă, dar în practică recursivitatea nu se folosește pentru că o să dai în stack overflow o dată ce programul scalează. Orice algoritm recursiv se poate transforma într-unul iterativ (și viceversa).
7) funcția back() e greșită conceptual pentru că parametru k nu are nicio relevanță în funcționarea internă a funcției. Cu alte cuvinte te bazezi pe side effects și îi transmiți funcției parametrii de care nu are nevoie. Din moment de funcția depinde de n, funcția trebuie scrisă astfel încat să ia ca parametru n, și nu 1.
8) Ăsta e C, nu Pascal. Îndecșii unui array încep de la 0 și nu de la 1!
9) Îndentarea e varză. Niciun programator serios nu ar citi ceva care arată așa.
10) Algoritmul este extrem de ineficient și inutil pentru problema în cauză. Ca aproape tot ce se face la liceu în domeniu ăsta, din păcate.
11) Numerele variabilelor sunt generice și nu înseamnă nimic. Trebuie să folosești nume de variabile sugestive.
PS: backtrackingul nu este o metodă eficientă de a rezolva probleme, este de fapt cea mai ineficientă metodă. De departe. Și este totdeauna metoda banală. Orice programator cu experiență de 2 zile trebuie să șție să facă așa ceva. Problemele din programarea reală sunt altele.
Backtracking este totusi la nivel de clasa a 10-a liceu, nu e chiar rocket science, parcurgi in adancime arborele combinatiilor posibile.
E bine insa ca se mai si programeaza pe mac-uri, toata lumea presupune ca sunt vre-un designer si eu bag toata ziua Java…
Evident ca se programeaza :-D Si eu sunt programator, iar in calitate da student masterand mi-am realizat toate proiectele scolare pe Mac, atat in Java, cat si in C si Python. Sincer mi se pare chiar mai usor sa programezi pe Mac decat pe Windows, avand multe utilitare si compilatoare deja preinstalate (Java, Python, Open MPI etc), altele fiind la distanta unui click.
Un program atât de mic și cu atâtea probleme… De unde să încep?
1) Nu faci nici un fel de bounds checking, ai array-ul ăla alocat static și limitat în dimensiune dar nu faci nici un fel de input validation și e trivial să faci un exploit pentru programul în cauză el suferind de buffer overflow.
2) Folosești variabilele alea globale absolut gratuit. Se recomandă a se minimiza program state, hence, variabilele globale, iar un program de dimensiunea asta nu are nevoie în nici un caz de variabile globale.
3) Funcțiile alea violează conceptul de programare procedurală pentru că nu sunt stateless și au side effects ascunse. (Asta e legat de (2)).
4) Structura programului este de asemenea haotică, fară nici un fel de separation of concerns inerente programării procedurale. Amesteci I/O în funcționarea algoritmilor. Nu există o separație clară între date și algoritmi, input și output la o funcție ce implementează algoritmul. Tot programul e monolitic și nu este scalabil.
5) main() e int main(), chiar și în C. În C tipul de retur default este int, dar în C++ este void, de asta ar trebui să ai int main() acolo, pentru a fi compatibil cu C++.
6) Recursivitatea e bună în teorie pentru că mulți algoritmi se înțeleg mai ușor în forma recursivă, dar în practică recursivitatea nu se folosește pentru că o să dai în stack overflow o dată ce programul scalează. Orice algoritm recursiv se poate transforma într-unul iterativ (și viceversa).
7) funcția back() e greșită conceptual pentru că parametru k nu are nicio relevanță în funcționarea internă a funcției. Cu alte cuvinte te bazezi pe side effects și îi transmiți funcției parametrii de care nu are nevoie. Din moment de funcția depinde de n, funcția trebuie scrisă astfel încat să ia ca parametru n, și nu 1.
8) Ăsta e C, nu Pascal. Îndecșii unui array încep de la 0 și nu de la 1!
9) Îndentarea e varză. Niciun programator serios nu ar citi ceva care arată așa.
10) Algoritmul este extrem de ineficient și inutil pentru problema în cauză. Ca aproape tot ce se face la liceu în domeniu ăsta, din păcate.
11) Numerele variabilelor sunt generice și nu înseamnă nimic. Trebuie să folosești nume de variabile sugestive.
PS: backtrackingul nu este o metodă eficientă de a rezolva probleme, este de fapt cea mai ineficientă metodă. De departe. Și este totdeauna metoda banală. Orice programator cu experiență de 2 zile trebuie să șție să facă așa ceva. Problemele din programarea reală sunt altele.
Nu inteleg de ce abordezni un ton atat de dur si dispretuitor? Nu spun ca nu ai dreptate, dar gandeste-te ca si tu ai pornit de undeva, nu te-ai nascut uberprogramator. Comentariile de genul acesta nu fac altceva decat sa-i alunge si pe putinii tineri interesati si entuziasmati de programare. Apreciez totusi scopul didactic de dedesubt.
yap o alta varianta de backtracking, eu il faceam altfel pe vremuri (adik acum 6 ani), parca fara alte functii, direct in “void main (void)”, sau nu mai tin bine minte ... mult timp de atunci.
Aron stai liniștit omul a încercat doar să ajute. Ar fi putut ajuta ce-i drept cu un cod sursă făcut de el mai bun.
OK, stiu, si apreciez gestul. Ceea ce nu aoreciam era stilul de a-si prezenta ideile. Poate sunt prea sensibil, dar nu-mi place genul de programator (si om in general) “Mr. Know-It-All”.
void usage(void) { printf( "Program prints all possible `n' digit numbers.\n" "Syntax:\n\n" "\tprogram n\n\n" "where `n' is the number of digits (1 <= n <= 100).\n"); }
void print_number(signed char digits[], long num_digits) { int i;
if (num_digits > MAX_DIGITS) { fprintf(stderr, "Number of digits is out of range.\n"); exit(16); }
for (i = 0; i < num_digits; ++i) { printf("%d", digits[i]); } printf("\n"); }
int is_number(signed char digits[], long num_digits) { int i; int ret = 1;
for (i = 0; i < num_digits; ++i) if (digits[i] < 0) ret = 0;
return ret; }
void generate_numbers(long num_digits) { signed char digits[MAX_DIGITS]; int current_pos = 0; int i;
for (i = 0; i < num_digits; ++i) digits[i] = -1;
for (;;) { if (current_pos == -1) break;
if (current_pos == num_digits - 1) { if (is_number(digits, num_digits)) print_number(digits, num_digits); }
int main(int argc, char **argv) { long digit_count;
if (argc != 2) { usage(); return 1; }
digit_count = strtol(argv[1], NULL, 0); if (errno == EINVAL || errno == ERANGE) { fprintf(stderr, "Number is out of range " "or not in supported format.\n"); return 2; } if (digit_count < 1 || digit_count > MAX_DIGITS) { fprintf(stderr, "Number is out of range.\n"); return 4; }
... mult timp de atunci.
