Chuyên mục thuật toán - Học thuật toán với ngôn ngữ C/C++

Tính lũy thừa ma trận trong C/C++

ByNguyễn Thanh Châu 09/01/202209/01/2022

Hướng dẫn cách tính lũy thừa ma trận – Ma trận là một chủ đề không còn xa lạ với những người dấn thân vào ngành lập trình. Trong hầu hết tất cả các nhánh của ngành IT như web, game, AI, lập trình thi đấu,… ma trận đều giữ một vị trí đặc biệt…

Machine learning | Featured | Giải thuật

Beam search là gì? Vai trò của beam search trong NLP

ByNguyễn Văn Hiếu 02/08/202008/08/2020

Thuật toán beam search là một thuật toán tìm kiếm heuristic. Nó được sử dụng trong các bài toán như dịch máy, nhận dạng giọng nói, tóm tắt văn bản,… Đó là các bài toán NLP có đầu ra liên quan đến việc tạo một chuỗi các từ. Trong bài viết này, LTKK sẽ cùng…

Học C/C++ | Giải thuật

Bài 52. Thêm/ xóa phần tử trong mảng 1 chiều

ByNguyễn Văn Hiếu 01/09/201914/12/2019

This entry is part 50 of 69 in the series Học C Không Khó

Hôm nay, Lập trình không khó sẽ cùng các bạn đi giải quyết bài tập “Thêm phần tử trong mảng 1 chiều và xóa phần tử trong mảng 1 chiều” nhé. Đây là 1 bài tập thực hành hơi nâng cao một chút. Nó thường gây ra những khó khăn nhất định cho các bạn…

Học C/C++ | Featured | Học Java | Giải thuật

Bài 50. Thuật toán tìm kiếm nhị phân

ByNguyễn Văn Hiếu 01/09/201907/12/2020

This entry is part 48 of 69 in the series Học C Không Khó

Thuật toán tìm kiếm nhị phân là một trong các thuật toán sắp xếp được sử dụng rất nhiều trong thực tế. Hãy cùng mình đi tìm hiểu thuật toán tìm kiếm này nhé. Tìm kiếm là một phần không thể thiếu của mọi ứng dụng, website hay phần mềm. Tính năng tìm kiếm cho…

Giải thuật | Thuật toán sắp xếp | Học C/C++

Bài 49. Thuật toán sắp xếp chèn (Insertion sort)

ByNguyễn Văn Hiếu 01/09/201923/09/2020

This entry is part 47 of 69 in the series Học C Không Khó

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Ở bài viết này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp chèn. Nội dung bài…

Học C/C++ | Giải thuật | Thuật toán sắp xếp

Bài 48. Thuật toán sắp xếp chọn (Selection sort)

ByNguyễn Văn Hiếu 01/09/201923/09/2020

This entry is part 46 of 69 in the series Học C Không Khó

Chào mừng các bạn quay trở lại với blog của Nguyễn Văn Hiếu. Đây là một bài viết trong series các thuật toán sắp xếp có minh họa code sử dụng ngôn ngữ lập trình C++. Bài viết đầu tiên này Nguyễn Văn Hiếu xin giới thiệu tới các bạn thuật toán sắp xếp chọn. Nội…

Giải thuật | Thuật toán sắp xếp | Học C/C++

Bài 47. Thuật toán sắp xếp nổi bọt

ByNguyễn Văn Hiếu 01/09/201923/09/2020

This entry is part 45 of 69 in the series Học C Không Khó

Học C/C++ | Giải thuật

Cài đặt code bài toán người du lịch cài đặt bằng C++, Java

ByNguyễn Văn Hiếu 20/05/201920/05/2019

Bài toán người du lịch: Một nguời du lịch muốn đi tham quan n thành phố T1,T2…, Tn . Xuất phát từ một thành phố nào đó, người du lịch muốn đi qua tất cả các thành phố còn lại, mỗi thành phố đi qua duy nhất 1 lần rối quay trở trở lại thành…

Giải thuật

