Hàm atoi trong C/C++ – chuyển xâu thành số nguyên

Mô tả

Chuyển chuỗi kí tự thành số nguyên

Khai báo

int atoi(const char *str)

  • str là chuỗi ký tự cần chuyển sang số nguyên. VD: str=”5678123″

Ví dụ:

  • atoi(“101”);
  • atoi(‘5’);

Cần khai báo thư viện stdlib.h trước khi sử dụng.

Giá trị trả về

Trả về số nguyên kiểu int. Nếu xâu không có dạng số nguyên thì trả về giá trị 0

Ví dụ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main () {
   int val;
   char str[20];
 
   strcpy(str, "98993489");
   val = atoi(str);
   printf("String value = %s, Int value = %d\n", str, val);
 
   strcpy(str, "tutorialspoint.com");
   val = atoi(str);
   printf("String value = %s, Int value = %d\n", str, val);
 
   return(0);
}

Kết quả:

String value = 98993489, Int value = 98993489
String value = tutorialspoint.com, Int value = 0

Học toán rời rạc để làm gì?

Toán rời rạc đa phần là lý thuyết nên nhiều bạn thường đặt ra câu hỏi học toán rời rạc thì để làm gì.

Vậy học toán rời rạc để làm gì?

  • Lý thuyết tập hợp (ánh xạ tập hợp giao hợp, quan hệ) giúp ta xây dựng hệ quản trị cơ sở dữ liệu.
  • Lý thuyết đồ thị giúp bạn xấy dựng các mạng lướti truyền tin. Giải được các bài toàn về đồ thị. Như giải thuật BFS thường được dùng trong các rounter để tìm đường đi ngắn nhất.
  • Cây thì nhờ đó có thuật giải huffman giúp nén thông tin. hoặc giúp làm cây quyết định, xây dựng chiến thuật min-max dùng trong trí tuệ nhân tạo để giải quyết các bài toàn về chơi cờ, nim. Xây dựng cây tiền tố, hậu tố để máy tính có thể hiểu và tính toán đc các phép tính thông thường của con người.
  • Học về độ tăng của hàm giúp ta đánh giá thuật toán từ đó chọn thuật toán thích hợp cho mỗi bài toán đề ra.
  • Lý thuyết số có vài ứng dụng trong Cryptography. Ví dụ như lý thuyết đồng dư của TRR.
  • Xác xuất thống kê được ứng dụng trong AI.
  • Ngoài ra rời rạc còn giúp ta hiểu cách máy tính biểu diễn các số như thế nào.

 

PCIRCLE – spoj

Đề bài:

Thuật toán:

  • Duyệt cấu hình tổ hợp

Code:

uses    math;
 
const   fi='';
        fo='';
        maxn=10;
 
type    data=longint;
 
var     x       :array[1..2*maxn] of longint;
        i,j,n,m :longint;
        st      :array[1..2*maxn] of longint;
        kq      :array[1..10001,1..2*maxn] of longint;
        res     :int64;
        cx      :array[1..2*maxn] of boolean;
 
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        close(input);
end;
 
function ngto(x : longint) : boolean;
var     i       :longint;
begin
        for i:=2 to trunc(sqrt(x)) do
                if x mod i = 0 then exit(false);
        exit(true);
end;
 
procedure cnkl;
begin
        if ngto(x[2*n]+x[1]) then
                begin
                        inc(res);
                        if res<=10000 then
                        kq[res] := x;
                end;
end;
 
procedure try(i : longint);
var     j :longint;
begin
        for j:= 1 to 2*n do
                if cx[j] then
                        if ngto(j+x[i-1]) then
                        begin
                                x[i] := j;
                                cx[j] := false;
                                if i=2*n then cnkl else try(i+1);
                                cx[j] := true;
                        end;
end;
procedure process;
begin
        {for i:=2 to 2*n do
                if ngto(i) then
                        begin
                                inc(m);
                                st[m] := i;
                        end;     }
        fillchar(cx,sizeof(cx),true);
        cx[1] := false;
        x[1] := 1;
        try(2);
