Lập trình C/C++, Lập trình Pascal, Lập trình Python

Đề, đáp án thi học sinh giỏi môn Tin học (thành phố Yên Bái) năm học 2022-2023

Posted on by Đỗ Thành
20
Th3
View: 21

ĐỀ THI 

Loader Loading...
EAD Logo Taking too long?

Reload Reload document
| Open Open in new tab

ĐÁP ÁN 

Đáp án Câu 1 (6 điểm)

Thuật toán

Bài toán sắp xếp bảng điểm có thể được giải bằng nhiều thuật toán khác nhau, bao gồm:

  1. Bubble sort: là thuật toán sắp xếp đơn giản nhất, hoạt động bằng cách so sánh các phần tử liên tiếp và hoán đổi chúng cho đến khi toàn bộ dãy được sắp xếp. Độ phức tạp trung bình của thuật toán bubble sort là O(n^2).

  2. Insertion sort: là thuật toán sắp xếp dựa trên việc chèn phần tử vào vị trí đúng trong dãy đã được sắp xếp. Thuật toán này phù hợp khi dãy đã gần như sắp xếp, độ phức tạp trung bình của thuật toán insertion sort cũng là O(n^2).

  3. Quick sort: là thuật toán sắp xếp nhanh, phân chia dãy thành hai phần dựa trên một phần tử được chọn làm pivot. Dãy được sắp xếp bằng cách sắp xếp các phần tử nhỏ hơn pivot và các phần tử lớn hơn pivot riêng lẻ. Độ phức tạp trung bình của thuật toán quick sort là O(n*log n).

  4. Merge sort: là thuật toán sắp xếp dựa trên phương pháp chia để trị, phân chia dãy thành các dãy con nhỏ hơn và sắp xếp các dãy con này rồi kết hợp chúng lại. Độ phức tạp trung bình của thuật toán merge sort là O(n*log n).

So sánh độ phức tạp của các thuật toán:

  • Bubble sort và insertion sort có độ phức tạp trung bình O(n^2), do đó không phù hợp với dữ liệu lớn.
  • Quick sort và merge sort có độ phức tạp trung bình O(n*log n), phù hợp với dữ liệu lớn. Tuy nhiên, quick sort có thể bị xấu đi khi dữ liệu gần như đã sắp xếp, trong khi merge sort không bị ảnh hưởng bởi trường hợp này.
  • Vì vậy, trong trường hợp bài toán sắp xếp bảng điểm, ta có thể sử dụng thuật toán merge sort để có độ phức tạp tốt nhất và đáp ứng được yêu cầu với dữ liệu lớn.
Giải câu 1 bằng ngôn ngữ C++

Đáp án của câu 1 với ngôn ngữ C++. Sử dụng Quicksort:

#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
int a[nmax], n;
void sapxepnhanh(int l, int r) {
    int i = l;
    int j = r;
    int mid = a[(l+r)/2];
    while (i <= j) {
        while (a[i] < mid) i++;
        while (a[j] > mid) j--;
        if (i <= j) {
            swap(a[i],a[j]);
            i++;
            j--;
        }
    }
    if (i < r) sapxepnhanh(i, r);
    if (j > l) sapxepnhanh(l, j);
}	
int main() {
    freopen("AVEXSLAP.INP","r",stdin);
    freopen("AVEXSLAP.OUT","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sapxepnhanh(1,n);
    for(int i = n; i >= 1; i--)
        cout << a[i] << " ";
    return 0;
}

Để giải bài toán trên, ta có thể sử dụng thuật toán sắp xếp nổi bọt (bubble sort) để sắp xếp các điểm theo thứ tự giảm dần.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // sắp xếp mảng điểm theo thứ tự giảm dần bằng thuật toán nổi bọt
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (a[j] < a[j+1]) {
                swap(a[j], a[j+1]);
            }
        }
    }

    // xuất bảng điểm đã sắp xếp
    ofstream outfile("AVEXSLAP.OUT");
    for (int i = 0; i < n; i++) {
        outfile << a[i] << " ";
    }
    outfile.close();

    return 0;
}

Trong đoạn code trên, ta sử dụng vector để lưu trữ mảng điểm của các đội. Sau khi đọc dữ liệu vào, ta sử dụng thuật toán nổi bọt để sắp xếp mảng điểm theo thứ tự giảm dần. Cuối cùng, ta xuất bảng điểm đã sắp xếp ra tệp văn bản “AVEXSLAP.OUT”.