Thuật toán Kruskal – Cài đặt Kruskal algorithm sử dụng C/C++

ByNguyễn Văn Hiếu 22/01/201924/01/2019

// C++ implementation of Kruskal's Algorithm to find the Minimum Spanning tree for a weighted, connected and undirected graph.

#include <iostream>
#include <climits>
#define n 6
int parent[n]; // Parent array to hold the parent nodes of each node in the graph

using namespace std;

void printMST(int a[n], int b[n], int weight[n]) // Printing the MST
{
    int Minweight = 0; // Weight of Minimum spanning tree
    for (int i = 0; i < n - 1; i++)
    {
        cout << "Edge: " << a[i] << "-" << b[i] << " "
             << "cost: " << weight[i] << endl;
        Minweight += weight[i];
    }
    cout << "Minimum Weight is " << Minweight << endl; // Printing the weight of MINIMUM SPANNING TREE
}

int findParent(int node) // Function to determine the parent node
{
    while(parent[node] >= 0)
        node = parent[node];

    return node;
}

/* "findParentPathCompression" is an alternative for "findParent" which is more efficient.
 * We use a technique called "path compression" here.
 * With path compression, we destroy the structure of the tree, and only focus on which group a node is in.
 */

int findParentPathCompression(int node)
{
    if(node == parent[node]) return node;
    return parent[node] = findParentPathCompression(parent[node]);
}


void kruskal(int cost[n][n]) // Function performing Kruskal's algorithm
{
    fill_n(parent, n, -1);
    int u, v, k = 0, count = 0;
    int firstNode, secondNode;
    int a[n]; // Array containing the first nodes of all the edges present in MST
    int b[n]; // Array containing the second nodes of all the edges present in MST
    int weight[n]; // Array containing the weights of the edges present in MST
    int minimum;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (cost[i][j] == 0) //  If i and j nodes are not adjacent
                cost[i][j] = INT_MAX; // Then, initialize their weight as INFINITE

    while(count < n-1)
    {
        minimum = INT_MAX; // Initializing minimum as INFINITE

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (cost[i][j] < minimum)
                {
                    minimum = cost[i][j]; // find the minimum cost edge
                    firstNode = i; // First node of determined edge
                    secondNode = j; // Second node of determined edge
                }
            }
        }

        u = findParent(firstNode);
        v = findParent(secondNode);


        if (u != v) // If parents of both the nodes are different, no circuit is being formed
        {
            parent[v] = u;
            a[k] = firstNode; // Store first node in array
            b[k] = secondNode; // Store second node in array
            weight[k] = cost[firstNode][secondNode]; // Store the determined edge's weight in array
            count++;
            k++;
        }

        cost[firstNode][secondNode] = cost[secondNode][firstNode] = INT_MAX; // Edges getting included in MST will be given the weight of INFINITE
    }

    printMST(a, b, weight); // Printing the MST
}

// Driver program to test above function
int main()
{

/* Let the given graph is :
     (1)____1___(2)
    /  \       /  \
   3    4     4    6
  /      \   /      \
 /        \ /        \
(0)___5___(5)____5___(3)
 \         |         /
  \        |        /
   \       |       /
    \      2      /
     6     |     8
      \    |    /
       \   |   /
        \  |  /
         \ | /
          (4)
*/

    int cost[n][n] = {
        { 0, 3, 0, 0, 6, 5 },
        { 3, 0, 1, 0, 0, 4 },
        { 0, 1, 0, 6, 0, 4 },
        { 0, 0, 6, 0, 8, 5 },
        { 6, 0, 0, 8, 0, 2 },
        { 5, 4, 4, 5, 2, 0 }
    };

    kruskal(cost);
    return 0;
}

/*
Output :
 Edge: 0-1 cost: 3
 Edge: 1-2 cost: 1
 Edge: 1-5 cost: 4
 Edge: 5-4 cost: 2
 Edge: 5-3 cost: 5
 Minimum Weight is 15
*/

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

// C++ implementation of Kruskal's Algorithm to find the Minimum Spanning tree for a weighted, connected and undirected graph.

