Showing posts with label cautrucdulieu. Show all posts
Showing posts with label cautrucdulieu. Show all posts

11/01/2023

Cấu trúc dữ liệu và thuật toán | tổng hợp 7 CTDL phổ biến

  11/01/2023    trannguyenhan

Xem lại 3 bài viết về CTDL trên website: 

- Cấu trúc dữ liệu và thuật toán | Mảng (Array) và Linked List

- Cấu trúc dữ liệu và thuật toán | Ngăn xếp (Stack)

- Cấu trúc dữ liệu và thuật toán | Hàng đợi (Queue)

Cấu trúc dữ liệu là cách tổ chức và lưu trữ dữ liệu trong máy tính để chúng ta có thể thực hiện các hoạt động dựa trên dữ liệu được lưu trữ một cách hiệu quả hơn. Với sinh viên CNTT hay là các bạn đã ra trường đi làm, các lập trình viên lâu năm thì CTDL là hành trang không thể thiếu, và CTDL cũng là các câu hỏi được các nhà tuyển dụng thường xuyên sử dụng để hỏi các ứng viên. Trên website cũng đã có một bài viết tổng hợp các câu hỏi phỏng vấn về CTDL các bạn có thể xem lại TẠI ĐÂY.

7 CTDL phổ biến được đề cập tới trong bài viết bao gồm: 

- Mảng (Array)

- Danh sách liên kết ( Linked list)

- Ngăn xếp ( Stack)

- Hàng đợi ( Queue)

- Cây ( Tree)

- Đồ thị ( Graph)

- Bảng băm ( Hash table)

1. Mảng ( Array)

Một mảng ( Array) là một cấu trúc dữ liệu với kích thước cố định, lưu trữ các phần tử cùng kiểu dữ liệu. Nó có thể là một mảng số nguyên, mảng số thực, mảng chuỗi hay một mảng của mảng. Mảng được đánh chỉ mục, được lưu ở các ô nhớ liên tiếp nhau cho phép ta có thể truy cập ngẫu nhiên vào mảng một cách dễ dàng, nhanh chóng.


2. Danh sách liên kết ( Linked List)

Danh sách liên kết là một cấu trúc tuần tự bao gồm một chuỗi các phần tử theo thứ tự tuyến tính được liên kết với nhau. Việc truy cập vào các phần tử trong danh sách liên kết phải là tuần tự, không thể thực hiện truy cập ngẫu nhiên.

- Các phần tử trong danh sách liên kết được gọi là các node

- Mỗi node chứa giá trị và một con trỏ trỏ tới node kế tiếp

- Có một con trỏ head trỏ tới phần tử đầu tiên của danh sách liên kết


3. Ngăn xếp ( Stack)

Là một CTDL hoạt động theo nguyên tắc LIFO ( Last In First Out - phần tử đưa vào sau cùng sẽ được truy cập đầu tiên), CTDL này được thấy thường xuyên trong ngôn ngữ lập trình và ứng dụng của nó đem lại cũng là rất lớn.

Có 2 hoạt động cơ bản được thực hiện trên 1 ngăn xếp đó là: 

- Push: Thêm một phần tử vào đỉnh của ngăn xếp

- Pop: Xóa một phần tử khỏi đỉnh của ngăn xếp

Tùy vào nhu cầu mỗi bài toán chúng ta có thể thêm các hàm phù hợp để thuận tiện hơn khi sử dụng ngăn xếp, ví dụ như xem phần tử ở đỉnh mà không xóa, kiểm tra ngăn xếp rỗng,...


4. Hàng đợi ( Queue)

Là một CTDL hoạt động theo nguyên tắc FIFO ( First In First Out - phần tử được đặt ở đầu sẽ được truy cập đầu tiên), có 2 hoạt động cơ bản được thực hiện trên một hàng đợi đó là:  

- enqueue: thêm một phần tử vào phía cuối hàng đợi

- dequeue: xóa một phần tử ở phía đầu hàng đợi

Tùy vào nhu cầu mỗi bài toán chúng ta có thể thêm các hàm phù hợp để thuận tiện hơn khi sử dụng hàng đợi tương tự như ngăn xếp. Ngoài ra còn có rất nhiều biến thể của hàng đợi để phù hợp hơn với một số bài toán đặc thù như hàng đợi ưu tiên, hàng đợi 2 đầu,...

5. Cây ( Tree)

Cây là một cấu trúc dữ liệu có phân cấp, trong đó dữ liệu được tổ chức theo thứ bậc và được liên kết với nhau khi lưu trữ. Ứng dụng của cây là rất lớn mà bình thường chúng ta sẽ thấy được ở một số khái niệm như cây đơn vị, cây thư mục,...

