Tiếp cận ngôn ngữ lập trình mới

TIẾP CẬN NGÔN NGỮ LẬP TRÌNH NHƯ THẾ NÀO?

Khi dự định học một ngôn ngữ lập trình mới, chúng ta thường cảm thấy choáng ngợp vì sự lạ lẫm, đồ sộ, phức tạp của ngôn ngữ mới. Chính vì vậy, chúng ta cần suy nghĩ về phương pháp tiếp cận ngôn ngữ để việc học ngôn ngữ mới diễn ra tự nhiên và nhanh chóng.

Khi học một ngôn ngữ lập trình mới, chúng ta có thể từng bước tìm hiểu các thành phần cơ bản của ngôn ngữ như sau:
- Học cách khai báo một số kiểu cơ bản: số nguyên, số thực, ký tự, chuỗi, mảng một chiều, mảng hai chiều (hay nhiều chiều hơn)
- Xem qua các phép toán trên số: +, -, x, :, chia lấy dư (mod)
- Tìm hiểu 3 loại lệnh: lệnh gán, lệnh điều kiện, lệnh lặp
- Các thao tác trên mảng một chiều, hai chiều
- Sử dụng các hàm cơ bản trên chuỗi: sao chép chuỗi con, xóa chuỗi con, chèn chuỗi con, ...
- Cách viết hàm
- Viết thử các thuật toán cơ bản: như sắp xếp, tìm kiếm, ...

Sau khi đã tìm hiểu và thực hành các nội dung trên, chúng ta có thể tự tin cho rằng mình đã nắm được nội dung cơ bản của ngôn ngữ mới và có thể sử dụng ngôn ngữ mới để làm việc và/hoặc sẵn sàng học thêm những phần cao cấp khác của ngôn ngữ mới.

Sàng nguyên tố trên đoạn [L, R]

SÀNG NGUYÊN TỐ TRÊN ĐOẠN [L, R]

Bài toán: Hãy tìm các số nguyên thuộc đoạn [L, R], trong đó (1<=L<=R<=2.000.000.000 và R-L<=1.000.000).

Thuật toán:
- Trường hợp 1. Nếu R<=1.000.000 thì áp dụng phương pháp sàng bình thường
- Trường hợp 2. Nếu R>1.000.000 thì ta có có nhận xét

Nhận xét: nếu số nguyên n không là số nguyên tố thì n có ước số là sqrt(n).
Trong trường hợp n là số lớn nhất như trong đề bài, tức là n=2.000.000.000 thì n có ước số nhỏ hơn hay bằng sqrt(n)=44.722. Vậy ta sẽ tìm các số nguyên tố nhỏ hơn hay bằng 44.722


Bước 1. Sàng các số nguyên tố trên đoạn [1...44.722], để cho gọn gàng ta có thể sàng trên đoạn [1...50.000], còn nếu chính xác thì ta chỉ cần sàng trên đoạn [1...sqrt(R)]
Bước 2. Xét các số nguyên tố i trong đoạn [1...sqrt(R)], ta sẽ loại bỏ đi các số không nguyên tố j là bội của i. Nhưng để cho nhanh ta phải tính toán sao cho j thuộc [L, R]

Cách tính j:
- Nếu L chia hết cho i thì j=L
- Nếu L không chia hết cho i thì:
  + Tìm số lớn nhất gần L mà chia hết cho i, tức là ta lấy số L trừ đi phần dư khi chia L cho i: k=L-(L%i). Lúc này k chia hết cho i.
  + Vậy j = k+i sẽ là số lớn hơn L và chia hết cho i

Cách đánh dấu đoạn [L, R]:
- Vì L, R có thể lên đến 2 tỷ, nhưng đoạn từ L đến R chỉ có tối đa 1 triệu số nên ta ánh xạ đoan [L, R] sang đoạn [0, R-L]

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

bitset<1000000+10> isSmallPrime;
bitset<1000000+10> isLargePrime;

vector<int> primes;

void SangTrenDoan(int L, int R) {
  // Buoc 1: Sang các số nguyên tố <= sqrt(R)
  int n = (int) sqrt(R);
  isSmallPrime.set(); isSmallPrime[0]=isSmallPrime[1]=false;
  for (int i=4; i<=n; i+=2) isSmallPrime[i]=false;

  for (int i=3; i*i<=n; i+=2)
    if (isSmallPrime[i])
      for (int j=i*i; j<=n; j+=i) isSmallPrime[j]=false;

  // Bước 2: Sang các số nguyên tố thuộc đoạn [L, R]
  isLargePrime.set();
  for (int i=2; i*i<=R; i++)
    if (isSmallPrime[i]) {
      if (L%i==0) 
        for (int j=L; j<=R; j+=i) isLargePrime[j-L]=false;
      else if (L>i) {
        int du = L%i;
        for (int j=(L-du)+i; j<=R; j+=i) isLargePrime[j-L]=false;
      }
    }
   
  for (int i=L; i<=R; i++)
    if (isLargePrime[i-L]) primes.push_back(i);
}

Lập trình là gì

LẬP TRÌNH LÀ GÌ?

Lập trình là gì?
Lập trình là giải quyết vấn đề bằng cách viết các chương trình máy tính.

Định nghĩa ngắn gọn trên, nhấn mạnh rằng người lập trình là người giải quyết vấn đề, là một solver. Qua đó định hướng cho người lập trình là phải luôn luôn có thói quen suy nghĩ về các cách giải quyết vấn đề.

Học lập trình cần học gì?
Vì lập trình là giải quyết vấn đề nên người lập trình cần phải học:
(1) Học ngôn ngôn ngữ lập trình: Học ngôn ngữ lập trình để chúng ta có thể hiểu được khả năng của máy tính, khả năng của ngôn ngữ. Và qua ngôn ngữ lập trình chúng ta sẽ thể hiện các ý tưởng của mình cho máy tính thực hiện
(2) Học phương pháp giải quyết vấn đề: Học phương pháp giải quyết vấn đề thông qua các phần như
  + Học các thuật toán và cấu trúc dữ liệu kinh điển
  + Học phương pháp thiết kế thuật toán, như: (1) phương pháp chia để trị, (2) phương pháp quy hoạch động, (3) phương pháp tham lam, (4) phương quay lui, (5) phương pháp nhánh cận
  + Học các mô hình toán, công cụ toán cho từng loại bài toán
  + Rèn luyện, tìm tòi, học hỏi các ý tưởng giải quyết từng bài toán cụ thể khác nhau

Việc học ngôn ngữ mới có thể thực hiện trong 1-2 tuần là có thể nắm được cơ bản của ngôn ngữ và có có thể sử dụng ngôn ngữ đó để làm việc. Trong quá trình làm việc chúng ta sẽ tìm hiểu thêm về ngôn ngữ và sẽ dần dần thành thạo ngôn ngữ.

Việc học phương pháp giải quyết vấn đề là hành trình không bao giờ kết thúc. Chính vì vậy chúng ta không thể ép bản thân phải nắm mọi thứ trong thời gian ngắn. Chúng ta cứ từ từ học, cần học điều đặn mỗi ngày một chút

Lập trình, khoa học và nghệ thuật

Lập trình, khoa học và nghệ thuật

Lập trình vừa mang tính khoa học vừa mang tính nghệ thuật

1. Tính khoa học của lập trình thể hiện:
Mỗi bước trong thuật toán, mỗi lệnh trong chương trình phải:
- Có lý do
- Logic
- Chính xác
- Được chứng minh rõ ràng hay phải dựa trên mô hình toán, hay mô hình xác suất đã được chứng minh
- Tính khoa học còn thể hiện ở sự bất định của chương trình, chương trình thường có lỗi, cần luôn cải tiến, xem đi xem lại


2. Tính nghệ thuật của lập trình thể hiện:
- Trong ý tưởng:
  + Ý tưởng đơn giản, hiệu quả
  + Ý tưởng có tính bất ngờ
  + Ý tưởng được lấy ra trong đời sống thường ngày hay trong thế giới tự nhiên
  + Mỗi ý tưởng đều có một câu truyện đằng sau nó

- Trong khi viết chương trình:
  + Cấu trúc chương trình đơn giản, rõ ràng, đẹp đẽ
  + Các biến được đặt tên có nghĩa, dễ đọc, dễ hiểu
  + Mỗi đoạn chương trình được viết ngắn gọn, dễ đọc, dễ nhớ
  + Mỗi dòng lệnh, đoạn mã thể hiện một câu truyện. Chúng diễn đạt rất tự nhiên những suy nghĩ của người lập trình

Cho nên khi lập trình, chúng ta cần chú ý, thể hiện cả tính khoa học và tính nghệ thuật trongchương trình.

Cây khung nhỏ nhất - Thuật toán Prim

Cây khung nhỏ nhất - Thuật toán Prim

Độ phức tạp: O(E * logV)


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

const int INT_MAX = 1e9; typedef pair<int, int> pii;

// input
vector<vector<pii> > adj;

// output
vector<int> pre;


long long Prim() {
  int n = adj.size();
  pre.assign(n, -1);
  vector<bool> visited(n);
  vector<int> dist(n, INT_MAX);
  dist[0] = 0;

  priority_queue<pii, vector<pii> , greater<pii> > q;
  q.push(make_pair(0, 0));

  long long res = 0;

  while (!q.empty()) {
    int d = q.top().first;
    int u = q.top().second;
    q.pop();
    
    if (visited[u]) continue;

    visited[u] = true;
    res += d;

    for (int i = 0; i < (int) adj[u].size(); i++) {
      int v = adj[u][i].first;

      if (visited[v]) continue;

      int nprio = g[u][i].second;
      if (dist[v] > nprio) {
        dist[v] = nprio;
        pred[v] = u;
        q.push(make_pair(nprio, v));
      }
    }
  }

  return res;
}


int main() {
  adj.resize(3);
  adj[0].push_back(make_pair(1, 10));
  adj[1].push_back(make_pair(0, 10));
  adj[1].push_back(make_pair(2, 10));
  adj[2].push_back(make_pair(1, 10));
  adj[2].push_back(make_pair(0, 5));
  adj[0].push_back(make_pair(2, 5));

  long long res = Prim();
  cout << res << endl;
}

Ước số chung lớn nhất - Bội số chung nhỏ nhất

Thuật toán tìm ước số chung lớn nhất - bội số chung nhỏ nhất

Khái niệm: Ước số chung lớn nhất của hai số nguyên a và b, ký hiêu là USCLN(a, b), là số nguyên d lớn nhất mà cả a và b đều chia hết cho d.

Công thức: USCLN(a, b) = USCLN(b, a mod b)

Nhận xét: Công thức đệ quy trên sẽ dừng khi b=0 và kết quả là a

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int USCLN(int a, int b) {

  if (b==0) return a;

  return USCLN(b, a%b);

}

Khái niệm: Bội số chung nhỏ nhất của hai số nguyên a và b, ký hiêu là BSCNN(a, b), là số nguyên d nhỏ nhất mà d đều chia hết cho cả a và b.

Công thức: BSCNN(a, b) = (a*b)/USCLN(a, b)

Nhận xét: Cả a và b đều chia hết cho USCLN(a, b) nên chúng ta có thể viết lại công thức trên để tránh việc tràn số khi tính toán phép nhân trước: BSCNN(a, b) = a/USCLN(a, b)*b;

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int BSCNN(int a, int b) {

  return a/USCLN(a, b)/b;

}

Phân tích thừa số nguyên tố

Thuật toán phân tích thừa số nguyên tố

Chức năng: Phân tích số nguyên n thành các thừa số nguyên tố

Chương trình:

#include <bits/stdc++.h>

using namespace std;

vector<int> p, alpha;

void Factor(int n) {

  if ((n<=1000000 && isPrime[n]) || (n>1000000 && IsPrime(n) == true)) {

    p.push_back(n); alpha.push_back(1);

    return;

  }

  int i=0;

  while (n>1) {

    while ((i<primes.size()) && (n%primes[i]!=0)) i++;

    if (i==primes.size()-1) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

    int count=0;

    while (n%primes[i] == 0) {

      count++; 

      n = n/primes[i];

    }

    p.push_back(primes[i]); alpha.push_back(count);

    if ((n<=1000000 && isPrime[n])) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

  }

}

Kiểm tra số nguyên tố

Thuật toán kiểm tra số nguyên tố

Chức năng: Kiểm tra số nguyên n có phải là số nguyên tố không

Thuật toán 1: Kiểm tra số n có chia hết cho các số i, số nguyên i chạy từ 2 đến sqrt(n), hay không
Thuật toán 2: Cải tiến giá trị của biến chạy i
Số nguyên i luôn có một trong các dạng sau:
  (1) 6k+1, 6k-1
  (2) 6k+2, 6k-2

  (3) 6k+3, 6k-3

Trường hợp i có dạng 6k+2, 6k-2, lúc đó i chia hết cho 2. Nếu n chia hết cho i thì n chia hết cho 2
Trường hợp i có dạng 6k+3, 6k-3, lúc đó i chia hết cho 3. Nếu n chia hết cho i thì n chia hết cho 3

Chúng ta kiểm tra trường hợp i có dạng (1) và (2) riêng bằng cách kiểm tra n có chia hết cho 2 hay 3 không

Sau đó chúng ta xét i có dạng (3), tức là i có giá trị: (5, 7), (11, 13), (17, 19), ...

Độ phức tạp: O(sqrt(n))

Chương trình:

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n) {

  if (n<2) return false;

  if (n==2 || n==3) return true;

  if (n%2==0 || n%3==0) return false;

  for (int i=5; i*i<=n; i+=6)

    if (n%i==0 || n%(i+2)==0) return false;

  return false;

}

Nếu chúng ta đã tính sàng nguyên tố hoặc việc tính sàng nguyên tố không ảnh hưởng độ phức tạp của thuật toán cả chương trình thì chúng ta có thuật toán kiểm tra số nguyên tố sau hiệu quả hơn bằng cách xét xem n có chia hết các số nguyên tố không.

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n) {

  if (n<2) return false;

  if (n<=1000000) return isPrime[i];

  for (int i=0; primes[i]*primes[i]<=n; i++)

    if (n%primes[i]==0) return false;

  return false;

}

Sàng nguyên tố Eratosthenes

Thuật toán Sàng nguyên tố Eratosthenes

Chức năng: Sàng nguyên tố Eratosthenes có hai chức năng

(1) Liệt kê các số nguyên tố nhỏ hơn hay bằng n

(2) Tạo mảng dùng để truy vấn kiểm tra môt số có phải là số nguyên tố hay không

Độ phức tạp: O(N*loglogN)

Chương trình:

#include <bits/stdc++.h>

using namespace std;

bitset<1000000+10> isPrime;

vector<int> primes;

void Eratosthenes(int n) {

  isPrime.set(); isPrime[0]=isPrime[1]=false;

  for (int i=4; i<=n; i+=2) isPrime[i]=false;

  for (int i=2; i*i<=n; i++)

    if (isPrime[i])

     for (int j=i*i; j<=n; j+=i) isPrime[j] = false;

  for (int i = 2; i <= n; i++) if (isPrime[i]) primes.push_back(i);

}

Các khía cạnh của toán học

Toán học có 3 khía cạnh:
1. Các cấu trúc (biểu diễn, mô tả): cấu trúc đồ thị, cấu trúc nhóm (cấu trúc đối xứng), cấu trúc số phức, cấu trúc số tự nhiên, ... Cần phải học cách phân tích các cấu trúc, tìm các cấu trúc thích hợp.
2. Các đại lượng (con số, các phép toán, các đo lường, tính toán)
3. Các thuật toán (phương pháp tiếp cận, chiến lược, các bước)