Bài toán phân tích số (đệ quy quay lui)

Bài toán phân tích số.

Cho một số nguyên dương n<=30, hãy liệt kê tất cả các cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích số là hoán vị của nhau chỉ tính là 1 cách.

Hướng làm bài toán phân tích số theo đệ quy quay lui:

     1.     Ta sẽ lưu nghiệm trong mảng x, ngoài ra có một mảng t. Mảng t xây dựng như sau: t[i] sẽ là tổng các phần tử trong mảng x từ x[1] đến x[i]: 

      t[i]=x[1]+x[2]+ ……+ xi.

     2.     Khi liệt kê các dãy x có tổng các phần tử đúng bằng n, để tránh sự trùng lặp ta đưa thêm ràng buộc x[i-1]<=x[i].

    3.     Vì số phần tử thực sự của mảng x là không cố định nên thủ tục in ra dùng để in ra một cách phân tích phải có thêm tham số để cho biết sẽ in ra bao nhiêu phần tử.

     4.     Thủ tục đệ quy sẽ thử các giá trị có thể nhận x[i] ( x[i]>=x[i-1]).

     5.     Khi nào thì in kết quả, khi nào thì gọi đệ quy tiếp.

Lựu ý : t[i-1] là tổng của tất cả các phần tử từ x[i] đến x[i-1] do đó

·        Khi t[i] = n tứ là ( x[i]=n-t[i-1] ) thì in kết quả.

·        Khi tìm tiếp, x[i+1] sẽ phải lớn hơn hoặc bằng x[i].

Mặt khác t[i+1] là tổng của các số từ x[1] tới x[i+1] không được vượt quá n.

Vậy ta có t[i+1] <= n

 ót[i-1] + x[i] +x[i-1]<=n

 óx[i] + x[i+1] <=n-t[i-1]

 tức là x[i] <= ( n-t[i-1])/2.

Một cách dễ hiểu ta gọi đệ quy tìm tiếp khi giá trị x[i] được chọn còn cho phép chọn thêm một phần tử khác lớn hơn hoặc bằng nó mà khong làm tổng vượt quá n. còn ta in kết quả khi x[i] mang giá trị đúng bằng số thiếu hụt của tổng [i-1] phần tử đầu so với n.

     6.     Vậy thủ tục đệ quy thử các giá trị cho x[i] có thể mô tả như sau: (để tổng quát cho i = 1, ta đặt x[0] = 1 tà t[0] = 0).

·        Xét các giá trị của xi từ x[i-1] đến (n-t[i-1])/2, cập nhật t[i]=t[i+1] + x[i] và gọi đệ quy tiếp.

·        Cuối cùng xét giá trị x[i] = n – t[i-1] và in ra kết quả từ x[1] đến x[i].

Input: nhập số nguyên dương n từ bàn phím  n<=30.

Outout: in ra màn hình các cách phân tích các số nguyên tương ứng.

Code đệ quy C/C++.

#include <stdio.h>

#include <conio.h>

intx[31],t[31],n;

voidkhoitao()

{

      printf("\nNhap n = ");

      scanf("%d",&n);

      x[0]=1;

      t[0]=0;

}

void xuat(int k)

{

      printf("\n%d = ",n);

      for (inti=1;i<k;i++) printf(" %d + ",x[i]);

      printf(" %d",x[k]);

}

voidphantich(int i)

{

      for(intj=x[i-1];j<=((n-t[i-1])/2);j++)

      {

            x[i]=j;

            t[i]=t[i-1]+j;

            phantich(i+1);

      }

      x[i]=n-t[i-1];

      xuat(i);

}

intmain()

{

      khoitao();

      phantich(1);

      getch();

}

Code theo tệp.     

                                                                     

Input: file văn bản PTSINP.TXT chứa các số nguyên dương cách nhau ít nhất 1 kí tự trống hoặc dấu xuống dòng  n<=30.

Outout: file PTSOUT.TXT ghi các cách phân tích các số nguyên tương ứng.

Để đơn giản hóa việc nhập và xem dữ liệu mình thực hiện thao tác 2 file input và output trên nền ổ C:

      C:\\PTSINP.txt

      C:\\PTSOUT.txt

PTSEINP.TXT

PTSOUT.TXT

3 6 7 11

