Quy hoạch động trạng thái

Giải bài toán chu trình Hamilton theo phương pháp quy hoạch động trạng thái.

Tham khảo:
http://en.wikipedia.org/wiki/Dynamic_programming

Dãy con tăng dài nhất bản khó (O(NlogN))

Tương tự như version1 của nó chỉ khác nhau chỗ tìm j<i sao cho f[j] lớn nhất mà a[j]<a[i] thôi. Ở đây ta áp dụng tìm kiếm nhị phân trong việc tìm kiếm j. Do đó thuật toán có độ phức tạp O(NlogN).
Solution C++:

#include <vector>
using namespace std;
 
/* Finds longest strictly increasing subsequence. O(n log k) algorithm. */
void find_lis(vector<int> &a, vector<int> &b)
{
 vector<int> p(a.size());
 int u, v;
 
 if (a.empty()) return;
 
 b.push_back(0);
 
 for (size_t i = 1; i < a.size(); i++) 
        {
                // If next element a[i] is greater than last element of current longest subsequence a[b.back()], just push it at back of "b" and continue
  if (a[b.back()] < a[i]) 
                {
   p[i] = b.back();
   b.push_back(i);
   continue;
  }
 
                // Binary search to find the smallest element referenced by b which is just bigger than a[i]
                // Note : Binary search is performed on b (and not a). Size of b is always <=k and hence contributes O(log k) to complexity.    
  for (u = 0, v = b.size()-1; u < v;) 
                {
   int c = (u + v) / 2;
   if (a[b[c]] < a[i]) u=c+1; else v=c;
  }
 
                // Update b if new value is smaller then previously referenced value 
  if (a[i] < a[b[u]]) 
                {
   if (u > 0) p[i] = b[u-1];
   b[u] = i;
  } 
 }
 
 for (u = b.size(), v = b.back(); u--; v = p[v]) b[u] = v;
}
 
/* Example of usage: */
#include <cstdio>
int main()
{
 int a[] = { 1, 9, 3, 8, 11, 4, 5, 6, 4, 19, 7, 1, 7 };
 vector<int> seq(a, a+sizeof(a)/sizeof(a[0])); // seq : Input Vector
 vector<int> lis;                              // lis : Vector containing indexes of longest subsequence 
        find_lis(seq, lis);
 
        //Printing actual output 
 for (size_t i = 0; i < lis.size(); i++)
  printf("%d ", seq[lis[i]]);
        printf("\n");    
 
 return 0;
}

Hay:

#define index_of(as,x) distance(as.begin(),lower_bound(as.begin(),as.end(),x))

#define inf 99999999

vector<int> lis_fast(const vector<int>& a){

            const int n=a.size();

            vector<int> A(n,inf);

            vector<int> id(n);

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

                        id[i]=index_of(A,a[i]);

                        //cout << id[i] << endl; system("pause");

                        A[ id[i] ]=a[i];

            }

            int m=*max_element(id.begin(),id.end());

            vector<int> b(m+1);

            for(int i=n-1;i>-1;i--)

                if(id[i]==m) b[m--]=a[i];

            return b;

}

Tham khảo: http://en.wikipedia.org/wiki/Longest_increasing_subsequence
http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

Dãy con tăng dài nhất. O(N^2)

Vấn đề:
Cho dãy số a1,a2,..an. Dãy con là một dãy sao cho ai1,ai2,...,aij; trong đó i1 < i2 < ij và ai1,ai2,...,aij phải có mặt trong dãy a1,a2,...,an ban đầu. Hãy tìm dãy con tăng dài nhất.
Lời giải tham khảo:
Gọi f[i] là dãy con tăng dài nhất khi xét dãy a1,a2,...,ai mà  ai là phần tử cuối cùng của dãy con.

• f[0] = 0;
• Tìm j<i sao cho f[j] lớn nhất mà a[j] < = a[i]. Nếu không tìm thấy thì j =0;
• f[i] = f[j] + 1
•  result = max (F[i]), i=1,...,N.

Độ phức tạp thuật toán O(N^2).
Áp dụng các bạn giải bài tập sau trên hệ thống vnoi:
Link: http://vnoi.info/index.php?option=com_voj2&page=problem&problem=LIQ#tab_statement

