Code Tổ Hợp chương 3, ACE góp ý nhé

Thuật toán thay thế:

Code:

#include"conio.h"
#include"stdio.h"

int A[100],max[100],n;

void in()
{
    for(int i=1;i<=n;i++)
    {
        printf("%4d",A[i]);
    }
    puts("");
}

int lonhon(int x,int y)
{
    return x>y?x:y;
}

void tinhlaimax()
{
    for(int i=2;i<=n;i++)
    max[i]=lonhon(max[i-1],A[i-1]);
}
void khoitao()
{
    for(int i=1;i<=n;i++)
    {
        A[i]=1;
        max[i]=0;
    }
}
void thaythe()
{
    tinhlaimax();
    in();
    int i=n;
    while(A[i]==max[i]+1)i--;
    A[i]++;
    for(int j=i+1;j<=n;j++)A[j]=1;
}
int main()
{
    printf("Nhap n : ");
    scanf("%d",&n);
    khoitao();
    while(A[n]!=n)thaythe();
    in();
    getch();
    return 0;
}
//thac mac xin gui ve vuthaihoc.ttud@gmail.com :)

Thuật toán tu điển giảm:

Code:

#include"conio.h"
#include"stdio.h"
#include"math.h"

int a[100],n;

void khoitao()
{
    printf("Nhap so can phan tich n (n<100) : ");scanf("%d",&n);
    for(int i=1;i<100;i++)
    a[i]=0;
    a[1]=n;//nghiem dau tien
}
//in ra day hien tai
void in()
{
    int i=1;
    while(a[i]!=0){printf("%4d",a[i]);i++;}
    puts("");
}
//do dai day hien tai
int dodaiday()
{
    int i=1;
    while(a[i]>0)i++;
    return i-1;
}

int timp()
{
    int i=dodaiday();
    while(a[i]==1)i--;
    return i;
}

void giamtudien()
{ 
    in();
    int p=timp(),k=dodaiday();//tim vi tri p va do dai day hien tai
    int sum=a[p]+k-p;//tong can thay doi
    int ap=a[p]-1;//
    //xoa cac thanh phan sau vi tri p
    for(int j=p;j<=k;j++)a[j]=0;
    //xac dinh so lan ap lap lai
    int rp=sum / ap;
    //thay cac vi tri bang ap
    for(int j=0;j<rp;j++)a[p+j]=ap;
    //them phan du neu can
    int l=sum % ap;
    if(l>0)a[p+rp]=l;
}

int main()
{
    khoitao();
    while(a[1]>1)giamtudien();
    in();//in ra nghiem cuoi cung
    getch();
    return 0;
}
//thac mac xin gui ve vuthaihoc.ttud@gmail.com :)

uh. Cảm ơn Học
Tớ có code khác
Thuật toán thay thế:

Code:

#include<stdio.h>
#include<conio.h>

int n;
int A[100];
int Max[100];

void khoi_tao()
{
    int i;
    for(i = 1; i<= n; i++)
      A[i] = 1;
}

void in_ket_qua()
{
    int i;
    for(i = 1; i <= n; i++)
    {
          printf("%3d", A[i]);
    }
    printf("\n");
}

void tim_max()
{
    Max[1] = 0;
    for(int i = 2; i <= n; i++)
      Max[i] = Max[i-1]>A[i-1]?Max[i-1]:A[i-1];
}

void sinh_phan_hoach()
{
    int i;
    while(A[n] != n)
    {
          in_ket_qua();
          tim_max();
         
          //tim phan phan hoach moi
          i = n;
          while(A[i] == Max[i] + 1)
          {
                      i --;
          }
         
          int p = i;
         
          // thay the
          A[p] = A[p] + 1;
          for(i = p + 1; i <= n; i++)
            A[i] = 1;         
    }
   
    //in ket qua khi A[n] = n
    in_ket_qua();
}

int main()
{
    printf("Nhap so phan tu n = ");
    scanf("%d", &n);
   
    khoi_tao();
    sinh_phan_hoach();
    getch();
}

