Phân biệt tham chiếu và tham trị

Tham trị

Tiếng Anh là pass-by-value. Tham trị có nghĩa là chỉ truyền giá trị của biến này cho một biến mới và khi thay đổi biến mới không làm thay đổi biến cũ

truyen-tham-so

 

Tham biến

Tên tiếng anh là pass-by-reference. Truyền tham biến có nghĩa là truyển cho biến mới địa chị ô nhớ y hệt của biến cũ mặc dù tên biến khác. Khi thay đổi biến mới thì cũng làm thay đổi biến cũ. Truyển tham biến còn được hiểu là thêm một nickname mới cho biến cũ.

tham-tri

MULONE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';//MULONE.INP';
  fo = '';//MULONE.OUT';
  maxn = 10000000;
var
  n,test,t : longint;
  kq : array[1..maxn] of longint;
 
procedure sol;
var
  i,nho,tong : longint;
  count : longint;
begin
  tong:=0; nho:=0; count:=0;
  for i:=1 to n do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=n-1 downto 1 do
    begin
      tong:=(i+nho) mod 10;
      nho:=(i+nho) div 10;
      inc(count);
      kq[count]:=tong;
    end;
  for i:=count downto 1 do write(kq[i]);
  writeln;
end;
 
BEGIN
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
  readln(T);
  for test:=1 to T do
    begin
      readln(N);
      sol;
    end;
  close(input);
  close(output);
END.

C11PNUM – spoj

Đề bài:

Thuật toán:

  • Sàng nguyên tố
  • Tính các tích k số nguyên tố liên tiếp để cập nhập cho kết quả

Code:

const   fi='';
        fo='';
        oo=3000000;
var     k,t,i,j,tt:longint;
        tam,n,res:qword;
        f:text;
        tmp:array[2..oo] of boolean;
        ngto:array[1..oo] of longint;
        d	:longint;
function max(a,b:qword):qword;
begin
        if a>b then exit(a) else exit(b);
end;
procedure xl;
var     i,j :longint;
begin
	for i:=1 to d-k+1 do
		begin
			tam :=1;
			for j:=i to i+k-1 do
			begin
				tam := tam*ngto[j];
			end;
                        if tam>n then break else res := max(res,tam);
		end;
end;
procedure init;
begin
        for i:=2 to trunc(sqrt(oo)) do
                if tmp[i]=false then
                        begin
                            j:=i*i;
                            while j<=oo do
                                begin
                                    tmp[j]:=true;
                                    j:=j+i;
                                end;
                        end;
        d:=0;
        for i:=2 to oo do
                if tmp[i]=false then begin inc(d); ngto[d]:=i; end;
        j:=d;
end;
procedure nhap;
begin
    assign(f,fi);reset(f);
    assign(output,fo);rewrite(output);
    read(f,t);
    for tt:=1 to t do
        begin
            read(f,n,k);
            res := 0;
            xl;
            if res=0 then writeln(-1) else writeln(res);
        end;
    close(f);close(output);
end;
begin
    init;
    nhap;
end.

Ứng dụng của đồ thị

Ta đang sống trong một thế giới mà mọi vật được liên kết, các thành phố được liên kết với nhau bởi các con đường, con người liên kết với nhau trên mạng xã hội… những liên kết như vậy chính là hình hài của đồ thị. Một trong những đồ thị lớn mà ai trong chúng ta cũng biết đó chính là Internet hay là mạng tìm kiếm Google.

Đồ thị được sinh ra từ nhu cầu giải quyết những vấn đề thực tế của đời sống. Ví dụ như là bài toán ‘7 cây cầu Königsberg’ từ những năm 1720. Đồ thị là một phần quan trọng trong Toán học rời rạc, là cơ sở của Tin học. Ứng dụng của nó vô cùng rộng, áp dụng vào trong nhiều lĩnh vực. Trong phạm vi bài viết, tác giải chỉ đề cập đến một vài ứng dụng thực tế cơ bản.

Bài toán bảy cây cầu

Tìm đường đi ngắn nhất

Trong thực tế, ta luôn phải lựa chọn đường đi ngắn nhất để đi sao cho tiết kiệm xăng. Đầu tiên là biểu diễn mạng giao thông dưới dạng đồ thị rồi sử dụng thuật toán tìm đường đi ngắn nhất. Thường thì mọi người sử dụng thuật toán Dijkstra nhưng giả dụ với dữ liệu không lồ như của Google Map thì thuật toán này không thể đáp ứng. Google đang sử dụng một thuật toán có tộc độ nhanh hơn nhiều thuật toán Dijkstra.

Tìm đường trên Google Maps

Nhưng nếu muốn tìm đường giữa Hà Nội và New York thì sao? Giữa chúng có hàng tỉ tỉ giao lộ thì phải làm thế nào?

 

Tô màu đồ thị

Ứng dụng điển hình của tô màu đồ thị là bài toán tô màu bản đồ. Làm sao để tô màu bản đồ sao cho không có hai vùng kề nhau có cùng màu và số màu cần dùng là ít nhất.

Biểu diễn bài toán dưới dạng đồ thị:

  • Coi mỗi vùng là một đỉnh
  • Hai đỉnh có cạnh nối với nếu hai vùng tương ứng kề nhau

Bài toán trở thành tô màu các đỉnh của đồ thị, giải quyết sẽ đơn giản hơn bài toán ban đầu.

Bài toán tô màu bản đồ

Một ứng dụng khác là trong bài toán xếp lịch ở UET, làm sao để xếp lịch thi cho sinh viên sao cho nếu sinh viên học môn A và môn B thì hai môn này không thi cũng lúc, ngoài ra kì thi cần kết thúc sớm nhất.

Với bài này ta giải quyết thế nào?

Gọi mỗi môn học là một đỉnh, hai đỉnh được nỗi với nhau nếu tồn tại học sinh học cả 2 môn này. Bài toán giờ trở thành bài toán tô màu cho các đỉnh.

 

Đồ thị hai phía

graph-yeulaptrinh.pw

Đồ thị ghép cặp hẹn hò

Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp, quan hệ hôn nhân giữa tập những người đàn ông và tập những người phụ nữ, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v…

 

Cài đặt SDL cho CodeBlocks

Tải về

  • Tải về: https://www.libsdl.org/projects/SDL_image/release/SDL2_image-devel-2.0.3-mingw.tar.gz
  • Giải nén ra thì thấy có 2 thư mục:
    • Bản 32bit: i686-w64-mingw32
    • Bản 64bit: x86_64-w64-mingw32
  • Ở đây ta dùng bản 32 bit (vì CodeBlock đang dùng mingw32),
  • Trong thư mục này có 4 thư mục bin, include, lib, share
  • Thư mục bin chứa SDL2.dll (liên kết khi chạy, copy file này vào thư mục
    mã nguồn project, cùng folder với main.cpp
    )
  • Thư mục include chứa các file .h (như stdio.h) khai báo các hàm của SDL. Cũng coppy vào thư mục project.
  • Thư mục lib chứa các thư viện (mã đối tượng) để liên kết chương trình. Tương tự như trên, cũng copy vào thư mục project

Cấu hình CodeBlocks

Settings / Compiler / Linker Settings / Other linker… 

Gõ thêm vào: -lmingw32 -lSDL2main -lSDL2

Làm như trên để khi biên dịch chương trình, Codeblocks sẽ biên dịch cả những thứ trong thư viện SDL

Tiếp theo, chọn tab Search directories / Compilers

Thêm vào đường dẫn đến thư mục SDL. Ví dụ: e:\myproject\SDL\

Chuyển sang tab Linker, thêm đường dẫn tới thư mục lib. Ví dụ: e:\myproject\lib

 

Queue (hàng đợi) trong C++

Queue là một loại cấu trúc dữ liệu và một loại container adaptor, được thiết kế để hoạt động theo kiểu FIFO (First – in first – out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách.

Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.

Khai báo: #include <queue>

Các hàm thành viên:

  • size : trả về kích thước hiện tại của queue. ĐPT O(1).
  • empty : true nếu queue rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy vào cuối queue. ĐPT O(1).
  • pop: loại bỏ phần tử (ở đầu). ĐPT O(1).
  • front : trả về phần tử ở đầu. ĐPT O(1).
  • back: trả về phần tử ở cuối. ĐPT O(1).

Chương trình demo:

#include <iostream>

#include <queue>

using namespace std;

queue <int> q;

int i;

main() {
  for (i=1;i<=5;i++) q.push(i);
  // q={1,2,3,4,5}
  q.push(100);
  // q={1,2,3,4,5,100}
  cout << q.front() << endl;
  // In ra 1
  q.pop();
  // q={2,3,4,5,100}
  cout << q.back() << endl;
  // In ra 100
  cout << q.empty() << endl;
  // In ra 0
  cout << q.size() << endl;
  // In ra 5
  system("pause");
}

Stack (ngăn xếp) trong C++

Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last – in first – out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.

 

Khai báo: #include <stack>

 

Các hàm thành viên:

  • size : trả về kích thước hiện tại của stack. ĐPT O(1).
  • empty : true stack nếu rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy phần tử vào stack. ĐPT O(1).
  • pop : loại bỏ phẩn tử ở đỉnh của stack. ĐPT O(1).
  • top : truy cập tới phần tử ở đỉnh stack. ĐPT O(1).

Chương trình demo:

#include <iostream>

#include <stack>

using namespace std;

stack <int> s;

int i;

main() {

  for (i=1;i<=5;i++) s.push(i); // s={1,2,3,4,5} 
  s.push(100); // s={1,2,3,4,5,100} 
  cout << s.top() << endl; // In ra 100 
  s.pop(); // s={1,2,3,4,5} 
  cout << s.empty() << endl; // In ra 0 
  cout << s.size() << endl; // In ra 5 system("pause");

}