Cho số tự nhiên n <= 100. Hãy cho biết có bao nhiêu cách phân tích số n thành tổng của dãy số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là một cách.
Ví dụ: n =5 có 7 cách phân tích:
5 = 1+1+1+1+1
5 = 1+1+1+2
5= 1+1+3
5= 1+2+2
5= 1+4
5 = 2+3
5=5
(Lưu ý: n= 0 vẫn coi là một cách phân tích tổng các số nguyên dương( 0 là tổng của dãy rỗng).
Nhận xét:
Nếu gọi F[m,v] là số cách phân tích số v thành tổng các số nguyên dương <= m. Khi đó:
Các cách phân tích số v thành tổng các số nguyên dương <= m có thể chia làm 2 loại:
· Loại 1: Không chứa số m trong phép phân tích, khi đó số cách phân tích loại này chính là số cách phân tích số v thành tổng các số nguyên dương < m, tức là số cách phân tích số v thành tổng các số nguyên dương <= m -1 và bằng F[m-1,v].
· Loại 2: Có ít nhất một số m trong phép phân tích. Khi đó nếu trong phép phân tích ta bỏ đi số m đó thì ta sẽ được các cách phân tích số v-m bởi các số <= m.( Lưu ý điều này chỉ đúng khi không lặp lại tính hoán vị của một cách). Có nghĩa là về mặt số lượng, số cách phân tích loại này bằng F[m,v-m].
Trong trường hợp m>v thì rõ ràng chỉ có cách phân tích loại 1 , còn trong trường hợp m<=v thì sẽ có cả cách phân tích loại 1 và loại 2.
If( m>v) F[m,v] = F[m-1,v];
If( m<=v) F[m,v] = F[m-1,v] + F[m,v-m];
F[0,0] = 1 và F[0,v] = 0 với mọi v.
// Dem so cach phan tich so n
program Analyse1; {Bai toan phan tich so }
const
max = 100;
var
F: array[0..max, 0..max] of Integer;
n,m,v: Integer;
begin
Write(' n = ');ReadLn(n);
FillChar(F[0], SizeOf(F[0],0);
{ Khoi tao dong o cua bang F toan so 0}
F[0,0] := 1;
for m:= 1 to n do
{ Dung cong thuc tinh cac dong theo thu tu tu tren xuong duoi}
for v:= 0 to n do
{Cac phan tu tren mot dong thi tinh theo thu tu tu trai qua phai }
if v<m then F[m,v] := F[m-1,v]
else F[m,v] := F[m-1,v] + F[m,v-m];
WriteLn ( F[n,n],'Analyses');
{Cuoi cung F[n,n] la so cach phan tich }
end.
// DEM SO CACH PHAN TICH SO n
#include<iostream>
#define MAX 100
int main()
{
int n,m,v, F[MAX][MAX];
std::cin>>n;
for( m = 1;m<=n;++m)
F[0][m] = 0;
F[0][0] = 1;
for( m = 1; m <= n; ++m)
for( v = 0; v <= n; ++v)
{
if( m <= v)
{
F[m][v] = F[m-1][v] + F[m][v-m];
continue;
}
else
{
F[m][v] = F[m-1][v];
continue;
}
}
std::cout<<F[n][n]<<std::endl;
system("pause");
return 0;
}
CẢI TIẾN THỨ NHẤT:
Cách làm như trên có thể tóm tắt lại là: Khởi tạo dòng 0 của bảng, sau đó dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2,…. tới khi tính được hết dòng n. Có thể nhận thấy rằng sau khi đã tính xong dòng thứ k thì việc lưu trữ các dòng từ 0 tới dòng k-1 là không cần thiết bởi vì việc tính dòng k+1 chỉ phụ thuộc vào các giá trị lưu trữ trên dòng k.
Vậy ta có thể dùng 2 mảng một chiều : Mảng Current lưu dòng hiện thời đang xét cúa bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Curent được gán các giá trị tương ứng trên dòng 0.
Sau đó, dùng mảng Current tính mảng Next, mảng Next sau khi tính sẽ mang các giá trị tương ứng trên dòng 1.
Rồi lại gán mảng Curent := Next và tiếp tục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương ứng trên dòng 2,….
//DEM SO CACH PHAN TICH SO N
program Analyse2;
const
max = 100;
var
Current, Next: array[0...max] of Integer;
n,m,v: Integer;
begin
Write(' n = ');ReadLn(n);
FillChar(Current,Sizeof(Current),0);
Current[0] := 1;
{ Khoi tao mang Current}
{Quy uoc F[0,0] = 1;}
for m := 1 to n do
begin {Dung dong hien thoi Current }
for v := 0 to n do
if v < m then Next[v] := Current[v];
else Next[v] := Current[v] + Next[v-m];
Current := Next;
{Gan gia tri Current := Next tuc la bay gio lai luu cac phan tu tren dong m cua F}
end;
WriteLn(Current[n], 'Analyses');
end.
//DEM SO CACH PHAN TICH SO N
// CAI TIEN THU NHAT
#include<iostream>
#define MAX 100
int main()
{
int n,m,v, Current[MAX], Next[MAX];
std::cin>>n;
for( m =1;m<=n;++m)
Current[m] = 0;
Current[0] = 1;
for( m = 1; m<=n;++m)
{
for( v = 0; v<=n;++v)
{
if( m>v)
{
Next[v] = Current[v];
continue;
}
else
{
Next[v] = Current[v] + Next[v-m];
continue;
}
}
for( v = 0;v<=n;++v)
Current[v] = Next[v];
}
std::cout<<Current[n]<<std::endl;
system("pause");
return 0;
}
CẢI TIẾN THỨ NHẤT:
Cách làm như trên có thể tóm tắt lại là: Khởi tạo dòng 0 của bảng, sau đó dùng dòng 0 tính dòng 1, dùng dòng 1 tính dòng 2,…. tới khi tính được hết dòng n. Có thể nhận thấy rằng sau khi đã tính xong dòng thứ k thì việc lưu trữ các dòng từ 0 tới dòng k-1 là không cần thiết bởi vì việc tính dòng k+1 chỉ phụ thuộc vào các giá trị lưu trữ trên dòng k.
Vậy ta có thể dùng 2 mảng một chiều : Mảng Current lưu dòng hiện thời đang xét cúa bảng và mảng Next lưu dòng kế tiếp, đầu tiên mảng Curent được gán các giá trị tương ứng trên dòng 0.
Sau đó, dùng mảng Current tính mảng Next, mảng Next sau khi tính sẽ mang các giá trị tương ứng trên dòng 1.
Rồi lại gán mảng Curent := Next và tiếp tục dùng mảng Current tính mảng Next, mảng Next sẽ gồm các giá trị tương ứng trên dòng 2,….
//CAI TIEN LAI CACH 2
program Analyse3;
const
max = 100;
var
B: array[1..2,0..max] of Integer;
{Bang B chi gom 2 dong thay the cho 2 dong lien tiep cua bang phuong an}
n,m,v,x,y : Integer;
begin
Write('n = '); ReadLn(n);
{Truoc het, dong 1 cua bang B tuong ung voi dong 0 cua phuong an F, duoc dien co so quy hoach dong}
FillChar(B[1], SizeOf(B[1]),0);
B[1][0] := 1;
x := 1; {Dong B[x] dong vai tro la dong hien thoi cua bang phuong an}
y := 2; { Dong B[y] dong vai tro la dong ke tiep cua phuong an}
for m := 1 to n do
begin
{Dung dong x tinh dong y <=> Dung dong hien thoi trong bang phuogn an de tinh dong ke tiep}
for v:= 0 to n do
if v<m then B[y][v] := B[x][v];
else B[y][v] := B[x][v] + B[y][v-m];
x := 3 - x; y : 3 -y;
{Dao gia tri va y, tinh xoay lai}
end;
WriteLn(B[x][n],'Analyses');
end.
//Dem so cach phan tich so n
#include<iostream>
#define MAX 100
int main()
{
int x,y,n,m,v, B[3][MAX];
std::cin>>n;
for( m =1;m<=n;++m)
B[1][m] = 0;
B[1][0] = 1;
x = 1;
y = 2;
for( m =1; m <= n;++m)
{
for( v =0; v <= n;++v)
{
if( m > v)
{
B[y][v] = B[x][v];
continue;
}
else
{
// std::cout<<1;
B[y][v] = B[x][v] + B[y][v-m];
continue;
}
}
x = 3 - x;
y = 3 - y;
}
std::cout<< B[x][n]<<std::endl;
system("pause");
return 0;
}
CẢI TIẾN THỨ 2:
Ta vẫn còn cách tốt hơn nữa, tại mỗi bước ta chỉ cần lưu lại một dòng của mảng F và dùng chính dòng đó để tính dòng tiếp theo .
// program Analyse4;
const
max = 100;
var
L : array[0...max] of Integer; {Chi can luu 1 dong }
n,m,v : Integer;
begin
Write(' n = '); ReadLn(n);
FillChar(L, SizeOf(L),0);
L[0] := 1;
{ Khoi tao mang 1 chieu L luu dong 0 cua bang}
for m := 1 to n do { Dung L tinh lai chinh no}
for v := m to n do
L[v] := L[v] + L[v-m];
WriteLn( L[n], 'Analyse');
end.
// Dem so cach bieu dien n thanh tong cac so hang
#include<iostream>
#define MAX 100
int main()
{
int n,m,v, L[MAX];
std::cin>>n;
//Khoi tao gia tri cho mang L[ MAX ];
for( m =1;m<=n;++m)
L[m] = 0;
L[0] = 1;
for ( m = 1; m<=n;++m)
for ( v = m; v<=n; ++v)
{
L[v] += L[v-m];
}
std::cout<<L[n]<<std::endl;
system("pause");
return 0;
}
.png)
.png)
.png)
0 comments:
Post a Comment