Dãy con có tổng bằng s python

Đặt L[i, t] = 1 nếu có thể tạo ra tổng bằng t từ dãy con gồm các phần tử nằm trong dãy từ A1 -> Ai và ngược lại L[i, t] = 0. Nếu L[n, S] = 1 thì ta có thể tạo ra dãy con có tổng bằng S từ A1 -> AN.

Ta có thể tính L[i, t] theo công thức: L[i, t] = 1 nếu L[i-1, t] = 1 hoặc L[i-1, t-a[i]] = 1.

Cài đặt:

Nếu áp dụng luôn công thức trên ta cần dùng mảng 2 chiều. Ta có thể nhận xét rằng để có thể tính dòng thứ i, ta chỉ cần dòng i-1. Bảng phương án khi đó chỉ cần mảng 1 chiều L[0…S] và được tính như sau:

L[t] = 0; L[0] = 1;

for [int i=1;i=a[i];t–]

if [L[t]==0 && L[t-a[i]] ==1] L[t] = 1;

Dễ thấy độ phức tạp của cách cài đặt là O[m], độ phức tạp của thuật toán là O[n*m], m là tổng của n số.

Bài 03: Viết một chương trình C++ tính giai thừa của một số bằng cách không sử dụng đệ quy và có sử dụng đệ quy.

Gợi ý:

• Sử dụng đệ quy
• Không sử dụng đệ quy

Code mẫu: Tính giai thừa trong C++ không sử dụng đệ quy.

/**
 * Tinh giai thua KHONG dung phuong phap de quy
 *  
 * @author viettuts.vn
 */

#include 
 
using namespace std;

/**
 * tinh giai thua
 * 
 * @author viettuts.vn
 * @param n: so nguyen duong
 * @return giai thua cua so n
 */
long tinhGiaithua[int n] {
 int i;
    long giai_thua = 1;
    if [n == 0 || n == 1] {
        return giai_thua;
    } else {
        for [i = 2; i