Đến nội dung


Hình ảnh

Tìm hệ thức truy hồi cho số các xâu có độ dài n được tạo từ các phần tử của tập {a,b,c}, chưa hoặc các xâu con aa hoặc các xâu con bb?


  • Please log in to reply
Chủ đề này có 3 trả lời

#1 betty

betty

    Lính mới

  • Thành viên mới
  • 5 Bài viết

Đã gửi 16-04-2021 - 11:36

1. Tìm hệ thức truy hồi cho số các xâu có độ dài n được tạo từ các phần tử của tập {a,b,c}, chưa hoặc các xâu con aa hoặc các xâu con bb?

2. Tìm hệ thức truy hồi cho xâu có độ dài n (n >4 ) được tạo từ các phần tử của tập {x,y,z,t} và không chứa các xâu con xx, yy, zz, tt?

Mọi người giúp em 2 câu trên với ạ!! Em cảm ơn.



#2 Nobodyv3

Nobodyv3

    Binh nhì

  • Thành viên mới
  • 14 Bài viết
  • Giới tính:Không khai báo
  • Sở thích:Error Version of Titu

Đã gửi 16-04-2021 - 21:43

1. Tìm hệ thức truy hồi cho số các xâu có độ dài n được tạo từ các phần tử của tập {a,b,c}, chưa hoặc các xâu con aa hoặc các xâu con bb?
2. Tìm hệ thức truy hồi cho xâu có độ dài n (n >4 ) được tạo từ các phần tử của tập {x,y,z,t} và không chứa các xâu con xx, yy, zz, tt?

1/ Gọi $A_{n},B_{n},C_{n} $ lần lượt là tập các xâu kích thước $n$ thỏa đề bài và tận cùng là $a, b, c$. Như vậy số các xâu thỏa yêu cầu là $S_{n}=\left | A_{n} \right |+\left | B_{n} \right |+\left | C_{n} \right |$.
Ta có:
$\left | C_{n} \right |=\left | A_{n-1}\right | +\left | B_{n-1}\right | +\left | C_{n-1}\right | $
$\left | A_{n} \right | =\left | B_{n-1}\right | +\left | C_{n-1}\right |$
$\left | B_{n} \right |=\left | A_{n-1}\right |+\left | C_{n-1}\right |$
Công vế với vế:
$S_{n} =2S_{n-1} +\left | C_{n-1}\right |=2S_{n-1}+(\left | A_{n-2}\right | +\left | B_{n-2}\right | +\left | C_{n-2}\right | )$ hay ta có hệ thức truy hồi:
$S_{n} =2S_{n-1}+S_{n-2},n \geq 3 $

2/ Lâp luận tương tự bài 1/, ta có:
$\left | X_{n} \right | =\left |Y_{n-1} \right | +\left |Z_{n-1} \right | +\left |T_{n-1} \right | $
$\left | Y_{n} \right | =\left |X_{n-1} \right | +\left |Z_{n-1} \right | +\left |T_{n-1} \right | $
$\left | Z_{n} \right | =\left |X_{n-1} \right | +\left |Y_{n-1} \right | +\left |T_{n-1} \right | $
$\left | T_{n} \right |=\left |X_{n-1} \right | +\left |Y_{n-1} \right | +\left |Z_{n-1} \right | $
Cộng vế với vế:
$S_{n} =3(\left |X_{n-1} \right | +\left |Y_{n-1} \right | +\left |Z_{n-1} \right | +\left |T_{n-1} \right | ) $ hay ta có HTTH :
$S_{n} =3S_{n-1},n \geq 2 $

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 17-04-2021 - 15:10


#3 betty

betty

    Lính mới

  • Thành viên mới
  • 5 Bài viết

Đã gửi 19-04-2021 - 15:21

 

Ý 1 hình như cách giải đó là không chứa xâu con aa và bb, chứ không phải là hoặc chứa aa, hoặc chứa bb. Anh giải sai rồi hay sao ạ


Bài viết đã được chỉnh sửa nội dung bởi betty: 19-04-2021 - 15:22


#4 Nobodyv3

Nobodyv3

    Binh nhì

  • Thành viên mới
  • 14 Bài viết
  • Giới tính:Không khai báo
  • Sở thích:Error Version of Titu

Đã gửi 21-04-2021 - 15:01

Ý 1 hình như cách giải đó là không chứa xâu con aa và bb, chứ không phải là hoặc chứa aa, hoặc chứa bb. Anh giải sai rồi hay sao ạ

Hihi, Lỡ rồi thì mình tính phần bù vậy:
$N_{n}=3^{n}-S_{n}=3^{n} -\left ( 2S_{n-1}+S_{n-2} \right )$, giá trị khởi tạo :$S_{1}=3,S_{2}=7$

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 21-04-2021 - 15:19





1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh