Bài tập pascal nâng cao - chuyên đề dãy số và lưới ô vuông  (Bấm vào liên kết phía dưới để tải xuống)

Tài liệu bài tập là tuyển tập bài tập pascal nâng cao, chuyên đề về dãy số và lưới ô vuông. Có cả các dạng bài dễ, trung bình và khó. Phù hợp cho giáo viên, học sinh ôn thi hsg môn Tin học. Tài liệu có bao gồm cả hướng dẫn giải. Mời các bạn tham khảo

Chuyên đề bài tập về dãy số và lưới ô vuông
Bài tập số 1:
Đề bài : Quân mã
Cho một bàn cờ kích thước n*n (n <= 200) trên đó mốt số ô đã bị đánh dấu. Hãy tìm cách đặt các quân mã lên các ô trống của bàn cờ sao cho :
Không có hai con mã đặt trên cùng một ô
Không có hai quân mã nào khống chế nhau.
Số quân mã đặt được là lớn nhất có thể.

Input KNiGHT.INP
Dòng đầu ghi hai số n, m - số ô bị đánh dấu.
M dòng tiếp theo mỗi dòng ghi hai số thể hiện một ô bị đánh dâu gồm hai số x, y là vị trí của ô hàng x, cột y.
Output KNiGHT.OUT
K số quấn mã nhiều nhất.
K dòng tiếp theo mô tả một vị trí quân mã gồm hai số x, y giống như mô tả ở Input.

Bài tập số 2:
Đề bài : Hình chữ nhật lớn nhất.
Cho một hình chữ nhật C kích thước m x n. Có k điểm nằm trong hình chữ nhật. Hãy tìm hình chữ nhật có diện tích lớn nhất nằm trong, có các cạnh song song các cạnh hình chữ nhật C, và không chứa bất kì điểm nào trong số các điểm đã cho.
Input
Dòng đầu ghi m, n, k
K dòng tiếp theo ghi toạ độ của các điểm. Hệ trục toạ độ lấy một đỉnh C làm gốc, Ox, Oy song song với hai cạnh của C, sao cho toàn bộ C nằm trong góc phần tư thứ nhất của trục toạ độ.
Output
Một dòng ghi 5 số : diện tích, 4 số ghi toạ độ đỉnh trái trên, phải dưới của hình chứ nhật tìm được.
Bài tập số 3:
Đề bài : Light
Một kho xăng dầu là lưới ô vuông hình chữ nhật m x n ( m, n <= 100). Trong một số ô có đặt bể xăng. Để quản lý kho, cần một hệ thống các đèn để chiếu sáng. Mỗi đèn chỉ có thể chiếu sáng toàn bộ một hàng hay một cột của lưới, và mỗi đèn cũng có một chi phí.Yêu cầu: Cần chiếu sáng tất cả các ô có bể xăng sao cho tổng chi phí nhỏ nhất.
Input
m n k - số ô có đặt bể xăng
dòng 2 chứa m số tương ứng là chi phí lắp đèn chiếu sáng hàng 1, hàng 2, … hàng m.
dòng 3 chứa n số tương ứng là chi phí lắp đèn chiếu sáng cột 1, cột 2, … cột n.
k dòng tiếp theo mỗi dòng có hai số là vị trí của một ô có đặt bể xăng.
Output
dòng đầu ghi s là tổng chi phí nhỏ nhất.
Dòng 2 ghi chỉ số các hàng được có đèn chiếu.
Dòng 3 ghi chỉ số các cột có đèn chiếu.
Bài tập số 4:
Đề bài : Bro
Có n quán bia (n <= 10000) nẵm trên một đường tròn, đánh số 1,2..n theo chiều kim đồng hồ. Thông tin về một quán bia bao gồm A(i) là lượng bia cần cung cấp theo lít , B(i) là khoảng cách đến quán bía tiếp theo theo chiều kim đồng hồ. Chú ý khi đó B(n) là khoảng cách từ quán n đến quán 1. Hàng ngày, nhà máy bia phải cung cấp bia cho các quán, giá chuyên chở 1 lít trên 1 đơn
Chuyên đề bài tập về dãy số và lưới ô vuông vị khoảng cách. Vì tất cả đèu nằm trên đường tròn nên có hai con đường từ nhà máy đến quán, do đó chi phí tính theo đường ngắn hơn trong hai đường. Cần đặt nhà máy bia tại một vị trí trên đường tròn sao cho tổng chi phí vận chuyển bia là nhỏ
nhất.
Input BRO.INP
N
N dòng, dòng thứ i ghi 2 số A(i), B(i) theo như đã mô tả.
Các A(i), B(i) nguyên dương <= 32000
Output BRO.OUT
Một dòng ghi tổng chi phí tối thiểu.
Bài tập số 5 : Dãy Catalan
Đề bài :
Cho số nguyên duơng N ( N <= 15 ),dãy Catalan là dãy C1, C2 … C2n+1 gồm các số nguyên không âm thoả mãn : C(1) = C(2n+1) = 0 với i bất kì 1 <= i <= 2n thì C(i), C(i+1) hớn kém nhau 1 đơn vị.
Với mỗi n ta sắp xếp các dãy Catalan theo thú tự từ điển, dánh số từ 1 trở đi . Yêu cầu :
1 Cho một dãy Catalan, hãy tìm thứ tự của dãy.
2.Cho só nguyên dương k hãy tìm dãy có thứ tự k
Input CATALAN.INP
Dòng đầu ghi n.
Dòng hai ghi một dãy Catalan cấp n
Dòng 3 ghi một số nguyên dương k (k có thể rất lớn nhưng đảm bảo luôn có nghiệm)
Output CATALAN.OUT
Dòng 1 ghi số thứ tự dãy ở dòng 2 Input
Dòng 2 ghi dãy ứng với số thứ tự