Thuật toán tu điển giảm:

Code:

/*
  Phan tich so
*/

#include<stdio.h>
#include<conio.h>

int n;
int a[100];

void khoi_tao()
{
    int i;
    for(i = 2; i <= n; i++)
        a[i] = 0;
   
    a[1] = n;
}

void ket_qua()
{
    int i;
   
    for(i = 1; i <= n; i++)
        if(a[i] > 0)printf("%3d", a[i]);
   
    printf("\n");
}

//vi tri lon nhat i ma a[i] > 1
int tim_vi_tri_thay_doi()
{
    int i = n;
    while(a[i] <= 1)
      i --;
     
    return i;
}

//so cac phan tu khac 0
int do_dai()
{
    int d = 0;
   
    while(a[d + 1] != 0)
      {
              d ++;           
      }
   
    return d;
}

void phan_tich()
{
    int i;
    while(a[1] != 1)
    {
            ket_qua();
            // tim vi tri thay doi
            int p = tim_vi_tri_thay_doi();
            int k = do_dai();
            //thay doi
            int sum = a[p] + (k - p);
            a[p] = a[p] - 1;
           
            //them r ptu bang nhau va bang a[p]
            int r = sum / a[p];
            for(i = p + 1; i <= n; i++)
              if(i < p + r)a[i] = a[p];
              else a[i] = 0; // cac phan tu con lai bang 0
           
            //tin phan du
            int l = sum % a[p];
            if(l > 0) a[p+r] = l;
    }
   
    // in voi bo 1 1 1 11 1 ...
    ket_qua();
}

int main()
{
    printf("Nhap n = ");
    scanf("%d", &n);
   
    khoi_tao();
    phan_tich();
   
    getch();
}

// thuật toán từ điển giảm code theo sách của thầy thành có chỉnh sửa cho đúng

#include<conio.h>
#include<stdio.h>
#include<math.h>
int s[100];
int n;
int r[100];
int sum;
int d,l;

void innit()
{
puts("Moi nhap so can phan tich");
scanf("%d",&n);

}
void in()
{
int i=1;
while(s[i]>0)
{
for(int j=1;j<=r[i];j++)
{
printf("%3d",s[i]);
}
i++;
}
puts("");
}
int mod(int x,int y)
{
int t;
int l= x/y;
t=x-l*y;
return t;
}

void process()
{

s[1]=n;
r[1]=1;
d=1;
in();
while(s[1]>1)
{
sum=0;
if(s[d]==1)
{
sum=sum+r[d];
r[d]=0;
d=d-1;

}
sum=sum+s[d];r[d]=r[d]-1; l=s[d]-1;
if(r[d]>0)d=d+1;
s[d]=l;r[d]= sum/l ;
l=mod(sum,l);
if(l!=0)
{
d++;
s[d]=l;
r[d]=1;
}
in();
}
}
int main()
{
innit();
process();
getch();
return 1;
}

chẳng hìu j cả, học vẹt ko biết vào fong thi có nhớ ko nữa

Chúc mọi ng làm bài tốt nha

Hạnh ơi, học vẹt những cái gì đấy? hihi. Môn này vẫn chưa qua.lo quá

đã gọi là học vẹt mà học xong rùi ứ có biết là mh vừa học cái j nữa

code đọc khó hiểu quá :D

Khuyen mai cai bai chia kẹo này ai cần thì lấy về dùng dễ lắm nó cũng chỉ giống thuật toán sinh tập con bằng phương pháp cộng 1 thôi chỉ có điều sau mỗi lần ta đánh giá sự chênh lệch số kẹo giữa 2 lớp và nghiệm sau tốt hơn nghiệm trước

// bài toan chia keo
có n goi kẹo mỗi gói có ki cái kẹo. chia cho 2 lớp mẫu giáo sao cho sự chênh lệch số kẹo giữa 2 lớp là ít nhất



