Đây là đề thi Toán rời rạc của lớp TCD đợ vừa rồi. Có đáp án bên dưới. Các bạn tham khảo nhé!
Đề Toán rời rạc cô Nguyễn Thị Anh Đào, lớp K16TCD1
Câu 1.a:
¬p <-> q ó p<-> ¬q
¬p <-> q = (¬p -> q) ^ (q->¬p) = ( p V q ) ^ (¬q V ¬p) (1)
p<-> ¬q = (¬q -> p) ^ (p->¬q) = (q V p) ^ (¬p V ¬q)(2)
Thấy 1 và 2 giống chưa ;))
Câu 1.b:
¬(p <-> q) ó ¬p<-> q
¬(p <-> q) = ¬((p->q) ^ ( q->p)) = ¬(¬p V q) V ¬(¬q V p) = (p ^ ¬q) V (q ^ ¬p)(1)
¬p<-> q = (¬p -> q) ^ (q->¬p) = (p V q) ^ (¬q V ¬p) = (p ^ ¬p) V (q ^ ¬q) V (p ^ ¬q) V (q ^ ¬p)
= F V F V (p ^ ¬q) V (q ^ ¬p) = (p ^ ¬q) V (q ^ ¬p)(2)
Thấy 1 và 2 giống chưa ;))
Cách giải:
Học thuộc bảng:
• ¬ ¬ p ⇔ p
• ¬ 1 ⇔ 0
• ¬ 0 ⇔ 1
• p ∧ q ⇔ q ∧ p
• p ∨ q ⇔ q ∨ p
• p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r
• p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r
(fix)
• p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
• p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)
• ¬ (p ∧ q) ⇔¬ p ∨¬ q
• ¬ (p ∨ q) ⇔¬ p ∧¬ q
• p ∨¬ p ⇔ 1
• p ∧¬ p ⇔ 0
• p → q ⇔¬ p ∨ q
• p ↔ q ⇔ (p → q) ∧ (q → p)
• p ∨ p ⇔ p
• p ∨ 1 ⇔ 1
• p ∨ 0 ⇔ p
• p ∨ (p ∧ q) ⇔ p
• p ∧ p ⇔ p
Xem giáo trình để biết chi tiết hơn
Câu 2:
a/ Phương trình sau đây có bao nhiêu bộ nghiệm không âm:
x1+x2+x3+x4 = 9 (1)
Chứng minh:
Gọi số nghiệm là n, số tổng là 9
Giả sữ ta gọi ngăn cách giữa các bộ nghiệm là | như hình dưới đây
|*|**|***|***| -> x1 = 1, x2 = 2, x3 = 3, x4 =3 , đây là 1 nghiệm của pt (1)
Như vậy, ngoài cùng luôn là các vạch thẳng đứng, bên trong là n-1 = 3 vạch và 20 dấu * được xếp tùy ý.
Như vậy số cách xếp khác nhau bằng số cách chọn n phần tữ từ m-1+n phần tữ (cả dấu vạch à dấu *) đó chính là C(n, m-1+n)
Định nghĩa này người ta gọi là tổ hợp chập lặp, vote google để biết thêm chi tiết.
Cách giải dạng này:
Hiểu và nhớ các cấu hình và công thức chính:
§ Các chỉnh hợp lặp chập 5 của 7 phần tử có thể là: 24355, 11111, 22334, 43215,...
§ Các chỉnh hợp không lặp chập 5 của 6 như: 12345, 23456, 73241...
§ Các tổ hợp chập 5 như : {1,2,3,4,5}, {2,3,4,5,6}, {3,4,5,6,7}...
§ Chỉnh hợp lặp 22234557777 là chỉnh hợp lặp với tần số 0,3,1,1,2,0,4
b/ Viết hàm liệt kê các chỉnh hợp không lặp chập r của n số nguyên dương đầu tiên
(trong đó r, và n là số tùy ý nhập từ bàn phím).
Chỉnh hợp (không lặp) chập k (
) của n phần tử đó là một bộ sắp thứ tự k phần tử của A, các phần tử đôi một khác nhau.
Vd: Các chỉnh hợp không không lặp chập 5 của 6 số nguyên dương đầu tiên như: 12345, 23456, 63241...
Okay, hàm của bài này là hàm quay lui, bây giờ sẽ ôn quay lui nhé:
Giải thuật quay lui có dạng như sau:
Try(i)
{ For <mỗi khả năng j có thể đề cử cho xi>
[If < chấp nhận j theo điều kiện B> Then]
{<xác nhận xi theo j>
[đánh dấu đã sử dụng j]
If <i là trạng thái cuối> Then
<Xác định được 1 kết quả >
Else
Call Try(i+1)
[Huỹ đánh dấu đã sử dụng j]
}
}
Khi gọi hàm, sử dụng Try(1)
Áp dụng đối với bài này:
· For <mỗi khả năng j có thể đề cử cho xi> là các số nguyên dương đầu tiên, từ 1 -> n (okay??)
· Do đây là chỉnh hợp không lặp nên ta phải đánh dấu các phần tữ đã sữ dụng:
[If < chấp nhận j theo điều kiện B> Then]
Trong quay lui thì ta thường dùng 1 mảng để đánh dấu phần tữ A[n], ở đây ta đặt đk nếu A[n-1] = 1 thì n đã được sữ dụng ngược lại thì chưa được sữ dụng ta tiếp tục xữ lý.
· <xác nhận xi theo j> tức là lưu lại j vào 1 mảng kết quả, j trong bài này là các số nguyên dương từ 1->n, B[i] = j;
· Do bài toán có điều kiện không lặp nên ta phải đánh dấu j đã sữ dụng A[j-1] = 1; để vòng lặp sau nhận biết được j đã sữ dụng.
· Nếu i là trạng thái cuối tức là mảng B đã đủ k phần tữ thì ta xác định kết quả hay nói cách khác ở đây là xuất ra mảng đó, sữ dụng 1 hàm Xuat()
· Nếu không thì gọi lại hàm Try(i+1)
· Cuối cùng thì ta sẽ hủy đánh dấu của j, B[j] = 0;
Tổng hợp lại thì ta được full code của bài này:
Void Try(int i)
{
For (int j = 1; j<=n; j++)
{
If (A[j-1] == 0)
{
B[i] = j;
A[j-1] =1;
If (i ==k) xuat();
Else Try(i+1);
A[j-1] = 0;
}
}
}
Câu 3:
a/ Giải thích đường đi độ dài n trên đồ thị:
đường đi từ đỉnh u đến v có độ dài n trên đồ thị là số cạnh nó đi qua vd: (a,b,c,d,e) những cạnh đường đi này đi qua: ab, bc, cd, de là 4 cạnh => dộ dài 4
b/ định nghĩa đồ thị liên thong:
Đồ thị được gọi là liên thông nếu mọi cặp đỉnh của đồ thị đều có đường đi vô hướng nối với nhau
Câu 4:
Ma trận trọng số của:
Đối với bài này thì chỉ cần viết chỉ số trên cạnh vào bảng là được
|
|
A
|
B
|
C
|
D
|
E
|
F
|
|
A
|
0
|
1
|
0
|
0
|
0
|
3
|
|
B
|
1
|
0
|
2
|
0
|
3
|
1
|
|
C
|
0
|
2
|
0
|
2
|
1
|
0
|
|
D
|
0
|
0
|
2
|
0
|
3
|
0
|
|
E
|
0
|
3
|
1
|
3
|
0
|
2
|
|
F
|
3
|
1
|
0
|
0
|
2
|
0
|
b/ Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến các đỉnh còn lại
Đối với thuật toán Dijkstra thì nguyên tắc chủ chốt là sẽ tìm kiếm đường đi ngắn nhất từ đỉnh này đến đỉnh kia.
Theo đó, đối với bài này thì: đáp án như sau:
A đến B: A->B
A đến C: A->B->C
A đến D: A->B->C->D
A đến E: A->B->C->E:
Ps: , đối với đoạn này, ngoài A->B->F->E thì có thể có thêm 2 đường đi tới E cùng độ dài là:
A->B->E và A->B->F->E với cùng độ dài là 4, tuy nhiên theo thuật toán thì ta sẽ xét đỉnh C trước (do vòng for từ A->F), nên ta phải xét đỉnh C trước, các đỉnh còn lại cùng độ dài nhưng đỉnh C xét trước nên kết quả cuối cùng vẫn là A->B->C->E:
A đến F: A->B->F
Câu 5: Giải hệ thức truy hồi sau:
an = an-1 + an-2 với a0 = 0, a1 = 1
Phương trình đặc trưng của công thức là:
r2 –r -1 = 0 ó r1 = (1+sqrt(5))/2, r2 = (1-sqrt(5))/2
từ đó ta có: an = α1 * [(1+sqrt(5))/2]^n + α2 * [(1-sqrt(5))/2]^n
Thay các điều kiện ban đầu a0 = 0, a1 = 1
Ta được:
α1 + α2 = 0
α1 * [(1+sqrt(5))/2]^n + α2 * [(1-sqrt(5))/2]^n = 1
giải hệ ta được:
α1 = 1/sqrt(5) α2= -1/sqrt(5)
vậy:
an = 1/sqrt(5) * [(1+sqrt(5))/2]^n -1/sqrt(5) * [(1-sqrt(5))/2]^n
Đối với bài giải hệ thức đệ quy này thì có thể đọc trong giáo trình toán rời rạc kèm theo.