Bài tập số 6: Bién đổi xâu
Đề bài :
Cho một từ điển gồm m (m <= 2000) từ có độ dài không quá 20 và hai từ S1, S2 thựôc từ điẻn.
Một phép biên đổi xâu S có thể là : chèn thêm 1 kí tự x vào vị trí k của S - kí hiệu C k x xoá đi 1 kí tự ở một vị trí k - kí hiệu X k Thay thế kí tự ở vị trí k bởi 1 kí tự c - kí hiệu T k c. đảo một đoạn xâu con (i,j) bất kì của S. - kí hiệu D i, j
Hãy tìm một cách biến đổi từ S1 thành S2 sau ít nhất lần biến đổi mà mọi xâu trung gian đều
thuộc từ điển.
Input
Dòng đầu ghi m, p1, p2 trong đó p1, p2 là thú tự tương ứng của hai xâu trong danh sách.
M dòng tiếp theo, mỗi dòng ghi 1 từ của từ điển.
Output
Dãy các kí hiệu các biến đổi , mỗi biến đổi 1 dòng.

Bài tập số 7:
Đề bài : Số Fibonacci
Dãy số Fibonacci F1 F2 …
F1 = F2 = 1
Fn+1 = Fn + Fn-1
được viết liên tục thành dã dài : 11235 …
Cho số tự nhiên N ( N<= 20000) hãy tìm chữ số thứ N của dãy trên.
Page 2
Chuyên đề bài tập về dãy số và lưới ô vuông
Input
N
Output
Chữ số thứ N của dãy.
Bài tập số 8:
Đề bài : Xâu Fibonacci
Xét dãy xâu Fibonacci được xác định như sau :
F1 = A
F2 = B
Fn+2 = Fn + Fn+1 (n > 0)
Yêu cầu : Cho n <= 40, và xâu S, hãy tìm số lần xuất hiện của S trong Fn.
Input
N M ( M <= 100)
M dòng tiếp theo, mỗi dòng ghi 1 xâu S có độ dài <= 40
Output
Với mỗi xâu S trong Input, đưa ra số lần xuất hiện tuơng ứng.
Bài tập số 9:
Đề bài : Chữ Braille
Bảng chữ cái cho người khiếm thị, được tổ chức dưới dạng các chấm nhỏ trên nền chữ nhật m *
n (m * n <= 30).
Vì người khiếm thị không phân biẹt biên giới các bảng chữ nên cũng không phân biệt được hai tổ hợp chấm nhận được bằng dịch chuyển tịnh tiến theo hàng và cột. Do đó các chữ cái khác nhau thì tổ hợp chấm tương ứng cũng không giống nhau qua các phép kể trên. Yêu cầu tìm số tất cả các tổ hợp khác nhau có thể tạo ra từ bảng m * n
Input
m n
Output
Số tổ hợp khác nhau.
Bài tập số 10: Di chuyển rôbốt.
Đề bài :
Trên lưới ô vuông có một con rôbôt. Mỗi bứớc đi của rôbốt là di chuyển sang một ô kề cạnh.
Cần viết chương trình đều khiển rôbốt. Hãy tính số các chương trình có thể viết đề di chuyển
rôbôt từ vị trí 0, 0 đến vị trí x, y cho trước sau đúng k bước di chuyển.
Input
3 số nguyên x, y, k (|x|, |y| <= 16, k <= 16)
Output
Một dòng duy nhất ghi số các cách di chuyển.

