Giói thiệu về ngôn ngữ lập trình Go

Ở đây, tui sẽ giới thiệu một ngôn ngữ còn khá lạ lẫm với người Việt, đó là Go – một ngôn ngữ lập trình Server-side được phát triển bởi Google. Ngôn ngữ Go được phát triển từ năm 2007 bởi Robert Griesemer, Rob Pike, và Ken Thompson ở Google. Đến nay có thêm Ian Lance Taylor, Russ Cox và Andrew Gerrand tham gia với vai trò là một trong những thành viên trụ cột.

Tới thời điểm này, khá nhiều ngôn ngữ đã ra đời phục vụ việc lập trình cho phía Server-side như: PHP, Ruby on Rails, Python, NodeJs… Mỗi ngôn ngữ đều có những ưu khuyết điểm riêng. Những riêng Go thì khá là toàn diện.

Giới thiệu Go

Go là một ngôn ngữ lập trình đồng thời (Concurrent Program) được Google giới thiệu lần đầu tiên vào nằm 2009. Go được các thành viên phát triển nói đến về một ngôn ngữ cho server, được phát triển cho cộng đồng trên nền C.

Go được ví như C – rút gọn. Những gì bạn có thể viết được trên C, bạn có thể viết được trên Go với tốc độ nhanh hơn gấp 5 lần với khác biệt rất nhỏ. Có thể đối với những bạn thường lập trình trên C# hay Java thì Go nhìn có vẻ khá lạ lẫm, nhưng khi bạn đã làm quen dc với Go, bạn sẽ thấy Go khá thú vị và tốc độ lập trình rất nhanh (như tui đã đề cập trước đó)

Một trong những điểm tui thích nhất ở Go là tốc độ xử lý. Trong khi C được đánh giá có tốc độ xử lý cực nhanh, thì Go chỉ bị C bỏ lại với khoảng cách rất gần! Trước khi nhìn vào benchmark của Go, tui sẽ giởi thiệu với các bạn các cú pháp syntax Go chuẩn, các kiểu dữ liệu cơ bản, và so sánh nó với C.

Go, một ngôn ngữ server ngắn gọn

Nói đến đây, bạn có thấy Go thú vị và hấp dẫn hơn một tẹo rồi phải không? Mong là vậy! Dù rồi hay chưa, tui sẽ tăng tính thuyết phục và đặc sắc của Go bằng cách cho bạn xem những syntax đẹp và so sánh nó với C! Thứ nhất, khai báo biến (variable) trong Go vô cùng ngắn gọn. Thay vì khai báo cụ thể kiểu dữ liệu của biến, Go có bộ tham chiếu kiểu dữ liệu (type inference) thực hiện việc gán kiểu và khởi tạo biến cho chúng ta. Để khai báo một biến đơn giản… Trong C:

int myVar = 33;
Trong Go:
myVar := 33
Ngắn gọn hơn C, bạn có thể thấy như thế! Không chỉ có thế, Go không đòi hỏi kết thúc câu lệnh bằng dấu “;”, trả về nhiều kết quả trong function, và có thể trả về cặp (pair) kết quả và lỗi cho bạn (result, err). Pair cũng là cách chuẩn để xử lý lỗi trong Go. Tôi sẽ đề cập kỹ hơn ở các bài viết về syntax trong Go. Hơn vậy, bạn có thể định nghĩa một biến bằng utf-8, một điều khá mới mẻ trong Go, ví dụ: biếnSố := 33 Bây giờ, ta tiến hành xét một chương trình Hello World trong Go và C:

helloworld.c

#include <stdio.h>
 
int main ()
{
  printf ("Hello World!\n");
}
helloworld.go
package main
 
import (
    "fmt"
)
 
func main() {
    fmt.Println("Hello World!")
}
Chúng ta có thể thấy được sự tương đồng giữa Go và C qua đoạn code trên Bạn sẽ thấy được Go ngắn gọn hơn C rõ ràng hơn khi bạn viết các chương trình lớn, phức tạp và cần xử lý đồng thời (concurrency). Có một bài blog so sánh C và Go, cũng như các chi tiết về những lợi thế về syntax của Go so với C: http://www.syntax-k.de/projekte/go-review Tiếp theo. chúng ta sẽ so sánh khả năng chịu tải của Go để xem Go có thực sự chịu tải tốt đúng như tuyên bố của những lập trình viên hay không

