Câu hỏi:
20/04/2023 622
Thiết kế thuật toán cho nhiệm vụ 1 với ý tưởng khác như sau: Dãy A là một hoán vị của dãy các số từ 1 đến n khi và chỉ khi dãy A có độ dài n và mọi số i từ 1 đến n đều nằm trong A.
Thiết kế thuật toán cho nhiệm vụ 1 với ý tưởng khác như sau: Dãy A là một hoán vị của dãy các số từ 1 đến n khi và chỉ khi dãy A có độ dài n và mọi số i từ 1 đến n đều nằm trong A.
Sách mới 2k7: Tổng ôn Toán, Lí, Hóa, Văn, Sử, Địa…. kỳ thi tốt nghiệp THPT Quốc gia 2025, đánh giá năng lực (chỉ từ 110k).
Quảng cáo
Trả lời:
Giải bởi Vietjack
Một ý tưởng khác để kiểm tra xem dãy n số có phải là một hoán vị của dãy số 1, 2, ..., n hay không là sử dụng tính chất đặc biệt của hoán vị. Ta biết rằng một hoán vị của dãy số từ 1 đến n sẽ có các giá trị từ 1 đến n đúng một lần, tức là không có giá trị lặp lại và không có giá trị bỏ sót. Với ý tưởng này, ta có thể thiết kế thuật toán như sau:
-Đọc dãy số vào mảng a gồm n phần tử.
-Kiểm tra độ dài của dãy a có bằng n không. Nếu không bằng n, in ra "KHÔNG" và kết thúc thuật toán.
-Khởi tạo một mảng visited gồm n phần tử, với giá trị ban đầu là False. Mảng visited này sẽ được sử dụng để đánh dấu các số đã xuất hiện trong dãy a.
-Duyệt qua từng phần tử trong dãy a, đồng thời đánh dấu số đó đã xuất hiện trong dãy a bằng cách đặt giá trị True tại vị trí tương ứng trong mảng visited.
-Kiểm tra mảng visited. Nếu một trong các phần tử của visited là False, tức là có giá trị bị bỏ sót trong dãy a, in ra "KHÔNG" và kết thúc thuật toán.
-Sau khi kiểm tra xong mảng visited, in ra "CÓ" nếu không có giá trị nào bị bỏ sót, ngược lại in ra "KHÔNG".
-Thuật toán:
function kiemTraHoanVi(a):
n = len(a)
visited = [False] * n
# Kiểm tra độ dài của dãy a
if n != len(set(a)):
return "KHÔNG"
# Duyệt qua từng phần tử trong dãy a
for i in a:
# Nếu số i đã xuất hiện trong dãy a
if i < 1 or i > n or visited[i-1]:
return "KHÔNG"
visited[i-1] = True
# Kiểm tra mảng visited
if all(visited):
return "CÓ"
else:
return "KHÔNG"
Nhà sách VIETJACK:
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Xâu kí tự được gọi là đối xứng nêu thay đổi thứ tự ngược lại các kí tự của xâu thì vẫn nhận được dãy ban đầu. Ví dụ xâu “abcdcba" là đối xứng, còn xâu “1011” không là đối xứng. Thiết kế và viết chương trình kiểm tra một xâu kí tự cho trước có là đối xứng hay không. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.
Xâu kí tự được gọi là đối xứng nêu thay đổi thứ tự ngược lại các kí tự của xâu thì vẫn nhận được dãy ban đầu. Ví dụ xâu “abcdcba" là đối xứng, còn xâu “1011” không là đối xứng. Thiết kế và viết chương trình kiểm tra một xâu kí tự cho trước có là đối xứng hay không. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.
Xem đáp án »
13/07/2024
1,310
Câu 2:
Cho dãy số A = A[0], A[1]. .... A[n — 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phân tử nào trùng nhau hay không. Cần đưa ra câu trả lời là “có” hay “không”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.
Cho dãy số A = A[0], A[1]. .... A[n — 1]. Thiết kế và viết chương trình kiểm tra trong dãy A có hai phân tử nào trùng nhau hay không. Cần đưa ra câu trả lời là “có” hay “không”. Yêu cầu đưa ra quy trình thiết kế theo phương pháp làm mịn dần.
Xem đáp án »
13/07/2024
959
Câu 3:
Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ hình cây để mô tả phương pháp này không?
Phương pháp làm mịn dần là một trong các cách tiếp cận tổng quát khi giải quyết các bài toán cụ thể. Em có thể sử dụng sơ đồ hình cây để mô tả phương pháp này không?
Xem đáp án »
20/04/2023
275
Câu 4:
Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?
Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?
Xem đáp án »
20/04/2023
252
về câu hỏi!