Bài tập số 11 : Đường đi trên lưới ô vuông.
Đề bài :
Cho lưới ô vuông m * n (m, n <= 20), trên mỗi ô của lưới có ghi một số nguyên dương.
Mỗi bước đi trên lưới là từ một ô di chyển sang ô kề cạnh. Hãy tìm một đường đi trên lưới qua
đúng k ô sao cho tổng tất cả các số nhận được khi đi qua các ô là lớn nhất có thể ( mỗi ô có thể
qua lại nhiều lần).
Input
m n k (k <= 200)
m dòng tiếp theo, mỗi dòng ghi n số trong đó số thứ j của dòng thứ i là số ghi trên ô i,j của lưới.
Output
S là tổng cực đại.
K dòng tiếp theo ghi danh sách các ô trên đường đi gồm hai số là hàng và cột của ô.
Page 3
Chuyên đề bài tập về dãy số và lưới ô vuông
Bài tập số 12: Gray Code
Đề bài :
n
Xét dãy gồm các số 0 , 1, … 2 - 1. Hãy tìm cách xếp các số này thành một vòng tròn sao cho
hai số bất kì cạnh nhau thì trong biểu diễn nhị phân chỉ khác nhau ở đúng 1 bit.
Input
n (n <= 15)
Output
n
Gồm 1 dòng ghi 2 số theo vòng tròn tìm được.

Bài tập số 13 : Thay xâu
Đề bài :
Cho N xâu kí tự (N <= 200), mỗi xâu có độ dài L (L <= 20), và chỉ gồm các kí tự 0, 1, và *.
Mỗi cách biến đổi một xâu là thay toàn bộ * trong xâu đó bởi 0, hay toàn bộ bởi 1.
Yêu cầu hãy tìm cách biến đổi các xâu sao cho cuối cùng thu được các xâu chỉ gồm 0, 1 và đôi
một khác nhau.
Input REPL.INP
N L
N dòng tiếp theo, dong thứ i ghi xâu thứ i.
Output REPL.OUT
Dòng đầu ghi 1 / 0 tương ứng có tìm được nghiệm hay không. Nếu có :
N dòng tiếp theo, dòng thứ i ghi một trong 3 số : 0 / 1 / 2 tương ứng với biến đổi toàn bộ * của
xâu i thành 0 / 1 / hay không biến đổi gì.

