Problema backtracking C
Last Updated: May 26 2016 13:28, Started by
Kain_12
, May 25 2016 01:16
·
0
#1
Posted 25 May 2016 - 01:16
Salut, am o problema in C pe care ma chinui sa o rezolv de 4 ore. Nu mai stiu ce sa ii fac. Sunt destul de obosit si probabil de aia imi scapa. Pun codul aici :
#include <stdio.h> // PERMUTĂRI int n, X, v[20]; //n-nr. de elemente, v[20]-vectorul în care construim soluția int valid(int k); int solutie(int k); void afisare(int k); void BK(int k); int main() { FILE *f; scanf("%d", &n); BK(1); _getch(); return 0; //apelăm funcția BK pentru completarea poziției 1din vectorul v } void BK(int k) { int i; //i-elementul selectat din multimea Sk, trebuie sa fie variabilă locală, pentru // a se memora pe stivă for (i = 0; i <= 9; i++) //parcurgem elementele mulțimii Sk { v[k] = i; //selectăm un element din mulțimea Sk if (valid(k)) //verificăm dacă eelementul ales îndeplinește condiiile de continuare { if (solutie(k)) //verificăm dacă am obținut o soluție afisare(k); //se afișează soluția obținută else BK(k + 1); //reapemăm funcția pentru poziția k+1 din vectorul v } } } int valid(int k) //verificăm condițiile de continuare { int j; int contor = 0; for (j = 1; j <= k - 1; j++) //comparăm fiecare element din vectorul v cu ultimul element selectat { if (v[j] == 2) //deoarece într-o permutare elementele nu au voie să se repete, contor++; } return 1; //returnăm 1 în cazul în care elementul nu mai apare în vector } int solutie(int k) //verificăm dacă am obținut o soluție { int contor4 = 0; int contor1 = 0; int i; if (k == n) //am obținut o permutare, dacă am reușit să depunem în vector n elemente { for (i = 1; i <= k - 1; i++) { if (v[i] == 4) contor4++; if (v[i] == 1) contor1++; } if (contor4 != 3 || contor1 != 2) return 0; else return 1; } return 0; } void afisare(int k) //afișează conținutul vectorului v { FILE *g; g = fopen("out.txt", "w+t"); int i; for (i = 1; i <= k; i++) printf("%d ", v[i]); printf("\n"); }Ignorati comentariile, nu sunt de la problema asta. Ce am nevoie eu : Sa imi genereze numerele de 9 cifre care contin 3 de 4 si 2 de 1. Daca scot conditiile din valid sau solutie, imi genereaza toate numerele. Imediat cum pun ceva conditii, nu mai apare nimic. |
#2
Posted 25 May 2016 - 13:56
if (solutie(k)) afisare(); else BK(k + 1); solutie(k) nu returnează 0 doar dacă k ≠ n. Și un număr nu poate să înceapă cu cifra 0. |
#3
Posted 25 May 2016 - 23:09
Chiar trebuie sa ti le genereze pe TOATE?
Ca din ce am calculat eu sunt 5160960 (C(9,3) * C(6,2) * 8^4). Cum vrei sa verifici daca nu lipseste vreunul? |
#4
Posted 26 May 2016 - 01:51
Ba poate sa inceapa cu 0. E numar de telefon. Trebuie sa generez numerele de telefon formate din n cifre.
|
#6
Posted 26 May 2016 - 08:28
Functia valid are rolul de a limita spatiul de cautare. In cazul tau nu face absolut nimic. Incearca sa te gandesti ce conditii poti pune la pasii 1,2,3,...,9.
- trebuie sa continuam daca numarul generat este 44444? - trebuie sa continuam daca numarul generat este 111? - trebuie sa continuam daca numarul generat este 00000? Ce ti-am dat aici sunt doar cazuri extreme. Incearca sa sintetizezi conditiile corecte. Este absolut aberant sa faci verificarea in solutie. PS: Ai deschis un topic despre rotirea matricilor. Ti-am dat indicatii, dar l-ai lasat balta. Oare sa aibe si acest topic aceeasi soarta? |
#7
Posted 26 May 2016 - 13:28
Acolo am rezolvat problema, imi cer scuze ca "l-am lasat balta". Acum incerc cu solutiile propuse de voi.
|
Anunturi
Bun venit pe Forumul Softpedia!
▶ 0 user(s) are reading this topic
0 members, 0 guests, 0 anonymous users