Jump to content

Metoda Backtracking


skyler_sdf

Recommended Posts

177-permutari de n elem.

178-siruri de cifre cu cifrele 1, 2, 3, 4

179-secvente de n litere

180-combinari de n luate cate k

181-combinari de n luate cate k-var.generalizat

182-aranjamente de n luate cate k

183-produs cartezian a n multimi

184-produs cartezian a n cuvinte

185-fotografia unui obiect

177.

#include<iostream.h>

#include<stdio.h>

int st[25], n;

void initializari()

{

int i;

cout<<"n="; cin>>n;

for(i=1; i<=25; i++)

 st[i]=0;

 }

 void tipar(int p)

 {

	int j;

	for(j=1; j<=p; j++)

	 cout<<st[j]<<" ";

	 cout<<endl;

	 }

	int valid(int p)

	{

	 int i, ok=1;

	 for(i=1; i<=p-1; i++)

		if(st[p]==st[i])

		 ok=0;

		return ok;

		}

		void bktr(int p)

		 {

			int pval;

			for(pval=1; pval<=n; pval++)

			{

			 st[p]=pval;

			 if(valid(p))

				if(p==n)

				 tipar(p);

				else

				 bktr(p+1);

				 }

			}

		void  main()

		{

		initializari();

		bktr(1);

    }
178.
#include<iostream.h>

#include<conio.h>

int st[30], n;

void initializare()

{

int i;

for(i=1; i<=30; i++)

 st[i]=0;

 }

 void tipar(int p)

 {

	int j;

	 for(j=1; j<=p; j++)

		cout<<st[j]<<" ";

		cout<<endl;

		}

	int validare(int p)

	{

	 int i;

	 int ok=1;

	 for(i=1; i<=p-1; i++)

		if((st[p]%2==0 && st[p-1]!=0) || (st[p]%2 !=0 && st[p-1]==0))

		 ok=0;

		return ok;

		}

	 void bktr(int p)

	 {

		int pval;

		for(pval=1; pval<=n; pval++)

		{

		 st[p]=pval;

			if(validare(p))

			 if(p==n)

				tipar(p);

			 else

			 bktr(p+1);

			 }

			 }

		void main()

		{

		initializare();

		bktr(1);

		getch();

    }
179.
#include<iostream.h>

#include<conio.h>

#include<math.h>

#include<string.h>

#include<stdio.h>

char st[1000]; int  n;

void initializare()

{

 int i, l;

 l=strlen(st);

	for(i=1; i<=l; i++)

	 st[i]=' ';

	 }

 void tipar(int p)

 {

	int j;

	for(j=1; j<=p ;j++)

	 puts(st);

	 puts(" ");

	 puts("\n");

	 }

 int valid(int p)

 {

 int i, ok=1;

 for(i=1; i<=p-1; i++)

	if(abs(st[p]-st[p-1]) !=1 && st[p]==st[i])

	 ok=0;

	return ok;

	}

	 void bktr(int p)

	 {

		int pval;

		for(pval='A'; pval<='Z'; pval++)

		{

		 st[p]=pval;

			if(valid(p))

			 if(p==n)

				tipar(n);

				else

				 bktr(p+1);

				 }

			}

	 void main()

	 {

	 initializare();

	 bktr(1);

	 getch();

	 }
180.
#include<iostream.h>

#include<conio.h>

int st[40], n, k;

void initializare()

{

 int i;

	for(i=1; i<=40; i++)

	 st[i]=0;

 do{	cout<<"n="; cin>>n;

	cout<<endl<<"k="; cin>>k;

	 }while(n<k);

	 }

		void tipar(int p)

		{

		 int j;

		 for(j=1; j<=p; j++)

			cout<<st[j]<<" ";

			cout<<endl;

		 }

	 int validare(int p)

	 {

		int i;

		if(p>1 && st[p]<=st[p-1])

		 return 0;

		else

		 return 1;

		 }

	 void bktr(int p)

	 {

		int pval;

		for(pval=1; pval<=n; pval++)

		{

		 st[p]=pval;

		 if(validare(p))

			if(p==k)

			 tipar(p);

			else

			 bktr(p+1);

			 }

		 }

			void main()

			{

			 initializare();

			 bktr(1);

			 getch();

    }
181.
#include<iostream.h>

#include<conio.h>

int st[40], n, k;

void bktr(int p)

{

 int i, pval;

 for(pval=st[p-1]+1; pval<=n; pval++)

 {

 st[p]=pval;

 if(p==k)

 {

	for(i=1; i<=p; i++)

	 cout<<st[i]<<" ";

	 cout<<endl;

	 }

	else

	 bktr(p+1);

	 }

	}

 void main()

 {

	cout<<"n="; cin>>n;

	cout<<endl<<"k=" ;cin>>k;

	st[0]=0;

	bktr(1);

	}
182.
#include<iostream.h>

#include<stdio.h>

#include<conio.h>

int st[500], n, k;

FILE *f;

void initializare()

{

 int i;

 for(i=1; i<=500; i++)

	st[i]=0;

	do{

	 cout<<"n="; cin>>n;

	 cout<<endl<<"k="; cin>>k;

	 }while(n<k);

		}

		 void tipar(int p)

			{

			 int j;


				for(j=1; j<=p; j++)

				 fprintf(f, "%d \n", st[j]);


				}

			int valid(int p)

			{

			int i;

			 if(st[p]<=st[p-1] && st[p]>=st[p-1])

				return 0;

			 else

			 return 1;

			 }

			void bktr(int p)

			{

			int pval;

			for(pval=1; pval<=n; pval++)

			 { st[p]=pval;

			 if(valid(p))

				if(p==k)

				 tipar(p);

				else

				 bktr(p+1);

				 }

			}

		void main()

		{

//in exemplul nostru fisierul este "aranjamente.txt"

		 initializare();

		 f=fopen("aranjamente.txt", "w"); //se deschide pentru scriere

		 bktr(1);

		 getch();

		 fclose(f);

     }


183.
#include<iostream.h>

#include<conio.h>

int st[50], nr[50], n;

void initializare()

{

int i;

cout<<"n="; cin>>n;

 for(i=1; i<=50; i++)

	st[i]=0;

 for(i=1; i<=n; i++)

	{

	 cout<<endl<<"numarul de elemente al multimii "<<i<<": ";

	 cin>>nr[i];

	 }

	}

 void tipar(int p)

 {

	int j;

	for(j=1; j<=p; j++)

	 cout<<st[j]<<" ";

	 cout<<endl;

	 }

 int valid()

 {

	return 1;

	}

	void bktr(int p)

	 {

		int pval;

		if(p==n+1)

		 tipar(p-1);

		else

		 for(pval=1; pval<=nr[p]; pval++)

			{

			 st[p]=pval;

				if(valid())

				 bktr(p+1);

				 }

			 }

		void main()

		{

		 initializare();

		 bktr(1);

		 getch();

     }

184.
#include<iostream.h>

#include<conio.h>

#include<string.h>

#include<stdio.h>

int n, nr[40];

FILE *f;

char  st[20][30], st1[20];

void initializare()

{

int i;     int l;

cout<<"n="; cin>>n;

for(i=1; i<=n; i++)

{

 cout<<"numarul de caractere "<<i<<":";

 cin>>st1[i];

 l=strlen(st1);

 nr[i]=l;

 st1[i]=' ';

 }

 }

void tipar(int p)

{

 int j;

 for(j=1; j<=p ;j++)

	fprintf(f, "%c \n", st[st1[j]][j]);

	}

int valid()

{return 1; }

void bktr(int p)

{ int pval;

for(pval=1; pval<=nr[p]; pval++)

 {

 st1[p]=pval;

 if(valid())

	if(p==n)

	 tipar(p);

	else

	 bktr(p+1);

	 }}

 void main()

 {

//in exemplul nostru fisierul este "cuvinte.txt"

 f=fopen("cuvinte.txt", "w"); //se deschide pentru scriere

 initializare();

 bktr(1);

 getch();

 fclose(f);

 }

  • Upvote 1
Link to comment
Share on other sites

  • 3 years later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.