Để giải bài toán trên bằng thuật toán quicksort với, ta cần định nghĩa hàm partition để phân hoạch mảng thành hai phần trái và phải, sao cho các phần tử trong phần trái đều nhỏ hơn một phần tử chốt (pivot) và các phần tử trong phần phải đều lớn hơn pivot. Sau đó, ta đệ quy sắp xếp phần trái và phải của mảng cho đến khi chỉ còn một phần tử.

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& a, int l, int r) {
    int pivot = a[r]; // chọn phần tử cuối cùng làm pivot
    int i = l - 1; // i là vị trí phần tử cuối cùng trong phần trái
    for (int j = l; j < r; j++) {
        if (a[j] >= pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i+1], a[r]);
    return i+1;
}

void quicksort(vector<int>& a, int l, int r) {
    if (l < r) {
        int pi = partition(a, l, r);
        quicksort(a, l, pi-1);
        quicksort(a, pi+1, r);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // sắp xếp mảng điểm theo thứ tự giảm dần bằng thuật toán quicksort
    quicksort(a, 0, n-1);

    // xuất bảng điểm đã sắp xếp
    ofstream outfile("AVEXSLAP.OUT");
    for (int i = 0; i < n; i++) {
        outfile << a[i] << " ";
    }
    outfile.close();

    return 0;
}

Trong bài toán sắp xếp mảng điểm theo thứ tự giảm dần, thuật toán tối ưu nhất là sử dụng hàm sort có sẵn trong thư viện algorithm của C++. Hàm sort này sử dụng thuật toán quicksort hoặc mergesort tùy vào từng trường hợp và đã được tối ưu để đạt được hiệu suất tốt nhất.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // sắp xếp mảng điểm theo thứ tự giảm dần bằng hàm sort có sẵn
    sort(a.begin(), a.end(), greater<int>());

    // xuất bảng điểm đã sắp xếp
    ofstream outfile("AVEXSLAP.OUT");
    for (int i = 0; i < n; i++) {
        outfile << a[i] << " ";
    }
    outfile.close();

    return 0;
}

Trong đoạn code trên, ta sử dụng hàm sort của thư viện algorithm để sắp xếp mảng điểm theo thứ tự giảm dần. Tham số greater<int>() được truyền vào hàm sort để chỉ định thứ tự sắp xếp là giảm dần. Sau đó, ta xuất bảng điểm đã sắp xếp ra file AVEXSLAP.OUT.

Giải câu 1 bằng ngôn ngữ Python

Đây là đoạn code Python giải bài toán sắp xếp mảng điểm theo thứ tự giảm dần bằng thuật toán quicksort:

def partition(arr, low, high):
    i = low - 1
    pivot = arr[high]

    for j in range(low, high):
        if arr[j] > pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

def quicksort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quicksort(arr, low, pi-1)
        quicksort(arr, pi+1, high)

n = int(input())
a = list(map(int, input().split()))

# sắp xếp mảng điểm theo thứ tự giảm dần bằng quicksort
quicksort(a, 0, n-1)
a.reverse()

# xuất bảng điểm đã sắp xếp
with open('AVEXSLAP.OUT', 'w') as f:
    f.write(' '.join(map(str, a)))

Tuy nhiên, với Python chúng ta hoàn toàn có thể sử dụng hàm sort có sẵn như C++ để xử lý tối ưu nhất với bài toán này:

n = int(input())
a = list(map(int, input().split()))

# sắp xếp mảng điểm theo thứ tự giảm dần
a.sort(reverse=True)

# xuất bảng điểm đã sắp xếp
with open('AVEXSLAP.OUT', 'w') as f:
    f.write(' '.join(map(str, a)))
Giải câu 1 bằng ngôn ngữ Pascal

Với Pascal, chúng ta nên sử dụng Quicksort là thuật toán tối ưu nhất. Đây là đoạn code Pascal giải bài toán sắp xếp mảng điểm theo thứ tự giảm dần bằng thuật toán quicksort:

program AVEXSLAP;
uses sysutils;

const
  MAXN = 100005;

var
  n, i: longint;
  a: array[1..MAXN] of longint;

procedure swap(var x, y: longint);
var
  tmp: longint;
begin
  tmp := x;
  x := y;
  y := tmp;
end;

function partition(var arr: array of longint; low, high: longint): longint;
var
  i, j, pivot: longint;
begin
  i := low - 1;
  pivot := arr[high];
  
  for j := low to high - 1 do
  begin
    if arr[j] > pivot then
    begin
      i := i + 1;
      swap(arr[i], arr[j]);
    end;
  end;
  
  swap(arr[i+1], arr[high]);
  partition := i + 1;
