THAM KHẢO!

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"

Input: N và dãy số nguyên a1, a2,..., aN

Ouput: dãy số sắp xếp theo thứ tự tăng dần

B1: Nhập vào n và dãy số nguyên a1, . . . ,aN;

B2: M ← N;

B3: Nếu M<2 thì in dãy đã sắp xếp rồi kết thúc;

B4. M ← M – 1; i ← 0;

B5: i ← i + 1;

B6: Nếu i > M thì quay lại bước 3;

B7. Nếu ai > ai+1 thì tráo đổi cho nhau;

B8: Quay lại bước 5; 

c sai

Bài 4: 

#include <bits/stdc++.h>

using namespace std;

long long a[1000],i,n;

int main()

{

cin>>n;

for (i=1; i<=n; i++) cin>>a[i];

sort(a+1,a+n+1);

cout<<"So lon nhat la: "<<a[n]<<endl;

cout<<"So nho nhat la: "<<a[1]<<endl;

cout<<"So lon thu hai la: "<<a[n-1]<<endl;

cout<<"So nho thu hai la: "<<a[2];

return 0;

}

program so_lon_nhat;
uses crt;
var a: array[1..100] of integer;
i,n,max,k,dem: integer;
s,tbc: real;
begin
clrscr;
writeln(' nhap so phan tu cua day'); readln(n);

for i:=1 to n do
begin
writeln('a[',i,']'); readln(a[i]);
end;
writeln(' nhap so can tim:'); readln(k);
max:=a[1];
i:=1;
dem:=0;
for i:=1 to n do
begin
if max<a[i] then max:=a[i];
s:=s+a[i];
tbc:=s/n;
if a[i]=k then dem:=dem+1;
end;
writeln(' so lon nhat trong day tren la:',max);
while (i<n) and (a[i]<>k) do i:=i+1;
if a[i]=k then writeln(' phan tu thu ', i ,' bang ',k)
else writeln(' k tim dc phan tu',k);
writeln(tbc:6);
writeln('co', dem, ' phan tu', k);
readln
end.