#include <iostream>

#include <climits>

#define n 6

int parent[n]; // Parent array to hold the parent nodes of each node in the graph

using namespace std;

void printMST(int a[n], int b[n], int weight[n]) // Printing the MST

{

int Minweight = 0; // Weight of Minimum spanning tree

for (int i = 0; i < n - 1; i++)

{

cout << "Edge: " << a[i] << "-" << b[i] << " "

<< "cost: " << weight[i] << endl;

Minweight += weight[i];

}

cout << "Minimum Weight is " << Minweight << endl; // Printing the weight of MINIMUM SPANNING TREE

}

int findParent(int node) // Function to determine the parent node

{

while(parent[node] >= 0)

node = parent[node];

return node;

}

/* "findParentPathCompression" is an alternative for "findParent" which is more efficient.

* We use a technique called "path compression" here.

* With path compression, we destroy the structure of the tree, and only focus on which group a node is in.

int findParentPathCompression(int node)

{

if(node == parent[node]) return node;

return parent[node] = findParentPathCompression(parent[node]);

}

void kruskal(int cost[n][n]) // Function performing Kruskal's algorithm

{

fill_n(parent, n, -1);

int u, v, k = 0, count = 0;

int firstNode, secondNode;

int a[n]; // Array containing the first nodes of all the edges present in MST

int b[n]; // Array containing the second nodes of all the edges present in MST

int weight[n]; // Array containing the weights of the edges present in MST

int minimum;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

if (cost[i][j] == 0) // If i and j nodes are not adjacent

cost[i][j] = INT_MAX; // Then, initialize their weight as INFINITE

while(count < n-1)

{

minimum = INT_MAX; // Initializing minimum as INFINITE

for (int i = 0; i < n; i++)

{

for (int j = 0; j < n; j++)

{

if (cost[i][j] < minimum)

{

minimum = cost[i][j]; // find the minimum cost edge

firstNode = i; // First node of determined edge

secondNode = j; // Second node of determined edge

}

u = findParent(firstNode);

v = findParent(secondNode);

if (u != v) // If parents of both the nodes are different, no circuit is being formed

{

parent[v] = u;

a[k] = firstNode; // Store first node in array

b[k] = secondNode; // Store second node in array

weight[k] = cost[firstNode][secondNode]; // Store the determined edge's weight in array

count++;

k++;

}

cost[firstNode][secondNode] = cost[secondNode][firstNode] = INT_MAX; // Edges getting included in MST will be given the weight of INFINITE

}

printMST(a, b, weight); // Printing the MST

}

// Driver program to test above function

int main()

{

/* Let the given graph is :

(1)____1___(2)

/ \ / \

3 4 4 6

/ \ / \

(0)___5___(5)____5___(3)

\ | /

\ 2 /

6 | 8

\ | /

(4)

int cost[n][n] = {

{ 0, 3, 0, 0, 6, 5 },

{ 3, 0, 1, 0, 0, 4 },

{ 0, 1, 0, 6, 0, 4 },

{ 0, 0, 6, 0, 8, 5 },

{ 6, 0, 0, 8, 0, 2 },

{ 5, 4, 4, 5, 2, 0 }

};

kruskal(cost);

return 0;

}

Output :

Edge: 0-1 cost: 3

Edge: 1-2 cost: 1

Edge: 1-5 cost: 4

Edge: 5-4 cost: 2

Edge: 5-3 cost: 5

Minimum Weight is 15

Giải thuật | Featured | Thuật toán sắp xếp | Học C/C++

Counting Sort – Thuật toán sắp xếp đếm phân phối

ByNguyễn Văn Hiếu 22/01/201923/09/2020

Counting sort là một thuật toán sắp xếp cực nhanh một mảng các phần tử mà mỗi phần tử là các số nguyên không âm; Hoặc là một danh sách các ký tự được ánh xạ về dạng số để sort theo bảng chữ cái. Counting sort là một thuật toán sắp xếp các con…