Hướng dẫn giải của LIST08: Vị trí các số chính phương
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy ~n~ số nguyên. Hãy đếm số lượng số chính phương trong dãy và in ra các vị trí (đánh số từ 1) của chúng.
Cách làm
Với mỗi số ~x~, kiểm tra xem có số nguyên ~r~ nào mà ~r \times r = x~ hay không. Để làm việc đó, thử lần lượt ~r = 0, 1, 2, \ldots~ cho đến khi ~r \times r~ lớn hơn ~x~.
- Bước 1: Đọc ~n~ và dãy ~a~.
- Bước 2: Với mỗi ~a_i~, đặt cờ ~chinhphuong = 0~, thử các ~r~ và nếu ~r \times r = a_i~ thì đặt cờ bằng 1.
- Bước 3: Nếu cờ bằng 1 thì lưu vị trí ~i+1~ (vì đề đánh số từ 1) và tăng ~dem~.
- Bước 4: In ~dem~ ở dòng đầu, các vị trí ở dòng thứ hai.
Bẫy: số âm không bao giờ là số chính phương, vòng lặp với số âm sẽ không chạy. Số 0 là số chính phương vì ~0 = 0 \times 0~.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int a[1005];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// dem là số lượng số chính phương, vitri lưu các vị trí (đánh số từ 1)
int dem = 0;
int vitri[1005];
for (int i = 0; i < n; i++) {
// Thử các số r = 0, 1, 2, ... cho đến khi r*r vượt quá số đang xét
// Số âm không bao giờ là số chính phương nên vòng lặp không chạy
int chinhphuong = 0;
for (int r = 0; r * r <= a[i]; r++) {
if (r * r == a[i]) {
chinhphuong = 1;
}
}
if (chinhphuong == 1) {
vitri[dem] = i + 1;
dem++;
}
}
cout << dem << "\n";
for (int i = 0; i < dem; i++) {
cout << vitri[i] << " ";
}
cout << "\n";
return 0;
}
Bình luận