// chia keo
#include "conio.h"
#include "stdio.h"
#include "math.h"

int n,sum;// sum tong so keo trong n goi
int k[20];// so luong keo moi goi
int a[20];// bien nhi phan =1 tuc la goi keo chia cho lop 1 = 0 chia cho lop 2

void nhap()
{
sum =0;
int tg;
printf("Nhap so goi keo n= ");
scanf("%d",&n);
printf("Nhap so luong keo moi goi:\n");
for(int i=1;i<=n;i++)
{

scanf("%d",&k[i]);
sum+=k[i];

}



}
void in()
{
for(int i=1;i<=n;i++)
printf("%4d",a[i]);
puts("");
}
void chiakeo()
{
int j;
int sum1,sum2,min,hieu;
min = 10000; //khoi tao gia tri min
for(int i=1;i<=n;i++)
a[i] =0;
do
{
sum1=0;// so keo chia cho lop 1
sum2=0;// so keo chia cho lop 2

if(hieu<min)
{
// cap nhat lai cach chia moi
min = hieu;
in();
}
j=n;

while(a[j]==1)
{
a[j]=0;
j--;
}
a[j]=1;
for(int i = 1;i<=n;i++)
{
if(a[i]==1)
sum1=sum1+k[i];
}
sum2 = sum - sum1;
hieu = fabs(sum1-sum2);
}
while(j!=0);

printf ("Cach chia sau cung la tot nhat");

}
int main()
{
nhap();
chiakeo();
getch();
printf("%d",sum);
return 0;
}



có gì sai sót các bác thông cảm

[Bổ sung] . Tư tưởng của thuật toán trên là : Ta đánh số thứ tự các túi là 12..n. coi mỗ túi như một bit nhị phân.
Bài toán trên quy về tìm 1 tập con A của tập X (toàn bộ các túi) sao cho lưc lượng của A và X\A là chênh lệnh ít nhất
Loop :
=> tìm tất cả các dãy nhị phân a1,a2...an (ai=0/1) , mỗi khi tìm dc 1 nghiệm mới thì ta đánh giá độ tốt của nghiệm (hieu = |sum1-sum2| là tiêu chí đánh giá)
If (tốt hơn) lưu lại nghiệm.
Else bỏ qua
End loop.
In ra dãy nhị phân tốt nhất <=> cách chia tốt nhất.
Độ phức tạp = số các dãy nhị phân độ dài n * số phép toán cơ bản cần xử lí trong mỗi dãy = 2^n * n

Nếu dùng phương pháp thêm bớt để tìm nghiệm tối ưu thì độ phức tạp chỉ là 2^n - tốt hơn rất nhiều

Che..vankhe đã viết:

[Bổ sung] . Tư tưởng của thuật toán trên là : Ta đánh số thứ tự các túi là 12..n. coi mỗ túi như một bit nhị phân.
Bài toán trên quy về tìm 1 tập con A của tập X (toàn bộ các túi) sao cho lưc lượng của A và X\A là chênh lệnh ít nhất
Loop :
=> tìm tất cả các dãy nhị phân a1,a2...an (ai=0/1) , mỗi khi tìm dc 1 nghiệm mới thì ta đánh giá độ tốt của nghiệm (hieu = |sum1-sum2| là tiêu chí đánh giá)
If (tốt hơn) lưu lại nghiệm.
Else bỏ qua
End loop.
In ra dãy nhị phân tốt nhất <=> cách chia tốt nhất.
Độ phức tạp = số các dãy nhị phân độ dài n * số phép toán cơ bản cần xử lí trong mỗi dãy = 2^n * n

Nếu dùng phương pháp thêm bớt để tìm nghiệm tối ưu thì độ phức tạp chỉ là 2^n - tốt hơn rất nhiều

Thì nói chung nó giống tương tự thuật toán tìm tất cả các tập con của tập n phần tử nhưng có thêm đánh giá nghiệm nào tốt hơn thôi.