end;

procedure quicksort(var arr: array of longint; low, high: longint);
var
  pi: longint;
begin
  if low < high then
  begin
    pi := partition(arr, low, high);
    quicksort(arr, low, pi - 1);
    quicksort(arr, pi + 1, high);
  end;
end;

begin
  // đọc dữ liệu từ file AVEXSLAP.INP
  assign(input, 'AVEXSLAP.INP');
  reset(input);
  readln(n);
  for i := 1 to n do
    read(a[i]);
  close(input);

  // sắp xếp mảng điểm theo thứ tự giảm dần bằng quicksort
  quicksort(a, 1, n);
  for i := 1 to n div 2 do
    swap(a[i], a[n-i+1]);

  // xuất bảng điểm đã sắp xếp ra file AVEXSLAP.OUT
  assign(output, 'AVEXSLAP.OUT');
  rewrite(output);
  for i := 1 to n do
  begin
    write(a[i]);
    if i < n then
      write(' ');
  end;
  close(output);
end.

Đáp án câu 2 (6 điểm)

Thuật toán

Có thể sử dụng các thuật toán sau để giải bài toán trên:

  1. Brute-force: Duyệt tất cả các cách chọn đĩa từ danh sách ban đầu và kiểm tra số lượng đĩa có số nguyên tố lớn nhất có thể nhận được. Độ phức tạp của thuật toán này là O(2^n), với n là số lượng đĩa.

  2. Sàng Eratosthenes: Áp dụng thuật toán Sàng Eratosthenes để tìm tất cả các số nguyên tố trong khoảng từ 10 đến 20. Sau đó, duyệt danh sách các đĩa ban đầu và kiểm tra xem số ghi trên đĩa có phải là số nguyên tố hay không. Độ phức tạp của thuật toán này là O(nlog(log(n))), với n là số lượng đĩa.

  3. Kiểm tra số nguyên tố: Duyệt danh sách các đĩa ban đầu và kiểm tra xem số ghi trên đĩa có phải là số nguyên tố hay không bằng cách áp dụng thuật toán kiểm tra số nguyên tố (ví dụ: kiểm tra xem số đó có chia hết cho bất kỳ số nguyên tố nào từ 2 đến căn bậc hai của số đó hay không). Độ phức tạp của thuật toán này là O(n*sqrt(a)), với n là số lượng đĩa và a là giá trị lớn nhất của các số ghi trên đĩa.

Trong số các thuật toán trên, sàng Eratosthenes có độ phức tạp tốt nhất. Tuy nhiên, nếu số lượng đĩa là rất nhỏ thì thuật toán brute-force có thể được sử dụng vì độ phức tạp của nó không phụ thuộc vào giá trị của các số ghi trên đĩa.

Giải câu 2 với ngôn ngữ C++

Đáp án với mảng dữ liệu:

#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
int a[nmax], n, res = 0;
bool prime(int u) {
    if (u <= 1) return false;
    for(int i = 2; i*i <= u; i++)
    if (u % i == 0) return false;
    return true;
}
void cach1() {
    for(int i = 1; i <= n; i++)
        if (prime(a[i]))
            res++;
    cout << res;
}
void cach2() {
    for(int i = 1; i <= n; i++)
        if (a[i] == 11 || a[i] == 13 || a[i] == 17 || a[i] ==19)
            res++;
    cout << res;
}
int main() {
freopen("BONUSDIS.INP","r",stdin);
freopen("BONUSDIS.OUT","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    //cach1();
    cach2();
    return 0;
}

Cách 2.

Để giải quyết bài toán này, chúng ta cần thực hiện các bước sau:

  1. Viết hàm kiểm tra số nguyên tố.
  2. Đọc dữ liệu từ file.
  3. Duyệt qua tất cả các đĩa, kiểm tra xem chúng có phải số nguyên tố hay không và đếm số lượng đĩa số nguyên tố.
  4. Ghi kết quả ra file.
#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    ifstream inFile;
    ofstream outFile;
    inFile.open("BONUSDIS.INP");
    outFile.open("BONUSDIS.OUT");

    int n, count = 0;
    inFile >> n;

    for (int i = 0; i < n; i++) {
        int a;
        inFile >> a;
        if (isPrime(a)) {
            count++;
        }
    }

    outFile << count;

    inFile.close();
    outFile.close();
    return 0;
}