Bài tập số 14 : Cắt hình vuông
Đề bài :
Cho hình chư nhật kích thước m * n chia thành các ô vuông đơn vị. Một phép cắt hình chữ nhật cắt nó thành hai hình chữ nhật bằng một nhát cắt tại một đường kẻ ô vuông nào đó. Một hình chữ nhật được cắt thành hai hình chữ nhật con, sau đó lại thực hiện tiếp với hai hình chữ nhật con, cứ cắt cho đến khi còn lại là các hình vuông. Yêu cầu tìm cách cắt sao cho số hình vuông sinh ra là ít nhất.
Kết quả cắt thể hiện trên hình vè : các ô thuộc cùng hình vuông sau khi cắt sẽ có cùng số.
(5, 6) cắt thành (3,6) và (2,6)
(3, 6) cắt thành 2 hình vuông (3,3)
( 2,6) cắt thành 3 hình vuông (2,2)
Input
M n (m,n <= 100)
Output
Môt số là số hình vuông nhỏ nhất

Bài tập số 15:Di chuyển trong mê cung
Đề bài :
Cho mê cung là môt ma trận vuông , trong đó ô trái trên và phải dưới ghi 0, các ô còn lại ghi 1, 2, 3, hoặc 4. Trò chơi như sau : một người cần đi vào từ ô trái trên và đi ra khỏi mê cung tại ô  
Chuyên đề bài tập về dãy số và lưới ô vuông phải dưới. Từ một ô có thể đi sang mộ ô chung cạnh. Các ô trên đường đi phải có dạng 1, 2, 3, 4, 1, 2 … từ ô 0 xuất phát chỉ có thể đến ô 1, nhưng từ ô kề với ô thoát có thể đi tới ô thoát. Yêu cầu : tìm đường đi ngắn nhất cho người chơi.
Input
m, n (m, n <= 500)
m dòng tiếp theo, mỗi dòng n số mô tả ma trận số.
Output
1 / 0 trong trường hợp có hay không có đường đi.
Nếu có các dòng sau ghi các ô lần lượt trên đường đi, kết thúc bằng ô thoát m, n.

Bài tập số 16 : Ghép xâu
Đề bài
Cho hai tập xâu A và B, tập A có m xâu, B có n xâu. Các xâu thuộc tập A và B chỉ gồm các chữ cái thường và độ dài không quá 100. Bài toán đặt ra là hãy tìm một xâu không rỗng có độ dài ngắn nhất mà có thể biểu diễn dưới dạng tổng của các xâu thuộc A, cũng như dưới dạng tổng các xâu thuộc B, với số lần ghép của một xâu con trong mỗi tập là không hạn chế. Nếu có nhiều xâu như vậy thì chỉ cần chỉ ra một.

Input
Dòng đầu ghi m, n.
m+n dòng tiếp theo, mỗi dòng ghi một xâu, gồm m xâu thuộc A, rồi n xâu thuộc B.
Output
Dòng đầu ghi k là dộ dài nhỏ nhất hoặc -1 nếu không tồn tại xâu thoả mãn bài toán.
Nếu có nghiệm, dòng thứ hai ghi xâu tìm được

Bài tập số 17 : Phân chia dãy.
Đề bài
Một dãy số a nguyên dương gồm n phần tử ( n < 10000 ), hãy tìm cách phân hoạch tập (1..n) thành một số ít nhất các tập con, sao cho nếu i, j bất kì thuộc cùng 1 tập hợp mà i < j thì a(i) <
a(j).
Input
N
Dòng thứ hai ghi N số nguyên dương a(1), a(2), … a(n)
Output
Dòng đầu ghi k là số phân hoạch nhỏ nhất tìm đựoc. K dòng tiếp theo, mỗi dòng ghi danh sách theo thứ tự tăng dần chí số các phần tử của môt phân hoạch.

