dungnvBài toán phân tích số (đệ quy quay lui)
Friday, December 26, 2014
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>
int
x[31],t[31],n;
void
khoitao()
{
printf("\nNhap n = ");
scanf("%d",&n);
x[0]=1;
t[0]=0;
}
void xuat(int k)
{
printf("\n%d = ",n);
for (int
i=1;i<k;i++) printf(" %d + ",x[i]);
printf(" %d",x[k]);
}
void
phantich(int i)
{
for(int
j=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);
}
int
main()
{
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>
int
x[31],t[31],n;
void
khoitao(FILE *u)
{
fscanf(u,"%d",&n);
x[0]=1;
t[0]=0;
}
void xuat(int k,FILE *v)
{
fprintf(v,"\n%d = ",n);
for (int
i=1;i<k;i++) fprintf(v," %d + ",x[i]);
fprintf(v," %d",x[k]);
}
void
phantich(int i,FILE *v)
{
for(int
j=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);
}
int
main()
{
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.
All comments [ 4 ]
cho hỏi là tại sao t[i]=n tức là ( x[i]=n-t[i-1] ) v ạ?
@Unknown t[i] là tổng từ x[1] đến x[i]; t[i-1] = tổng(x[1]...x[i-1]) => t[i]=t[i-1]+x[i]=n => x[i]=n-t[i-1]
Bạn ơi cho mình hỏi nếu phân tích 1 số n thành tổng các ước khác 1 của m thì làm sao ạ?
vd: n=10,m=6 thì được
10= 2+2+2+2+2
10=2+2+3+3
10=2+2+6
cám ơn bạn nhiều
truyền vào lúc đệ quy tham số khác
Your comments