Cấu trúc dữ liệu và Giải thuật Archives - Page 3 of 5

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 | Học C/C++ | Thuật toán sắp xếp

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ó

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 nổi bọt. Nội dung bài viết…

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

Bài 45. Sắp xếp dãy số giảm dần, tăng dần

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

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

Sắp xếp dãy số theo thứ tự tăng dần hay giảm dần là 1 bài toán sắp xếp đơn giản và cơ bản nhất đối với bất cứ ai học lập trình. Nói theo cách khác, bài toán này chính là bài toán sắp xếp mảng 1 chiều tăng dần/giảm dần. Bài toán sắp xếp…

Cấu trúc dữ liệu | Học C/C++ | Featured

Bài 41. Mảng 1 chiều trong C

ByNguyễn Văn Hiếu 25/08/201904/12/2020

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

Mảng 1 chiều là cấu trúc dữ liệu đầu tiên và cũng là cấu trúc dữ liệu đơn giản & phổ biến nhất. Mảng 1 chiều hay tiếng anh là One-Dimensional Array là bài viết đầu tiên trong loạt bài viết hướng dẫn về cấu trúc dữ liệu tại Blog Nguyenvanhieu.vn. Hi vọng series này…

Cấu trúc dữ liệu | Học C/C++ | Mã nguồn

Bài tập cấu trúc dữ liệu và giải thuật tổng hợp

ByVõ Văn Tâm 20/07/201922/02/2020

Hôm nay mình sẽ hướng dẫn các bạn giải quyết một bài toán cấu trúc dữ liệu và giải thuật, đồng thời cũng chia sẻ source code luôn nhé! Đây là một bài tập cấu trúc dữ liệu và giải thuật tổng hợp bao gồm nhiều cấu trúc dữ liệu và giải thuật khác nhau…

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…

Học C/C++ | Cấu trúc dữ liệu | Download | Chia sẻ

Bài tập C/C++ có lời giải PDF – Tuyển tập đề thi của các trường ĐH

ByNguyễn Văn Hiếu 18/05/201909/10/2020

Chào tất cả các bạn, hôm nay mình xin chia sẻ tới các bạn bộ bài tập C/C++ có lời giải được lưu trong file pdf. Đây là bộ đề thi bộ môn tin học của của các trường đại học sử dụng ngôn ngữ C/C++. Nếu bạn chỉ có nhu cầu download bộ “bài…

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 | Học C/C++ | Featured | Thuật toán sắp xếp

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…

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

Thuật toán kiểm tra năm nhuận

ByNguyễn Văn Hiếu 15/01/201931/10/2020

Năm nhuận là gì? Để cài đặt thuật toán kiểm tra năm nhuận, bạn cần hiểu năm nhuận là gì? Theo lịch dương, năm nhuận là những năm có 366 ngày, nếu năm đó không phải năm nhuận thì chỉ có 365 ngày. Cụ thể, các năm nhuận thì tháng 2 sẽ có 29 ngày…