Jump to content

SUBIECTE NOI
« 1 / 5 »
RSS
O smecherie pe care nu o inteleg

Balcon parter fara acte

unde gasesc un speed bag in bucur...

Programe TV cu altfel de sporturi
 Laptop "bun la toate" max...

ctfmon.exe - System Error (in Saf...

Ați prins vremurile cand 120 Volț...

Whatsapp nu afișeaza numele ...
 Medii admitere Politehnica Bucure...

Se extinde Baza de la Kogalniceanu

Politist mutilat de caine in curt...

Trotineta- cat rezista?
 Windows 11 si inregistrare de pe ...

Cont Facebook spart

Accesare Plex prin webstation

Reziliere contract Digi Mobil?
 

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,640
  • Î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,640
  • Î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