Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự




Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 1 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Tại sao phải chuyển các bài toán tổ hợp về hệ thức truy hồi bởi các lý do sau:

    1. Tổ hợp rất dễ nhầm lẫn, hay bỏ sót
    2. [You must be registered and logged in to see this link.]
    Ở đây đưa ra một số bài toán mẫu, có thể áp dụng luôn cách làm vào các bài thi. Rất hay.

    1. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có 3 bit 0 liên tiếp.

    Đặt Sn là số chuỗi nhị phân độ dài n, có 3 bit 0 liên tiếp:
    Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
    A1 ( A là chuỗi có độ dài n -1, A chứa 3 bit 0 liên tục) , gọi số cách là S(n-1)
    B10 (B là chuỗi có độ dài n - 2, B chứa 3 bít 0 liên tục), gọi số cách là S(n-2)
    C100 (C là chuỗi có độ dài n - 3, C chứa 3 bít 0 liên tục, gọi số cách là S(n-3)
    D000 (D là chuỗi tùy ý dài n - 3), số cách tính được luôn là 2(n-3)

    Ta có công thức truy hồi:
    Sn=S(n-1)+S(n-2)+S(n-3)+2(n-3)
    Khởi tạo:
    S1 = S2 = 0; S3 = 1.

    2. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n không có 3 bit 0 liên tiếp.
    Đặt Sn là số chuỗi nhị phân độ dài n, không có 3 bit 0 liên tiếp:
    Một chuỗi dài n (n>3) thoả mãn điều kiện đầu bài sẽ thuộc một trong các dạng sau:
    A1 (A là chuỗi có độ dài n - 1, không có 3 bit 0 liên tiếp), gọi số cách là S(n-1)
    B10 (B là chuỗi có độ dài n - 2, không có 3 bit 0 liên tiếp), gọi số cách là S(n-2)
    C100 (C là chuỗi có độ dài n - 3, không có 3 bit 0 liên tiếp), gọi số cách là S(n-3)

    Nên ta có hệ thức truy hồi:
    Sn=Sn-1 + Sn-2 + Sn-3
    Khởi tạo: S1 = 2, S2 = 4, S3 = 7

    3. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có chứa chuỗi con 01.

    Đặt Sn là số chuỗi nhị phân có chứa chuỗi con 01 (*) ta suy ra ngay số chuỗi nhị phân không chứa chuỗi con 01 là 2n-Sn (**)
    Chuỗi nhị phân có chứa chuỗi con 01, thuộc 1 trong 2 dạng:
    Ax (A là chuỗi có độ dài n - 1, A chứa chuỗi con 01, x = 0 hoặc 1) gọi số cách là S(n-1), nhưng do x có 2 trạng thái 0 và 1, nên nhớ phải nhân 2.
    B01 (B là chuỗi có độ dài n - 2, B không chứa chuỗi 01) lập luận như (**) thì B là 2(n-2)-Sn-2

    Ta có hệ thức truy hồi:
    Sn=2 Sn-1 + (2(n-2)-Sn-2)
    hay Sn = 2 Sn-1 - Sn-2 + 2(n-2)
    Giá trị khởi tạo: S1 = 0;S2 = 1

    Thực ra Sn có thể tính dễ dàng không truy hồi như sau:
    Chuỗi không thỏa mãn (*) chỉ có thể có dạng: 111...111000...000 số chuỗi thế này = n+1
    Suy ra:
    Sn=2n-(n+1)

    4. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số cách đi lên n bậc thang nếu có thể đi 1, 2 hoặc 3 bước một lần.

    Muốn bước lên tới bậc n(n>3) có 3 cách:
    Bước tới bậc thứ n-1, rồi bước 1 bậc để lên n
    Bước tới bậc thứ n-2 rồi bước 2 bậc để lên tới n
    Bước tới bậc thứ n-3 rồi bước 3 bậc để lên tới n
    Vậy ta xậy dựng được:
    Sn = Sn-1 + Sn-2 + Sn-3
    Khởi tạo:
    S1=1;
    S2=2;
    S3=3;

    5. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi nhị phân độ dài n có một số chẵn bit 0.
    Gọi Sn là số chuỗi có số chẵn bit 0
    Gọi Kn là số chuỗi có số lẻ bít 0
    Ta có Sn + Kn = 2n
    Một chuỗi dài n có số chẵn bit 0, được thành lập bằng 2 cách
    * Chuỗi số chẵn bít 0 có độ dài n-1, thêm 1
    * Chuỗi số lẻ bít 0 có độ dài n-1, thêm 0
    Ta có hệ thức sau:
    Sn=S(n-1)+K(n-1)

    Tương tự ta có:
    Kn = S(n-1) + K(n-1)
    Suy ra: Sn = Kn
    Hay hệ thức truy hồi là:
    Sn = 2S(n-1)
    Với giá trị khởi tạo :
    S1=1

    [You must be registered and logged in to see this link.]


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    6. Tìm hệ thức truy hồi mà Rn thoả mãn, trong đó Rn là số miền của mặt phẳng bị phân chia bởi n đường thẳng nếu không có hai đường nào song song và không có 3 đường nào cùng đi qua một điểm.

    Trên mặt phẳng có n (Với n>1) đường thẳng đôi một cắt nhau và không có 3 đường đồng quy. Ta thấy rằng cứ mỗi đường thẳng bị n - 1 đường còn lại chia làm n phần. Bởi vậy nếu ta bỏ đi một đường bất kì thì khi mất n phần này, 2 mặt miền 2 bên lập tức họp lại làm một, điều đó nghĩa là nếu bỏ đi 1 đường thẳng thì số miền bị mất đi là n:

    Tức là
    Rn = n + Rn-1,
    R1 = 2.
    Giải hệ truy hồi này để dễ dạng có được công thức
    Rn = n(n + 1)/2 + 1


    7. Tìm hệ thức truy hồi và điều kiện khởi tạo để tính số chuỗi ký tự gồm A, B, C có độ dài n chứa hai kí tự liên tiếp giống nhau.

    Gọi Sn là số chuỗi thỏa mãn: Có chưa 2 kí tự liên tiếp giống nhau (*)
    thì số chuỗi không thỏa mãn (*) là 3n - Sn
    Chuỗi thỏa mãn có 1 trong 2 dạng:

    * Mx (M thỏa (*), x có 3 cách)
    * Nxx (Nx không thỏa (*))

    → Sn = 3 Sn - 1 + (3n-1 - Sn - 1) = 2 Sn - 1 + 3n-1

    Khởi tạo: S1 = 0,
    S2 = 3

    Có thể giải không truy hồi như sau:

    Đầu tiên tìm số chuỗi không có 2 kí tự liên tiếp bằng nhau:
    Chọn kí tự đầu tiên có 3 cách, kí tự tiếp theo có 2 cách (Trừ kí tự trước nó)
    Vậy tất cả có: 3. 2n-1 cách
    → Sn = 3n - 3. 2n-1

    8. Cho dãy S = {Sn}, Sn là số chuỗi n bit không chứa mẫu 00.
    a) Tìm hệ thức truy hồi và các điều kiện khởi tạo cho dãy {Sn}
    b) Chứng tỏ Sn = fn+1, n = 1, 2, … với f là dãy Fibonacci.

    Giải

    a) Chuỗi dài n thỏa mãn không chứa 00 thì có một trong 2 dạng
    * A1 (A không chứa mẫu 00)
    * B10 (B không chứa mẩu 00)

    Vậy có hệ thức truy hồi:
    Sn = Sn-1 + Sn-2
    S1 = 2 (0;1),
    S2 = 3 (01;10;11)

    b)
    Quy nạp:

    S1 = f2; S2 = f3 đúng.

    Giả sử đúng đến n - 1
    tức là Sk = fk+1, mọi k = 1.. n - 1

    → Sn = Sn-1 + Sn-2 = fn + fn-1 = fn+1

    Vậy Sn = ffn+1 mọi n = 1, 2, 3,..

    9. Tìm hệ thức truy hồi và điều kiện khởi tạo cho số cách đóng cặp ngoặc đơn trong biểu thức
    a1 * a2 * … * an, Với n ≥ 2.

    Nếu chỉ có một ngoặc thì một cách đóng cho biểu thức dài n = a1 * a2 * … * an
    Gọi công thức tính số cách đóng cặp ngoặc là Sn với n>2:

    Một cách đóng sẽ có 1 trong 2 dạng
    * Aan, với cặp ngoặc nằm trong A, A có độ dài n - 1, Sn-1 cách
    * Aan), dấu mở ngoặc nằm ở A, có n - 1 cách.

    → Sn = Sn-1 + n - 1
    S2 = 1;
    S3 = 3
    S4 = 3 + 3 = 6

    Giải hệ hồi quy dễ tính được
    Sn = (n - 1) + (n - 2) +.. + 3 + 2 + 1 = n(n - 1)/2

    Thực ra bài này có thể giải đơn giản, một cách đóng ngoặc chính là một tổ hợp chập 2 của n phần tử, đáp số là Cn2 = n(n - 1)/2

    10. Gọi an là số các chữ số 0 có trong các số tự nhiên từ 0 đến 10n - 1.
    a)Chứng tỏ rằng an thoả mãn hệ thức truy hồi an = a(n - 1) + 9 * (n - 1) * 10n-2
    b)Biết giá trị đầu a1 = 1, giải hệ thức truy hồi trên.

    Giải

    a)
    Gọi Kn (n>0) là số các chữ số 0 có trong các số tự nhiên từ 10n-1 đến 10n - 1 (Tức có đúng n chữ số, chữ số đầu tiên bên trái khác 0)
    Ta sẽ đi chứng minh Kn = 9(N - 1). 10n-2
    Một số có n chữ số sẽ có dạng Ax, trong đó A có n - 1 chữ số và x = 0.. 9
    Kn là số các số 0 trong các số dạng Ax
    Số các số 0 trong Ax bằng 10 lần số các số 0 trong A cộng thêm các số 0 trong x.
    Số các số 0 trong A thì bằng 10 lần số các số Kn-1 (Vì Ax, x có 10 cách chọn)
    Số các số 0 ở dạng A0 thì bằng số các số dạng A, số đầu khác 0 nên số cách chọn là 9. 10n-2

    Vậy rốt cuộc ta có công thức:
    Kn = 10. Kn-1 + 9. 10n-2, từ đây dễ dàng quy nạp được
    Kn = 9(n - 1). 10n-2
    (vì 10. 9(n - 2). 10n-3 + 9. 10n-2 = 9(n - 1). 10n-3 )

    Mặt khác an = An-1 + Kn
    (chia từ 1 đến 10n - 1 thành 2 đoạn, từ 1 đến 10n-1 - 1 và 10n-1 đến 10n - 1. )

    Vậy ta có hệ thức truy hồi:
    An = An-1 + 9(N - 1). 10n-2

    b) Ta có:
    an = 9(n - 1). 10n-2 + 9(n - 2). 10n-3 +... + 9. 1. 10o + Ao (Ao = 1)
    xn - 1 = (x - 1) (xn-1 + xn-2 +... + x2 + x + 1)
    (xn - 1)/(x - 1) = (xn-1 + xn-2 +... + x2 + x + 1)

    Đạo hàm 2 vế

    (n. xn-1. (x - 1) - (xn - 1))/(x - 1)2
    = (n - 1… + (n - 2). xn-3 +... + 2x + 1

    Thay x = 10 ta có:
    (n. 10n-1. 9 - (10n - 1))/92 = (n - 1). 10n-2 + (n - 2). 10n-3 +.. + 2. 10 + 1
    → an = (n. 10n-1. 9 - (10n - 1))/9 + 1
    = n. 10n-1 - (10n - 1)/9 + 1

    11. Gọi an là số dãy bit độ dài n không có 2 bit 0 kề nhau.
    a)Tìm hệ thức truy hồi cho an
    b)Biết giá trị đầu a1 = 2, a2 = 3, giải hệ thức truy hồi trên.

    Một dãy độ dài n không có 2 bit 0 kề nhau thì có 1 trong 2 dạng
    * A10 (A có n - 2 bit và không có 2 bit 0 kề nhau)
    * B1 (B có n - 1 bít và không có 2 bit 0 kề nhau)

    Vậy suy ra
    an = a(n - 1) + a(n - 2)
    a1 = 2;
    a2 = 3

    Dãy này bắt đầu từ a1 = 2 là dãy Fibonaci
    Giải truy hồi bằng cách xét nghiệm của phương trình đặc trưng
    x2 = x + 1
    x1 = (1 + √5)/2;
    x2 = (1 - √5)/2
    an = c1. x1n + c2. x2n

    Thay n = 1, 2 vào tìm c1, c2 (Khách viếng thăm tự thực hiện)

    12. Gọi an là số dãy bit độ dài n có 2 bit 0 kề nhau.
    a) Tìm hệ thức truy hồi cho an
    b) Biết giá trị đầu ao = 0 và a1 = 0, tính số dãy bit độ dài 7 có 2 bit 0 kề nhau.

    a)Một số có 2 bít 0 kề nhau thuộc 1 trong 3 dạng
    * A00 (A bất kì dài n - 2, số trường hợp là 2n-2)
    * B10 (B chứa 2 bít 0 liền nhau dài n - 2, số trường hợp là an-2)
    * C1 (C chứa 2 bít 0 liền nhau dài n - 1, số trường hợp là an-1)

    Vậy
    an = an-1 + an-2 + 2n-2

    b)
    ao = 0,
    a1 = 0
    → a2 = 0 + 0 + 20 = 1
    → a3 = 1 + 0 + 21 = 3
    → a4 = 3 + 1 + 22 = 8
    → a5 = 8 + 3 + 23 = 19
    → a6 = 19 + 8 + 24 = 43
    → a7 = 43 + 19 + 25 = 94


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Bài thầy cho sát đề:
    Cho dãy số xác định công thức truy hồi:
    an + 4an-1 - 21an-2 = 5.3n với n ≥ 2 và ao = 1, a1 = 2.

    1. Tính giá trị a7

    2. Tìm công thức tường minh biểu diễn an


    Bài này ta làm phần 2 trước.
    Ta viết lại công thức truy hồi cho giống tổng quát, làm cho dễ
    an = - 4an-1+ 21an-2 + 5.3n (*)

    Theo định lý 5.
    Bước 1. Chia làm 2 phần ta có:
    AH = - 4an-1+ 21an-2
    AP = 5.3n

    Bước 2. an(h) là nghiệm của phương trình:
    r2 + 4r - 21 = 0 (*)
    Hay → r1 = 3, r2 = -7.
    Theo định lý 1 của Hệ thức truy hồi thì:
    an(h) = α1(3)n + α2(-7)n

    Bước 3. Tìm nghiệm riêng an(p)
    - Xác định dạng của nghiệm riêng, do nghiệm riêng của phương trình (*) trùng với cơ số của AP 1 lần, nên nó phải có dạng : C.n.3n
    - Do nghiệm riêng thoả mãn phương trình hồi quy của định lý 5, nên thay vào và biến đổi tương ứng ta có:
    c.n.3n = (-4)c.(n-1).3n-1 + 21c.(n-2).3n-2 + 5.3n

    Hay:
    cn3n + 4c(n-1)3n-1 - 21c(n-2)3n-2 - 5.3n = 0;
    Chia cả 2 vế cho 3n-2 và chuyển c thành biến để tính sẽ được:
    30c - 45 =0 → c = 3/2

    Thay hệ số tìm được này vào dạng nghiệm riêng để có được an(p). Ta có:
    [You must be registered and logged in to see this image.]

    Bước 4. Thông báo dạng nghiệm của hệ thức là dạng:
    an = an(h) + an(p)
    Thay kết quả của bước 3 vào.
    Trường hợp cụ thể bài toán này ta có:
    an = an(h) + an(p)
    [You must be registered and logged in to see this image.]
    Thay vào các giá trị đầu mà đề bài cho ao = 1, a1 = 2 để tính các α
    ao = 1 = α1.3o + α2(-7)o - 5.3o + 0
    a1 = 2 = α1.31 + α2(-7)1 - 5.31 + (1.31+1)/2
    Giải cái này ra được:
    [You must be registered and logged in to see this image.]

    Vậy kết quả cần tìm là:
    [You must be registered and logged in to see this image.]

    Việc thay n = 7 do Khách viếng thăm tự thực hiện.



    Được sửa bởi Admin ngày Fri Jun 24, 2011 5:58 pm; sửa lần 1.


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Bạn nào nắm được căn cứ và cơ sở về nghiệm riêng của hệ thức truy hồi hồi quy không thuần nhất, định lý 5, thì nói rõ giúp 1 chút. Hiện tại chẳng biết căn cứ vào đâu để viết ra dạng nghiệm cả. Nhớ là căn cứ vào đâu. Yêu cầu thế nào, thì dạng nghiệm riêng thế nào. Được cái bảng tổng kết là tốt nhất. Google trên mạng chưa tìm thấy cái này. Các bạn Phan Việt, Phan Thị, Hà Thị, Mai Đình, Phan Quốc, Phạm Thái... kiểm tra xem ở Học viện KTQS đang căn cứ vào đâu để tính cái nghiệm riêng này nhé! Tài liệu ý. Thanks trước.

    Thanks LĐS đã có buổi làm việc chi tiết về vấn đề nghiệm riêng của hệ thức truy hồi hồi quy không thuần nhất, định lý 5. Đã cập nhật trong [You must be registered and logged in to see this link.].


    ================
    Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    khanhhuyenvo@gmail.com


    Thành viên ít chịu khó
    Thành viên ít chịu khó
    tren mot so tai leu khac bai giai cuoi cung tren co ket qua anfa 1= 1; anfa2 = 0 nhung o day ket qua lon vay.

    Sponsored content


    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 1 trang]

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Sosblogs