CTDL và giải thuật - In các số chính phương

Nhập và một số nguyên dương n, tiếp theo là n số nguyên của dãy số a.
Hãy in ra các số chính phương*  có trong dãy theo thứ tự tăng dần (phía sau mỗi phần tử có đúng một khoảng trắng), nếu không tồn tại số chính phương nào trong dãy a thì in ra "NULL".

*Số chính phương là số có thể biểu diễn được dưới dạng bình phương của một số nguyên ví dụ 0, 1, 4, 9, 16, ... là các số chính phương.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    6
    16 1 2 1 10 8

    1 16

    Với a = [16, 1, 2, 1, 10, 8] , thì kết quả mong muốn là "1 16 ".
     
  • Test mẫu 2:
     
    Input Output

    4
    7 5 8 3

    NULL

    Với a = [7, 5, 8, 3] thì kết quả mong muốn là "NULL".

Đầu vào/Đầu ra:

  • [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.

  • [Đầu vào] Array: Integer: a.
    1 ≤ a.size()≤ 105.
    0 ≤ a[i] ≤ 109

     

Hướng dẫn bài tập.

Để kiếm tra một số n có phải là số chính phương hay không ta làm như sau:

bool check(int n){
	int k = (int) sqrt(n);
	return k*k == n;
}

Ta sẽ dùng dãy b lưu các số nguyên tố có trong dãy a.

Sắp xếp dãy b và in dãy đó ra, lưu ý mỗi số chỉ được in ra 1 lần.

void printArray(int a[], int n){
	if (n == 0){
		cout << "NULL";
	} else{
		cout << a[0] << " ";
		for (int i = 1; i < n; i++){
			if (a[i] != a[i-1]){
    			cout << a[i] << " ";				
			}
		}	
	}
}

 

Code mẫu:

Ngôn ngữ C++:

#include<iostream>
#include<math.h>

using namespace std;

void quickSort(int a[], int l, int r){
	int p = a[(l+r)/2];
	int i = l, j = r;
	while (i < j){
		while (a[i] < p){
			i++;
		}
		while (a[j] > p){
			j--;
		}
		if (i <= j){
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i++;
			j--;
		}
	}
	if (i < r){
		quickSort(a, i, r);
	}
	if (l < j){
		quickSort(a, l, j);
	}
}
void printArray(int a[], int n){
	if (n == 0){
		cout << "NULL";
	} else{
		cout << a[0] << " ";
		for (int i = 1; i < n; i++){
			if (a[i] != a[i-1]){
    			cout << a[i] << " ";				
			}
		}	
	}
}
bool check(int n){
	int k = (int) sqrt(n);
	return k*k == n;
}
int a[100001];
int b[100001];
int main()
{
	int n, k = 0;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i];		
	}
	for (int i = 0; i < n; i++){
		if (check(a[i])){
			b[k] = a[i];
			k++;
		}
	}
	quickSort(b, 0, k-1);
	printArray(b, k);
	
    return 0;
}