Khả năng chịu tải của Go

Hãy nhìn cách Go chạy một loạt các chương trình đơn giản nhưng lặp đi lặp lại trong bảng dưới đây:

( Website test trực tuyến: http://benchmarksgame.alioth.debian.org/ )

Như chúng ta thấy từ số liệu thống kê, Golang hiệu quả hơn Ruby rất nhiều!!! Trong chương trình đầu tiên – ‘fasta-redux’, Ruby mất 110 giây để thực thi xong, nhưng Go chỉ mất 1.79 giây. Nhanh hơn gấp gần 100 lần! Quá ấn tượng phải không!!!

Go không chỉ ấn tượng về tốc độ xử lý, mà còn thuận lợi về xử lý đồng thời hơn hầu hết các ngôn ngữ server hiện giờ. Go sử dụng các Goroutines (tui sẽ nói rõ hơn về Goroutlines ở những bài viết sau).

Go đã cung cấp được chúng ta một ngôn ngữ lập trình ở server với tốc độ cực nhanh, một cú pháp ngắn gọn, hằng trăm package mặc định hữu dụng, cơ chế xử lý đa luồng đồng thời, và vô số thư viện được phát triển bởi các lập trình viên trên khắp thế giới. Tất cả giúp chúng ta xây dựng website, server bằng Go một cách nhanh và hiệu quả nhất.

Tóm tắt

Với tuổi đời còn khá non trẻ (từ 2009) so với những ngôn ngữ khác (C hơn 40 năm, C++ hơn 30 năm, Ruby khoảng 20 năm, Java cỡ 17 năm, C# tầm 10-12 năm…) thì 5 năm thực sự là khoảng thời gian không nhiều để ta so sánh những sản phẩm nổi bật được viết và phát hành bằng Go so với những ngôn ngữ khác. Tuy nhiên, Go đang được Google và cộng đồng lập trình viên tiếp tục phát triển và hoàn thiện. Tin vui là hiện nay, cộng đồng quan tâm đến Go trên thế giới không nhỏ!

Cộng đồng Go lớn nhất hiện nay trên thế giới là Gopherarcademy, bên cạnh đó còn cóGoMeetUp

Một trong những event lớn về Go trong thời gian gần đây là ngày 23 – 25/01/2015 vừa qua, GopherGala đã đứng ra tổ chức sự kiện Hackathon đầu tiên cho Go trên toàn thế giới

Go đang dần được chấp nhận và triển khai rộng rãi trên nhiều Startup và Công ty thương mại. Nhiều nhà cung cấp Saas/ Paas sử dụng Go trong dự án của họ. Dịch vụ gửi mail SendGrid cũng đang áp dụng Go để xây dựng hệ thống mạnh mẽ hơn, nhanh hơn và đáng tin cậy hơn!

Túm cái váy lại, nếu bạn đang tìm kiếm một ngôn ngữ lập trình đồng thời, song song, đơn giản, sexy và tuyệt vời, hãy đến với Go!

Tạo Makefile trên Go

Makefile thực hiện một số thao tác thường dùng trong Go

Khi làm project Go mình thường tạo một file Makefile có form như này:

Lưu ý nhớ thay &lt;tên-file-binary-muốn-build&gt; thành tên mà bạn muốn build ra.

Makefile

SRC = $(wildcard *.go)
OUT = <tên-file-binary-muốn-build>

CC = go
go = $(shell which go 2> /dev/null)

ifeq (, $(go))
    @printf "\e[91mGo not found!"
endif

$(OUT): clean $(SRC)
    @printf "\e[33mBuilding\e[90m %s\e[0m\n" $@
    @$(CC) build -o $@ $(SRC)
    @printf "\e[34mDone!\e[0m\n"

test: clean
    @printf "\e[33mTesting...\e[0m\n"
    go test ./...
    @printf "\e[34mDone!\e[0m\n"

clean:
    @rm -f $(OUT)
    @printf "\e[34mAll clear!\e[0m\n"

install: $(OUT)
    @printf "\e[33mInstalling\e[90m %s\e[0m\n" $(OUT)
    sudo rm -f /usr/local/bin/$(OUT)
    sudo ln -s $(PWD)/$(OUT) /usr/local/bin/$(OUT)
    @printf "\e[34mDone!\e[0m\n"

uninstall:
    @printf "\e[33mRemoving\e[90m %s\e[0m\n" $(OUT)
    sudo rm -f /usr/local/bin/$(OUT)
    @printf "\e[34mDone!\e[0m\n"
Chức năng gồm có:

Tự động build thành file binary với tên file được định sẵn

Chạy lệnh:

make
alt text

Chạy toàn bộ test của tất cả các packages trong project

Chạy lệnh:

make test

alt text

Build và install vào /usr/local/bin

Nếu viết các ứng dụng command line, thì chức năng này sẽ giúp bạn tiết kiệm thời gian và có thể test thực tế trên môi trường của máy bằng cách copy file binary được build ra vào thư mục /usr/local/bin. Khi đó bạn có thể chạy chương trình của mình ở bất kì thư mục nào trong máy tính.

make install

alt text
Khi không cần dùng nữa hoặc muốn gỡ nó ra thì chạy:

make uninstall

Hướng dẫn cài đặt và viết chương trình với Go

Mình khuyến khích các bạn sử dụng môi trường Unix như Linux hay Mac OS X cho việc dev. Mình không ghét Windows nhưng mà cài đặt môi trường dev trên win rất tốn thời gian và phiền phức (các bạn đã từng cài đặt môi trường Python hay Ruby chắc sẽ đồng ý).

Nếu không có điều kiện sử dụng các môi trường Unix, các bạn có thể dùng Docker hoặc Vagrant, sẽ tiện hơn là cài trực tiếp trên môi trường Windows.

 

Bước 1: Cài đặt Go runtime

 

Windows

Đối với các bạn dùng Windows, cài bằng bộ cài MSI sẽ tiện hơn, nó sẽ tự động config hết mọi thứ cần thiết.

Đầu tiên, tải bộ cài tại đây https://golang.org/dl và chạy file go<version>.windows-386.msi (32 bit) hoặc go<version>.windows-amd64.msi (64 bit), tuỳ vào hệ điều hành bạn đang sử dụng.

 

Linux và Mac OS X

Với các bạn xài môi trường Unix, chúng ta nên cài bằng dòng lệnh.

Chúng ta sẽ cài Go thông qua Homebrew (có thể bỏ qua nếu bạn đã cài trước rồi), khởi động Terminal lên và gõ:

ruby -e "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/master/install)"
Sau khi cài xong Homebrew, chúng ta bắt đầu cài Go với lệnh:
$ brew install go --cross-compile-common
Ngồi rung đùi vài phút (hoặc vài giây, hoặc vài tiếng, tuỳ vô đường truyền nhà bạn).

 

Mac OS X Installer

Trên Mac, nếu bạn không thích cài bằng dòng lệnh, có thể tải bộ cài từ trang chủ https://golang.org/dl/ và cài trực tiếp.

Go runtime sẽ được cài vào thư mục /usr/local/go và chúng ta cần setup biến môi trường (PATH) ở bước tiếp theo.

 

Bước 2: Cài đặt biến môi trường

 

Windows

Trên Windows, chúng ta sẽ cài đặt biến môi trường bằng cách click phải vào My Computer chọn Properties, chọn tab Advanced và click nút Environment Variables.

Nếu bạn cài đặt Go vào thư mục mặc định là C:\Go thì bạn cần cấu hình như sau:

  • Tạo một biến mới tên là GOROOT với giá trị là C:\Go
  • Chọn biến PATH có sẵn, thêm vào sau dấu chấm phẩy ; cuối dòng đường dẫn sau: C:\Go\bin;

 

Linux và Mac OS X

Trên các máy Unix, bạn cài đặt biến môi trường bằng cách chỉnh sửa file $HOME/.profile hoặc $HOME/.bash_profile.

Nếu không tìm thấy biến $HOME, có thể thay nó bằng /user/local

Hãy thêm nội dung sau:

export GOROOT=$HOME/go
export PATH=$PATH:$GOROOT/bin
Thế là xong rồi đấy! Đơn giản, phải không nào?

 

Bước 3: Chạy thử

Bây giờ, chúng ta có thể kiểm tra xem Go đã được cài hoàn chỉnh hay chưa, bằng cách gõ lệnh sau vào Terminal (hoặc Command Line trên Windows):

$ go version
Nếu Go được cài đặt đầy đủ thì nội dung output sẽ giống thế này:
go version go1.4.2 darwin/amd64
 

Viết chương trình đầu tiên bằng Go

OK, cài đặt xong rồi thì bắt tay vào code thôi. Chương trình đầu tiên, đoán ra rồi phải không? là chương trình huyền thoại mà bài nào cũng viết: Hello World =))