Cho một dãy số nguyên gồm N phần tử A[1], A[2], ... A[N].
Biết rằng dãy con tăng đơn điệu là 1 dãy A[i₁],... A[i_k] thỏa mãn
i₁ < i₂ < ... < i_k và A[i₁] < A[i₂] < .. < A[i_k]. Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử?

Download test và solution (C/C++, Pascal) tại đây.

Input

• Dòng 1 gồm 1 số nguyên là số N (1 ≤ N ≤ 1000).
• Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Ví dụ

Input:
6
1 2 5 4 6 2 

Output:
4

Giải thích test ví dụ: Dãy con dài nhất là dãy A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài dãy này là 4.

Gợi ý: Sử dụng phương pháp Quy Hoạch Động. F[i]: Độ dài dãy con đơn điệu tăng dài nhất mà phần tử cuối cùng là số A[i] này.

Code:
DevC:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int N;
int a[1001];
int f[1001];

int main()
{
scanf("%d",&N);
for(int i=1;i<=N;i++)
scanf("%d",&a[i]);
f[1] = 1;
for(int i=2;i<=N;i++)
{
int temp = 0;
for(int j=1;j<i;j++)
if(a[j]<a[i]&&temp<f[j]) temp = f[j];
f[i] = temp + 1;
}
int res = -1;
for(int i=1;i<=N;i++)
{
res = max(res,f[i]);
}
printf("%d",res);
//system("pause"); dừng lại để xem kết quả.
return 0;
}

Free pascal:

var

    N,i,res,temp,j:longint;

    a,f:array[1..1001]of longint;

begin

    readln(N);

    for i:=1 to N do

        read(a[i]);

    f[1]:=1;

    for i:=2 to N do

        begin

            temp:=0;

            for j:=1 to i-1 do

                if((a[j]<a[i]) and (f[j]>temp)) then

                    temp:=f[j];

            f[i]:=temp+1;

        end;

    res:=0;

    for i:=1 to N do

        if(res<f[i]) then res:=f[i];

    writeln(res);

end.

Tham khảo: http://en.wikipedia.org/wiki/Longest_increasing_subsequence

Bài tập cơ bản về số học (Dành cho cấp hai)

Bài 1: Số hoàn chỉnh là số có tổng các ước (không kể nó) bằng chính nó . Liệt kê các số hoàn chỉnh nhỏ hơn  hoặc bằng N. N<=10000000. Vào từ file Perfect.INP chỉ có một dòng chứa số N. Dữ liệu ra trong file Perfect.OUT như sau: dòng đầu ghi ra tổng các số hoàn chỉnh nhỏ hơn hoặc bằng N, các dòng sau liệt kê các số hoàn chỉnh. mỗi số trên một dòng.

Solution (free pascal):

program Perfect;
var
    N:longint;
    fi,fo:text;

(*Check number perfect*)
function IsPerfect(num:longint):boolean;
var
    i:longint;
    sum:longint;
    num_:longint;
begin
    sum:=1;
    num_:=num;
    i:=2;
    while(i*i<=num) do
        begin
            if((num mod i)=0) then
                begin
                    sum :=sum+ i;
                    sum :=sum+(num div i);
                end;
            i :=i+ 1;
        end;
    if sum = num_ then
        IsPerfect:=true
    else
        IsPerfect:=false;
    (*
    writeln('num=',num_,'sum=',sum);
    readln;
    *)
end;

begin
    assign(fi,'Perfect.INP');reset(fi);
    assign(fo,'Perfect.OUT');rewrite(fo);
    read(fi,N);
    (*write(N);*)
    while N>1 do
        begin
            if(IsPerfect(N)) then
                writeln(fo,N);
            N:=N-1;
        end;
    (*readln;  *)
    close(fi);
    close(fo);
end.

Xâu con chung dài nhất

Phương pháp quy hoạch động giải bài toán xâu con chung dài nhất:

1. Bài toán:

Xâu ký tự X được gọi là xâu con của xâu ký tự Y nếu ta có thể xoá đi một số ký tự trong xâu Y để được xâu X.

Cho biết hai xâu ký tự A và B, hãy tìm xâu ký tự C có độ dài lớn nhất và là con của cả A và B.

Input

Dòng 1: chứa xâu A

Dòng 2: chứa xâu B

Output

Chỉ gồm một dòng ghi độ dài xâu C tìm được

