Câu hỏi:
11/07/2024 3,008
Xét bài toán; Tỉnh tổng bình phương các số tự nhiên từ 1 đến n, với n là một số tự nhiên lớn hơn 0. Nói cách khác, tính giá trị S = 1 + 2 + ... + (n - 1) +1)2 n2.
Em hãy xây dựng thuật toán để giải quyết bài toán trên với độ phức tạp.
1) O(n).
2) O(1).
Xét bài toán; Tỉnh tổng bình phương các số tự nhiên từ 1 đến n, với n là một số tự nhiên lớn hơn 0. Nói cách khác, tính giá trị S = 1 + 2 + ... + (n - 1) +1)2 n2.
Em hãy xây dựng thuật toán để giải quyết bài toán trên với độ phức tạp.
1) O(n).
2) O(1).
Quảng cáo
Trả lời:
1) Dùng vòng lặp từ 1 đến n để cộng từng giá trị bình phương vào biến tổng S.
2) Dùng công thức
Hot: Học hè online Toán, Văn, Anh...lớp 1-12 tại Vietjack với hơn 1 triệu bài tập có đáp án. Học ngay
- Trọng tâm Sử, Địa, GD KTPL 11 cho cả 3 bộ Kết nối, Chân trời, Cánh diều VietJack - Sách 2025 ( 38.000₫ )
- Sách - Sổ tay kiến thức trọng tâm Vật lí 11 VietJack - Sách 2025 theo chương trình mới cho 2k8 ( 45.000₫ )
- Sách lớp 11 - Trọng tâm Toán, Lý, Hóa, Sử, Địa lớp 11 3 bộ sách KNTT, CTST, CD VietJack ( 52.000₫ )
- Sách lớp 10 - Combo Trọng tâm Toán, Văn, Anh và Lí, Hóa, Sinh cho cả 3 bộ KNTT, CD, CTST VietJack ( 75.000₫ )
CÂU HỎI HOT CÙNG CHỦ ĐỀ
Lời giải
f(x) = số lượng ước số của x.
Thuật toán thô
– Tạo hàm ((-x), đếm số lượng ước số của x.
Lặp khi 1 <<n. Nếu f(x) > f(x,) thì gán x = x (x là kết quả bài toán, ban đầu x − 1).

Cải tiến:
Nhận xét: x chia hết cho i nghĩa là x = i × j, x có hai ước là i và j. Giả sử i<j thì i < sqrt(x) . Em chỉ cần kiểm tra với i không lớn hơn căn bậc hai của x, giảm được số lần lặp. Chú ý đến trường hợp x là số chính phương thì x=ixinên x chỉ có một ước.
Cải tiến hàm f(x) như sau:
Mã giả

Lời giải
Để cắt hết tấm bìa mà không còn thừa mảnh nào thì kích thước cạnh d của hình vuông được cắt ra là ước số của x và y (x : d và y : d).
- Số lượng hình vuông ít nhất thì d phải lớn nhất, tức là: d = ƯCLN (x, y).
- Vậy kết quả của bài toán là:
Đầu vào: Hai số nguyên x, y.
Đầu ra: Số lượng hình vuông thoả mãn.
Thuật toán thô: Tìm giá trị max{d | x : d; y : d).
– Lặp khi min(x,y)>d>1:
Nếu phát hiện x chia hết cho d và y chia hết cho d thì kết quả bài toán là:

Cải tiến:
Nhận xét: Giá trị của d chính là ước số chung lớn nhất của x và y, có thể dùng hàm có sẵn tìm ước chung lớn nhất để chương trình chạy nhanh hơn.

Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.
Lời giải
Bạn cần đăng ký gói VIP ( giá chỉ từ 199K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.