Chúng ta sẽ tạo một file mới, tên là hello.go và gõ đoạn chương trình sau vào. Nhưng hãy nhớ là: Gõ vào, đừng copy paste!. Phải tự gõ vào mới nhớ được!

package main

import "fmt"

func main() {
    fmt.Printf("Hello Gopher's World!")
}
Gõ xong rồi. Bạn có thấy code nó quái thế nào không?

Không có chấm phẩy cuối dòng, từ khoá func cứ như là Swift vậy, hao hao giống Javascript nữa. Còn cái gì nữa đây? fmt.Printf để in nội dung ra màn hình, có cần phải dài dòng vậy không?

Golang là thế đấy, nếu bạn không thích nó, thì phải tập thích nó đi thôi =))

Bây giờ hãy compile và chạy chương trình với lệnh:

$ go run hello.go
Output sẽ là:
Hello Gopher's World!
Xong rồi đó, chúc mừng, bạn đã viết được chương trình đầu tiên của mình bằng Go rồi đấy =))

Học máy là gì?

Định nghĩa

Với trí tuệ nhân tạo cổ điển, khi mà muốn máy tính hoàn thành một nhiệm vụ thì lập trình viên phải chỉ rõ trong code (mã nguồn) cách thực hiện nhiệm vụ đó như thế nào. Trong khi đó ML, nói một cách đơn giản là tập hợp của những phương pháp giúp cho máy tính có thể học được cách thực hiện những nhiệm vụ đó mà không cần sự chỉ dẫn trực tiếp của con người (Arthur Samuel, 1959).

Những bài toán được giải quyết bởi ML thường là

Những bài toán có quy mô lớn như việc xử lí dữ liệu web, dữ liệu đa phương tiện (multimedia), dữ liệu từ cảm biến (sensors), …
Những bài toán quá phức tạp mà chúng ta không biết lời giải dạng hiện (closed form solution) hoặc không thể lập trình bằng tay được như thị giác máy tính (Computer Vision, CV, giúp cho máy tính có khả năng nhận biết thế giới qua hình ảnh tương tự như thị giác con người), xử lí ngôn ngữ tự nhiên (Natural Language Processing, NLP, giúp cho máy tính có khả năng hiểu được ngôn ngữ của con người), điều khiển robot, xe cộ trong môi trường tự nhiên, …
Một số ví dụ cụ thể về bài toán phù hợp với ML như:

Tìm kiếm trên web: hàng ngày chúng ta cần phải tìm rất nhiều thông tin trên web, việc dùng người duyệt qua hàng tỉ trang web để tìm thứ phù hợp là không khả thi. Các thuật toán ML có khả năng tính toán độ phù hợp giữa câu hỏi của người dùng (query) và nội dung của các trang web và sắp xếp chúng theo thứ tự để trả về cho người dùng.
Lọc spam mail: các hệ thống lọc spam cần phát hiện nhưng email có nội dung khác thường và lừa đảo và ngăn chúng tới được inbox của người dùng. Khác biệt với bài toán trên, chúng ta cần phát hiện ra sự bất thường, đo đạc sự khác nhau giữa những email thông thường và spam.
Nhận dạng ảnh: khác với văn bản, khi mà một ý tưởng thường chỉ có một số nhỏ cách diễn đạt và các cách diễn đạt thường sử dụng những từ ngữ giống nhau hoặc đồng nghĩa, ảnh chụp của cùng một vật thể ở mỗi góc độ khác nhau, điều kiện môi trường khác nhau thì có thể rất khác nhau nếu so sánh ở từng điểm ảnh. Các hệ thống xử lí ảnh cần phải nhận ra những đặc trưng bất biến (invariants) trong những bức ảnh để có thể đạt được độ chính xác cao
Định nghĩa: Bài toán ML một chương trình A được gọi là học từ kinh nghiệm E(xperience) để thực hiện một nhiệm vụ T(ask) nếu như hiệu quả thực hiện P(erformance) của nó tăng lên sau khi được bổ sung E.

Huấn luyện và kiểm tra

Quá trình xây dựng một hệ thống ML thường bao gồm hai giai đoạn: huấn luyện và kiểm tra.

Huấn luyện Quá trình dạy một hệ thống ML học gọi là huấn luyện (training). Huấn luyện thường là việc đưa cho hệ thống ML những ví dụ mẫu (training example) và dựa trên những ví dụ đó, hệ thống phải hiệu chỉnh các tham số (parameters) của mình để có thể cho ra được kết quả đúng ở những ví dụ sau. Quá trình hiệu chỉnh tham số thường sử dụng các thuật toán tối ưu (optimization ví dụ convex optimization, linear optimization, …) và quy hoạch (programming, ví dụ dynamic programming, approximate dynamic programming, …) và nhiều phương pháp toán học, thống kê khác.

Kiểm tra Sau khi hoàn thành huấn luyện, hiệu năng (performance) của một hệ thống thường được ước lượng bằng hiệu năng của nó trên một tập dữ liệu kiểm tra (test set) khác với tập huấn luyện (training set). Quá trình này gọi là kiểm tra (testing) nhằm ước lượng hiệu quả thực sự của hệ thống trong môi trường làm việc. Test set bắt buộc phải khác với training set vì hệ thống được huấn luyện trên training set nên nó sẽ dần thích nghi với những đặc điểm của training set và đạt được hiệu năng cao trên tập này, không phản ánh hiệu năng thực tế của hệ thống trong môi trường làm việc.

Sự tương đồng Quá trình training và testing giống như quá trình dạy học và thi cử trong đời sống. Trong quá trình dạy, giáo viên đưa cho sinh viên rất nhiều bài tập và qua quá trình giải các bài tập đó, sinh viên dần hiểu được bản chất của vấn đề. Tương tự như vậy, chúng ta đưa cho hệ thống ML rất nhiều ví dụ và qua các ví dụ đó, hệ thống dần dần xây dựng hiểu biết về bài toán. Thi cử là để đánh giá hiểu biết của sinh viên, nếu giáo viên đưa cho sinh viên những bài toán đã dùng trong quá trình giảng dạy, sinh viên sẽ dễ dàng đạt được điểm cao hơn hiểu biết thực sự của họ về vấn đề. Do đó, bài toán trong đề thi cần phải khác với những bài toán sử dụng trong quá trình dạy học. Năng lực thực sự của sinh viên, giống như hiệu năng hệ thống ML, là những đại lượng ẩn (hidden variables), chúng ta ước lượng nó thông qua thi cử. Đến đây thì có lẽ mọi người đều hiểu rõ vì sao có tên gọi Machine learning. Tuy nhiên, khi dịch sang tiếng Việt là học máy thì nghe không được xuôi tai cho lắm, :v.

Phân loại hệ thống ML

Các hệ thống ML được phân loại theo cách thức mà người ta huấn luyện nó. Một số nhánh chính của học máy bao gồm:

Học có giám sát (Supervised learning, SL)

Phương pháp này được gọi là có giám sát vì trong quá trình huấn luyện, hệ thống ML cần phải biết được câu trả lời chính xác cho mỗi training example. Với mỗi example, hệ thống đo đạc sự khác nhau giữa câu trả lời đúng và câu trả lời mà nó đưa ra. Mục tiêu của training là làm giảm độ sai lệch giữa tập hợp câu trả lời đúng và tập hợp câu trả lời của hệ thống. Mỗi mẫu dùng để huấn luyện bao gồm 2 phần: các đặc trưng để mô tả vật mẫu (features) và nhãn của mẫu (label).