3 =  1 +  1 +  1 3 =  1 +  2 3 =  3 6 =  1 +  1 +  1 +  1 +  1 +  1 6 =  1 +  1 +  1 +  1 +  2 6 =  1 +  1 +  1 +  3 6 =  1 +  1 +  2 +  2 6 =  1 +  1 +  4 6 =  1 +  2 +  3 6 =  1 +  5 6 =  2 +  2 +  2 6 =  2 +  4 6 =  3 +  3 6 =  6 7 =  1 +  1 +  1 +  1 +  1 +  1 +  1 7 =  1 +  1 +  1 +  1 +  1 +  2 7 =  1 +  1 +  1 +  1 +  3 7 =  1 +  1 +  1 +  2 +  2 7 =  1 +  1 +  1 +  4 7 =  1 +  1 +  2 +  3 7 =  1 +  1 +  5 7 =  1 +  2 +  2 +  2 7 =  1 +  2 +  4 7 =  1 +  3 +  3 7 =  1 +  6 7 =  2 +  2 +  3 7 =  2 +  5 7 =  3 +  4 7 =  7 11 =  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 11 =  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 +  2 11 =  1 +  1 +  1 +  1 +  1 +  1 +  1 +  1 +  3 11 =  1 +  1 +  1 +  1 +  1 +  1 +  1 +  2 +  2 11 =  1 +  1 +  1 +  1 +  1 +  1 +  1 +  4 11 =  1 +  1 +  1 +  1 +  1 +  1 +  2 +  3 11 =  1 +  1 +  1 +  1 +  1 +  1 +  5 11 =  1 +  1 +  1 +  1 +  1 +  2 +  2 +  2 11 =  1 +  1 +  1 +  1 +  1 +  2 +  4 11 =  1 +  1 +  1 +  1 +  1 +  3 +  3 11 =  1 +  1 +  1 +  1 +  1 +  6 11 =  1 +  1 +  1 +  1 +  2 +  2 +  3 11 =  1 +  1 +  1 +  1 +  2 +  5 11 =  1 +  1 +  1 +  1 +  3 +  4 11 =  1 +  1 +  1 +  1 +  7 11 =  1 +  1 +  1 +  2 +  2 +  2 +  2 11 =  1 +  1 +  1 +  2 +  2 +  4 11 =  1 +  1 +  1 +  2 +  3 +  3 11 =  1 +  1 +  1 +  2 +  6 11 =  1 +  1 +  1 +  3 +  5 11 =  1 +  1 +  1 +  4 +  4 11 =  1 +  1 +  1 +  8 11 =  1 +  1 +  2 +  2 +  2 +  3 11 =  1 +  1 +  2 +  2 +  5 11 =  1 +  1 +  2 +  3 +  4 11 =  1 +  1 +  2 +  7 11 =  1 +  1 +  3 +  3 +  3 11 =  1 +  1 +  3 +  6 11 =  1 +  1 +  4 +  5 11 =  1 +  1 +  9 11 =  1 +  2 +  2 +  2 +  2 +  2 11 =  1 +  2 +  2 +  2 +  4 11 =  1 +  2 +  2 +  3 +  3 11 =  1 +  2 +  2 +  6 11 =  1 +  2 +  3 +  5 11 =  1 +  2 +  4 +  4 11 =  1 +  2 +  8 11 =  1 +  3 +  3 +  4 11 =  1 +  3 +  7 11 =  1 +  4 +  6 11 =  1 +  5 +  5 11 =  1 +  10 11 =  2 +  2 +  2 +  2 +  3 11 =  2 +  2 +  2 +  5 11 =  2 +  2 +  3 +  4 11 =  2 +  2 +  7 11 =  2 +  3 +  3 +  3 11 =  2 +  3 +  6 11 =  2 +  4 +  5 11 =  2 +  9 11 =  3 +  3 +  5 11 =  3 +  4 +  4 11 =  3 +  8 11 =  4 +  7 11 =  5 +  6 11 =  11

Code đệ quy bài phân tích số C/C++

#include <stdio.h>

#include <conio.h>

intx[31],t[31],n;

voidkhoitao(FILE *u)

{

      fscanf(u,"%d",&n);

      x[0]=1;

      t[0]=0;

}

void xuat(int k,FILE *v)