Bài tập số 18: Đặt trạm bưu điện
Đề bài
Trên đường cao tốc (coi như một đường thẳng nằm ngang) có n làng đánh số từ 1đến n dọc theo đường , ví trí của mỗi làng được thể hiện bằng một số nguyên dương s là khoảng cách từ làng đó đến làng 1. Người ta cần đặt k trạm bưu điện tại các làng sao cho tổng khoảng các từ các làng đến trạm bưu điện gần làng nhất là nhỏ nhất.
Input
Dòng đầu ghi hai số n, k ( 1 <= k < n < 1000 )
Dòng thứ hai dòng ghi dãy n-1 số nguyên dương tăng dần là vị trí của các làng 2, 3, … n (vị trí
làng 1 bằng 0).
Output
Dòng đầu ghi T là đáp số tối ưu.
Dòng hai ghi k só theo thứ tự tăng dần là danh sách tên các làng được đặ trạm bưu điện.
Page 5
Chuyên đề bài tập về dãy số và lưới ô vuông

Bài tập số 19 : Hình vuông Latin.
Đề bài :
Một hình vuông Latin cấp N là một ma trận N*N trong đó mỗi hàng, mỗi cột đều là một hoán vị của tập {1,2, …,N}. Cho N, hãy cho biết có bao nhiêu hình vuông Latin khác nhau cấp N.
Input
N (N <= 7)
Output
Số các hình vuông Latin cấp N

Bài tập số 20 : Cắt hàng rào.
Đề bài :
Một người nông dân cần rào mảnh vườn của anh ta lại. Để rào mảnh vườn, anh ta cần m đoạn rào với các độ dài a1, a2, …, am. Trong tay anh ta có N đoạn rào với độ dài tương ứng L1, L2,
… LN. Để có thể rào, anh ta phải cắt N đoạn rào này thành các đoạn rào trong m đoạn cần thiết (có thể có đoạn thừa, không nhất thiết phải dùng hết ). Một đoạn chỉ có thể được sử dụng nếu nó không là ghép của hai đoạn nào, mà phải là từ nguyên một đoạn cắt ra. Hãy giúp anh nông dân cắt các đoạn có sẵn để được nhiều đoạn cần thiết nhất.
Input
N, M (N <= 100, M <= 1000)
Dòng 2 ghi a1,a2, …,aM
Dòng 3 ghi L1,L2, …,LN.
Các độ dài nguyên dương <= 1000.
Output
Dòng đầu ghi k là số đoạn lớn nhất được cắt ra.
K dòng tiếp theo, mỗi dòng ghi hai số i, j cho biết đoạn cần thiết thứ i được cắt ra từ đoạn có sẵn
j.

Bài tập số 21 : Nối điểm.
Đề bài :
Trên vòng tròn cho N điểm đôi một khác nhau, đánh số từ 1 đến N theo chiều kim đồng hồ. Mỗi điểm chỉ được nối với hai điểm kề với nó trên đường tròn. Cần phải nối các điểm sao cho thoả mãn sự liên thông giữa một số cặp điểm cho trước, đồng thời số đoạn cần nối là nhỏ nhất có thể được.
Input
Dòng đầu ghi N là số điểm ( N <= 1000 ) và M là số các yêu cầu (M <= 10000)
M dòng tiếp theo, mỗi dòng ghi hai số u, v cho biết cách nối phải đảm bảo đi lại giữa u và v.
Output
K là số ít nhất các cạnh cần nối.
K dòng tiếp theo, mỗi dòng ghi một số cho biết cần nối u với đỉnh tiếp theo u theo chiều kim đồng hồ.