Ở đây, chúng ta sử dụng hàm isPrime để kiểm tra số nguyên tố. Hàm này sẽ trả về true nếu số đầu vào là số nguyên tố và false nếu không phải.

Sau đó, chúng ta mở hai file để đọc dữ liệu vào và ghi kết quả ra. Tiếp theo, chúng ta đọc số lượng đĩa từ file đầu vào và duyệt qua từng đĩa để kiểm tra xem chúng có phải số nguyên tố hay không và đếm số lượng đĩa số nguyên tố.

Cuối cùng, chúng ta ghi số lượng đĩa số nguyên tố ra file đầu ra và đóng cả hai file.

Giải Câu 2 bằng ngôn ngữ Python
import math

def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

with open('BONUSDIS.INP', 'r') as inFile, open('BONUSDIS.OUT', 'w') as outFile:
    n = int(inFile.readline().strip())
    count = 0
    for i in range(n):
        a = int(inFile.readline().strip())
        if isPrime(a):
            count += 1
    outFile.write(str(count))
Giải Câu 2 bằng ngôn ngữ Pascal
program bonusdis;

uses math;

function isPrime(n: integer): boolean;
var
  i: integer;
begin
  if n <= 1 then
    isPrime := False
  else
  begin
    for i := 2 to trunc(sqrt(n)) do
    begin
      if n mod i = 0 then
      begin
        isPrime := False;
        exit;
      end;
    end;
    isPrime := True;
  end;
end;

var
  inFile, outFile: text;
  n, a, count: integer;
begin
  assign(inFile, 'BONUSDIS.INP');
  reset(inFile);
  assign(outFile, 'BONUSDIS.OUT');
  rewrite(outFile);
  readln(inFile, n);
  count := 0;
  for i := 1 to n do
  begin
    readln(inFile, a);
    if isPrime(a) then
      count := count + 1;
  end;
  writeln(outFile, count);
  close(inFile);
  close(outFile);
end.

Đáp án Câu 3 (5 điểm)

Thuật toán

Với bài toán trên, ta có thể sử dụng thuật toán tìm kiếm nhị phân để giải quyết với độ phức tạp O(log n).

Các thuật toán có thể sử dụng để giải quyết bài toán này bao gồm:

  1. Brute Force: Sử dụng thuật toán duyệt tất cả các hoán vị của các phần tử trong dãy và kiểm tra xem liệu dãy đã được sắp xếp hay chưa. Độ phức tạp của thuật toán này là O(n!) vì số lượng hoán vị của n phần tử là n!.

  2. Selection Sort: Sử dụng thuật toán Selection Sort để sắp xếp dãy và so sánh dãy đã sắp xếp với dãy ban đầu để tìm ra vị trí ban đầu của các phần tử. Độ phức tạp của thuật toán này là O(n^2).

  3. Merge Sort: Sử dụng thuật toán Merge Sort để sắp xếp dãy và so sánh dãy đã sắp xếp với dãy ban đầu để tìm ra vị trí ban đầu của các phần tử. Độ phức tạp của thuật toán này là O(nlogn).

  4. Quicksort: Sử dụng thuật toán Quicksort để sắp xếp dãy và sử dụng thuật toán tìm kiếm nhị phân để tìm ra vị trí ban đầu của các phần tử. Độ phức tạp của thuật toán này là O(nlogn) trong trường hợp trung bình và O(n^2) trong trường hợp xấu nhất.

  5. Hàm sort có sẵn: Sử dụng hàm sort có sẵn trong các thư viện ngôn ngữ lập trình để sắp xếp dãy và sử dụng thuật toán tìm kiếm nhị phân để tìm ra vị trí ban đầu của các phần tử. Độ phức tạp của thuật toán này là O(nlogn).

Tóm lại, để giải quyết bài toán trên, ta nên sử dụng các thuật toán có độ phức tạp thấp như Merge Sort, Quicksort hoặc hàm sort có sẵn kết hợp với thuật toán tìm kiếm nhị phân. Các thuật toán có độ phức tạp cao như Brute Force và Selection Sort không nên được sử dụng trong trường hợp này. Qua đây có thể thấy được việc sử dụng ngôn ngữ C++ hoặc Python sẽ giúp cho học sinh giải quyết các bài toán tối ưu hơn nhiều so với ngôn ngữ lập trình pascal.

Giải câu 3 với ngôn ngữ C++

Dưới đây là đáp án ngôn ngữ C++ với việc sử dụng mảng:

#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
int a[nmax], b[nmax], n;
void cach1() {
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if (a[i] == b[j])
                cout << j << " ";
}
int tknp(int u) {
        int dau = 1;
        int cuoi = n;
        while (dau <= cuoi)
        {
            int giua = (dau + cuoi)/ 2;
            if (b[giua] == u) return giua;
            if (b[giua] > u) cuoi = giua - 1;
            else dau = giua + 1;
        }
}
void cach2() {
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++)
        cout << tknp(a[i]) << " ";
}
int main() {
    freopen("CTONGSPO.INP","r",stdin);
    freopen("CTONGSPO.OUT","w",stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b[i] = a[i];
    }
    //cach1();
    cach2();
    return 0;
}

Tiếp theo, chúng ta cùng tham khảo code C++ với việc sử dụng vector:

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Đọc dữ liệu vào từ file input
    freopen("CTONGSPO.INP", "r", stdin);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // Sắp xếp mảng a theo thứ tự tăng dần
    sort(a.begin(), a.end());

    // Tìm vị trí của các phần tử của a trong mảng đã sắp xếp
    vector<int> idx(n);
    for (int i = 0; i < n; i++) {
        idx[i] = lower_bound(a.begin(), a.end(), a[i]) - a.begin() + 1;
    }

    // Ghi kết quả vào file output
    freopen("CTONGSPO.OUT", "w", stdout);
    for (int i = 0; i < n; i++) {
        cout << idx[i] << " ";
    }
    cout << endl;
    return 0;
}
Giải câu 3 với ngôn ngữ Python

Dưới đây là code Python để giải bài toán trên sử dụng hàm sort và thuật toán tìm kiếm nhị phân:

# Hàm tìm kiếm nhị phân
def binary_search(arr, left, right, x):
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Đọc dữ liệu từ file input và lưu vào list
with open("CTONGSPO.INP", "r") as f:
    n = int(f.readline().strip())
    arr = list(map(int, f.readline().strip().split()))

# Sắp xếp list theo thứ tự tăng dần
arr_sorted = sorted(arr)

# Tìm vị trí của từng phần tử trong list ban đầu và lưu vào một list mới
pos = []
for i in range(n):
    idx = binary_search(arr_sorted, 0, n-1, arr[i])
    pos.append(idx+1)

# Xuất kết quả ra file output
with open("CTONGSPO.OUT", "w") as f:
    f.write(" ".join(map(str, pos)))
Giải Câu 3 với ngôn ngữ Pascal

Với bài toán này chúng ta dùng Quicksort và thuật toán tìm kiếm nhị phân để tối ưu nhất có thể với ngôn ngữ lập trình Pascal:

const
  MAX = 100000;

var
  n, i: longint;
  a, b: array[1..MAX] of longint;

procedure QuickSort(var a: array of longint; l, r: longint);
var
  i, j, p, temp: longint;
begin
  i := l;
  j := r;
  p := a[(l + r) div 2];
  repeat
    while a[i] < p do inc(i);
    while a[j] > p do dec(j);
    if i <= j then
    begin
      temp := a[i];
      a[i] := a[j];
      a[j] := temp;
      inc(i);
      dec(j);
    end;
  until i > j;
  if l < j then QuickSort(a, l, j);
  if i < r then QuickSort(a, i, r);
end;

function BinarySearch(x: longint): longint;
var
  l, r, mid: longint;
begin
  l := 1;
  r := n;
  while l <= r do
  begin
    mid := (l + r) div 2;
    if b[mid] = x then exit(mid)
    else if b[mid] < x then l := mid + 1
    else r := mid - 1;
  end;
  exit(0);
end;

begin
  assign(input, 'CTONGSPO.INP');
  reset(input);
  assign(output, 'CTONGSPO.OUT');
  rewrite(output);

  readln(n);
  for i := 1 to n do
  begin
    readln(a[i]);
    b[i] := a[i];
  end;

  QuickSort(b, 1, n);

  for i := 1 to n do
  begin
    write(BinarySearch(a[i]), ' ');
  end;

  close(input);
  close(output);
end.

Đáp án câu 4 (3 điểm)

Thuật toán

Để giải quyết bài toán này, chúng ta có thể sử dụng một số thuật toán như sau:

  1. Thuật toán sinh hoán vị (Permutation):

Thuật toán sẽ sinh ra tất cả các hoán vị của dãy số đã cho và kiểm tra xem các số ghép lại có tạo thành số đối xứng hay không. Tuy nhiên, độ phức tạp của thuật toán này là O(n!), vì số lượng hoán vị sẽ tăng rất nhanh với n.

  1. Thuật toán Quay lui (Backtracking):