Example

Input:

abc1def2ghi3

abcdefghi123

Output:

10

Link: http://vn.spoj.pl/problems/QBSTR/

2. Tiếp cận bài toán:

Định nghĩa xâu con của một xâu: một xâu X có dộ dài l là xâu con của xâu Y có độ dài m khi có một dãy c sao cho 1<=c[1]<=c[2]<=c[3]<…<=c[i]<=…c[l]<=m, và X[c[i]]=Y[c[i]], mọi 1<=i<=l. Nói một cách khác, từ xâu gốc ta xóa đi các kí tự tại các vị trí tùy ý, các kí tự còn lại được dồn lại kề nhau và vẫn bảo toàn thứ tự.

Ví dụ: Có xâu X: abcdfr. Các xâu con có thể là a, ab,  bc, bd, dfr, abcdfr,…Các xâu không phải xâu con là ba,cda,…

Để giải quyết bài toán này đầu tiên, ta xét bài toán đơn giản hơn.

Bài toán 1: Có 2 xâu, một xâu có m kí tự, xâu còn lại không có kí tự nào. Với bài toán này dễ thấy độ dài xâu con chung dài nhất là 0 (không có xâu nào).

Bài toán 2: Có hai xâu, mỗi xâu có đúng một kí tự.

Ví dụ 2.1: xâu X: a, xâu Y: b. Dễ thấy độ dài xâu con chung dài nhất là 0, vì không có xâu nào thỏa mãn.

Ví dụ 2.2: xâu X: a, xâu Y: a. Dễ thấy độ dài xâu con chung dài nhất là 1, xâu con chung khi đó là xâu có một kí tự a.

Bài toán 3: Có hai xâu, xâu X là: abc1def2ghi3, xâu Y là: abcdefghi123. Làm thế nào để có đáp án.

Ta giả sữ đã biết cấu trả lời trong trường hợp xâu X có độ dài i-1 kí tự đầu tiên, xâu Y có độ dài j-1 kí tự đầu tiên, khi đó đáp án trong trường hợp xâu X có độ dài i kí tự đầu tiên, xâu Y có độ dài j kí tự

đầu tiên thì sao? F[i-1][j-1],f[i-1][j],f[i][j-1] đã biết, F[i][j]=?.

Xâu X: x1x2…xi-1xi

Xâu Y: y1y2…yj-1yj

Ta có các trương hợp sau:

TH1: xi=yj, như vậy thì f[i][j]=f[i-1][j-1]+1.

Th2: xi!=yj, f[i][j]=max(f[i-1][j],f[i][j-1]).

Các bạn vẽ bảng sau:

	1	2	3	4	j-1	j	7	8	9	10	11	12
1
2
3
4
5
i-1					F[i-1][j-1]	F[i-1][j]
i					F[i][j-1]	F[i][j]
8
9
10
11
12

Tính như thế nào? Trong bài này ta tính từng dòng, nghĩa là ta tính hết f[i-1][j], thì sau đó ta mới f[i][j], mọi j.

Trên một dòng muốn tính f[i][j] thì trước hết ta phải tính f[i][j-1].

3.Code:

/*Code được cài trên IDE DevC++*/

#include<iostream>

#include<algorithm>

#include<cstring>

#define maxS 1001

using namespace std;

char a[maxS],b[maxS];

int f[maxS][maxS];

int main(){

    // Doc du lieu

    scanf("%s",&a);

    scanf("%s",&b);

    // Khoi tao mang f

    memset(f,0,sizeof(f));

    int da=strlen(a);

    int db=strlen(b);

    int i,j;

    for(i=1;i<=da;++i)

    for(j=1;j<=db;++j)

        if(a[i-1]==b[j-1]) f[i][j]=f[i-1][j-1]+1;

        else f[i][j]=max(f[i-1][j],f[i][j-1]);

    // Ket qua o f[da][db]

    printf("%d",f[da][db]);   

    return 0;   

}

4. Độ phức tap:

O(m*n) về xử lý.

O(m*n) không gian lưu trữ.

5. Ghi chú:

Code trên đã test trên vn.spoj.pl. Các bạn chú ý tài liệu trên mình biên soạn chỉ dành cho CLB thuật toán khoa CNTT đại học Nha Trang.

Tham khảo:
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem