Thứ Ba, 23 tháng 10, 2018

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;
}

Thứ Hai, 22 tháng 10, 2018

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);
}

Thứ Bảy, 24 tháng 2, 2018

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)


Thứ Tư, 19 tháng 4, 2017

Rendering các tài liệu đẹp với calibre

Có những lúc chúng ta có nhu cầu chuyển ebook file (mobi, epub) sang file pdf (để gởi cho bạn bè hay để in ấn ra giấy đọc). Có nhiều phần mềm khác nhau để làm việc này, nhưng có một phần mềm vừa cho phép đọc file ebook vừa cho phép chuyển sang các định dạng khác nhau, đồng thời lại free nữa. Đó chính là phần mềm có tên Calibre.

Calibre cho phép chúng ta can thiệp, điều chỉnh rất nhiều phần khác nhau trong quá trình chuyển đổi file. Điều này làm cho phần mềm Calibre vừa mạnh mẽ, vừa làm cho nó trở nên phức tạp đối với những người không chuyên.

Sau đây, chúng tôi sẽ hướng dẫn cách chuyển file ebook sang định dạng PDF đẹp như mong đợi.

Bước 1. Chọn file muốn chuyển đổi


Bước 2. Chọn kiểu file muốn chuyển sang và Font chữ



Bước 3. Định dạng Text


Bước 4. Thiết lập Page Setup

Bước 5. Thiết lập PDF Output

Nhấn OK để bắt đầu chuyển đổi định dạng.

Thứ Tư, 25 tháng 6, 2014

Vì sao người lương thiện cả đời gặp nỗi buồn và trắc trở?

Một bài lý giải tại sao người tốt lại gặp đều không may. 

Tôi đã tìm một người thầy thông thái và đạo hạnh xin chỉ bảo:
-Vì sao những người lương thiện như con lại thường xuyên cảm thấy khổ, mà những người ác lại vẫn sống tốt như vậy?

Thầy hiền hòa nhìn tôi trả lời:
- Nếu một người trong lòng cảm thấy khổ, điều đó nói lên rằng trong tâm người này có tồn tại một điều ác tương ứng. Nếu một người trong nội tâm không có điều ác nào, như vậy, người này sẽ không có cảm giác thống khổ. Vì thế, căn cứ theo đạo lý này, con thường cảm thấy khổ, nghĩa là nội tâm của con có tồn tại điều ác, con không phải là một người lương thiện thật sự. Mà những người con cho rằng là người ác, lại chưa hẳn là người thật sự ác. Một người có thể vui vẻ mà sống, ít nhất nói rõ người này không phải là người ác thật sự.

Có cảm giác như bị xúc phạm, tôi không phục, liền nói:
-Con sao có thể là người ác được? Gần đây, tâm con rất lương thiện mà!

Thầy trả lời:
-Nội tâm không ác thì không cảm thấy khổ, con đã cảm thấy khổ, nghĩa là trong tâm con đang tồn tại điều ác. Con hãy nói về nỗi khổ của con, ta sẽ nói cho con biết, điều ác nào đang tồn tại trong con.

Tôi nói:
-Nỗi khổ của con thì rất nhiều! Có khi cảm thấy tiền lương thu nhập rất thấp, nhà ở cũng không đủ rộng, thường xuyên có “cảm giác thua thiệt”, bởi vậy trong tâm con thường cảm thấy không thoải mái, cũng hy vọng mau chóng có thể cải biến tình trạng này; trong xã hội, không ít người căn bản không có văn hóa gì, lại có thể lưng quấn bạc triệu, con không phục; một trí thức văn hóa như con, mỗi tháng lại chỉ có một chút thu nhập, thật sự là không công bằng; người thân nhiều lúc không nghe lời khuyên của con, con cảm thấy không thoải mái…

Cứ như vậy, lần lượt tôi kể hết với thầy những nỗi thống khổ của mình.

Thầy gật đầu, mỉm cười, một nụ cười rất nhân từ đôn hậu, người từ tốn nói với tôi:
- Thu nhập hiện tại của con đã đủ nuôi sống chính con và Gia đình. Con còn có cả phòng ốc để ở, căn bản là đã không phải lưu lạc nơi đầu đường xó chợ, chỉ là diện tích hơi nhỏ một chút, con hoàn toàn có thể không phải chịu những khổ tâm ấy.

- Nhưng bởi vì nội tâm con có lòng tham đối với tiền tài và của cải, cho nên mới cảm thấy khổ. Loại lòng tham này là ác tâm, nếu con có thể vứt bỏ ác tâm ấy, con sẽ không vì những điều đó mà cảm thấy khổ nữa.

- Trong xã hội có nhiều người thiếu văn hóa nhưng lại phát tài, rồi con lại cảm thấy không phục, đây chính là tâm đố kị. Tâm đố kị cũng là một loại ác tâm. Con tự cho mình là có văn hóa, nên cần phải có thu nhập cao, đây chính là tâm ngạo mạn. Tâm ngạo mạn cũng là ác tâm. Cho rằng có văn hóa thì phải có thu nhập cao, đây chính là tâm ngu si; bởi vì văn hóa không phải là căn nguyên của sự giàu có, kiếp trước làm việc thiện mới là nguyên nhân cho sự giàu có của kiếp này. Tâm ngu si cũng là ác tâm!
Người thân không nghe lời khuyên của con, con cảm thấy không thoải mái, đây là không rộng lượng. Dẫu là người thân của con, nhưng họ vẫn có tư tưởng và quan điểm của riêng mình, tại sao lại cưỡng cầu tư tưởng và quan điểm của họ bắt phải giống như con? Không rộng lượng sẽ dẫn đến hẹp hòi. Tâm hẹp hòi cũng là ác tâm.