end;
 
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        for i:=1 to min(res,10000) do
                begin
                        for j:=1 to 2*n do write(kq[i,j],' ');
                        writeln;
                end;
        close(output);
end;
 
begin
        enter;
        process;
        print;
end.

QBSCHOOL – spoj

Đề bài:

Thuật toán:

  • Gọi Gọi f[i] và d[i] lần lượt là độ dài và số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.
  • Để tính d[i] ta sử dụng thuật toán Dijkstra
  • Để tính số lượng đường đi ngắn nhất giữa hai đỉnh ta tính như sau
  • Nếu d[v]>d[u]+c(u,v), ta gán d[v]=d[u]+c(u,v) và f[v]=f[u]

    Nếu d[v]=d[u]+c(u,v) thì gán f[v]=f[v]+f[u].

    (có thể xem rõ hơn ở code bên dưới)

Code:

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     u,v,w,k:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(k,u,v,w);
                        add(i,u,v,w);
                        if k=2 then add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(d1[n],' ',f1[n]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef pair<long long, int> lli;
 
const long long oo = ((1 << 30)-1)*2-1;
const int max_n = 5000+1;
 
int n, m;
long long min_d, dist = 0, f[max_n];
vector<lli> adj[max_n];
 
inline void load_map()
{
    cin >> n >> m;
    int type, u, v, w;
    while (m--)
    {
        cin >> type >> u >> v >> w;
        adj[u].push_back(lli(w, v));
        if (type==2) adj[v].push_back(lli(w, u));
    }
}
 
inline void dijkstra()
{
    vector<lli>::iterator it;
    long long cuv, du, d[max_n];
    int u, v;
    priority_queue<lli, vector<lli>, greater<lli> > heap;
    for (u=1; u <= n; u++) d[u] = +oo;
    memset(f, 0, sizeof(f));
    d[1] = 0; f[1] = 1;
    heap.push(lli(0, 1));
    while (heap.size())
    {
        du = heap.top().first; u = heap.top().second;
        heap.pop();
        if (du != d[u]) continue;
        if (u == n) break;
        for (it=adj[u].begin(); it != adj[u].end(); it++)
        {
            cuv = it->first; v = it->second;
            if (d[v]==d[u]+cuv) f[v] += f[u];
            if (d[v] > d[u]+cuv)
            {
                d[v] = d[u]+cuv;
                f[v] = f[u];
                heap.push(lli(d[v], v));
            }
        }
    }
    min_d = d[n];
}
 
main()
{
    load_map();
    dijkstra();
    cout << min_d << " " << f[n];
}

Giải thuật tìm kiếm Fibonacci

Mình không tìm được từ nào tiếng Việt có thể dịch được từ “Fibonaccian Searching”,
nếu “binary searching” có thể dịch là “tìm kiếm nhị phân”, thì “Fibonaccian Searching”
không có ngữ nghĩa gì nhiều.

Nguồn gốc thuật toán này xuất phát từ bài tập 1.4.22 (Algorithms, Fourth Edition, Sedgewick). Ngoài
ra đây cũng là một nội dung được đề cập trong TAoCP – Vol 3.

Lịch sử

Thuật toán được để xuất bởi Devid E. Ferguson (CACM-1960, link).
Một số phát hiện liên quan, chủ yếu về nguồn gốc cây Fibonacci có thể tham khảo tại TAoCP – Vol 3 (Mục 6.2.1).

Thuật toán

Điểm thú vị của thuật toán này nằm ở chỗ thuật toán không sử dụng phép chia, nhưng vẫn đạt được
độ hiệu quả của binary search. Tuy nhiên, ưu điểm này thực sự có tác dụng
vào thời điểm thuật toán này được đề xuất (1960) khi mà các chép chia, hay
shift bit tốn nhiều chi phí hơn so với phép cộng trừ. Tuy nhiên, fibsearch còn được sử dụng khi tốn ưu thời gian tìm kiếm khi mà dữ liệu quá lớn không
thể đọc lên được toàn bộ lên RAM hoặc cache, khi đó thời gian đọc trên bộ
lưu trữ ngoại vi trở nên tốn kém ( link ).
Tuy nhiên mình nghĩ fibsearch sẽ là một câu hỏi phỏng vấn cực kì thú vị.

Thiết kế một thuật toán tìm kiếm nhị phân không sử dụng phép nhân, chia hoặc
dịch bit với độ phức tạp $\mathcal{O}(\lg N)$

Cài đặt

Phần dưới đây là giải thuật lấy từ TAoCP, mình nghĩ là cực kì dễ hiểu, tạm thời
mình chỉ trình bày mã giả. Có thể tham khảo phần cài đặt bằng C, trong phần
References. Một phiên bản cải tiến với kích thức mảng $N$ bất
kì sẽ được update sau.

[[code]]czo2MDQ6XCJJbnB1dDogbeG6o25nICRLXzEsIEtfMiwgLi4uLCBLX04kIMSRxrDhu6NjIHPhuq9wIHjhur9wIHbDoCBwaOG6p24gdOF7WyYqJl19u60gJEskIGPhuqduIHTDrG0uIEdp4bqjIHPhu60NCiROKzEgPSBGX3trKzF9LiBMxrB1IMO9IGluZGV4IGPhu6dhIG3huqNuZyBi4XtbJiomXX26r3QgxJHhuqd1IDEkDQoNClAxLiBbS2jhu59pIHThuqFvXSBpID0gRltrXSwgcCA9IEZbay0xXSwgcSA9IEZbay0yXQ0KUDIuIFtTe1smKiZdfW8gc8OhbmhdLg0KICAgIGlmIEtbaV0gJmx0OyBLOiBnbyB0byBQMy4NCiAgICBlbHNlIGlmIEtbaV0gJmd0OyBLOiBnbyB0byBQNC57WyYqJl19DQogICAgZWxzZTogcmV0dXJuIGk7DQpQMy4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gdHLDoWldDQogICAgaWYgcSA9IHtbJiomXX0wOiByZXR1cm4gLTENCiAgICBlbHNlOg0KICAgICAgICBpIC09IHENCiAgICAgICAgKHAsIHEpID0gKHEsIHAtcSkNCiAgICAgICAge1smKiZdfWdvIHRvIFAyDQpQNC4gW1jDqXQgY8OieSBjb24gRmlib25hY2NpIGLDqm4gcGjhuqNpXQ0KICAgIGlmIHAgPSAxOiByZXR1cm4gLTF7WyYqJl19DQogICAgZWxzZToNCiAgICAgICAgaSArPSBxDQogICAgICAgIHAgLT0gcQ0KICAgICAgICBxIC09IHANCiAgICAgICAgZ28gdG8gUHtbJiomXX0yDQpcIjt7WyYqJl19[[/code]]

Bài tập

  • Thiết kế thuật toán cho trường hợp $N \geq 0$.
  • Thiết kế thuật toán với index bắt đầu bằng 0. Về mặt kĩ thuật chỉ có 1 thay đổi
    nhỏ trong code, nhưng cây Fibonacci sẽ tương đối khác.

Phân tích

Cây tìm kiếm Fibonacci với k=6. Source: TAoCP, Vol 3, P417.

Phần dưới đây là mô tả ngắn gọn cách mà thuật toán này thực thi. Khác với tìm
kiếm nhị phân chia các nhánh tìm kiếm thành các cây nhị phân, fibsearch thay
vào đó xây dựng cây Fibonacci. Cây Fibonacci bậc $k$ được định nghĩa là “cây” với
$F_{k+1}-1$ internal nodes (vòng tròn) và $F_{k+1}$ external nodes (hình vuông),1
cây Fibonacci được xây dựng như sau:

  1. $k=0$ hoặc $k=1$, cây chỉ có 1 external node là 0.
  2. $k \geq 2$, root là có giá trị $F_k$, cây con bên trái là cây fibonacci
    bậc $k-1$ và cây con bên phải là cây fibonacci bậc $k-2$ với tất cả các nodes
    tăng $F_k$ đơn vị.

Thuật toán fibsearch chính là việc xây dựng cây fibonacci bậc $k$ với $N=F_{k+1}$.

Trong Figure 1, cây có bậc $k=6$ (tương đương với tìm mảng có $N=12$ phần tử
($N+1=F_{k+1} = F_7 = 13$)), số internal nodes
$F_{k+1}-1=12$ và $F_{k+1}=13$ external nodes. Ngoài ra,
ta có thể thấy root = $F_6 = 8$, phần nhánh bên trái của 8 có
$F_6-1=7$ internal nodes, và bên phải gồm $F_5-1 = 4$ internal
nodes. Tiếp tục xuống các level thấp hơn là các giá trị $F$ nhỏ hơn và theo
đúng quy luật đã nêu. Nhìn hình ta có thể hình dung phần nào, với cách tiếp cận
chia để trị tương đồng với tìm kiếm nhị phân, tìm kiếm fibonaci “có thể”
có độ phức tạp tương tự.

Một chứng minh cụ thể và chi tiết hơn sẽ được cập nhật sau, kèm theo đó là mã
nguồn C++ của thuật toán.

Dạng tổng quát

Cả tìm kiếm nhị phân lẫn Fibonacci search thực ra cũng thuộc một dạng tổng quát
của một chiến lược chia để trị trong tìm kiếm chuỗi đã được sắp xếp.

Gọi $p$ và $q$ thỏa $p+q=1$, gọi $C(N)$ là số phép so sánh cần thực hiện của
giải thuật. Chiến lược ở đây đó là chia mảng thành 2 phần với số lượng phần
tử lần lượt là $pN$ và $qN$. Ta có dãy truy hồi số phép so sánh trong thuật toán:

$$ C(N) = 1 + pC(pN) + qC(qN) $$

Công thức này có dạng close form là $C(N) = \log_bN$ trong đó $b$ là hằng số
cần tìm. Dễ dàng thấy được với tìm kiếm nhị phần $p=q={1 \over 2}$, còn với
fibsearch thì $p={1 \over \phi}$ và $q= {1 \over \phi^2}$. Cụm $pC(pN)$ ở
đây có nghĩa là xác suất $p$ phần tử cần tìm nằm trong khoảng $pN$ phần tử
đã được chia, tương tự với $qC(qN)$.

[$b = p^{-p}q^{-q}$
nhưng hiện giờ vẫn chưa biết giải như thế nào. Đây là dạng divide-and-conquer
recurrence. Nếu sử dụng Akra-Bazzi method
thì ta chỉ mới tìm được $\Theta(1 + \ln N)$ của nó nhưng vẫn chưa xác định được $b$].

References

TODO

Mình cũng không biết nên dịch internal nodes với external nodes thế nào cho hợp (node trong và node ngoài?). ^

Heroku là gì?

Heroku là dịch vụ cung cấp máy chủ miễn phí cho người dùng. Với cái giá phải trả 0$ cùng với vô vàn các addons hỗ trợ cực kỳ hữu ích thì đấy được coi là một trong những dịch vụ hấp dẫn khó cưỡng. Dù miễn phí nhưng nó có thể so sanh với các server trả phí.

Heroku hỗ trợ nhiều ngôn ngữ lập trình

  • NodeJS
  • Ruby
  • Python
  • PHP
  • Java
  • Scala
  • Clojure
  • Go
  • Kotlin

heroku-yeulaptrinh.pw

Cách sử dụng

Trước mình có code server-side bằng NodeJS rồi deploy(triển khai) lên Heroku. Qua một thời gian trải nghiệm, mình thấy Heroku không quá khó dùng nhưng cũng không quá đơn giản dành cho gà mờ. Sử dụng nó cũng tương tự như Github với một số câu lệnh cơ bản như:

(bạn phải download heroku CLI về)

Một số tính năng khác

Ngoài những tính năng trên heroku còn hỗ trợ nhiều tính năng khác:

  • Database miễn phí
  • SSL miễn phí
  • Hỗ trợ làm việc team
  • Liên kết với Github đơn giản

Bất tiện khi sử dụng

Cái gì miễn phí thì cũng có một số bất tiện của nó. Ở Heroku thì là:

  • Heroku chỉ cho người dùng 550 giờ mỗi tháng để sử dụng. Tuy nhiên bạn có thể tăng số lượng giờ đồng hồ sử dụng lên con số 1000 nếu như bạn cài đặt phương thức thanh toán vào trong tài khoản. 1000 giờ đồng hồ là quá đủ để blog cá nhân của bạn chạy êm ru cả tháng (31 ngày * 24 giờ = 744 giờ)
  • Sau 2 đến 3 giờ nếu server không có người truy cập thì server sẽ chuyển sang trạng thái ngủ.Về việc server bị tắt khi không có traffic, cách đơn giản nhất là tự tạo traffic cho nó. Cách dễ nhất là dùng Pingdom để ping trang blog của bạn thường xuyên giữ cho server không bị tắt.Cài đặt Pingdom khá đơn giản, chỉ việc điền thông tin và nhấn chừng 3-4 cái nút. Cài đặt tại:

Bạn có thể nâng cấp lên để trải nghiệm tốt hơn.

Có một số tips nhỏ mình muốn giới thiệu cho bạn:

Tip: Vấn đề SSL

(SSL là chứng chỉ bảo mật)

Nếu bạn dùng domain mặc định của heroku (*.herokuapp.com) thì bạn sẽ dùng SLL không phải trả tiền. Tuy nhiên nếu bạn muốn trỏ sang domain cá nhân của bạn thì SSL sẽ không còn.

Để có được SSL miễn phí thi ta dùng Cloudflare để làm DNS và Cloudflare hỗ trợ miễn phí kết nối Full SSL đến host.

Pipeline là gì?

Ở heroku có một khái niệm mới là pipeline. Pipeline mang đến cho người dùng giải pháp Test automation và Continuous Integration/Continuous Development(CICD).

Pipeline là kiến trúc cho phép song song hoá các công đoạn trong xử lý vài lệnh đồng thời

Bạn có thể tìm hiểu thêm trên mạng.

GSON là gì?

Gson là một thư viện java cho phép người sử dụng có thể chuyển đổi từ một đối tượng Java sang JSON và cũng có thể chuyển đổi từ một đối tượng JSON sang java.Gson có thể làm việc với đối tượng java tùy ý bao gồm các đối tượng tồn tại sẵn mà bạn không có source-code của chúng.

Việc dùng Gson rất dễ dàng, không tốn công parse và cũng giúp chúng ta đỡ nhầm lẫn hơn khi parse trực tiếp từ JSON sang java. Đặc biệt là khi làm việc với những chuỗi JSON có rất nhiều trường.

  • Mục tiêu của Gson:
    • Cung cấp đơn giản toJson()và fromJson()phương pháp để chuyển đổi các đối tượng Java để JSON và ngược lại.
    • Cho phép tồn tại trước đó đối tượng unmodifiable để được chuyển đổi sang và từ JSON.
    • Hỗ trợ mở rộng của Java Generics.
    • Cho phép đại diện tùy chỉnh cho các đối tượng.
    • Hỗ trợ đối tượng tùy tiện phức tạp (với phân cấp thừa kế sâu và sử dụng rộng rãi các loại generic).
  • Tài liệu về Gson
    • Gson API: Javadocs for the current Gson release
    • Gson user guide: This guide contains examples on how to use Gson in your code.
    • Gson Roadmap: Details of changes in the recent versions
    • Gson design document: This document discusses issues we faced while designing Gson. It also includes a comparison of Gson with other Java libraries that can be used for Json conversion

    Thắc mắc và hỏi đáp tại google-gson Google group.

  • Chi tiết hơn về GSON cũng như các tài liệu tham khảo liên quan có thể tham khảo trên link sau :https://github.com/google/gson