Có rất nhiều loại cây đã ra đời để giải quyết các bài toán từ dễ tới khó, khắc phục nhược điểm của cây trước như: cây tìm kiếm nhị phân, B-Tree, Splay Tree, Cây đỏ đen,...


6. Đồ thị ( Graph)

Đồ thị là một tập hợp hữu hạn đỉnh ( nút) và đường đi giữa các đỉnh này. Có nhiều khái niệm liên quan tới đồ thị như bậc của đồ thị, kích thước đồ thị,... 2 đỉnh được gọi là liền kề nếu chúng được nối với nhau bởi 1 đường.

Cây cũng là một loại đồ thị và là đồ thị liên thông, không có chu trình. Nhưng vì cây đặc biệt và ứng dụng lớn vì thế chúng thường được nhắc riêng khi nói về chủ đề đồ thị.

Có 2 loại đồ thị: 

- Đồ thị có hướng: tất cả đường đi đều được đánh dấu chiều giữa điểm đầu và điểm cuối

- Đồ thị vô hướng: tất cả đường đi trên nó đều không quy định chiều


7. Bảng băm ( Hash table)

Bảng băm cũng là một loại CTDL khá phổ biến và đặc biệt, nó lưu trữ các giá trị mà mỗi giá trị có một khóa ( key) được liên kết với nó. Bảng băm hỗ trợ tìm kiếm hiệu quả nếu ta biết được khóa của giá trị cần tìm. 



   / /

  No Comments

8/31/2023

Cấu trúc dữ liệu và thuật toán | Hàng đợi (Queue)

  8/31/2023    trannguyenhan

1. Cấu trúc dữ liệu hàng đợi và ứng dụng

Hàng đợi là một dạng CTDL mà ở đó thao tác chèn vào sẽ được diễn ra ở một đầu, thường gọi là phía sau hay cuối (back or rear), trong khi phép toán xóa chỉ được thực hiện ở phía còn lại, gọi là phía trước hay đầu (front or head).

Nguyên tắc của hàng đợi: Vào trước ra trước, First-In First-Oout (FIFO)


Giống với ngăn xếp, hàng đợi cũng có 2 cách cài đặt cơ bản là dùng mảng và con trỏ.

Hàng đợi cũng có rất nhiều ứng dụng trong thực tế, ví dụ như là:

- Trong hệ điều hành: hàng đợi xử lý sự kiện, quản lý tiến trình, xử lý các câu lệnh. CPU không thể chạy tất cả các task cùng lúc nên các task sẽ được sắp xếp theo thứ tự ưu tiên lần lượt.

- Web server: một trang web cần phải xử lý vài nghìn files của người dùng nhưng khả năng của trang web chỉ xử lý được 100 files cùng một lúc, lúc này chúng ta cần một hàng đợi để đưa các request vào hàng đợi để chờ xử lý.

- Ứng dụng khi in hoặc upload nhiều ảnh cùng lúc

- Lưu vết trong quá trình tìm kiếm, quay lui, vét cạn,...

- Duyệt đồ thị

2. Cài đặt ngăn xếp sử dụng mảng

Khai báo một struct Queue và viết các hàm tương ứng với các phép toán trên hàng đợi:

- isFull(): kiểm tra hàng đợi đã đầy chưa

- enqueue(): thêm phần từ vào cuối hàng đợi

- dequeue(): lấy phần tử ra khỏi đầu hàng đợi

- getFront(): xem phần tử đầu hàng đợi

- getRear(): xem phần tử ở cuối hàng đợi

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho hàng đợi thì chúng ta có thể viết thêm các hàng tương ứng để công việc được thực hiện một cách dễ dàng hơn.

#define INT_MIN -2147483648

struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

struct Queue* createQueue(unsigned capacity){
    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = -1;
    queue->array = (int*) malloc(queue->capacity * sizeof(int));
    return queue;
}

// Kiem tra queue day
int isFull(struct Queue* queue){
    return (queue->size == queue->capacity);
}

// Kiem tra queue rong
int isEmpty(struct Queue* queue){
    return (queue->size == 0);
}

// Them phan tu vao queue
void enqueue(struct Queue* queue, int item){
    if(isFull(queue)){
        return;
    }

    queue->rear = (queue->rear + 1);
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d enqueued to queue\n", item);
}

int dequeue(struct Queue* queue){
    if(isEmpty(queue)){
        return INT_MIN;
    }

    int item = queue->array[queue->front];
    queue->front = (queue->front + 1);
    queue->size = queue->size - 1;
    return item;
}

int getFront(struct Queue* queue){
    if(isEmpty(queue)){
        return INT_MIN;
    }

    return queue->array[queue->front];
}

int getRear(struct Queue* queue){
    if(isEmpty(queue)){
        return INT_MIN;
    }

    return queue->array[queue->rear];
}