{

      fprintf(v,"\n%d = ",n);

      for (inti=1;i<k;i++) fprintf(v," %d + ",x[i]);

      fprintf(v," %d",x[k]);

}

voidphantich(int i,FILE *v)

{

      for(intj=x[i-1];j<=((n-t[i-1])/2);j++)

      {

            x[i]=j;

            t[i]=t[i-1]+j;

            phantich(i+1,v);

      }

      x[i]=n-t[i-1];

      xuat(i,v);

}

intmain()

{

      FILE *u,*v;

      u=fopen("C:\\PTSINP.txt","rt");

      v=fopen("C:\\PTSOUT.txt","wt");

      while (!feof(u))

      {

            khoitao(u);

            phantich(1,v);

      }

      fclose(u);

      fclose(v);

      printf("\nHoan Tat. Moi xem ket qua tai C:\\PTSOUT.txt ");

      getch();

}

Thẻ : đệ quy , đệ quy cấu trúc dữ liệu giải thuật .dequy dequyctdlgt

Mong các bạn góp ý và  nhấn G+ ủng hộ blog.

Bài làm tham khảo câu 1 đề ctdlgt đề 14-TI21006-I-1-01-ctdlgt

Câu 1a. đề thi cấu trúc dữ liệu giải thuật (ctdlgt).

      ·         Hàm xem danh sách liên kết dùng được cho cả lifo và fifo.

voidxem(node *f){

      node *p=f;

      while (p!=NULL) {

            printf("%5d",p->info);

            p=p->link;

      }

}

      §  Hàm kiểu void nên khi gọi sẽ thực hiện in danh sách liên kết.

      §  Gọi hàm : xem(f);

       ·        Hàm nhập danh sách liên kết đơn FIFO.

node *nhapfifo(node *f,node *l,int n) {

      node *p=f;

      for(inti=0;i<n;i++) {

            p=new(node);

            printf("\nNhap phan tu thu %d  :  ",i+1);

            scanf("%d",&p->info);

            p->link=NULL;

            if(f==NULL){

                  f=p;

                  l=p;

            }

            else {

                  l->link=p;

                  l=p;

            }

      }

      return f;

}

      §  Hàm trả về địa chỉ của con trỏ f. Con trỏ f trỏ vào ô đầu tiên của danh sách liên kết. Hàm trả về địa chỉ con trỏ f để lấy mốc truy vết các phần tử tiếp theo của DSLK. Mất địa chỉ cô đầu (con trỏ f) có thể nói là mất luôn dslk.

      §  Gọi hàm : f=nhapfifo(f,l,n);

      ·        Hàm tìm kiếm. truyền vào hàm con trỏ f và biến x. Biên x này được truyền từ lúc gọi hàm vào.

inttimkiem(node *f,int x){

      int dem=0;

      node *p=f;

      while (p!=NULL){

            dem++;

            if (p->info==x) returndem;

            p=p->link;

      }

      return 0;

}

       §  Hàm trả về vị trí khi tìm thấy x (if (p->info==x) return dem;) khi tìm thấy sẽ thoat khỏi hàm. Nếu không có x xuất hiện trong danh sách thì trả về giá trị 0 (return 0;) ở cuối hàm.

       §  Gọi hàm : k=timkiem(f,x);

Nếu kết hợp với hàm printf  hay if  hay …… thì chỉ cần gọi timkiem(f,x) hàm khi gọi tương đương với 1 số kiểu int. Và 1 lưu ý nữa là có thể thay x bằng số trực tiếp ví dụ tìm kiếm x=20 thì có thể thay x=20 lúc gọi hàm (timkiem(f,20)).

       ·         Hàm sắp xếp giảm.

voidsapxepgiam(node *f){

      node *p1,*p2;

      p1=f;

      while(p1->link!=NULL){

            p2=p1->link;

            while (p2!=NULL){

                  if (p1->info<p2->info){

                        int tg=p1->info;

                        p1->info=p2->info;

                        p2->info=tg;

                  }

                  p2=p2->link;

            }

            p1=p1->link;

      }

}

  §  Do hàm sắp chỉ đổi chỗ phần ruột chứ không đổi chỗ các mối nối nên không thay đổi các liên kết nên ta sử dụng hàm kiểu void và không cần trả về con trỏ f chứa địa chỉ ô đầu tiên. Hàm sử dụng giải thuật sắp xếp tuần tự.

        §  Gọi hàm: sapxepgiam(f);

         ·        Hàm main() Nếu tìm với số x cố định khác thì có thể thay đổi giá trị bôi vàng. Còn nếu tìm kiếm giá trị nhập từ bàn phím thì bạn cần khai thêm biến x. và làm lệnh nhập x. sau đó thay thế phần bôi vàng bằng x.