Chuyên đề bài tập về dãy số và lưới ô vuông
Bài tập số 22 : Lát nền.
Đề bài :
Cho một hình vuông kích thước 2N x 2N bị khuyết một ô, trong đó N là một số nguyên dương >= 4 và không chia hết cho 3. Hãy tìm cách lát hình vuông bị khuyết 1 ô đó bằng các hình thước thợ như hình vẽ 
Input
N
Dòng 2 ghi u,v là hàng và cột của ô bị khuyết
Output
Ma trận 2Nx2N trong đó mỗi ô ghi một số nguyên s :
s = 0 nếu đó là ô khuyết, ngược lại là thứ tự của viên gạch lát nền.
Bài tập số 23 : Xây cầu.
Đề bài :
Một quần đảo gồm N đảo, mỗi đảo được biểu diễn như 1 điểm trên mặt phẳng. Có M cầu nối giữa một số cặp đảo với nhau, khi đó độ dài sẽ bằng độ dài của đoạn thẳng nối hai điểm tương ứng. Quần đảo có 3 đảo lớn đánh số 1, 2, 3 và các đảo nhỏ còn lại. Độ dài giữa hai đảo là đường đi ngắn nhát giữa hai đảo đó. Hãy tìm phương án xây dựng thêm một cây cầu nối 2 đảo nào đó thoả mãn các điều kiện sau :
+ cây cầu với độ dài <= L.
+ Độ dài giữa đảo 1 đến đảo 2,3 đều được rút ngắn lại.
+ Tổng độ dài đường đi từ 1 đén 2 và từ 1 đến 3 là nhỏ nhất.
Input
Dòng đầu ghi hai số N, M nguyên dương, (N <= 1000 ; M<=5000).
Dòng 2 ghi L.
N dòng tiếp theo, dòng thứ i mô tả vị trí hòn đảo thứ i gồm hai số x, y.
M dòng tiếp theo, mỗi dòng ghi hai số u, v cho biết có cầu nối hai đảo u và v.
Output
Dòng đầu ghi hai số u, v cho biết cần xây dựng cầu nối hai đảo u, v thoả mãn đề bài hoặc ghi -1 nếu không tồn tại cách xây thêm thoả mãn bài toán.

Bài tập số 24 : Mua hàng khuyến mại.
Đề bài :
Một cửa hàng có N gói hàng, trọng lượng lần lượt là w1,w2, …,wn đơn vị. Nhân cửa hàng mở đợt khuyến mại, một người muốn mua càng nhiều hàng khuyến mại càng tốt. Tuy nhiên túi của anh ta chỉ có thể mang không quá L đơn vị, vì không thích rườm rà cho nên anh ta muốn trong số các phương án mua được nhiều hàng nhất thì chọn phương án có số gói hàng phải mang về là nhỏ nhất. Hãygiúp anh ta đạt được các mong muốn của mình.
Input
Dòng đầu ghi N, L (N <= 50000 ; L <= 5000).
Dòng 2 ghi N số nguyên dương w1, w2, …,wN.
Output
Dòng đầu ghi T là trọng lượng hàng lớn nhất mà anh có thể mua.
Dòng 2 ghi số gói ít nhất cần phải mua với trọng lượng T.

Page 7
Chuyên đề bài tập về dãy số và lưới ô vuông
Bài tập số 25 : Đặt quân xe lên bàn cờ.
Đề bài :
Cho bàn cờ hình vuông kích thước N x N. Hãy tìm cách đặt các quân xe vào các ô của bàn cờ thoả mãn các yêu cầu sau đây:
+ Một ô có không quá 1 quân cờ.
+Một quân xe bất kì chỉ bị khống chế bởi không quá 1 quân xe khác.
+Số quân xe đặt được là nhiều nhất.
Input
N (N <= 100)
Output
Dòng đầu ghi M là số quân xe nhiều nhất đặt được.
M dòng tiếp theo, mỗi dòng ghi vị trí một quân xe gồm hai số u, thể hiện hàng và cột của ô tương ứng.

Bài tập số 26 :
Đề bài :
Cho một xâu kí tự S chỉ gồm các chữ số 0,1, …,9 và các chữ cái A,B, …,Y,Z. Hãy tìm số k nhỏ nhất thoả mãn:
+11 <= k <= 36.
+Số tương ứng với S trong biểu diễn trên hệ cơ số k chia hết cho k-1.
Input
6
Xâu S gồm không quá 10 kí tự.
Output
Số k thoả mãn các yêu cầu của đề bài hoặc -1 nếu không có số k nào thoả mãn.
Chú ý:
Trong dạng biểu diễn số thì A tương ứng 10, B tưong ứng 11, …, Z tương ứng 35. Số k phải thoả mãn số đúng tức là các số của S và các số tươg ứng chữ cái phải trong khoảng
0,..k-1.

