Câu hỏi:
12/07/2024 612Cho một dãy số bất kì (chưa được sắp xếp) và một số K, hãy tìm số lần xuất hiện của K trong dãy số trên. Yêu cầu sử dụng phương pháp chia để trị.
Sale Tết giảm 50% 2k7: Bộ 20 đề minh họa Toán, Lí, Hóa, Văn, Sử, Địa…. form chuẩn 2025 của Bộ giáo dục (chỉ từ 49k/cuốn).
Quảng cáo
Trả lời:
Để tìm số lần xuất hiện của K trong một dãy số chưa được sắp xếp bằng phương pháp chia để trị, ta có thể sử dụng đệ quy và chia dãy số ban đầu thành hai phần. Tiếp tục chia đến khi dãy số chỉ còn một phần tử hoặc không có phần tử nào
Với đầu vào là một dãy số A và một số K, hàm countNum sẽ trả về số lần xuất hiện của K trong dãy số A. Ví dụ
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Câu 1:
Cho trước dãy số A đã sắp xếp theo thứ tự tăng dần, cho trước hằng số C. Cần thiết lập hai hàm sau bằng kĩ thuật chia để trị:
– Hàm firstInd(A, left, right, C) sẽ tìm chỉ số của phần tử đầu tiên của dãy A có giá
trị bằng C. Nếu không sẽ trả về -1.
– Hàm lastInd(A, left, right, C) sẽ tìm chỉ số của phần tử cuối cùng của dãy A có giá trị bằng C. Nếu không thấy sẽ trả về – 1.
Từ hai hàm đã thiết kế trên, đưa ra một cách giải khác cho bài toán trong nhiệm vụ 1. Lời giải này có độ phức tạp O(logn).
Câu 2:
Cho một dãy số nguyên được sắp xếp theo thứ tự tăng dần, hãy tìm một vị trí thứ i trong dãy sao cho phần tử thứ i có giá trị bằng i.
Câu 3:
Chỉnh sửa nâng cấp chương trình của nhiệm vụ thực hành để đưa ra kết quả là vùng các phần tử có giá trị bằng C của dãy gốc, tức là yêu cầu đưa ra chỉ số đầu, chỉ số cuối và số lượng phần tử của vùng có giá trị bằng C.
Ví dụ nếu A = [0, 1, 2, 2, 2, 2, 4, 5, 5, 6], C = 2, thì kết quả trả lại là 2, 5, 4.
Câu 4:
Cho một dãy số A bất kì. Để xác định một số C cho trước xuất hiện trong dãy A bao nhiều lần thì làm thế nào?
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 3)
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 1)
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 11 có đáp án
Đề thi cuối học kì 1 Tin học 11 Kết nối trí thức có đáp án (Đề 2)
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 10 có đáp án
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 12 có đáp án
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 13 có đáp án
15 câu Trắc nghiệm Tin học 11 Kết nối tri thức Bài 14 có đáp án
về câu hỏi!