Đến nội dung

Hình ảnh

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 bậc thang nếu có thể đi 1 hoặc 2 bước một lần.

- - - - -

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

#1
duyphung2k

duyphung2k

    Lính mới

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

B1. 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 bậc thang
nếu có thể đi 1 hoặc 2 bước một lần.

 

B2 Trong một nhóm có 6 người, trong đó có 2 người là bạn hoặc là thù của
nhau. Chứng tỏ rằng luôn tìm được một nhóm có ba người là bạn hoặc là thù của
nhau

 

B3  Cho tập hợp X gồm 7 phần tử, X = {1, 2, 3, 4, 5, 6, 7}, anh (chị) hãy chỉ ra
cách tìm tập con kế tiếp của tập 4 phần tử {3, 4, 5, 7}

 

 

giải chi tiết giúp mình nhá :))


Bài viết đã được chỉnh sửa nội dung bởi duyphung2k: 24-05-2021 - 21:38


#2
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

B1. 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 bậc thang
nếu có thể đi 1 hoặc 2 bước một lần.

B2 Trong một nhóm có 6 người, trong đó có 2 người là bạn hoặc là thù của
nhau. Chứng tỏ rằng luôn tìm được một nhóm có ba người là bạn hoặc là thù của
nhau

B3 Cho tập hợp X gồm 7 phần tử, X = {1, 2, 3, 4, 5, 6, 7}, anh (chị) hãy chỉ ra
cách tìm tập con kế tiếp của tập 4 phần tử {3, 4, 5, 7}


giải chi tiết giúp mình nhá :))

B!: Gọi $a_{n}$ là số cách bước lên cầu thang $n$ bậc thỏa đề bài. Bắt đầu bước lên cầu thang ta có 2 TH:
- Đi 1 bậc: có $a_{n-1}$ cách.đi các bậc thang còn lại.
- Đi 2 bậc: có $a_{n-2}$ cách.đi các bậc thang còn lại.
Theo qui tắc cộng, ta có hệ thức truy hồi:
$a_{n}=a_{n-1}+a_{n-2}$; $n> 2$; đk khởi tạo: $a_{1}=1, a_{2}=1$

B2: Để dễ hình dung ta biểu diễn 6 người là 6 điểm trên mặt phẳng, ta nối 2 điểm bất kỳ bằng đoạn thẳng xanh ( tượng trưng quan hệ là bạn) hoặc màu đỏ ( tượng trưng quan hệ là thù). như vậy bài toán đã cho trở thành: Cho 6 điểm trên mặt phẳng, 2 điểm bất kỳ được nối với nhau bởi 1 đoạn thẳng màu xanh hoặc màu đỏ. Chứng minh rằng tồn tại 3 điểm mà các đoạn thẳng nối chúng cùng màu.
Gọi A là 1 điểm bất kỳ trong 6 điểm, Vì các đoạn thẳng nối A với 5 điểm chỉ có 1 trong 2 màu xanh hoặc đỏ cho nên, theo nguyên lý Dirichlet, sẽ có 1 màu xuất hiện ít nhất 3 lần. WLOG, giả sử A nối với B, C, D bằng 3 đoạn thẳng màu xanh.
Nhận thấy:
Nếu BC, CD, BD là màu xanh thì lần lượt các tam giác ABC, ACD, ABD đều là các tam giác có các cạnh là màu xanh.và ngược lại, nếu cả 3 cạnh BC, CD, BD không là màu xanh thì tam giác BCD có các cạnh là màu đỏ. Điều này chứng tỏ rằng luôn luôn tồn tại 3 điểm mà các đọan thẳng nối chúng cùng màu.

B3: Ta có thể dùng phương pháp liệt kê theo thứ tự từ điển để tìm sinh tổ hợp chập $k$ của tập $X$ có $n$ phần tử. Có thể xây dựng tổ hợp liền sau tổ hợp $a_{1}a_{2}...a_{k}$ bằng cách : trước hết, tìm phần tử đầu tiên $a_{i}$ trong dãy đã cho từ phải qua trái sao cho $a_{i}\leq n-k+i$; sau đó thay $a_{i}$ bằng $a_{i}+1$ và các phần tử phía sau cộng dồn 1 đơn vị. Cụ thể:
Trong bài toán này thì $k=4$ và $n=7$. Ta thấy, từ phải qua trái $a_{3} =5$ là số hạng đầu tiên của tổ hợp thỏa điều kiện $a_{i}\leq 7-4+i$ (mặc dù trước đó $a_{4}=7$ đã thỏa đk này nhưng do đã đạt giá trị max nên không tăng được nữa). Để nhận được tổ hợp tiếp theo sau ta tăng $a_{i}$ lên 1 đơn vị, tức $a_{3}=6$ và đặt $a_{4}=6+1=7$. Vậy tổ hợp liền sau tổ hợp $\left \{ 3,4,5,7 \right \}$ là tổ hợp $\left \{ 3,4,6,7 \right \}$.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 03-06-2021 - 01:30

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...

#3
Nobodyv3

Nobodyv3

    Generating Functions Faithful

  • Thành viên
  • 935 Bài viết

B!: Gọi $a_{n}$ là số cách bước lên cầu thang $n$ bậc thỏa đề bài. Bắt đầu bước lên cầu thang ta có 2 TH:
- Đi 1 bậc: có $a_{n-1}$ cách.đi các bậc thang còn lại.
- Đi 2 bậc: có $a_{n-2}$ cách.đi các bậc thang còn lại.
Theo qui tắc cộng, ta có hệ thức truy hồi:
$a_{n}=a_{n-1}+a_{n-2}\;$; $n> 2$; đk khởi tạo: $a_{1}=1, a_{2}=1$

B1: Đọc lại, mình xin chỉnh sửa:
- Đi n-1 bậc: có 1 cách đi bậc thang còn lại.
- Đi n-2 bậc: có 2 cách đi các bậc còn lại.
Theo qui tắc cộng, ta có hệ thức truy hồi:
$a_{n}=a_{n-1}+a_{n-2}\; ;n> 2$; đk khởi tạo: $a_{1}=1, a_{2}=2$
Do đó $ a_{n}=F_{n+1}$ trong đó $ F_n$ là số hạng thứ n của dãy Fibonacci được định nghĩa bởi $F_1=F_2=1, F_{n+1}=F_n+F_{n-1}$.

Bài viết đã được chỉnh sửa nội dung bởi Nobodyv3: 08-07-2023 - 20:41

===========
Thà rót cho ta..... trăm nghìn chung... rượu độc ...miễn sao đừng bắt em làm toán!..hu hu...




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

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