Sư phụ tiếp tục mỉm cười:
- Lòng tham, tâm đố kỵ, ngạo mạn, ngu si, hẹp hòi, đều là những ác tâm. Bởi vì nội tâm của con chứa đựng những ác tâm ấy, nên những thống khổ mới tồn tại trong con. Nếu con có thể loại trừ những ác tâm đó, những thống khổ kia sẽ tan thành mây khói.”
Con đem niềm vui và thỏa mãn của mình đặt lên tiền thu nhập và của cải, con hãy nghĩ lại xem, căn bản con sẽ không chết đói và chết cóng; những người giàu có kia, thật ra cũng chỉ là không chết đói và chết cóng. Con đã nhận ra chưa, con có hạnh phúc hay không, không dựa trên sự giàu có bên ngoài, mà dựa trên thái độ sống của con mới là quyết định. Nắm chắc từng giây phút của cuộc đời, sống với thái độ lạc quan, hòa ái, cần cù để thay thế lòng tham, tính đố kỵ và ích kỷ; nội tâm của con sẽ dần chuyển hóa, dần thay đổi để thanh thản và bình an hơn.

-Trong xã hội, nhiều người không có văn hóa nhưng lại giàu có, con hãy nên vì họ mà vui vẻ, nên cầu chúc họ càng giàu có hơn, càng có nhiều niềm vui hơn mới đúng. Người khác đạt được, phải vui như người đó chính là con; người khác mất đi, đừng cười trên nỗi đau của họ. Người như vậy mới được coi là người lương thiện! Còn con, giờ thấy người khác giàu con lại thiếu vui, đây chính là tâm đố kị. Tâm đố kị chính là một loại tâm rất không tốt, phải kiên quyết tiêu trừ!”

- Con cho rằng, con có chỗ hơn người, tự cho là giỏi. Đây chính là tâm ngạo mạn. Có câu nói rằng: “Ngạo mạn cao sơn, bất sinh đức thủy” (nghĩa là: ngọn núi cao mà ngạo mạn, sẽ không tạo nên loại nước tốt) người khi đã sinh lòng ngạo mạn, thì đối với thiếu sót của bản thân sẽ như có mắt mà không tròng, vì vậy, không thể nhìn thấy bản thân có bao nhiêu ác tâm, sao có thể thay đổi để tốt hơn. Cho nên, người ngạo mạn sẽ tự mình đóng cửa chặn đứng sự tiến bộ của mình. Ngoài ra, người ngạo mạn sẽ thường cảm thấy mất mát, dần dần sẽ chuyển thành tự ti. Một người chỉ có thể nuôi dưỡng lòng khiêm tốn, luôn bảo trì tâm thái hòa ái từ bi, nội tâm mới có thể cảm thấy tròn đầy và an vui.
-Kiếp trước làm việc thiện mới chính là nguyên nhân cho sự giàu có ở kiếp này, (trồng dưa được dưa, trồng đậu được đậu). Mà người thường không hiểu được nhân quả, trồng dưa lại muốn được đậu, trồng đậu lại muốn được dưa, đây là thể hiện của sự ngu muội. Chỉ có người chăm học Phật Pháp, mới có được trí huệ chân chính, mới thật sự hiểu được nhân quả, quy luật tuần hoàn của vạn vật trong vũ trụ, nội tâm mới có thể minh tỏ thấu triệt. Để từ đó, biết làm thế nào lựa chọn tư tưởng, hành vi và lời nói của mình cho phù hợp. Người như vậy, mới có thể theo ánh sáng hướng đến ánh sáng, từ yên vui hướng đến yên vui.”

-Bầu trời có thể bao dung hết thảy, nên rộng lớn vô biên, ung dung tự tại; mặt đất có thể chịu đựng hết thảy, nên tràn đầy sự sống, vạn vật đâm chồi! Một người sống trong thế giới này, không nên tùy tiện xem thường hành vi và lời nói của người khác. Dẫu là người thân, cũng không nên mang tâm cưỡng cầu, cần phải tùy duyên tự tại! Vĩnh viễn dùng tâm lương thiện giúp đỡ người khác, nhưng không nên cưỡng cầu điều gì.

-Nếu tâm một người có thể rộng lớn như bầu trời mà bao dung vạn vật, người đó sao có thể khổ đây?

Vị thầy khả kính nói xong những điều này, tiếp tục nhìn tôi với ánh mắt đầy nhân từ và bao dung độ lượng.

Ngồi im lặng hồi lâu…xưa nay tôi vẫn cho mình là một người rất lương thiện, mãi đến lúc này, phải! chỉ đến lúc này, tôi mới biết được trong tôi còn có một con người rất xấu xa, rất độc ác! Bởi vì nội tâm của tôi chứa những điều ác, nên tôi mới cảm thấy nhiều đau khổ đến thế. Nếu nội tâm của tôi không ác, sao tôi có thể khổ chứ ?
Xin cảm tạ thầy, nếu không được người khai thị dạy bảo, con vĩnh viễn sẽ không biết có một người xấu xa như vậy đang tồn tại trong con!

Từ Đạo Tâm