intmain()

{

      node *f=NULL,*l=NULL;

      int n;

      printf("\nNhap so phan tu n : ");

      scanf("%d",&n);

      f=nhapfifo(f,l,n);

      printf("\nDanh sach vua nhap :");

      xem(f);

      int k=timkiem(f,20);

      if(k!=0) printf("\nTim thay x=20 xuat hien tai vi tri %d",k);

      else printf("\nKhong tim thay x=20");

      printf("\nDanh sach sau khi sap xep giam");

      sapxepgiam(f);

      xem(f);

      getch();

}

Code cả bài c/c++ câu 1a.

#include <stdio.h>

#include <conio.h>

typedef struct node {

      int info;

      node *link;

};

voidxem(node *f){

      node *p=f;

      while (p!=NULL) {

            printf("%5d",p->info);

            p=p->link;

      }

}

node *nhapfifo(node *f,node *l,int n) {

      node *p=f;

      for(inti=0;i<n;i++) {

            p=new(node);

            printf("\nNhap phan tu thu %d  :  ",i+1);

            scanf("%d",&p->info);

            p->link=NULL;

            if(f==NULL){

                  f=p;

                  l=p;

            }

            else {

                  l->link=p;

                  l=p;

            }

      }

      return f;

}

inttimkiem(node *f,int x){

      int dem=0;

      node *p=f;

      while (p!=NULL){

            dem++;

            if (p->info==x) returndem;

            p=p->link;

      }

      return 0;

}

voidsapxepgiam(node *f){

      node *p1,*p2;

      p1=f;

      while(p1->link!=NULL){

            p2=p1->link;

            while (p2!=NULL){

                  if (p1->info<p2->info){

                        int tg=p1->info;

                        p1->info=p2->info;

                        p2->info=tg;

                  }

                  p2=p2->link;

            }

            p1=p1->link;

      }

}

intmain()

{

      node *f=NULL,*l=NULL;

      int n;

      printf("\nNhap so phan tu n : ");

      scanf("%d",&n);

      f=nhapfifo(f,l,n);

      printf("\nDanh sach vua nhap :");

      xem(f);

      int k=timkiem(f,20);

      if(k!=0) printf("\nTim thay x=20 xuat hien tai vi tri %d",k);

      else printf("\nKhong tim thay x=20");

      printf("\nDanh sach sau khi sap xep giam");

      sapxepgiam(f);

      xem(f);

      getch();

}

test câu 1a

Câu 1b. đề thi cấu trúc dữ liệu giải thuật (ctdlgt).

Mô tả khai báo cấu trúc dữ liệu của danh sách liên kết kiểu LIFO với mỗi phần tử chứa

      ·        masv (mã sinh viên do chứa chữ và số dạng xâu kí tự nên ta khai báo mảng kiểu char để lưu trữ char masv[20];).

      ·        hoten ( Họ và tên dạng xâu kí tự nên ta cũng khai báo dưới dạng mảng kiểu char char hoten[40];).

      ·        tuoi ( Tuổi dạng số nguyên với phạm vi không lớn nhỏ hơn 300 và lớn hơn 0 nên ta khai báo kiểu int  int tuoi;).

      ·        dmon1,dmon2, tb (điểm môn 1,2 và điểm trung bình là kiểu số thực ta khai báo kiểu float  floatdmon1,dmon2,tb;).

      ·        xl (xếp loại dạng xâu kí tự nên ta cũng khai báo dưới dạng mảng kiểu char char xl[15];).

Code c/c++.

typedef struct sinhvien

{

      char masv[20],hoten[40],xl[15];

      int tuoi;

      float dmon1,dmon2,tb;

      sinhvien *link;

};

sinhvien *f=NULL,*p;

Mong các bạn góp ý ở phía dưới. Nhớ bấm G+ ủng hộ