Ví dụ một hệ thống SL dùng để phân loại trái cây thì mỗi training example sẽ có thể có dạng như sau: (màu sắc, vị, cân nặng : tên loại quả), (đỏ, ngọt, 130gram : táo), (vàng, chua, 200gram : cam), … Độ sai khác cho mỗi mẫu là 1 nếu như hệ thống đưa ra câu trả lời sai, 0 nếu câu trả lời đúng. Độ sai khác được tính cho toàn bộ các mẫu trong training set. Huấn luyện nhằm giúp hệ thống đạt được độ sai khác thấp hơn so với lúc ban đầu.

SL thường có hiệu năng cao hơn các phương pháp khác nhưng quá trình huấn luyện tốn kém hơn nhiều do phải gán nhãn cho từng mẫu.

Học không giám sát (Unsupervised learning, UL)

Khác với SL, mục tiêu của UL là học ra những hàm mô tả những cấu trúc ẩn trong dữ liệu. UL nhằm giải quyết những bài toán mà lượng dữ liệu có nhãn là rất ít hoặc không có, hoặc do những đặc trưng của bài toán mà dữ liệu có gán nhãn là không cần thiết.

Ví dụ chúng ta có một lượng lớn khách hàng với những sở thích khác nhau và muốn có một nhân viên hỗ trợ khách hàng cho mỗi nhóm sở thích. Ở đây chúng ta không cần quan tâm sở thích cụ thể của một người là gì mà chỉ muốn những khách hàng có cùng sở thích thì sẽ được hỗ trợ bởi cùng một nhân viên. Chúng ta sử dụng thuật toán phân cụm (clustering), ví dụ như k-means, để nhóm những khách hàng có cùng sở thích lại với nhau dựa theo một độ đo (measure) về sự giống/khác nhau về sở thích giữa 2 người.

Semi-supervised learning (học bán giám sát) là một phương pháp kết hợp giữa UL và SL để giải quyết những bài toán có ít dữ liệu có gán nhãn.

Học tăng cường (Reinforcement learning, RL)

Khác với 2 phương pháp trên, RL không học từ những tập dữ liệu có sẵn mà nó liên quan tới việc điều khiển một/nhiều tác tử (agent) đưa ra những hành động (actions) trong một môi trường (environment) một cách hợp lí để cực đại hóa giá trị phần thưởng tích lũy (cummulative reward).

Ví dụ chúng ta có một robot (agent) với khả năng quan sát hạn hẹp, ở trong một môi trường với nhiều chướng cạm bẫy và phần thưởng. Mục tiêu của robot là tìm ra cách hoạt động thu được nhiều phần thưởng nhất và tránh được các cạm bẫy. Để đạt được điều đó, robot phải trải qua quá trình dò tìm, khảo sát môi trường xung quanh và dần xây dựng nên một mô hình về môi trường đó. Quá trình học này khác với SL, UL vì dữ liệu về môi trường là không sẵn có mà phải được khám phá dần dần qua nhiều lần thử nghiệm.

SL và UL là hai phương pháp phổ biến nhất trong ML nhưng RL cũng là một phương pháp cực kì triển vọng và đang phát triển mạnh mẽ trong thời gian gần đây khi nó được kết hợp với SL và UL.

IOIBIN – spoj

Đề bài:

Thuật toán:

Code:

const   fi = '';
        fo = '';
        maxn = trunc(1e4)+3;
var     p : array[1..maxn] of longint;
        i,j,n,m : longint;
        x,u,v : longint;
procedure chuanbi;
begin
        for i:=1 to maxn do p[i]:=i;
end;
function find(i:longint):longint;
begin
        while p[i]<>i do i:=p[i];
        exit(i);
end;
procedure lam1;
var     i,j : longint;
begin
        i:=find(u);
        j:=find(v);
        if i<>j then
        if i<j then p[j]:=p[i] else p[i]:=p[j];
end;
procedure main;
var     i:longint;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        readln(m);
        chuanbi;
 
        for i:=1 to m do
                begin
                        readln(u,v,x);
                        if x=1 then lam1 else
                                if find(u)=find(v) then writeln(1) else writeln(0);
                end;
        close(input);
        close(output);
end;
begin
        main;
end.

Thuật toán sắp xếp tuần tự