Thuật toán sẽ cố gắng ghép các số lại với nhau, bắt đầu từ các số lớn nhất. Nếu tạo thành một số đối xứng, thì kết thúc thuật toán. Nếu không, ta thử ghép các số khác lại với nhau, cho đến khi tìm được số đối xứng lớn nhất. Độ phức tạp của thuật toán này là O(n!).

  1. Thuật toán Tìm kiếm nhị phân (Binary search):

Thuật toán này sẽ tìm kiếm số đối xứng bằng cách chia tỉ lệ các số trong dãy thành hai phần bằng nhau, rồi so sánh các số trong hai phần này với nhau. Nếu tìm thấy số đối xứng, thuật toán kết thúc. Nếu không, ta chọn phần nào có số lượng số lớn hơn và lặp lại quá trình. Độ phức tạp của thuật toán này là O(n log n).

Vì độ phức tạp của thuật toán Tìm kiếm nhị phân là nhỏ nhất trong các thuật toán trên, nên ta nên sử dụng thuật toán này để giải quyết bài toán.

Dưới đây là code của 3 ngôn ngữ lập trình C++, Python, Pascal với 3 ngôn ngữ trên.

Giải Câu 4 với ngôn ngữ C++

1. Thuật toán sinh hoán vị

#include <bits/stdc++.h>
using namespace std;

int n, a[11], max_palindrome = -1;

bool is_palindrome(int num) {
    int temp = num, rev = 0;
    while (temp > 0) {
        rev = rev * 10 + temp % 10;
        temp /= 10;
    }
    return num == rev;
}

void generate_permutation(int i) {
    if (i == n) {
        int num = 0;
        for (int j = 0; j < n; j++) {
            num = num * 10 + a[j];
        }
        if (is_palindrome(num)) {
            max_palindrome = max(max_palindrome, num);
        }
    } else {
        for (int j = i; j < n; j++) {
            swap(a[i], a[j]);
            generate_permutation(i + 1);
            swap(a[i], a[j]);
        }
    }
}

int main() {
    ifstream cin("DNUMPALI.INP");
    ofstream cout("DNUMPALI.OUT");

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a, a + n);

    generate_permutation(0);

    if (max_palindrome == -1) {
        cout << "NONE";
    } else {
        cout << max_palindrome;
    }

    return 0;
}

2. Thuật toán quay lui

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 11;

int n;
int a[MAXN];
bool chosen[MAXN];
int ans = -1;

bool isPalindrome(int x) {
    int y = 0, t = x;
    while (t > 0) {
        y = y * 10 + t % 10;
        t /= 10;
    }
    return x == y;
}

void dfs(int step, int cur) {
    if (step > n) {
        if (isPalindrome(cur)) {
            ans = max(ans, cur);
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!chosen[i]) {
            chosen[i] = true;
            dfs(step + 1, cur * 10 + a[i]);
            chosen[i] = false;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    dfs(1, 0);
    if (ans == -1) {
        cout << "NONE" << endl;
    } else {
        cout << ans << endl;
    }
    return 0;
}

3. Thuật toán tìm kiếm nhị phân

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

bool isPalindrome(int num) {
    string s = to_string(num);
    int i = 0, j = s.length() - 1;
    while (i < j) {
        if (s[i] != s[j]) {
            return false;
        }
        i++;
        j--;
    }
    return true;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    sort(nums.begin(), nums.end(), greater<int>());
    int left = 0, right = n - 1;
    int palindrome = -1;
    while (left <= right) {
        int mid = (left + right) / 2;
        vector<int> leftPart(nums.begin(), nums.begin() + mid + 1);
        vector<int> rightPart(nums.rbegin(), nums.rbegin() + n - mid - 1);
        int i = 0, j = 0;
        int temp = 0;
        while (i < leftPart.size() && j < rightPart.size()) {
            if (temp % 2 == 0) {
                if (leftPart[i] > rightPart[j]) {
                    temp++;
                    i++;
                }
                else {
                    temp++;
                    j++;
                }
            }
            else {
                if (leftPart[i] < rightPart[j]) {
                    temp++;
                    i++;
                }
                else {
                    temp++;
                    j++;
                }
            }
        }
        while (i < leftPart.size()) {
            temp++;
            i++;
        }
        while (j < rightPart.size()) {
            temp++;
            j++;
        }
        if (temp == n && nums[mid] != 0) {
            palindrome = nums[mid];
            break;
        }
        else if (temp < n) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    if (palindrome == -1) {
        cout << "NONE" << endl;
    }
    else {
        cout << palindrome << endl;
    }
    return 0;
}
Giải Câu 3 với ngôn ngữ Python

1. Thuật toán sinh hoán vị

def next_permutation(a):
    i = len(a) - 2
    while i >= 0 and a[i] >= a[i + 1]:
        i -= 1
    if i < 0:
        return False
    j = len(a) - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]
    a[i + 1:] = reversed(a[i + 1:])
    return True


def is_palindrome(num):
    return str(num) == str(num)[::-1]


n = int(input())
a = list(map(int, input().split()))
a.sort()
max_palindrome = 0
while True:
    num = int(''.join(map(str, a)))
    if is_palindrome(num):
        max_palindrome = max(max_palindrome, num)
    if not next_permutation(a):
        break
if max_palindrome > 0:
    print(max_palindrome)
else:
    print('NONE')

2. Thuật toán quay lui

def find_largest_palindrome(nums):
    result = []
    n = len(nums)
    used = [False] * n
    
    def is_palindrome(arr):
        return arr == arr[::-1]
    
    def backtrack(current):
        if len(current) == n:
            if is_palindrome(current):
                result.append(current)
        else:
            for i in range(n):
                if not used[i]:
                    used[i] = True
                    backtrack(current + [nums[i]])
                    used[i] = False
    
    backtrack([])
    if len(result) == 0:
        return "NONE"
    return max(result)
    
n = int(input())
nums = list(map(int, input().split()))
print(find_largest_palindrome(nums))

3. Thuật toán tìm kiếm nhị phân

def is_palindrome(num):
    # Hàm kiểm tra số đối xứng
    return str(num) == str(num)[::-1]

def binary_search(arr, low, high):
    # Hàm tìm kiếm nhị phân
    while low <= high:
        mid = (low + high) // 2
        if is_palindrome(arr[mid]):
            return arr[mid]
        elif int(str(arr[mid])[::-1]) < arr[mid]:
            high = mid - 1
        else:
            low = mid + 1
    return -1

n = int(input())
a = list(map(int, input().split()))

# Sắp xếp dãy số
a.sort()

# Tìm kiếm nhị phân
result = binary_search(a, 0, n-1)

if result == -1:
    print("NONE")
else:
    print(result)
Giải Câu 4 với ngôn ngữ Pascal

1. Thuật toán sinh hoán vị

program DNumpali;

const
  maxN = 11;

var
  a: array[1..maxN] of longint;
  n: longint;
  maxPalin: string;

procedure swap(var x, y: longint);
var
  tmp: longint;
begin
  tmp := x;
  x := y;
  y := tmp;
end;

procedure generatePermutations(k: longint);
var
  i, j: longint;
  palin: string;
  isPalin: boolean;
begin
  if k = n + 1 then
  begin
    // Check if current permutation forms a palindrome
    palin := '';
    for i := 1 to n do
      palin := palin + IntToStr(a[i]);
    isPalin := true;
    for i := 1 to Length(palin) div 2 do
      if palin[i] <> palin[Length(palin) - i + 1] then
      begin
        isPalin := false;
        break;
      end;

    // Update max palindrome if applicable
    if isPalin and (palin > maxPalin) then
      maxPalin := palin;
  end
  else
  begin
    for i := k to n do
    begin
      swap(a[k], a[i]);
      generatePermutations(k + 1);
      swap(a[k], a[i]);
    end;
  end;
end;

begin
  // Input
  Assign(input, 'DNUMPALI.INP');
  Reset(input);
  ReadLn(n);
  for i := 1 to n do
    Read(a[i]);
  Close(input);

  // Initialize maxPalin
  maxPalin := 'NONE';

  // Generate permutations and find max palindrome
  generatePermutations(1);

  // Output
  Assign(output, 'DNUMPALI.OUT');
  Rewrite(output);
  Write(maxPalin);
  Close(output);
end.

2. Thuật toán quay lui

function check_palindrome(num_str: string): boolean;
var
  i: integer;
begin
  for i := 1 to Length(num_str) div 2 do
    if num_str[i] <> num_str[Length(num_str) - i + 1] then
    begin
      check_palindrome := False;
      Exit;
    end;
  check_palindrome := True;
end;

procedure backtrack(nums: array of integer; var permutation: array of integer; used: array of boolean; var result: string);
var
  i: integer;
begin
  if Length(permutation) = Length(nums) then
  begin
    str(permutation[0], result);
    for i := 1 to Length(permutation) - 1 do
      result := result + IntToStr(permutation[i]);
    if check_palindrome(result) then
      WriteLn(result);
  end
  else
  begin
    for i := 0 to Length(nums) - 1 do
    begin
      if not used[i] then
      begin
        permutation[Length(permutation)] := nums[i];
        used[i] := True;
        backtrack(nums, permutation, used, result);
        used[i] := False;
        SetLength(permutation, Length(permutation) - 1);
      end;
    end;
  end;
end;

var
  n, i: integer;
  nums: array of integer;
  permutation: array of integer;
  used: array of boolean;
  result: string;
begin
  ReadLn(n);
  SetLength(nums, n);
  SetLength(permutation, 0);
  SetLength(used, n);
  for i := 0 to n - 1 do
    Read(nums[i]);
  backtrack(nums, permutation, used, result);
end.

3. Thuật toán Tìm kiếm nhị phân

program DNUMPALI;
uses SysUtils;

const MAX_N = 11;

var
  n: Integer;
  a: array[1..MAX_N] of Integer;

function check(p: Integer): Boolean;
var
  s, t: String;
  i, j: Integer;
begin
  Str(p, s);
  t := s;
  for i := 1 to Length(s) div 2 do begin
    j := Length(s) - i + 1;
    t[i] := s[j];
    t[j] := s[i];
  end;
  check := s = t;
end;

function solve(k: Integer): Integer;
var
  i, j, t: Integer;
begin
  if k = n + 1 then begin
    t := 0;
    for i := 1 to n do t := t * 10 + a[i];
    if check(t) then solve := t else solve := -1;
    Exit;
  end;
  solve := -1;
  for i := k to n do begin
    for j := i to n do begin
      t := a[i]; a[i] := a[j]; a[j] := t;
      solve := Max(solve, solve(k + 1));
      t := a[i]; a[i] := a[j]; a[j] := t;
    end;
  end;
end;

var
  f: TextFile;

begin
  AssignFile(f, 'DNUMPALI.INP');
  Reset(f);
  ReadLn(f, n);
  for i := 1 to n do Read(f, a[i]);
  CloseFile(f);
  t := solve(1);
  AssignFile(f, 'DNUMPALI.OUT');
  Rewrite(f);
  if t >= 0 then WriteLn(f, t) else WriteLn(f, 'NONE');
  CloseFile(f);
end.

Trong việc sử dụng thuật toán quay lui giải quyết bài toán trên, ta có thể thấy rằng đối với các ngôn ngữ lập trình C++, Python và Pascal, thời gian chạy của thuật toán sẽ khác nhau tùy vào cấu trúc và cú pháp của từng ngôn ngữ. Tuy nhiên, đây là một thuật toán phổ biến và đã được tối ưu hóa trong nhiều ngôn ngữ lập trình, do đó thời gian chạy của nó sẽ không quá khác biệt giữa các ngôn ngữ.

Đối với thuật toán sinh hoán vị, thời gian chạy sẽ phụ thuộc vào cách cài đặt thuật toán và cấu trúc dữ liệu được sử dụng để lưu trữ các hoán vị. Các ngôn ngữ lập trình có hỗ trợ sẵn các thư viện hoặc module để giải quyết vấn đề này sẽ có hiệu quả cao hơn so với việc cài đặt thuật toán từ đầu. Tuy nhiên, nếu cài đặt thuật toán đúng cách, thời gian chạy của nó sẽ không khác biệt quá nhiều giữa các ngôn ngữ.

Đối với thuật toán tìm kiếm nhị phân, thời gian chạy sẽ phụ thuộc vào cách cài đặt thuật toán và cấu trúc dữ liệu được sử dụng để lưu trữ dãy số. Thuật toán này được tối ưu hóa và sử dụng rộng rãi trong các ngôn ngữ lập trình, do đó thời gian chạy của nó sẽ không quá khác biệt giữa các ngôn ngữ.

Tuy nhiên, nên lưu ý rằng thời gian chạy của các thuật toán phụ thuộc vào độ lớn của đầu vào. Với bài toán trên, nếu số lượng đĩa n là rất lớn, thời gian chạy của thuật toán quay lui hoặc sinh hoán vị có thể trở nên quá chậm để xử lý. Trong trường hợp này, thuật toán tìm kiếm nhị phân có thể là một lựa chọn tốt hơn./.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *