PDA

View Full Version : thuật toán bài sinh dãy nhị phân, giúp em với !!!



rong3sao
10-10-2009, 11:39 AM
Đề bài :
Liệt kê các phần tử của tập D ={x1,x2,...,xn} thỏa mã : tổng tất cả các tính a[i]*x[i] = b ,trong đó b và mảng a cho trước .Các số xi nhận giá trị 0 hoặc 1. (mảng a và số b là các số nguyên dương).

Hướng mình nghĩ thế này : đầu tiên sinh tất cả các dãy nhị phân độ dài n ra .
Sau đó viết 1 cái hàm kiểm tra các dãy nhị phân đó , dãy nào thỏa mãn thì in ra . Nhưng khi vào code thì mới thấy ,ko biết cho cái hàm kiểm tra vào đâu đây.
Các bạn giúp mình với !!!!
Cảm ơn nhiều !!!




#include <stdio.h>
#include <conio.h>
void Init(int x[],int n)
{int i;
for(i=1;i<=n;i++) x[i]=0;
}
//==========================
void View(int x[],int n)
{int i;
for(i=1;i<=n;i++) printf("%4d",x[i]);
}
//===========================
void kiemtra(int x[],int n){
int i,a[50],b;
int tong=0;
for(i=1;i<=n;i++)
{
tong=tong + (a[i])*(x[i]);
i++;
}
if(tong=b)
for(i=1;i<=n;i++)
printf("%4d",x[i]);
}
//==========================
void NpKeTiep(int x[],int n)
{int i,k,r,s,tmp;
int static m=1;
printf("\nXau nhi phan thu %2d :",m++);
View(x,n);
tmp=0;
for(i=1;i<=n;i++)
if(x[i]!=1)
{
tmp=1;
break;
}
if(tmp==0)
return;//Da o xau cuoi cung
i=n;
//Tim a[i] dau tien tu phai sang trai ma a[i]==0
while(x[i]==1)
{
x[i]=0;
i--;
};//Dung lai khi a[i]==0
x[i]=1;//Chuyen a[i] tu 0 sang 1
NpKeTiep(x,n);
}
//================================
void main()
{
int x[50],n,i;
int a[50],b;
printf("\nn = ");
scanf("%d",&n);
printf("\nNhap mang a.");
for(i=1;i<=n;i++)
{
printf("\na[%d]= ",i);
scanf("%d",&a[i]);
}
printf("\nNhap so b= "); scanf("%d",&b);
Init(x,n);
kiemtra(x,n);
NpKeTiep(x,n);
printf("\nSo phan tu cua tap D:\n");

getch();
}


Mình đã code lại bằng thuật toán quay lui ,nhưng kết quả chưa đúng . Mọi người xem giúp mình với :


#include <stdio.h>
#include <conio.h>
int x[50],n;
int a[50],b,s=0;
int tong(int x[],int a[]){
int i;
for(i=1;i<=n;i++){
s = (s + (x[i])*(a[i]));
i++;
}
return s;
}
void result(void)
{ int i;
if(b==tong(x,a))
{
printf("\nCac phan tu cua tap D la: ");
for (i=1;i<=n;i++)
printf("%3d",x[i]);
}
}
void tri(int i)
{
int j;
for (j=0;j<=1;j++)
{
x[i]=j;
if(i==n){
result();
}
else tri(i+1);
}
}
void main(void)
{

int i;
printf("\nNhap n: "); scanf("%d",&n);
printf("\nNhap b: "); scanf("%d",&b);
printf("\nNhap mang a :");
for(i=1;i<=n;i++){
printf("\na[%d] = ",i); scanf("%d",&a[i]);
}
tri(1);
getch();
}