( Thuật toán quay lui)Bài toán phân tích số

Sưu tầm:


Cho một số nguyên dương n<=30 , hay tìm 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 là hoán vị của nhau chỉ tính là 1 cách.


Cách làm:


Ta sẽ lưu nghiệm trong mảng x, ngoài ra còn 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] + .... + x[3];


Khi liệt kê các dãy có tổng đúng bằng n, để tránh sự trùng lặp, ta đưa thêm điều kiện x[i -1]<=x[i];


Vì số phần tử của mảng x là không cố định nên thủ tục printResult phải có thêm tham số cho biết phải in ra bao nhiêu phần tử.


Thủ tục đệ quy sẽ thử các giá trị có thể nhận Attempt( i) của x[i] thỏa mãn x[i] >= x[i-1];


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


t[i -1] là tổng tất cả các phần tử từ x[1] đến x[i-1].


*  Khi t[i] = n ( tức là x[i] = n- t[i-1] thì in ra kết quả)
* Khi tìm tiếp x[i+1] không được nhỏ hơn x[i] và t[i+1] là tổng tất cả các phần tử từ  x[1] đến x[i+1] không được vượt quá n.
  Ta có:


t[i+1] <= n


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


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


<=> x[i] <= ( n - t[i-1])/2


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


Vậy thủ tục Attempt(i) thử các giá trị cho x[i] có thể viết như sau:


( Để tổng quát cho i =1, ta gán x[0] := 1 và t[0] := 0)


* Xét các giá trị x[i] từ x[i-1] đến (n-x[i-1] ) div 2, cập nhật t[i] = t[i-1] + x[i] và gọi đệ quy tìm tiếp.
* Cuối cùng ta xét x[i] = n - t[i-1] và in ra kết quả từ x[1] đến x[i];

program Analyse;
const
     max = 100;
     InputFile = 'ANALYSE.INP';
     OutputFile = 'ANALYSE.OUT';
var
    n: Integer;
    x : array[0...max] of Integer;
    t : array[0...max] of Integer;
    f : Text;
    
procedure Init; {Khoi tao }
begin
    Assign( f,InputFile);Reset(f);
    ReadLn(f);
    Close(f);
    x[0] := 1;
    t[0] := 0;
    
end;

procedure printResult ( k: Integer);
var

    i: Integer;
begin
    WriteLn(f,n,' = ');
    for i:= 1 to k-1 do Write(f,x[i],'+');
    WriteLn(f,x[k]);
end;

procedure Attempt( i: Integer);
begin
var
    j : Integer;
    for j:= x[i-1] to (n-t[i-1])div 2 do
{Trong truong hop con chon tiep duoc x[i+1]}
       begin
          x[i] = j;
          t[i] = x[i] + t[i-1];
          Attempt(i+1);
       end;
    x[i] = n -t[i-1];
{ Neu x[i] la phan tu cuoi thi no bat buoc phai bang
n- t[i-1]}
    printResult(i);
end;

begin

Init;
Assign(f,OutputFile); Rewrite(f);
Attempt(1);
Close(f);

//Bai toan phan tich so n su dung quay lui
#include<iostream>
#include<fstream.h>
#define MAX 100
#define nMAX 30
// x[] de luu cac gia tri thoa man ma tong cac phan tu bang n
// t[i] la tong cac phan tu tu x[0] den x[i]
void Init(int x[],int t[])
{
     x[0] = 1;
     t[0] = 0;
}

void printResult(int k ,int x[]) // k la so phan tu cua mang x[]
{
     for( int i =1;i<k;++i)
     std::cout<<x[i]<<" + ";
     std::cout<<x[k]<<std::endl;
}

void Attempt( int i,int n, int x[], int t[])
{
     int y = (n-t[i-1])>>1;
     for( int j = x[i-1];j<= y;++j)
     {
          x[i] = j;
          t[i] = t[i-1] + x[i];
          Attempt(i+1,n,x,t);
     }
      x[i]  = n - t[i-1]; 
      //Neu x[i] la phan tu cuoi thi x[i] phai bang n - t[i-1]
      printResult(i,x);
     
}
     


int main()
{
    fstream f;
    f.open("ANALYSES.txt");
    int n,x[MAX],t[MAX];
    f>>n;
    Init(x,t);
    Attempt(1,n,x,t);
    
    f.close();
    system("pause");
    return 0;
}