int main(){
    struct Queue* queue = createQueue(10);
    enqueue(queue, 1);
    enqueue(queue, 2);
    printf("Top of queue is %d", getFront(queue));
    printf("Rear of queue is %d", getRear(queue));

}

3. Cài đặt ngăn xếp sử dụng con trỏ

Với con trỏ thì chúng ta cũng cài đặt tương tự các hàm so với sử dụng mảng.


#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

struct node *front = NULL, *rear = NULL;

void enqueue(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = val;
    newNode->next = NULL;

    if(front == NULL && rear == NULL){
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

void dequeue()
{
    struct node *temp;

    if(front == NULL)
         printf("Queue is Empty\n");
    else
    {
        temp = front;
        front = front->next;

        if(front == NULL){
            rear = NULL;
        }

       free(temp);
    }

}

void printList()
{
    struct node *temp = front;

    while(temp)
    {
        printf("%d->",temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("Queue :");
    printList();
    dequeue();
    printf("After dequeue the new Queue :");
    printList();
    dequeue();
    printf("After dequeue the new Queue :");
    printList();

    return 0;
}

Xem đầy đủ code tại repo github: https://github.com/tailieubkhn/data-structures/blob/main/queue.c, https://github.com/tailieubkhn/data-structures/blob/main/queue_pointer.c

   / /

  No Comments

8/27/2023

Cấu trúc dữ liệu và thuật toán | Ngăn xếp (Stack)

  8/27/2023    trannguyenhan

1. Cấu trúc dữ liệu ngăn xếp và ứng dụng

Ngăp xếp là một dạng cấu trúc dữ liệu mà ở đó các thao tác với CTDL này chỉ diễn ra ở một đầu, được gọi là đỉnh của ngăn xếp (top). Hai thao tác phổ biến đối với ngăn xếp là đẩy vào (push) và lấy ra (pop), cả hai thao tác này đều tác động vào đỉnh của ngăn xếp.

Nguyên tắc của ngăn xếp: Vào trước ra sao, First-In Last-Out (FILO)

Có 2 cách cài đặt ngăn xếp là sử dụng mảng hoặc sử dụng con trỏ.

Mặc dù nhìn bề ngoài ngăn xếp có vẻ trông đơn giản nhưng nó lại có ứng dụng rất lớn trong thực tế. Ứng dụng trong sử dụng điều hướng các màn hình của điện thoại, ví dụ chúng ta đang ở một màn hình Settings của Facebook, Khi bấm vào General sẽ bị chuyển hướng sang một màn khác, vậy thì làm sao để khi bấm quay lại có thể quay lại đúng màn Settings một cách nhanh nhất? Đó chính là vứt nó vào ngăn xếp, mỗi khi bấm quay lại chỉ cần lấy nó ra từ đỉnh của ngăn xếp là được. Một số các ứng dụng khác của ngăn xếp như là lịch sử trình duyệt, hay là các cơ chế Undo (Redo) trong các trình soạn thảo văn bản. 

Ngăn xếp còn rất quan trọng trong việc giải một số bài toán như: 

- Tính giá trị biểu thức trung tố, hậu tố

- Bài toán cộng hai số lớn

- Bài toán kiểm tra ngoặc đúng 

- Bài toán đảo ngược xâu

2. Cài đặt ngăn xếp sử dụng mảng

Khai báo một struct Stack và viết các hàm tương ứng với các phép toán trên ngăn xếp: 

- isFull(stack): kiểm tra xem ngăn xếp đã đầy chưa 

- isEmpty(stack): kiểm tra ngăn xếp có rỗng không

- push(stack, item):  thêm phần tử vào ngăn xếp

- pop(stack): lấy phần tử ra khỏi ngăn xếp

- getTop(stack): xem phần tử ở đầu ngăn xếp và không xóa phần tử đó khỏi ngăn xếp

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho ngăn xếp thì chúng ta có thể viết thêm các hàm tương ứng để công việc được thực hiện một cách dễ dàng hơn.


#define INT_MIN -2147483648

struct Stack {
    int top;
    unsigned capacity;
    int* array;
};


// Khoi tao ngan xep
struct Stack* createStack(unsigned capacity){
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*) malloc(stack->capacity * sizeof(int));
}

// Kiem tra xem ngan xep day chua
int isFull(struct Stack* stack){
    return stack->top == stack->capacity - 1;
}

// Kiem tra ngan xep rong khong
int isEmpty(struct Stack* stack){
    return stack->top == -1;
}

// Them phan tu vao stack
void push(struct Stack* stack, int item){
    if(isFull(stack)){
        return;
    }

    stack->array[++stack->top] = item;
    printf("%d push to stack\n", item);
}

int pop(struct Stack* stack){
    if(isEmpty(stack)){
        return INT_MIN;
    }

    return stack->array[stack->top--];
}

int getTop(struct Stack* stack){
    if(isEmpty(stack)){
        return INT_MIN;
    }

    return stack->array[stack->top];
}

int main(){
    struct Stack* stack = createStack(10);
    push(stack, 2);
    push(stack, 3);
    printf("Top of value in stack: %d", getTop(stack));

}

3. Cài đặt ngăn xếp sử dụng con trỏ

Với con trỏ thì chúng ta cũng cài đặt tương tự các hàm so với cài đặt ngăn xếp sử dụng mảng.


#include <stdio.h>

struct Node {
    int data;
    struct Node* next;
};

struct Node* newNode(int val){
    struct Node* newN = (struct Node*) malloc(sizeof(struct Node));
    newN->data = val;
    newN->next = NULL;

    return newN;
}

void push(struct Node* head, int val){
    struct Node* newN = newNode(val);
    if(head == NULL){
        newN->next = NULL;
    } else {
        newN->next = head;
    }

    head = newN;

    printf("Top of stack is %d\n", head->data);
    printf("----------------\n");
}

int pop(struct Node* head){
    if(head == NULL){
        printf("Stack is empty\n");
        return;
    }

    int item = head->data;
    struct Node* tmp = head;
    head = head->next;
    free(tmp);

    printf("Top of stack is %d\n", head->data);
    return item;
}

int isEmpty(struct Node* head){
    return head == NULL;
}

int getTop(struct Node* head){
    if(head == NULL){
        return NULL;
    }

    return head->data;
}

int main(){
    struct Node* head = NULL;
    push(head, 10);
    pop(head);

    //printf("Top stack: %d", getTop(head));
}

Xem đầy đủ code tại repo github: https://github.com/tailieubkhn/data-structures/blob/main/stack.c, https://github.com/tailieubkhn/data-structures/blob/main/stack_pointer.c

   / /

  No Comments

8/19/2023

Cấu trúc dữ liệu và thuật toán | Mảng (Array) và Linked List

  8/19/2023    trannguyenhan

1. "Cấu trúc dữ liệu"

Cấu trúc dữ liệu là một họ các biến có thể có kiểu dữ liệu khác nhau, được liên kết với nhau theo một cách thức được quy định trước nào đó. Ví dụ như mảng là một dãy các ô có cùng kiểu dữ liệu xác định. 

Một số cấu trúc dữ liệu phổ biến như là: 

- Mảng

- Danh sách

- Đồ thị

- Ngăn xếp

- Hàng đợi

- Cây

Với các bài viết về cấu trúc dữ liệu này, mình sẽ đề cập tới khái niệm chính và cách cài đặt từng loại cấu trúc dữ liệu.

2. Cấu trúc dữ liệu mảng 

Dữ liệu dạng mảng là một dạng dữ liệu vô cùng phổ biến mà chúng ta có thể gặp thường xuyên trong mọi ngôn ngữ lập trình và mọi dự án.

Thông thường mảng thường được lưu trữ trên một dãy liên tiếp các ô nhớ trên bộ nhớ, vì vậy việc truy cập các phần tử trong mảng là cực kỳ nhanh chóng, nhưng lại bất lợi trong việc phân bổ thêm ô nhớ cho mảng.

Mảng thì rất quen thuộc rồi, các ngôn ngữ lập trình đều hỗ trợ hầu như mọi phép toán liên quan tới mảng, nên phần cài đặt mảng mình sẽ không đề cập tới trong phần này.

3. Cấu trúc dữ liệu danh sách liên kết đơn 

Danh sách liên kết đơn (hay một số tài liệu đề cập là danh sách móc nối đơn) là danh sách các phần tử mà mỗi phần tử sẽ chứa giá trị và một con trỏ chứa trỏ tới ô kế tiếp của danh sách.



Danh sách liên kết sẽ khắc phục được một số nhược điểm của việc sử dụng mảng đó là: 

- Bổ sung một phần tử tốn kém thời gian

- Lãng phí khoảng bộ nhớ trống khai báo ban đầu không dùng đến

- Phải duy trì một khoảng không gian lưu trữ liên tục trong bộ nhớ

3.1 Cài đặt danh sách liên kết đơn

Các ví dụ về cài đặt cấu trúc dữ liệu trong các bài viết mình sẽ sử dụng ngôn ngữ lập trình C.

Khai báo một struct node, và viết 5 hàm tương ứng với 5 phép toán trên danh sách liên kết: 

- isEmpty(): kiểm tra danh sách liên kết rỗng 

- print_list(): in danh sách phần tử 

- push(item): thêm phần tử vào đầu danh sách liên kết

- pop(): loại bỏ phần tử cuối danh sách

- insert_by_index(inx, item): chèn một phần tử vào vị trí bất kỳ trong danh sách liên kết

Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho danh sách liên kết thì chúng ta có thể viết thêm các hàm tương ứng để công việc được thực hiện một cách dễ dàng hơn.

#include<stdio.h>
#define INT_MIN -2147483648

struct node {
    int data;
    struct node *next;
};

struct node* head = NULL;

int isEmpty(){
    return head == NULL;
}

void print_list(){
    struct node *current = head;

    while(current != NULL){
        printf("%d\n", current->data);
        current = current->next;
    }
}

// push to front list
void push(int item){
    struct node* newN = (struct node*) malloc(sizeof(struct node));
    newN->data = item;
    newN->next = head;

    head = newN;
}

// pop last
void pop(){
    struct node* it = head;

    if(it->next == NULL){
        head = NULL;
        free(it);
        return;
    }

    while(it->next->next != NULL){
        it = it->next;
    }

    struct node* lastN = it->next;
    it->next = NULL;
    free(lastN);
}

void insert_by_index(int item, int inx){
    if(inx == 0){
        push(item);
        return;
    }

    struct node* it = head;
    int cnt = 1;

    while(cnt < inx){
        it = it->next;
        cnt++;
    }

    struct node* prev = it;
    struct node* next = it->next;

    // create new node
    struct node* newN = (struct node*) malloc(sizeof(struct node));
    newN->data = item;


}

3.2 Kiểm tra danh sách liên kết đơn vừa cài đặt

Chúng ta kiểm tra nhanh về cấu trúc dữ liệu vừa cài đặt có đúng không bằng cách sử dụng các hàm vừa cài đặt để thao tác với cấu trúc dữ liệu và kiểm tra dữ liệu sau khi sử dụng các hàm đã đúng chưa bằng cách in ra (sử dụng hàm print_list()).

int main(){
    // data example
    push(1);
    push(2);
    push(4);
    pop();
    pop();
    push(4);

    print_list();
}

Xem đẩy đủ code tại repo github: https://github.com/tailieubkhn/data-structures/blob/main/list.c

   / /

  No Comments

5/19/2023

Tổng hợp câu hỏi phỏng vấn về cấu trúc dữ liệu và giải thuật

  5/19/2023    trannguyenhan

Câu 1: Độ phức tạp của thuật toán sắp xếp nổi bọt?

A. N

B. 2N

C. N * Log(N)


Câu 2: Độ phức tạp của thuật toán sắp xếp Quicksort

a. N

b. 2N

c. N * Log(N)


Câu 3: Cấu trúc dữ liệu nào hỗ trợ nhanh nhất việc kiểm tra một phần tử có nằm trong danh sách hay không?

A. ArrayList

B. HashSet

C. TreeMap


Câu 4: Giải thuật đệ quy là?

A. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi nhỏ hơn

B. Trong giải thuật của nó có lời gọi tới chính nó

C. Trong giải thuật của nó có lời gọi tới một giải thuật khác đã biết kết quả

D. Trong giải thuật của nó có lời gọi tới chính nó nhưng với phạm vi lớn hơn


Câu 5: Ngăn xếp làm việc theo nguyên tắc

A. LILO ( last in last out)

B. LIFO ( last in first out)

c. FOLO (first out last out)

d. FIFO ( first in first out)


Câu 6: Định nghĩa danh sách tuyến tính hàng đợi:

A. Là một danh sách tuyến tính trong đó phép bổ sung một phần tử và phép loại bỏ một phần tử được thực hiện ở tại một vị trí bất kì trong danh sách.

B. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử được thực hiện ở một đầu, gọi là lối sau (rear) hay lối trước (front). Phép loại bỏ không thực hiện được.

C. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung một phần tử hay loại bỏ được thực hiện ở một đầu danh sách gọi là đỉnh (Top)

D. Hàng đợi là kiểu danh sách tuyến tính trong đó, phép bổ sung phần tử ở một đầu, gọi là lối sau (rear) và phép loại bỏ phần tử được thực hiện ở đầu kia, gọi là lối trước (front).


Câu 7: Độ phức tạp của việc tìm kiếm 1 số trong 1 mảng số nguyên đã sắp xếp là bao nhiêu?

A. N

B. N * Log(N)

C. Log(N)

D. N


Câu 8: Tạo một file ignore.txt gồm 500 nghìn phần tử random từ 1-> 2triệu.  Tạo một file data.txt có 1,5 triệu phần tử. Các phần tử tăng dần từ 1 đến 2 triệu và loại trừ các phần tử trong file ignore yêu cầu: Có thể dùng bất kỳ ngôn ngữ gì để thực hiện. 

Áp dụng các kiến thức về cấu trúc dữ liệu giải thuật sao cho code tối ưu và thời gian thực thi ngắn nhất có thể. 

Bài nộp bao gồm code và thời gian thực thi đoạn code đó. Không bao gồm các file dữ liệu.


Câu 9: A là một sinh viên CNTT, làm thêm việc shipper hàng ngày. A nhận ra, mỗi ngày mình chỉ có thể chở tổng cộng 100kg. Nên giờ A cần tìm một thuật toán để tối ưu giá trị thu lại của mình. Vì vậy A lên danh sách các đơn hàng mỗi ngày. Trong ngày hôm nay, A có danh sách như sau: 

Cân nặng = [20, 30, 40, 50]

Giá trị = [10, 40, 10, 20]

Theo danh sách trên, A sẽ trở món hàng ở vị trí 0, 1, 3 - tổng cân nặng là 20 + 30 + 50 = 100kg và có tổng giá trị là 10 + 40 + 20 = 70 là lớn nhất.

Yếu cầu: viết hàm với đầu vào là 2 danh sách, danh sách cân nặng và giá trị theo thứ tự tương ứng của từng mặt hàng, tính ra phương án cho A chọn những mặt hàng nào để tối ưu giá trị nhận được.

Input:

    Cân nặng = [20,30,40,50]

    Giá trị = [10,40,10,20]

Output:

    [0, 1, 3],100,70


Câu 10: Ai là người nổi tiếng:

Người nổi tiếng trong một nhóm là người không biết ai trong nhóm đó, nhưng tất cả mọi người trong nhóm đó đều biết anh ta. 

Ví dụ 1: Cho một nhóm người, dưới dạng ma trận như sau:

A B C
A 0 0 0
B 1 0 1
C 1 0 0

Như vậy người nổi tiếng là A, vì anh ta không quen ai trong nhóm, nhưng tất cả đều biết anh ta.

Ví dụ 2: 

A B C
A 0 1 0
B 1 0 1
C 1 1 0

Trong ví dụ này không có ai là người nổi tiếng cả.

Yêu cầu: Đầu vào là một ma trận quen biết như ví dụ, hãy tìm nguời nổi tiếng trong danh sách đầu vào.

Input:
[
[0, 0, 0],
[1, 0, 1],
[1, 0, 0]
      ]
Output: 0 => người ở vị trí 0 là người nổi tiếng

Input:
[
[0, 1, 0],
[1, 0, 1],
[1, 0, 0]
      ]
Output: null => không có ai là người nổi tiếng

Câu 11: Tính giai thừa của n một cách nhanh nhất.  Với n được người dùng nhập.

   / / /

  1 Comment

11/12/2021

C/C++ có thực sự cần thiết? Giới thiệu các IDE, Text Editor sử dụng cho lập trình C/C++

  11/12/2021    trannguyenhan

C/C++ có thực sự cần thiết?

C/C++ là ngôn ngữ dùng và giảng dạy trong hầu hết các môn học liên quan tới các môn cơ sở cốt lõi ngành CNTT như tin đại cương, cấu trúc dữ liệu, kỹ thuật lập trình, thuật toán ứng dụng,... tại Bách Khoa và hầu hết các trường đại học khác vì tính "nền tảng của C/C++".

Trong phần này mình sẽ giải thích cho các bạn vai trò của C/C++, và với sự phát triển mạnh mẽ của các ngôn ngữ lập trình bậc cao thì C/C++ có thực sự cần thiết?

- Câu trả lời của mình về C/C++ là cần thiết (*).

- Đầu tiên là mình muốn nói về C/C++ còn được các công ty sử dụng hay không?, chúng ta hãy xem danh sách các ngôn ngữ mà các công ty lớn đang sử dụng cho sản phẩm/dịch vụ của họ nha (Ảnh: Wiki - 2021): 

Như mọi người thấy C++ được hầu hết các ông lớn sử dụng ở phía server vì hiệu năng, tốc độ của nó là cực kì tốt.

- C/C++ gần với ngôn ngữ máy tính nhất nên qua đó, bạn có thể hiểu được bên dưới thật sự máy tính nó đang làm gì, cấp phát bộ nhớ ra sao, hoạt động như thế nào.

- C/C++ là cơ sở để xây dựng rất nhiều ngôn ngữ khác như Python, các thư viện hay core của Python đều được viết bằng C++, vì thế khi hiểu rõ bạn có thể tác động sâu hơn vào các ngôn ngữ này, cái này khá là hay mà khi mà mình đã bị bạn mình khuất phục bằng những thứ mình nghĩ là không thể nếu chúng ta chỉ là người giỏi ngôn ngữ Python mà không hiểu hệ thống bên dưới nó được chạy thế nào.

- Nhiều ngôn ngữ lập trình khác được phát triển dựa trên nền tảng C++, bao gồm C#, D, Java và các phiên bản mới hơn của C. Vậy nên các cấu trúc, câu lệnh, khai báo biến,... đều có phần giống với C/C++. Vì thế khi bạn học xong C/C++ thì tiếp cận các ngôn ngữ khác cũng dễ dàng hơn.

- Lập trình viên C/C++ được trả lương rất cao

Tuy nhiên chúng ta cần quay lại (*) ở bên trên, mình đã nói rằng C/C++ là cần thiết tuy nhiên chúng không phải là tất cả, bạn có thể bước vào và trở thành một lập trình viên mà không cần biết cũng như cần học qua C/C++. Với các bạn sinh viên và đặc biệt là sinh viên Bách Khoa thì C/C++ được sử dụng làm ngôn ngữ giảng dạy trong một số môn thì lời khuyên của mình là các bạn hãy cố gắng học cho tốt chú đừng cố kêu ca rằng nó đã lỗi thời và không còn được sử dụng.

Các IDE, Text Editor sử dụng cho lập trình C/C++

Khi năm nhất cũng mới học tin đại cương thôi, lúc ấy cũng là dân mới vào nghề, mình cũng không biết là dùng IDE gì để code C/C++, cũng đã thử cài vào rồi gỡ ra rất nhiều ứng dụng. Trong phần này mình sẽ chia sẻ tới mọi người một số IDE, Text Editor phổ biến cho lập trình C/C++ và các ưu, nhược điểm của nó để các bạn có thể chọn ra IDE, Text Editor phù hợp cho mình nha.

Dev-C/C++

Cái tên gạo cội thì phải nhắc tới Dev-C/C++, nó là IDE chính được sử dụng trong môn tin học đại cương, nó dễ cài đặt, dễ sử dụng và nhẹ tuy nhiên chưa phải là một IDE mạnh. Thường thì Dev-C/C++ sử dụng cho người mới bắt đầu.

Codeblocks

Codeblocks là IDE mà mình thấy là phù hợp cho việc học thuật toán và nó cũng được các thầy/cô giáo trong môn thuật toán ứng dụng gợi ý sử dụng. Codeblocks cũng rất dễ cài đặt, sử dụng và nhẹ. Với góc độ thuật toán thì Codeblocks là một IDE khá mạnh, tuy nhiên với project lớn phải chia các mô-đun thì mình thấy là Codeblocks chưa đủ mạnh.

Eclipse / Netbeans

C/C++ như là nghề tay trái khi nhắc tới 2 IDE này. Netbeans hay Eclipse đều là các IDE mạnh mẽ hỗ trợ Java và thường sử dụng cho các lập trình viên Java (Eclipse thì có cả 1 hệ sinh thái các ứng dụng của riêng chúng). 

Điểm mạnh của 2 IDE này là mã nguồn mở, hoàn toàn free cho người dùng và rất mạnh mẽ. Tuy nhiên thì việc sử dụng 2 IDE này trong 2 môn tin đại cương hay thuật toán ứng dụng có vẻ là hơi to và nặng.

Clion

Clion là một sản phẩm của Jetbrains và như mình đã viết trong một số bài viết thì các sản phẩm của Jetbrains là miễn bàn, ngon khỏi chê. 

Tuy nhiên Clion rất nặng, như với Netbeans và Eclipse thì Clion dành cho các project lớn. Còn nữa, Clion là không có bản miễn phí, nhưng với sinh viên chúng ta hoàn toàn có thể sử dụng miễn phí Clion mà không tốn một đồng nào từ mail edu của các bạn, bạn có thể xem lại bài hướng dẫn Mail edu của trường làm được gì để nhận và sử dụng miễn phí tất cả các sản phẩm của Jetbrains.

VSCode / Sublime Text

VSCode hay Sublime Text đều là các Text Editor, và muốn sử dụng chúng cho bất cứ ngôn ngữ hay framework nào thì các bạn phải cài thêm các extension hỗ trợ, và việc mày mò cài thêm  các extension cho từng ngôn ngữ là rắc rối. Thường thì những pro mới dùng editor để code, lời khuyên của mình nếu các bạn là newbie thì hãy lựa chọn Dev-C hoặc Codeblocks chứ đừng bem ngay vào 2 editor này.

Một editor nữa mình giới thiệu luôn ở phần này đó là vim, cũng giống như VSCode hay Sublime Text, bạn muốn sử dụng chúng cho các ngôn ngữ hay framework nào thì phải cài thêm các extension hỗ trợ. Vim thì sử dụng rất khó, cài đặt thêm các extension cũng khó. Thường thì các super-pro mới dùng vim để code.

replit

Cái này là một IDE online hỗ trợ khá nhiều các ngôn ngữ. Vì là online nên rất tiện vì các bạn không cần phải cài đặt, chỉ cần một trình duyệt có mạng là có thể vào code luôn, dùng mọi nơi chỉ cần là có máy tính nối mạng không cần phải cài môi trường hay gì cả. 

Tuy nhiên vì là online nên có rất nhiều hạn chế như các thư viện không đủ, các trình gợi ý code chưa đủ mạnh,...

Tham khảo: https://en.wikipedia.org/, https://codelearn.io/

   / / / / /

  No Comments

8/13/2021

Calendar Queue : A Fast O(1) Priority Queue Implementation for the Simulation Event Set Problem | Share

  8/13/2021    trannguyenhan

Chúng ta thường được học về hàng đợi ưu tiên cài đặt bằng cấu trúc dữ liệu Heap, tuy nhiên đây không phải là cách duy nhất để cài đặt hàng đợi ưu tiên và như ta được học mặc dù việc cài đặt bằng cấu trúc dữ liệu Heap thì các thao các như insert hay delete phần tử cũng đã rất nhanh rồi, tuy nhiên cài đặt hàng đơi ưu tiên bằng cấu trúc dữ liệu Heap cũng chưa phải cách nhanh nhất.

Có rất nhiều các cài đặt hàng đợi ưu tiên khác mang lại hiệu quả cao hơn việc sử dụng cấu trúc dữ liệu Heap, ví dụ như sử dụng cây S-Play, Calendar Queue,...

Việc cài đặt hàng đợi ưu tiên bằng Calendar Queue mang lại hiệu quả rất tốt, nó được đánh giá là một trong những phương pháp tốt nhất để cài đặt hàng đợi ưu tiên.

Nếu bạn muốn tìm hiểu về Calendar Queue để sắp xếp cho số lượng lớn các sự kiện thì có thể tham khảo qua bài báo Calendar Queue : A fast O(1) priority queue implementation for the simulation event set problem

Bạn có thể tham khảo code Calendar Queue bằng C của mình TẠI ĐÂY nha.

   / / /

  No Comments

12/03/2020

Cấu trúc dữ liệu và thuật toán | Tài liệu, cơ sở ngành CNTT

  12/03/2020    trannguyenhan

Cấu trúc dữ liệu và thuật toán là điều bắt buộc mà bất kì lập trình viên nào cũng đều phải biết. Quản lý dữ liệu có cấu trúc sẽ giúp giảm thời gian tính toán đi rất nhiều, còn thuật toán thì không phải nói tới nó quan trọng như nào, tuy rằng với thời đại mà máy tính rất mạnh mẽ thì việc một thuật toán chạy với O(n) hay O(n^2) có thể không quan trọng lắm nhưng khi dữ liệu lớn lên thì mọi thứ đều cần phải tối ưu để có được những kết quả tốt trong thời gian cho phép.

Tại Bách Khoa, môn Cấu trúc dữ liệu và thuật toán khá là nhàm chán, không có thực hành, học lý thuyết xuông và đi thi cũng thi trên giấy ( là thi code trên giấy hoặc là viết mã giả). Môn này đề cập tới những gì sâu xa nhất, giới thiệu tới những cấu trúc dữ liệu cơ bản, cách cài đặt những cấu trúc dữ liệu cơ bản này, các thao tác trên cấu trúc dữ liệu ( như chèn, xóa, sửa, ...). Về phần thuật toán các bạn sẽ được giới thiệu tới những thuật toán như sắp xếp, tìm kiếm,... và một số thuật toán trên đồ thị ( phần này toán rời rạc sẽ học sâu hơn, và nhiều khi Toán rời rạc với Cấu trúc dữ liệu học cùng kì thì các thầy dạy cấu trúc dữ liệu thường bàn với nhau việc lược bỏ phần này).

Tuy là học lý thuyết xuống nhưng các bạn cũng không nên quá nản vì môn này mới là khởi đầu thôi. Ngày trước môn này 3 tín và có thực hành, tuy nhiên bây giờ đã giảm xuống 2 tín và hoàn toàn không có thực hành. Phần thực hành đã được tách ra hẳn 1 môn khác là thuật toán ứng dụng mà các thầy vẫn hay gọi là cấu trúc dữ liệu 2, khi học môn này các bạn thao hồ code mỏi tay, code tới chán không muốn code nữa cơ nên không cần thắc mắc là môn này chỉ học lý thuyết rất nhàm chán nha. Nó sẽ cung cấp cho bạn kiến thức nền vững chắc nhất để học các môn học sau này.

Mình chia sẻ tới mọi người một số tài liệu học môn này để mọi người tham khảo và tự học : 

  • Slide bài giảng CTDL & TT thầy Nguyễn Đức Nghĩa : TẢI VỀ SLIDE (trả biết thầy Nghĩa nhét gì vào trong này mà slide của thầy nặng kinh khủng)

  • Đề thi CTDL & TT được tổng hợp từ nhiều nguồn ( cái này thực ra cũng là 1 số đề từ khá lâu, chỉ mang tính chất tham khảo là chính, ôn thi các bạn nên ôn thi theo các phần trọng tâm mà thầy dặn) : TẢI VỀ ĐỀ THI

   / / / /

  2 Comments