Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
teava rezistenta panou apa calda

Acces in Curte din Drum National

Sub mobila de bucatarie si sub fr...

Rezultat RMN
 Numar circuite IPAT si prindere t...

Pareri brgimportchina.ro - teapa ...

Lucruri inaintea vremurilor lor

Discuții despre TVR Sport HD
 Cost abonament clinica privata

Tremura toata, dar nu de la ro...

Renault Android

Recomandare bicicleta e-bike 20&#...
 Bing-Content removal tool

Nu pot accesa monitorulsv.ro de l...

Cum sa elimini urmele de acnee?

Wc Geberit
 

Problema backtracking C

- - - - -
  • Please log in to reply
6 replies to this topic

#1
Kain_12

Kain_12

    Senior Member

  • Grup: Senior Members
  • Posts: 2,009
  • Înscris: 25.11.2009
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
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
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
MeTrAX

MeTrAX

    Junior Member

  • Grup: Junior Members
  • Posts: 36
  • Înscris: 18.03.2016
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
Kain_12

Kain_12

    Senior Member

  • Grup: Senior Members
  • Posts: 2,009
  • Înscris: 25.11.2009
Ba poate sa inceapa cu 0. E numar de telefon. Trebuie sa generez numerele de telefon formate din n cifre.

#5
sftpdt

sftpdt

    Senior Member

  • Grup: Senior Members
  • Posts: 3,649
  • Înscris: 29.08.2013
Atunci apelează BK(k + 1); numai când k ≠ n.

#6
Cy_Cristian

Cy_Cristian

    Active Member

  • Grup: Members
  • Posts: 1,845
  • Înscris: 22.02.2009
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
Kain_12

Kain_12

    Senior Member

  • Grup: Senior Members
  • Posts: 2,009
  • Înscris: 25.11.2009
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

Forumul Softpedia foloseste "cookies" pentru a imbunatati experienta utilizatorilor Accept
Pentru detalii si optiuni legate de cookies si datele personale, consultati Politica de utilizare cookies si Politica de confidentialitate