Bài toán đặt ra

Cho mảng A gồm n phần tử. Sắp xếp lại dãy A theo chiều giảm dần

Nhập vào: số nguyên dương n và dãy A.

8
9 7 6 15 16 5 10 11
Xuất ra: dãy A sau khi đã được sắp xếp
5 6 7 9 10 11 15 16

Ý tưởng

Tư duy đơn giản như cách chúng ta xếp bài

sap-xep-1-yeulaptrinhHình trên là thao tác xếp cây bài 7 bằng cách rút nó ra và đặt vào vị trí của phù hợp.

Giải sử bài trên tay đang là:

2 5 7 10 4

ta thấy dãy 2,5,7,10 đã tăng dần chỉ còn cây 4 đứng chưa đúng chỗ nên ta đẩy 4 lên trước 10, rồi lên trước 7 cứ như vậy đến khi gặp cây 2 đứng trước. 2 < 4 suy ra thì dừng. Dãy trở thành

2 4 5 7 10

Dãy đã được sắp xếp.

Ý tưởng: duyệt lần lượt từng cây bài, nếu cây bài nhỏ thì ta đẩy dần lên đầu đến khi nào không chuyển lên được nữa

Ví dụ khác:

sap-xep-yeulaptrinh.pwCode:

#include <bits/stdc++.h>

using namespace std;

int n, a[10000];

void doi_cho(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<i; j++)
            if (a[j] > a[i])
            {
                doi_cho(&a[i], &a[j]);
            }
    }
    for (int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}
Ví dụ:

Với dãy A = {12, 11, 13, 5, 6}

Cho i chạy từ 1 đến 4

i=1. không làm gì cả

12, 11, 13, 5, 6

i = 2. Vì 11 nhỏ hơn 12 nên chuyển 11 lên trước 12
11, 12, 13, 5, 6

i = 3. 13 không cần chuyển lên đầu nữa
11, 12, 13, 5, 6

i = 4. 5 được chuyển chỗ với 13 rồi chuyển chố tiếp lần lượt với 12, 11.
5, 11, 12, 13, 6

i = 5. 6 cũng giông như 5 được chuyển dần lên đến khi gặp 5 nhỏ hơn thì dừng lại
5, 6, 11, 12, 13

Độ phức tạp:

  • O(n^2)

 

Quý bạn đọc có ý kiến, thắc mắc xin comment bên dưới <3

QBRECT – spoj

Đề bài:

Thuật toán:

Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian O(n^2):

Với mỗi ô j trên hàng i, ta tìm f(j) là số ô 1 liên tiếp trên cột j, tính từ hàng i trở lên. Sau đó, với mỗi cột j, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có f nhỏ hơn f(j), sau đó tính diện tích hình chữ nhật ở cột j là S=f(j)×(r−l−1) với l,r là chỉ số 2 ô bên trái và bên phải nói trên.
Hình minh hoạ khi tính f(4):
deque-yeulaptrinh.pw
Để tìm l,r nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Code:

uses    math;
const   fi='';
        fo='';
        maxn=1000;
var     a:array[1..maxn,1..maxn] of byte;
        i,j,m,n,res,top:longint;
        h,s,left,right:array[1..maxn] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    close(input);
end;
procedure push(x:integer);
begin
    inc(top);
    s[top]:=x;
end;
function get:integer;
begin
    exit(s[top]);
end;
procedure pop;
begin
    dec(top);
end;
procedure xuly;
begin
    for i:=1 to m do
     begin
        for j:=1 to n do
           if a[i,j]=1 then
                begin
                    h[j]:=h[j]+1;
                end else h[j]:=0;
        top:=0;
        for j:=1 to n do
            begin
                while (top<>0) and (h[j]<=h[get]) do pop;
                if top=0 then left[j]:=0 else left[j]:=get;
                push(j);
            end;
        top:=0;
        for j:=n downto 1 do
                begin
                    while (top<>0) and (h[j]<=h[get]) do pop;
                    if top=0 then right[j]:=n+1 else right[j]:=get;
                    push(j);
                end;
        for j:=1 to n do
                begin
                    res:=max(res,h[j]*(right[j]-left[j]-1));
                end;
     end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.