Kinh Nghiệm Hướng dẫn Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ Chi Tiết
Quý khách đang tìm kiếm từ khóa Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ được Update vào lúc : 2022-03-24 20:33:16 . Với phương châm chia sẻ Mẹo Hướng dẫn trong nội dung bài viết một cách Chi Tiết 2022. Nếu sau khi Read tài liệu vẫn ko hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Mình lý giải và hướng dẫn lại nha.
56. Hãy tìm toàn bộ những số tự nhiên có 9 chữ số thỏa mãn nhu cầu: a) Số có 9 chữ số tạo thành một số trong những thuận nghịch; b) Số có 9 chữ số tạo thành một số trong những thuận nghịch và có toàn bộ những chữ số đều khác 0; c) Số có 7 chữ số có tổng những chữ số là 19; 57. Hãy tìm toàn bộ những số tự nhiên có 10 chữ số thỏa mãn nhu cầu: a) Số có 10 chữ số tạo thành một số trong những thuận nghịch; b) Số có 10 chữ số tạo thành một số trong những thuận nghịch và có toàn bộ những chữ số đều khác 0; c) Số có 10 chữ số có tổng những chữ số là 18. 58. a) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n và không còn k số 1 liên tục? b) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n có tối thiểu một dãy k số 1 liên tục? 59. a) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n và không còn k số 0 liên tục? b) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n có tối thiểu một dãy k số 0 liên tục? PTIT
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán rời rạc 1, để xem tài liệu hoàn hảo nhất bạn click vào nút DOWNLOAD ở trên
dần. Thuật toán nhánh cận giải bài toán cái túi được mô tả như Hình 4.4 dưới đây. Thuật toán Brach_And_Bound (i) t = ( b – bi)/A[i]; //Khởi tạo số lượng dụng cụ thứ i for j = t; j 0; j–) x[i] = j; //Lựa chọn x[i] là j; ;iiii xabb // Trọng lượng túi cho bài toán bộ phận thứ i. ;iiii xc // Giá trị sử dụng cho bài toán bộ phận thứ i If (k==n) ; else if (k + (ck+1*bk)/ak+1 >FOPT) //Nhánh cận được triển khai tiếp theo Branch_And_Bound(k+1); ;iiii xabb ;iiii xc Hình 4.4. Thuật toán nhánh cận giải bài toán cái túi Ví dụ. Giải bài toán cái túi sau theo thuật toán nhánh cận trình diễn ở trên. .4,3,2,1, 84235 max63510)( 4321 4321 jZx xxxx xxxxxf j Lời giải. Quá trình giải bài toán được mô tả trong cây tìm kiếm trong Hình 4.4. tin tức về một phương án bộ phận trên cây được ghi trong những ô trên hình vẽ tương ứng theo thứ tự sau: Đầu tiên là những thành phấn của phương án bộ phận thứ i : X =(x1,x2,..,xi); Tiếp đến là giá trị của những dụng cụ theo phương án bộ phận thứ i; Kế tiếp là w tương ứng với trọng lượng còn sót lại của túi; Cuối cùng là cận trên g. PT IT 84 Kết thúc thuật toán, ta thu được phương án tối ưu là x* =(1, 1, 0, 1), giá trị tối ưu f*= 15. PT IT 85 x1=1 x1=0 x1=1 x2=0 Loại vì cận trên <kỷ lục x3=0 x4=0 x4=0 Hình 4.4. Lời giải bài toán cái túi theo thuật toán nhánh cận. Chương trình giải bài toán cái túi theo thuật toán nhánh cận được thể hiện như sau: #include #include #include #define MAX 100 int A[MAX], C[MAX], F[MAX][MAX]; int XOPT[MAX], X[MAX]; int n, b, ind; float W, FOPT=-32000, cost, weight=0; FILE *fp; void Init(void) fp = fopen("caitui1.in","r"); Gốc f (1); =10; w=3; g=15 (0) =0; w=8; g=40/3 (1,1) =15; w=0; g=15 (1, 0) =10; w=3; g=14.5 (1,1,0) =15; w=0; g=15 ;15 );0,0,1,1( f x PT IT 86 fscanf(fp,"%d%d", &n, &b); cout<<"n So luong do vat:"<<n; cout<<"n Trong luong tui:"<<b; for( int i=1; i<=n; i++) fscanf(fp,"%d%d", &A[i],&C[i]); cout<<"n Vector trong luong:"; for( i=1; i<=n; i++) cout<<A[i]<<" "; cout<<"n Vector gia tri su dung:"; for( i=1; i<=n; i++) cout<<C[i]<FOPT) FOPT =cost; for(int i=1; i<=n; i++) XOPT[i] = X[i]; void Result(void) cout<<"n Ket qua toi uu:"<<FOPT; cout<<"n Phuong an toi uu:"; for(int i=1; i<=n; i++) cout<<XOPT[i]<=0; j–) X[i] = j; weight = weight+A[i]*X[i]; cost = cost + C[i]*X[i]; if (i==n) Update_Kyluc(); else if ( cost+C[i+1]*(b-weight)/A[i+1]>FOPT) Branch_And_Bound(i+1); weight = weight-A[i]*X[i]; cost = cost – C[i]*X[i]; void main(void) Init(); Branch_And_Bound(1); Result(); PT I 87 Ví dụ 2. Bài toán Người du lịch. Một người du lịch muốn đi thăm quan n thành phố T1, T2, , Tn. Xuất phát từ một thành phố nào đó, người du lịch muốn trải qua toàn bộ những thành phố còn sót lại, mỗi thành phố trải qua đúng một lần, rồi quay trở lại thành phố xuất phát. Biết cij là ngân sách đi từ thành phố Ti đến thành phố Tj (i = 1, 2, . ., n), hãy tìm hành trình dài với tổng ngân sách là nhỏ nhất (một hành trình dài là một cách đi thoả mãn Đk). Giải. Cố định thành phố xuất phát là T1. Bài toán Người du lịch được đưa về bài toán: Tìm cực tiểu của phiếm hàm: min],[],[],[],1[),,,( 1132221 xxcxxcxxcxcxxxf nnnn với điều kiện jinjijicc ;,,2,1,],,[minmin là chi phí đi lại giữa các thành phố. Giả sử ta đang có phương án bộ phận (u1, u2, . . ., uk). Phương án tương ứng với hành trình bộ phận qua k thành phố: )()()( 121 kk uTuTuTT Vì vậy, chi phí phải trả theo hành trình bộ phận này sẽ là tổng các chi phí theo từng node của hành trình bộ phận. =c[1,u2] + c[u2,u3] + . . . + c[uk-1, uk] . Để tăng trưởng hành trình dài bộ phận này thành hành trình dài khá đầy đủ, ta còn phải trải qua n- k thành phố còn sót lại rồi quay trở về thành phố T1, tức là còn phải trải qua n-k+1 đoạn đường nữa. Do ngân sách phải trả cho việc trải qua mỗi trong n-k+1 đoạn đường còn sót lại đều không nhiều nếu không muốn nói là rất thấp hơn cmin, nên cận dưới cho phương án bộ phận (u1, u2, . . ., uk) hoàn toàn có thể được xem theo công thức g(u1, u2, . . ., uk) = +(n – k +1) cmin. Chẳng hạn ta giải bài toán người du lịch với ma trận ngân sách như sau 0511159 120726 4160917 2022403 15181430 C Ta có cmin = 2. Quá trình thực thi thuật toán được mô tả bởi cây tìm kiếm lời giải được thể hiện trong hình 4.2. tin tức về một phương án bộ phận trên cây được ghi trong những ô trên hình vẽ tương ứng theo thứ tự sau: thứ nhất là những thành phần của phương án. tiếp đến là ngân sách theo hành trình dài bộ phận. PT IT 88 g là cận dưới. Kết thúc thuật toán, ta thu được phương án tối ưu ( 1, 2, 3, 5, 4, 1) tương ứng với phương án tối ưu với hành trình dài 145321 TTTTTT và ngân sách nhỏ nhất là 22 . Hình 4.5. Cây tìm kiếm lời giải bài toán người du lịch. Chương trình giải bài toán theo thuật toán nhánh cận được thể hiện như sau: #include #include #include #include #define MAX 20 int n, P[MAX], B[MAX], C[20][20], count=0; int A[MAX], XOPT[MAX]; int can, cmin, fopt; f (2) =3; g=15 (3) =14; g=26 (4) =18; g=30 (5) =15; g=27 (2,3) =7; g=16 (2,4) =25; g=34 (2,5) =23; g=32 (2,3,4) =23; g=29 (2,3,5) =11; g=17 (2,3,4,5) =41; g=44 (2,3,5,4) =16; g=19 Hành trình ( 1, 2, 3,4, 5,1) ngân sách 53. Đặt 53f Hành trình ( 1, 2, 3, 5,4, 1) ngân sách 25(Kỷ lục mới) . Đặt 22f Các nhánh này bị loại vì có cận dưới g> 22f PT IT 89 void Read_Data(void) int i, j;FILE *fp; fp = fopen(“dulich.in”,”r”); fscanf(fp,”%d”, &n); printf(“n So thanh pho: %d”, n); printf(“n Ma tran chi phi:”); for (i=1; i<=n; i++) printf("n"); for(j=1; j<=n; j++) fscanf(fp,"%d",&C[i][j]); printf("%5d", C[i][j]); int Min_Matrix(void) int min=1000, i, j; for(i=1; i<=n; i++) for(j=1; jC[i][j]) min=C[i][j]; return(min); void Init(void) int i; cmin=Min_Matrix(); fopt=32000;can=0; A[1]=1; for (i=1;i<=n; i++) B[i]=1; void Result(void) int i; printf("n Hanh trinh toi uu %d:", fopt); printf("n Hanh trinh:"); for(i=1; i”, XOPT[i]); printf(“%d”,1); void Swap(void) int i; for(i=1; i<=n;i++) XOPT[i]=A[i]; PT IT 90 void Update_Kyluc(void) int sum; sum=can+C[A[n]][A[1]]; if(sum<fopt) Swap(); fopt=sum; void Try(int i) int j; for(j=2; j<=n;j++) if(B[j]) A[i]=j; B[j]=0; can=can+C[A[i-1]][A[i]]; if (i==n) Update_Kyluc(); else if( can + (n-i+1)*cmin 0 ) ; sum = sum + r[i]; for (j=1; j k; j++) s[j] := ; if (s[j] > 0 ) sum = sum + S[j]; return(sum); Ví dụ. Giả sử ta có ma trận ngân sách với n= 6 thành phố sau: 1 2 3 4 5 6 | r[i] 1 3 93 13 33 9 3 2 4 77 42 21 16 4 3 45 17 36 16 28 16 4 39 90 80 56 7 7 5 28 46 88 33 25 25 6 3 88 18 46 92 3 0 0 15 8 0 0 Đầu tiên trừ bớt mỗi thành phần của những dòng 1, 2, 3, 4, 5, 6 cho những hằng số rút gọn tương ứng là ( 3, 4, 16, 7, 25, 3) , tiếp theo đó trong ma trận thu được ta tìm kiếm được thành phần nhỏ khác 0 của cột 3 và 4 tương ứng là (15, 8). Thực hiện rút gọn theo cột ta nhận được ma trận sau: 1 2 3 4 5 6 1 0 75 2 30 6 2 0 58 30 17 12 3 29 1 12 0 12 4 32 83 58 49 0 PT IT 93 5 3 21 48 0 0 6 0 85 0 35 89 Tổng những hằng số rút gọn là 81, vì vậy cận dưới cho toàn bộ những hành trình dài là 81 (không thể có hành trình dài có ngân sách nhỏ hơn 81). Bây giờ ta xét cách phân tập những phương án ra thành hai tập. Giả sử ta chọn cạnh (6, 3) để phân nhánh. Khi đó tập những hành trình dài được phân thành hai tập con, một tập là những hành trình dài chứa cạnh (6,3), còn tập kia là những hành trình dài không chứa cạnh (6,3). Vì biết cạnh (6, 3) không tham gia vào hành trình dài nên ta cấm hành trình dài trải qua cạnh này bằng phương pháp đặt C[6, 3] = . Ma trận thu được sẽ hoàn toàn có thể rút gọn bằng phương pháp bớt đi mỗi thành phần của cột 3 đi 48 (hàng 6 không thay đổi). Như vậy ta thu được cận dưới của hành trình dài không chứa cạnh (6,3) là 81 + 48 = 129. Còn riêng với tập chứa cạnh (6, 3) ta phải loại dòng 6, cột 3 khỏi ma trận tương ứng với nó, chính bới đã đi theo cạnh (6, 3) thì không thể đi từ 6 sang bất sang bất kể nơi nào khác và cũng không được phép đi bất kể đâu từ 3. Kết quả nhận được là ma trận với bậc giảm sút 1. Ngoài ra, do đã đi theo cạnh (6, 3) nên không được phép đi từ 3 đến 6 nữa, vì vậy cần cấm đi theo cạnh (3, 6) bằng phương pháp đặt C(3, 6) = . Cây tìm kiếm thời gian hiện nay có dạng như trong hình 4.7. Cận dưới = 81 (Hình 4.7) Cận dưới =81 Cận dưới = 129 1 2 4 5 6 1 2 3 4 5 6 1 0 2 30 6 1 0 27 2 30 6 2 0 30 17 12 2 0 10 30 17 12 3 29 1 12 0 3 29 1 12 0 12 4 32 83 49 0 4 32 83 10 49 0 5 3 21 0 0 5 3 21 0 0 0 6 0 85 35 89 Tập toàn bộ những hành trình dài Tập hành trình dài chứa cạnh (6,3) Tập hành trình dài không chứa cạnh (6,3) PT IT 94 Cạnh (6,3) được chọn để phân nhánh vì phân nhánh theo nó ta thu được cận dưới của nhánh bên phải là lớn số 1 so với việc phân nhánh theo những cạnh khác. Qui tắc này sẽ tiến hành vận dụng ở để phân nhánh ở mỗi đỉnh của cây tìm kiếm. Trong quy trình tìm kiếm toàn bộ chúng ta luôn đi theo nhánh bên trái trước. Nhánh bên trái sẽ có được ma trận rút gọn với bậc giảm sút 1. Trong ma trận của nhánh bên phải ta thay một số trong những bởi , và hoàn toàn có thể rút gọn thêm được ma trận này khi tính lại những hằng số rút gọn theo dòng và cột tương ứng với cạnh phân nhánh, nhưng kích thước của ma trận vẫn không thay đổi. Do cạnh chọn để phân nhánh phải là cạnh làm tăng cận dưới của nhánh bên phải lên nhiều nhất, nên để tìm nó ta sẽ chọn số không nào trong ma trận mà khi thay nó bởi sẽ cho ta tổng hằng số rút gọn theo dòng và cột chứa nó là lớn số 1. Thủ tục đó hoàn toàn có thể được mô tả như sau để chọn cạnh phân nhánh (r, c). 4.4.2.Thủ tục chọn cạnh phân nhánh (r,c) void BestEdge(A, k, r, c, beta) Đầu vào: Ma trận rút gọn A kích thước k k Kết quả ra: Cạnh phân nhánh (r,c) và tổng hằng số rút gọn theo dòng r cột c là beta. beta = -; for ( i = 1; i k; i++) for (j = 1; j k; j++) if (A[i,j] == 0) minr = <thành phần nhỏ nhất trên dòng i khác với A[i,j]; minc =
beta ) beta = total; r = i; /* Chỉ số dòng tốt nhất*/ c = j; /* Chỉ số cột tốt nhất*/ PT IT 95 Trong ma trận rút gọn 5 5 của nhánh bên trái hình 5.4, số không ở vị trí (4, 6) sẽ cho tổng hằng số rút gọn là 32 ( theo dòng 4 là 32, cột 6 là 0). Đây là thông số rút gọn có mức giá trị lớn số 1 riêng với những số không của ma trận này. Việc phân nhánh tiếp tục sẽ nhờ vào cạnh (4, 6). Khi đó cận dưới của nhánh bên phải tương ứng với tập hành trình dài trải qua cạnh (6,3) nhưng không trải qua cạnh (4, 6) sẽ là 81 + 32 = 113. Còn nhánh bên trái sẽ tương ứng với ma trận 4 4 (vì ta phải vô hiệu dòng 4 và cột 6). Tình huống phân nhánh này được mô tả trong Hình 4.7. Nhận thấy rằng vì cạnh (4, 6) và (6, 3) đã nằm trong hành trình dài nên cạnh (3, 4) không thể trải qua được nữa (nếu trải qua ta sẽ có được một hành trình dài con từ những thành phố này). Để ngăn cấm việc tạo thành những hành trình dài con ta sẽ gán cho thành phần ở vị trí (3, 4) giá trị . Cận dưới = 81 Cận dưới = 81 Cận dưới = 113 (Hình 4.8) Ngăn cấm tạo thành hành trình dài con: Tổng quát hơn, khi phân nhánh nhờ vào cạnh (iu, iv) ta phải thêm cạnh này vào list những cạnh của node bên trái nhất. Nếu iu là đỉnh cuối của một lối đi (i1, i2, . ., iu) và jv là đỉnh đầu của lối đi (j1, j2, . ., jk) thì để ngăn ngừa kĩ năng tạo thành hành trình dài con ta phải ngăn ngừa kĩ năng tạo thành hành hành trình dài con ta phải cấm cạnh (jk, i1). Để tìm i1 ta đi ngược từ iu, để tìm jk ta đi xuôi từ j1 theo list những cạnh đã được kết nạp vào hành trình dài. Tập hành trình dài qua cạnh (6,3) Hành trình chứa (6,3), (4,6) H. trình chứa (6,3) không chứa (4,6) PT IT 96 Cận dưới = 81 Cận dưới= 129 Cận dưới = 81 Cận dưới= 113 Cận dưới = 81 Cận dưới= 101 Cận dưới = 84 Cận dưới= 112 Cận dưới = 84 Hành trình (1, 4, 6, 3, 5, 2, 1) độ dài 104 Hình 4.9 mô tả quy trình tìm kiếm giải pháp tối ưu Tiếp tục phân nhánh từ đỉnh bên trái bằng phương pháp sử dụng cạnh (2,1) vì số không ở vị trí này còn có hằng số rút gọn lớn số 1 là 17 + 3 = 20 ( theo dòng 2 là 17, theo cột 1 là 3). Sau khi phân nhánh theo cạnh (2, 1) ma trận của nhánh bên trái có kích thước là 3 3. Vì đã trải qua (2, 1) nên ta cấm cạnh (2, 1) bằng phương pháp đặt C[1, 2] = , ta thu được ma trận sau: Tập những hành trình dài chứa (2,1) Tập toàn bộ những hành trình dài Hành trình không chứa cạnh (6,3) Tập những hành trình dài chứa (6,3) Hành trình không chứa (4,6) Tập những hành trình dài chứa (4,6) Hành trình không chứa cạnh (2,1) Hành trình không chứa cạnh (1,4) Tập những hành trình dài chứa (1, 4) PT IT 97 2 4 5 1 2 30 3 1 0 5 21 0 Ma trận này hoàn toàn có thể rút gọn được bằng phương pháp bớt 1 tại cột 1 và bớt 2 đi ở dòng 1 để nhận được ma trận cấp 3: 2 4 5 1 0 28 3 0 0 5 20 0 Ta có cận dưới của nhánh tương ứng là 81 + 1 + 2 = 84. Cây tìm kiếm cho tới bước này được thể hiện trong hình 5.5. Chú ý rằng, sau khi đã đồng ý n-2 cạnh vào hành trình dài thì ma trận còn sót lại sẽ có được kích thước là 2 2. Hai cạnh còn sót lại của hành trình dài sẽ không còn phải lựa chọn nữa mà được kết nạp ngay vào quy trình (vì nó chỉ từ sự lựa chọn duy nhất). Trong ví dụ trên sau khi đã có những cạnh (6, 3), (4,6), (2, 1), (1,4) ma trận của nhánh bên trái nhất có dạng: 2 5 3 0 5 0 Vì vậy ta kết nạp nốt cạnh (3, 5), (5, 2) vào quy trình và thu được hành trình dài: 1, 4, 6, 3, 5, 2, 1 với ngân sách là 104. Trong quy trình tìm kiếm , mỗi node của cây tìm kiếm sẽ tương ứng với một ma trận ngân sách A. Ở bước thứ nhất ma trận ngân sách tương ứng với gốc đó đó là ma trận C. Khi hoạt động và sinh hoạt giải trí từ gốc xuống nhánh bên trái xuống phĩa dưới, kích thước của những ma trận ngân sách A sẽ giảm dần. Cuối cùng khi ma trận A có kích thước 2 2 thì ta chấm hết việc phân nhánh và kết nạp hai cạnh còn sót lại để thu được hành trình dài của người du lịch. Dễ dàng nhận thấy ma trận ở đầu cuối rút gọn chỉ hoàn toàn có thể ở một trong hai dạng sau: w x w x u 0 u 0 v 0 v 0 Trong số đó u, v, x, y hoàn toàn có thể là 4 đỉnh rất khác nhau hoặc 3 đỉnh rất khác nhau. Để xác lập xem hai cạnh nào cần phải nộp vào hành trình dài ta chỉ việc xét một thành phần của ma trận A: PT I 98 if A[1, 1] = then else ; Bây giờ toàn bộ những node có cận dưới to nhiều hơn 104 hoàn toàn có thể bị vô hiệu vì chúng không chứa hành trình dài rẻ hơn 104. Trên hình 5.4 toàn bộ chúng ta thấy chỉ có node có cận dưới là 101 < 104 là nên phải xét tiếp . Node này chứa những cạnh (6, 3), (4, 6) và không chứa cạnh (2, 1). Ma trận ngân sách tương ứng với đỉnh này còn có dạng: 1 2 4 5 1 0 2 30 2 13 0 3 26 1 0 5 0 21 0 Việc phân nhánh sẽ nhờ vào cạnh (5, 1) với tổng số rút gọn là 26. Quá trình rẽ nhánh tiếp theo được chỉ ra như trong hình 5.6. Hình 5.6. Duyệt hành trình dài có cận dưới là 101. Cận dưới = 101 Cận dưới = 127 Cận dưới = 103 2 4 5 1 0 0 3 11 0 Cận dưới = 114 5 1 0 Hành trình 1, 4, 6, 3, 2, 5, 1 ; Độ dài 104. Tập hành trình dài chứa (6,3), (4,6) không qua (2,1) Tập hành trình dài qua (5,1) Hành trình không qua (5,1) Hành trình chứa (1, 4) Hành trình không chứa (1, 4) PT IT 99 Như vậy toàn bộ chúng ta thu được hai hành trình dài tối ưu với ngân sách là 104. Ví dụ trên đã cho toàn bộ chúng ta biết bài toán người du lịch hoàn toàn có thể có nhiều phương án tối ưu. Trong ví dụ này hành trình dài thứ nhất nhận được đã là tối ưu, tuy nhiên điều này sẽ không còn thể mong đợi riêng với những trường hợp tổng quát. Trong ví dụ trên toàn bộ chúng ta chỉ việc xét tới 13 node, trong lúc tổng số hành trình dài của người du lịch là 120. 4.4.3.Thuật toán nhánh cận giải bài toán người du lịch Các bước chính của thuật toán nhánh cận giải bài toán người du lịch được thể hiện trong thủ tục TSP. Thủ tục TSP xét hành trình dài bộ phận với Edges là cạnh đã được chọn và tiến hành tìm kiếm tiếp theo. Các biến được sử dụng trong thủ tục này là: Edges – Số cạnh trong hành trình dài bộ phận; A – Ma trận ngân sách tương ứng với kích thước (n-edges, n-edges) cost – Chi phí của hành trình dài bộ phận. Mincost- Chi phí của hành trình dài tốt nhất đã tìm kiếm được. Hàm Reduce(A, k), BestEgde(A, k, r, c,beta) đã được xây dựng ở trên. void TSP( Edges, cost, A) cost=cost + Reduce(A, n-Edges); if (cost <MinCost) if (edges == n-2) ; MinCost :=Cost; else BestEdge(A, n-eges, r, c, beta); LowerBound = Cost + beta; ; NewA = ; TSP(edges+1, cost, NewA);/*đi theo nhánh trái*/ ; if (LowerBound 1. Tưởng chừng bài toán chỉ mang ý nghĩa thử thách trí tuệ con người thuần tuý như một bài toán đố. Nhưng mới gần đây, người ta phát hiện những ứng dụng quan trọng của yếu tố trên vào qui hoạch, thực nghiệm và hình học xạ ảnh. Bài toán 2. Bài toán 4 màu Có nhiều bài toán mà nội dung của nó hoàn toàn có thể lý giải được với bất kỳ ai, lời giải của nó ai cũng nỗ lực thử tìm nhưng khó hoàn toàn có thể tìm kiếm được. Ngoài định lý Fermat thì bài toán bốn màu cũng là một bài toán như vậy. Bài toán hoàn toàn có thể được phát biểu như sau: Chứng minh rằng mọi map đều hoàn toàn có thể tô bằng 4 màu sao cho không còn hai nước láng giềng nào lại bị tô bởi cùng một màu. Trong số đó, mỗi nước trên map sẽ là một vùng liên thông, hai nước được gọi là láng giềng nếu chúng có chung đường biên giới giới là một đường liên tục. Hình 5.1. Bản đồ tô bởi tối thiểu bốn màu Con số bốn màu không phải là ngẫu nhiên. Người ta đã chứng tỏ được rằng mọi map đều được tô bởi số màu to nhiều hơn 4, còn với số màu thấp hơn 4 thì không thể tô được, ví dụ điển hình map gồm 4 nước như trên Hình 5.1 không thể tô được với số màu thấp hơn 4. Bài toán này xuất hiện vào trong năm 1850 từ một lái buôn người Anh là Gazri khi tô map hành chính nước Anh đã nỗ lực chứng tỏ rằng nó hoàn toàn có thể tô bằng bốn màu. Sau đó, năm 1852, ông đã viết thư cho De Morgan để thông báo về giả thuyết này. 2 1 3 4 PT IT 105 Năm 1878, keli trong một bài báo đăng ở tuyển tập những khu công trình xây dựng nghiên cứu và phân tích của Hội toán học Anh có hỏi rằng bài toán này đã được xử lý và xử lý hay chưa? Từ đó bài toán trở nên nổi tiếng, trong xuốt hơn một thế kỷ qua, nhiều nhà toán học đã nỗ lực chứng tỏ giả thuyết này. Tuy vậy, mãi tới năm 1976 hai nhà toán học Mỹ là K. Appel và W. Haken mới chứng tỏ được nó nhờ máy tính điện tử. Bài toán 3. Hình lục giác thần bí. Năm 1890 Clifford Adams đưa ra bài toán hình lục giác thần bí sau: Trên 19 ô lục giác (như Hình 5.2) hãy điền những số từ là 1 đến 19 sao cho tổng theo 6 vị trí hướng của lục giác là bằng nhau (và đều bằng 38). Sau 47 năm trời kiên trì ở đầu cuối Adams đã và đang tìm kiếm được lời giải. Sau đó vì sơ ý đánh mất bản thảo ông đã tốn thêm 5 năm để Phục hồi lại. Năm 1962 Adams đã công bố lời giải đó. Nhưng thật không thể ngờ được đó là lời giải duy nhất. Hình 5.2. Hình lục giác thần bí Bài toán 3. Bài toán chọn 2n điểm trên lưới n n điểm Cho một lưới gồm n n điểm. Hỏi hoàn toàn có thể chọn trong số chúng 2n điểm sao cho không còn ba điểm nào được chọn là thẳng hàng? Hiện nay người ta mới biết được lời giải của bài toán này khi n 15. Hình 3.3 cho một lời giải với n = 12. 9 11 18 14 6 1 15 8 5 13 4 2 10 12 16 17 7 3 19 PT IT 106 Hình 2.4. Một lời giải với n = 12. 5.2. Phương pháp phản chứng Một trong những cách giải bài toán tồn tại là dùng lập luận phản chứng: giả thiết điều chứng tỏ là sai, từ đó dẫn đến xích míc. Ví dụ 1. Cho 7 đoạn thẳng có độ dài to nhiều hơn 10 và nhỏ hơn 100. Chứng minh rằng ta luôn luôn tìm kiếm được 3 đoạn để hoàn toàn có thể ghép lại thành một tam giác. Giải: Điều kiện cần và đủ để 3 đoạn là cạnh của một tam giác là tổng của hai cạnh phải to nhiều hơn một cạnh. Ta sắp những đoạn thẳng theo thứ tự tăng dần của độ dài a1, a2, . . ., a7 và chứng tỏ rằng dãy đã xếp luôn tìm kiếm được 3 đoạn mà tổng của hai đoạn đầu to nhiều hơn đoạn cuối. Để chứng tỏ, ta giả sử không tìm kiếm được ba đoạn nào mà tổng của hai đoạn nhỏ hơn một đoạn, nghĩa là những bất đẳng thức sau đồng thời xẩy ra: a1 + a2 a3 a3 20 (vì a1 , a2 10 ) a2 + a3 a4 a4 30 (vì a2 10 , a3 20) a3 + a4 a5 a5 50 (vì a3 20, a 4 30 ) a4 + a5 a6 a6 80 (vì a4 30 , a5 50) a5 + a6 a7 a7 130 (vì a5 50, a6 80) Mâu thuẫn (bài toán được xử lý và xử lý). Ví dụ 2. Các đỉnh của một thập giác đều được đánh số bởi những số nguyên 0, 1, . . , 9 một cách tuỳ ý. Chứng minh rằng luôn tìm kiếm được ba đỉnh liên tục có tổng những số là to nhiều hơn 13. PT IT 107 Giải : Gọi x1, x2, . ., x10 là những số gán cho những đỉnh của thập giác đều. Giả sử ngược lại ta không tìm kiếm được 3 đỉnh liên tục nào thoả mãn xác lập trên. Khi đó ta có k1 = x1 + x2 + x3 13 k2 = x2 + x3 + x4 13 k3 = x3 + x4 + x5 13 k4 = x4 + x5 + x6 13 k5 = x5 + x6 + x7 13 k6 = x6 + x7 + x8 13 k7 = x7 + x8 + x9 13 k8 = x8 + x9 + x10 13 k9 = x9 + x10 + x1 13 k10 = x10 + x1 + x2 13 130 k1 + k2 + . . . + k10 = 3 (x1+ + x2 + . . .+ x10) = 3 ( 0 + 1 + 2 + . . . + 9) = 135 Mâu thuẫn vì một số trong những bằng 135 không thể hơn 130. Khẳng định chứng tỏ. 5.3 Nguyên lý Dirichlet Trong thật nhiều bài toán tổng hợp, để chứng tỏ sự tồn tại của một thông số kỹ thuật với những tính chất cho trước, người ta sử dụng nguyên tắc đơn thuần và giản dị sau gọi là nguyên tắc Dirichlet. Nguyên lý Dirichlet. Nếu đem xếp nhiều hơn nữa n đối tượng người dùng vào n hộp thì luôn tìm kiếm được một chiếc hộp chứa quá nhiều hơn nữa 2 đối tượng người dùng. Chứng minh. Việc chứng tỏ nguyên tắc trên chỉ việc sử dụng một lập luận phản chứng đơn thuần và giản dị. Giả sử không tìm kiếm được một hộp nào chứa quá nhiều hơn nữa hai đối tượng người dùng. Điều đó nghĩa là mỗi hộp không chứa quá một đối tượng người dùng. Từ đó suy ra tổng những đối tượng người dùng không vượt quá n trái với giả thiết bài toán là có nhiều hơn nữa n đối tượng người dùng được xếp vào chúng. Ví dụ 1. Trong bất kỳ một nhóm có 367 người thế nào thì cũng luôn có thể có tối thiểu hai người dân có cùng trong thời gian ngày sinh. Giải: Vì một năm có nhiều nhất 366 ngày. Như vậy, theo nguyên tắc Dirichlet thì có tối thiểu một ngày có hai người cùng một ngày sinh. Ví dụ 2. Trong bất kỳ 27 từ tiếng Anh nào thì cũng đều phải có tối thiểu hai từ cùng khởi đầu bằng một vần âm. Giải: Vì bảng vần âm tiếng Anh chỉ có 26 vần âm. Nên theo nguyên tắc Dirichlet tồn tại tối thiểu 2 từ sẽ khởi đầu bởi cùng một vần âm. PT IT 108 Ví dụ 3. Bài thi những môn học cho sinh viên được chấm theo thang điểm 100. Hỏi lớp phải có tối thiểu bao nhiêu sinh viên để sở hữu tối thiểu hai sinh viên được trao cùng một điểm. Giải: Cần có tối thiểu 102 sinh viên vì thang điểm tính từ 0 . . 100 gồm 101 số. Do vậy, theo nguyên tắc Diriclet muốn có 2 sinh viên nhận cùng một điểm thì lớp phải có tối thiểu là 101 +1 = 102 sinh viên. Nguyên lý Dirichlet tổng quát. Nếu đem xếp n đối tượng người dùng vào k hộp thì luôn tìm kiếm được một hộp chứa tối thiểu n/k đối tượng người dùng. Nguyên lý trên được nhà toán học người Đức Dirichlet đề xuất kiến nghị từ thế kỷ 19 và ông đã vận dụng để giải nhiều bài toán tổng hợp. Ví dụ 4. Trong 100 người dân có tối thiểu 9 người sinh nhật cùng một tháng. Giải: Một năm có 12 tháng. Xếp toàn bộ những người dân sinh nhật vào cùng một nhóm. Theo nguyên tắc Dirichlet ta có tối thiểu 100/12 = 9 người cùng sinh nhật một tháng. Ví dụ 5. Có năm loại học bổng rất khác nhau để phát cho sinh viên. Hỏi phải có tối thiểu bao nhiêu sinh viên để chắc như đinh có 5 người được trao học bổng như nhau. Giải. Số sinh viên tối thiểu để sở hữu 5 sinh viên cùng được trao một loại học bổng là số n thoả mãn n/5 > 5. Số nguyên nhỏ nhất thoả mãn Đk trên là n = 25 + 1 = 26. Như vậy phải có tối thiểu 26 sinh viên để sở hữu tối thiểu 5 sinh viên cùng được trao một loại học bổng. Ví dụ 6. Trong một tháng có 30 ngày một đội nhóm bóng chày chơi tối thiểu mỗi ngày một trận, nhưng cả tháng chơi không thật 45 trận. Hãy chỉ ra rằng phải tìm kiếm được một quy trình gồm một số trong những ngày liên tục nào đó trong tháng sao cho trong quy trình đó đội chơi đúng 14 trận. Giải: Giả sử aj là số trận tranh tài cho tới ngày thứ j của đội. Khi đó a1, a2, . . ., a30 là dãy tăng của những số nguyên dương và 1 aj 45. Suy ra dãy a1 + 14, a2 + 14, . . ., a30 + 14 cũng là dãy tăng những số nguyên dương và 15 aj 59 Như vậy, dãy 60 số nguyên dương a1, a2, . . , a30, a1 + 14, a2 + 14 , . . ., a30 + 14 trong số đó toàn bộ những số đều nhỏ hơn hoặc bằng 59. Theo nguyên tắc Dirichlet thì phải tồn tại tối thiểu hai số trong số hai số nguyên này bằng nhau. Vì những số a1, a2, . . ., a30 là đôi một rất khác nhau và a1 + 14, a2 + 14, . . ., a30 + 14 cũng đôi một rất khác nhau. Nên ta suy ra phải tồn tại chỉ số i và j sao cho ai=aj + 14. Điều đó nghĩa là có đúng 14 trận đấu trong quy trình từ thời điểm ngày j + 1 đến ngày thứ i. 5.4. Những nội dung cần ghi nhớ PT IT 109 Bạn đọc cần ghi nhớ một số trong những kiến thức và kỹ năng quan trọng sau: Những nguyên tắc đếm cơ bản: nguyên tắc cộng, nguyên tắc nhân & nguyên tắc bù trừ. Sử dụng những nguyên tắc cơ bản tron đếm những hoán vị, tổng hợp. Hiểu phương pháp cách xử lý và xử lý bài toán đếm bằng hệ thức truy hồi. Nắm vững phương pháp qui một bài toán đếm về những bài toán con. Cách giải phổ cập cho bài toán tồn tại là sử dụng phương pháp phản chứng hoặc sử dụng nguyên tắc Dirichlet. BÀI TẬP 1 . Dùng bảng chân lý để chứng tỏ luật giao hoán: a) pqqp b) pqqp 2 . Dùng bảng chân lý để chứng tỏ luật phối hợp a) rqprqp b) rqprqp 3 . Dùng bảng chân lý để chứng tỏ luật phân phối a) rpqprqp b) rpqprqp 4 . Dùng bảng chân lý để chứng tỏ luật De Morgan a) qpqp b) qpqp 5. Dùng bảng chân lý để chứng tỏ những mệnh đề kéo theo dưới đấy là hằng đúng. a) pqp b) qpp c) qpp 6. Dùng bảng chân lý để chứng tỏ những mệnh đề kéo theo dưới đấy là hằng đúng. a) qpqp b) pqp c) qqp 7 . Dùng bảng chân lý để chứng tỏ những mệnh đề kéo theo dưới đấy là hằng đúng. a) qqpp b) rprqqp c) qqpp d) rrqrpqp PT IT 110 8. Chứng minh những cặp mệnh đề dưới đấy là tương tự. a) qpqpqp b) pqqp c) qpqp d) qpqp 9. Không dùng bảng chân lý chứng tỏ những mệnh đề kéo theo dưới đấy là hằng đúng. a) pqp b) qpp c) qpp d) qpqp e) pqp f) qqp 10. Không dùng bảng chân lý chứng tỏ những mệnh đề kéo theo dưới đấy là hằng đúng. a) qqpp b) rprqqp c) qqpp d) rrqrpqp 11. Không dùng bảng chân lý, chứng tỏ những cặp mệnh đề dưới đấy là tương tự. a) qpqpqp b) pqqp c) qpqp d) qpqp 12. Cho A, B, C là những tập hợp. Chứng minh rằng: a) ACBACAB b) BABA c) ABABA d) CBACBA e) CBBACBA 12. a) Trình bày thuật toán sinh hoán vị tiếp theo đó của một, 2, .., n ? b) Cho tập A = 1, 2, 3, 4, 5, 6, 7, 8, 9. Sử dụng phương pháp sinh hoán vị theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của hoán vị 568397421 ? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những hoán vị của một, 2, .., n ? PT IT 111 13. a) Trình bày thuật toán sinh hoán vị tiếp theo đó của một, 2, .., n ? b) Cho tập A = 1, 2, 3, 4, 5, 6, 7, 8, 9. Sử dụng phương pháp sinh hoán vị theo thứ tự từ điển, tìm 4 hoán vị liền kề tiếp theo của hoán vị 458796321 ? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những hoán vị của một, 2, .., n ? 14. a) Trình bày thuật toán quay lui liệt kê những hoán vị của một, 2, .., n ? b) Kiểm nghiệm thuật toán với n=3 ? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những hoán vị của một, 2, .., n ? 15 . a) Trình bày thuật toán sinh tổng hợp chập k của một, 2,..,n ? b) Cho tập A = 1, 2, 3, 4, 5, 6, 7, 8, 9. Sử dụng phương pháp sinh tổng hợp chập k của một tập hợp theo thứ tự từ điển, hãy tạo 4 tổng hợp chập 4 liền kề tiếp theo của tổng hợp 2,6,8,9? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những tổng hợp chập k của một, 2, .., n ? 16. a) Trình bày thuật toán quay lui liệt kê những tổng hợp chập k của một, 2,..,n ? b) Kiểm nghiệm thuật toán với n=5, k =3 ? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những tổng hợp chập k của một, 2, .., n ? 17. a) Trình bày thuật toán sinh xâu nhị phân có độ dài n? b) Cho xâu nhị phân X = 1, 0, 1, 1, 1, 1, 1, 1, 1. Sử dụng phương pháp sinh xâu nhị phân theo thứ tự từ điển, tìm 4 xâu nhị phân liền kề tiếp theo của X? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những xauu nhị phân có độ dài n? 18. a) Trình bày thuật toán sinh xâu nhị phân có độ dài n? b) Cho xâu nhị phân X = 1, 0, 1, 1, 0, 0, 1, 1, 1. Sử dụng phương pháp sinh xâu nhị phân theo thứ tự từ điển, tìm 4 xâu nhị phân liền kề tiếp theo của X? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những xauu nhị phân có độ dài n? PT IT 112 19. a) Trình bày thuật toán quay lui liệt kê những xâu nhị phân có độ dài n? b) Kiểm nghiệm thuật toán với n=3 ? c) Áp dụng thuật toán tại Mục a, viết chương trình liệt kêt toàn bộ những xâu nhị phân có độ dài n ? 20. Có bao nhiêu biển số xe khởi đầu bằng 2 hoặc 3 vần âm in hoa và kết thúc là 3 hoặc 4 chữ số, biết rằng có 26 vần âm trong bảng vần âm tiếng anh? (VD : RS 0912 là một trong biển số). 21. Có bao nhiêu biển số xe khởi đầu bằng 3 hoặc 4 vần âm in hoa và kết thúc là 2 hoặc 3 chữ số, biết rằng có 26 vần âm trong bảng vần âm tiếng anh? (VD : ABZ 09 là một trong biển số). 22. Có bao nhiêu số nguyên trong mức chừng từ 1000 đến 5000 chia hết cho 6 hoặc 9 ? 23. Có bao nhiêu số nguyên trong mức chừng từ 5000 đến 9999 chia hết cho 8 hoặc 12 ? 24. Giả sử toàn bộ những số điện thoại trên toàn thế giới đều theo quy tắc, khởi đầu bằng mã vương quốc dài từ là 1 đến 3 chữ số, tức là có dạng X, XX hoặc XXX ; tiếp theo là 10 chữ số dạng NXX-NXX-XXXX trong số đó N hoàn toàn có thể nhận giá trị từ là 1 đến 6, X biểu thị một chữ số từ 0 đến 9. Theo cách đánh số này, sẽ có được tối đa bao nhiêu số điện thoại hoàn toàn có thể dùng ? 25. Giả sử toàn bộ những số điện thoại trên toàn thế giới đều theo quy tắc, khởi đầu bằng mã vương quốc dài từ là 1 đến 3 chữ số, tức là có dạng X, XX hoặc XXX ; tiếp theo là 10 chữ số dạng NNX-NXX-XXXX trong số đó N hoàn toàn có thể nhận giá trị từ 5 đến 9, X biểu thị một chữ số từ 0 đến 9. Theo cách đánh số này, sẽ có được tối đa bao nhiêu số điện thoại hoàn toàn có thể dùng ? 26. Lớp học có 55 bạn nam và 35 bạn nữ. Hãy cho biết thêm thêm có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội văn nghệ cần tối thiểu 6 thành viên và nhiều nhất 10 thành viên. 27. Lớp học có 60 bạn nam và 42 bạn nữ. Hãy cho biết thêm thêm có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam bằng số bạn nữ, biết rằng đội văn nghệ cần tối thiểu 4 thành viên và nhiều nhất 8 thành viên. 28. Lớp học có 50 bạn nam và 20 bạn nữ. Hãy cho biết thêm thêm có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam đúng bằng 2 lần số bạn nữ, biết rằng đội văn nghệ cần tối thiểu 6 thành viên và nhiều nhất 12 thành viên. PT IT 113 29. : Lớp học có 60 bạn nam và 25 bạn nữ. Hãy cho biết thêm thêm có bao nhiêu cách chọn đội văn nghệ của lớp sao cho số bạn nam đúng bằng 2 lần số bạn nữ, biết rằng đội văn nghệ cần tối thiểu 3 thành viên và nhiều nhất 9 thành viên. 30. Trong kỳ thi tuyển sinh ĐH khối A, những thí sinh thi trắc nghiệm môn Lý và Hóa, mỗi môn thi có 50 vướng mắc. Mỗi vướng mắc có đúng 4 phương án vấn đáp và chỉ được lựa chọn tối đa 1 phương án. Mỗi câu vấn đáp đúng được 0.2 điểm, câu vấn đáp sai hoặc không vấn đáp thì không được điểm. a) Hãy cho biết thêm thêm có bao nhiêu cách điền phiếu trắc nghiệm môn Lý. b) Cần có tối thiểu bao nhiêu thí sinh tham gia để sở hữu tối thiểu 10 sinh viên có tổng điểm Lý và Hóa bằng nhau. Biết rằng điểm thi không được làm tròn. 31. Trong kỳ thi tuyển sinh ĐH khối A, những thí sinh thi trắc nghiệm môn Lý và Hóa, mỗi môn thi có 40 vướng mắc. Mỗi vướng mắc có đúng 5 phương án vấn đáp và chỉ được lựa chọn tối đa 1 phương án. Mỗi câu vấn đáp đúng được 0.25 điểm, câu vấn đáp sai hoặc không vấn đáp thì không được điểm. a) Hãy cho biết thêm thêm có bao nhiêu cách điền phiếu trắc nghiệm môn Hóa. b) Cần có tối thiểu bao nhiêu thí sinh tham gia để sở hữu tối thiểu 10 sinh viên có tổng điểm Lý và Hóa bằng nhau, biết rằng điểm thi không được làm tròn. 32. Một bài thi trắc nghiệm có 30 vướng mắc, mỗi vướng mắc có 5 phương án vấn đáp và chỉ có một phương án đúng. Mỗi câu vấn đáp đúng được 3 điểm, vấn đáp sai bị trừ 1 điểm, nếu không vấn đáp thì câu đó nhận 0 điểm. Biết rằng tổng điểm thấp nhất là 0. Hãy cho biết thêm thêm: a) Có bao nhiêu cách điền phiếu trắc nghiệm (mỗi câu chỉ được chọn tối đa 1 phương án). b) Cần bao nhiêu sinh viên tham gia thi để đảm bảo có tối thiểu 2 sinh viên có cùng kết quả thi. 33. Một bài thi trắc nghiệm có 35 vướng mắc, mỗi vướng mắc có 4 phương án vấn đáp và chỉ có một phương án đúng. Mỗi câu vấn đáp đúng được 3 điểm, vấn đáp sai bị trừ 1 điểm, nếu không vấn đáp thì câu đó nhận 0 điểm. Biết rằng tổng điểm thấp nhất là 0. Hãy cho biết thêm thêm: a) Có bao nhiêu cách điền phiếu trắc nghiệm (mỗi câu chỉ được chọn tối đa 1 phương án). b) Cần bao nhiêu sinh viên tham gia thi để đảm bảo có tối thiểu 2 sinh viên có cùng kết quả thi. PT IT 114 34. Phương trình x1 + x2 + x3 = 13 có bao nhiêu nghiệm nguyên không âm thỏa mãn nhu cầu a) x1 1, x2 3, x3 0 b) x1 0, x2 3, x3 5 35. Phương trình x1 + x2 + x3 = 15 có bao nhiêu nghiệm nguyên không âm thỏa mãn nhu cầu a) x1 2, x2 0, x3 4 b) x1 1, x2 0, x3 7 36. Phương trình x1 + x2 + x3 = 14 có bao nhiêu nghiệm nguyên không âm thỏa mãn nhu cầu a) x1 0, x2 3, x3 1 b) x1 0, x2 6, x3 3, 37. Phương trình x1 + x2 + x3 = 16 có bao nhiêu nghiệm nguyên không âm thỏa mãn nhu cầu a) x1 2, x2 0, x3 2 b) x1 6, x2 3, x3 0 38. a) Giải hệ thức truy hồi sau a0 = 2, a1 = 6, an = 3an-1 – 2an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n chứa 3 số 0 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 7. 39. a) Giải hệ thức truy hồi sau a0 = 4, a1 = 8, an = an-1 + 2an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n chứa 3 số 1 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 6. 40. a) Giải hệ thức truy hồi sau a0 = 1, a1 = 5, an = -an-1 + 6an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, khởi đầu bằng số 1 và có chứa 2 số 1 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 7. PT IT 115 41. a) Giải hệ thức truy hồi sau a0 = 6, a1 = 7, an = an-1 + 6an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, kết thúc bằng số 1 và có chứa 2 số 1 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 6. 42. a) Giải hệ thức truy hồi sau a0 = 5, a1 = 4, an = an-1 + 2an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, khởi đầu bằng số 0 và có chứa 2 số 1 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 7. 43. a) Giải hệ thức truy hồi sau a0 = 8, a1 = 3, an = -an-1 + 2an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, kết thúc bằng số 0 và có chứa 2 số 1 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 6. 44. a) Giải hệ thức truy hồi sau a0 = 5, a1 = 2, an = -3an-1 + 4an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, khởi đầu bằng số 1 và có chứa 2 số 0 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 7. 45. a) Giải hệ thức truy hồi sau a0 = 6, a1 = 9, an = 3an-1 + 4an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, kết thúc bằng số 1 và có chứa 2 số 0 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 6. PT IT 116 46. a) Giải hệ thức truy hồi sau a0 = 6, a1 = 9, an = 7an-1 – 12an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, khởi đầu bằng số 0 và có chứa 2 số 0 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 7. 47. a) Giải hệ thức truy hồi sau a0 = 8, a1 = 7, an = -an-1 + 12an-2 với n2 b) Tìm hệ thức truy hồi để tính số những xâu nhị phân độ dài n, kết thúc bằng số 0 và có chứa 2 số 0 liên tục. c) Tính số xâu nhị phân thỏa mãn nhu cầu Đk ở câu b với n = 6. 48. Hãy tìm nghiệm của công thức truy hồi với Đk đầu dưới đây: a) an = 3an-1 với a0 =2. b) an = -4an-1 – 4an-2 với n2 và a0 =0 và a1 =1. c) an = 14an-1 – 49an-2 với n2 và a0 =3 và a1 = 35. 49. Hãy tìm nghiệm của công thức truy hồi với Đk đầu dưới đây: a) an = an-1 + 2 với a0 =3. b) an = -4an-1 – 4an-2 với n2 và a0 =0 và a1 =1. c) an = 13an-1 – 22an-2 với n2 và a0 =3 và a1 = 15. 50. Hãy tìm nghiệm của công thức truy hồi với Đk đầu dưới đây: a) an = an-1 + 2n + 3 với a0 =4. b) an = -6an-1 – 9an-2 với n2 và a0 =3 và a1 =-3. c) an = 2an-1 + 5an-2 – 6an-3 với n3 và a0 =7 và a1 =-4, a2 =8. 51. Hãy tìm nghiệm của công thức truy hồi với Đk đầu dưới đây: a) an = an-1 + 2n với a0 =1. b) an = 14an-1 – 49an-2 với n2 và a0 =3 và a1 = 35. c) an = 2an-1 + an-2 – 2an-3 với n3 và a0 =3 và a1 =6, a2 =0. 52. Hãy tìm nghiệm của công thức truy hồi với Đk đầu dưới đây: a) an = an-1 + 2n với a0 =1. b) an = -13an-1 – 22an-2 với n2 và a0 =3 và a1 = 15. c) an = 2an-1 + 5an-2 – 6an-3 với n3 và a0 =7 và a1 =-4, a2 =8. PT IT 117 53. Hãy tìm nghiệm của công thức truy hồi với Đk đầu dưới đây: a) an = -4an-1 – 4an-2 với n2 và a0 =0 và a1 =1. b) an = 2an-1 + an-2 – 2an-3 với n3 và a0 =3 và a1 =6, a2 =0. c) an = 7an-2 + 6an-3 với n3 và a0 =9 và a1 =10, a2 =32. 54. Phương trình x1 + x2 + x3 + x4 + x5 +x6 = 24 có bao nhiêu nghiệm nguyên không âm sao cho a) xi 2 với i=1, 2, 3, 4, 5, 6? b) 1 x1 5 và x3 8? c) 1 x1 5 và 3 x2 7? d) 1 x1 5 và 3 x2 7 và x3 8? 55. Hãy tìm toàn bộ những số tự nhiên có 7 chữ số thỏa mãn nhu cầu: a) Số có 7 chữ số tạo thành một số trong những thuận nghịch; b) Số có 7 chữ số tạo thành một số trong những thuận nghịch và có toàn bộ những chữ số đều khác 0; c) Số có 7 chữ số có tổng những chữ số là 18; 56. Hãy tìm toàn bộ những số tự nhiên có 9 chữ số thỏa mãn nhu cầu: a) Số có 9 chữ số tạo thành một số trong những thuận nghịch; b) Số có 9 chữ số tạo thành một số trong những thuận nghịch và có toàn bộ những chữ số đều khác 0; c) Số có 7 chữ số có tổng những chữ số là 19; 57. Hãy tìm toàn bộ những số tự nhiên có 10 chữ số thỏa mãn nhu cầu: a) Số có 10 chữ số tạo thành một số trong những thuận nghịch; b) Số có 10 chữ số tạo thành một số trong những thuận nghịch và có toàn bộ những chữ số đều khác 0; c) Số có 10 chữ số có tổng những chữ số là 18. 58. a) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n và không còn k số 1 liên tục? b) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n có tối thiểu một dãy k số 1 liên tục? 59. a) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n và không còn k số 0 liên tục? b) Tìm hệ thức truy hồi và cho Đk đầu để tính số những xâu nhị phân độ dài n có tối thiểu một dãy k số 0 liên tục? 60. PT IT 118 a) Một khối mạng lưới hệ thống máy tính coi một xâu những chữ số hệ thập phân là một từ mã hợp lệ nếu nó chứa một số trong những chẵn chữ số 1. Ví dụ 1231407869 là hợp lệ, 120987045608 là không hợp lệ. Giả sử an là số những từ mã độ dài n. Hãy tìm hệ thức truy hồi và Đk đầu cho an? b) Giải hệ thức truy hồi an = 2an-1 + an-2 – 2an-3 với n3 và a0 =3 và a1 =6, a2 =0. 61. Phương trình 25654321 xxxxxx có bao nhiêu nghiệm nguyên không âm thỏa mãn nhu cầu a) x1 1, x2 2, x3 3, x4 4, x5 5 , x6 6? b) 2 x1 7, 4 x2 8; x3 5? 62. a) Một khối mạng lưới hệ thống máy tính coi một xâu những chữ số hệ thập phân là một từ mã hợp lệ nếu nó chứa một số trong những lẻ chữ số 0. Ví dụ 1231407869 là hợp lệ, 12098704568 là không hợp lệ. Giả sử an là số những từ mã độ dài n. Hãy tìm hệ thức truy hồi và Đk đầu cho an? b) Giải hệ thức truy hồi an = 7an-2 + 6an-3 với n3 và a0 =9 và a1 =10, a2 =32. 63. Phương trình 28654321 xxxxxx có bao nhiêu nghiệm nguyên không âm thỏa mãn nhu cầu c) x1 1, x2 2, x3 3, x4 4, x5 5 , x6 6? b) 1 x1 6, 4 x2 9; x3 4? 64. a) Trình bày thuật toán nhánh cận giải bài toán cái túi? b) Áp dụng thuật toán nhánh cận giải bài toán cái túi dưới đây, chỉ rõ kết quả theo từng bước thực thi của thuật toán? .4,3,2,1,1,0 ,103724 max,395 4321 4321 jx xxxx xxxx j PT IT 119 65. a) Trình bày thuật toán nhánh cận giải bài toán cái túi? b) Áp dụng thuật toán nhánh cận giải bài toán cái túi dưới đây, chỉ rõ kết quả theo từng bước thực thi của thuật toán? 4,3,2,1,1,0 ,124635 max,237 4321 4321 jx xxxx xxxx j 66. a) Trình bày thuật toán nhánh cận giải bài toán cái túi? b) Áp dụng thuật toán nhánh cận giải bài toán cái túi dưới đây, chỉ rõ kết quả theo từng bước thực thi của thuật toán? .10,2,1,1,0 6215122085152791215 max,111019862038131930 10987654321 10987654321 jx xxxxxxxxxx xxxxxxxxxx j 67. Giải bài toán người du lịch với ma trận ngân sách như sau: 2128132018 2303321016 4050332015 2554250334 1212072416 1710231531 68. Giải bài toán người du lịch với ma trận ngân sách như sau: 9246188803 2533884628 0756809039 2816361745 1621427704 0933139303 PT IT
Các file đính kèm theo tài liệu này:
bg_toan_roi_rac_1_6703.pdf
://.youtube/watch?v=-JusG5LMwjc
Video Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ ?
Bạn vừa tìm hiểu thêm nội dung bài viết Với Một số hướng dẫn một cách rõ ràng hơn về Review Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ tiên tiến và phát triển nhất
Chia Sẻ Link Cập nhật Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ miễn phí
Heros đang tìm một số trong những ShareLink Download Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ Free.
Thảo Luận vướng mắc về Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ
Nếu sau khi đọc nội dung bài viết Có bao nhiêu xâu gồm 3 chữ số thấp phân khởi đầu bằng chữ số lẻ vẫn chưa hiểu thì hoàn toàn có thể lại phản hồi ở cuối bài để Mình lý giải và hướng dẫn lại nha
#Có #bao #nhiêu #xâu #gồm #chữ #số #thấp #phân #bắt #đầu #bằng #chữ #số #lẻ
| 