Bài tập số 27 : Đường tròn may mắn.
Đề bài :
Trên mặt phẳng cho N điếm có toạ độ nguyên, trong đó không có 3 điểm nào thẳng hàng, không có 4 điểm cùng thuộc một đường tròn. Một đường tròn gọi là may mắn nếu nó đi qua 3 điểm trong N điểm trên và trong các điểm còn lại số điểm nằm trong bằng số điểm nằm ngoài đường tròn. Hãy tìm một đường tròn may mẵn như vậy hoặc chỉ ra không có đường tròn như vậy.
Input
Dòng đầu ghi N (N <= 1000)- N lẻ > 3.
N dòng tiếp theo, dòng thứ i ghi toạ độ của điểm thứ i bao gồm 2 số nguyên x,y lần lượt là hoành độ và tung độ của điểm.
Output
Nếu không có đường tròn may mẵn, dòng đầu ghi -1.
Nếu có thì dòng đầu ghi 3 số là thứ tự của 3 điểm tìm được trong.

Bài tập số 28 :
Đề bài :
Cho N khoảng trên trục số, đánh số từ 1 đến N. Mỗi khoảng được biểu diễn bởi hai số nguyên s,f là ví trí đầu và cuối của khoảng đó. Khoảng A được gọi là nằm trong khoảng B nếu như tập số tương ứng của A là con thực sự của tập ứng với B. Hãy tìm dãy dài nhất các khoảng
a1,a2, …,ak sao cho ai nằm trong a(i+1) với mọi 0 < i < k.
Input
Dòng đầu ghi N (N <= 500)
Chuyên đề bài tập về dãy số và lưới ô vuông
N dòng tiếp theo, dòng thứ i mô tả đoạn thứ i gồm hai số nguyên s,f.
Output
Dòng đầu ghi k
Dòng 2 ghi các số a1, a2, …,ak

Bài tập số 29: Dãy nhị phân
Đề bài :
Một tập hợp S gồm các dãy N bit 0, 1 trong đó không có hai bit 1 nào kề nhau. Ví dụ với N = 5 thì S gồm các dãy 00000, 00001, 000101, …. Tập S được săp xếp theo chiều tăng dần của số nguyên tương ứng mà dãy bit bieu dien. Cho số N và một số nguyên M hãy cho biết dãy bit thứ M trong S.
Input
N, M (N <= 40, M đảm bảo có nghiệm)
Output
Dãy N số 0, 1 ghi liền nhau mô tả dãy nhị phân tìm đựơc.

Bài tập số 30: Đoạn 1.
Đề bài :
Cho hai số nguyên dương N và k, tập S gồm các dãy nhị phân độ dài N thoả mãn số các đoạn 1 liên tiếp bằng k. Ví dụ N=5, k = 2 tập S gồm các dãy 00101, 01011, 11011, …. Các phần tử của S đựoc sắp xếp theo thú tự tăng dần của số nguyên tương ứng. Hãy cho biết dãy nhị phân thứ M của S.
Input
Một dòng 3 số nguyên N, k, M (N <= 50). Các số cho đảm bảo có nghiệm.
Output
Một dòng gồm các số 0, 1 ghi liền nhau thể hiện dãy nhị phân tìm đựơc.

Bài tập

Tải xuống để xem tài liệu hoàn chỉnh - Chia sẻ cho bạn bè nếu trang web có ích với bạn!
Nguồn tài liệu:

Bạn cũng có thể quan tâm:

Bài tập môn Tin học lớp Lớp 11
Mời bạn tham gia hỏi - đáp
Thư viện bài tập © 2014 -2017 - Liên hệ - Giới thiệu - Bản quyền - Chính sách bảo mật - Sitemap