c++ Archives - Page 2 of 8 - Lập trình không khó

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++

Bài 39. Cách tính giai thừa trong C/C++

ByNguyễn Văn Hiếu 25/08/201914/12/2019

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

Cách tính giai thừa trong c/c++ ? Bài viết này mình sẽ giới thiệu với các bạn cách tính giai thừa bằng phương pháp đệ quy và không dùng đệ quy. Cách tính giai thừa bằng phương pháp đệ quy Một số n! được định nghĩa như sau: n! = n*(n-1)*…*3*2*1 Trường hợp đặc biệt…

Học C/C++

Bài 12. Hoán vị 2 số trong C

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

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

Có lẽ với tất cả các bạn độc giả bài toán hoán vị 2 số nguyên đã cực kỳ quen thuộc. Bởi lẽ đây là một bài toán kinh điển mà chúng ta được học ngay từ lúc mới tiếp cận với lập trình. Nhưng hôm nay, Lập trình không khó sẽ trình bày cho…

Học C/C++

Tìm giá trị đầu tiên trong mảng có chữ số đầu tiên là chữ số lẻ

ByVõ Văn Tâm 23/01/2019

Bài toán: Hãy tìm giá trị đầu tiên trong mảng một chiều các số nguyên có chữ số đầu tiên là chữ số lẻ. Nếu trong mảng không tồn tại giá trị như vậy thì hàm sẽ trả về giá trị 0 Ví dụ: Input

21 13 53 26

1	21 13 53 26

Output

Gia tri thoa man bai toan la: 13

1	Gia tri thoa man bai toan la: 13

Input

21 23 20 25 28

1	21 23 20 25 28

Output

Khong ton tai gia tri thoa man bai toan

1	Khong ton tai gia tri thoa man bai toan

Ý tưởng tìm…

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

Học C/C++

Viết chương trình tính tích tất cả các ước số lẻ

ByVõ Văn Tâm 04/01/2019

Bài toán: Tính tích các ước số lẻ của số nguyên dương n nhập vào từ bàn phím. Input

15

Output

225

225

Tích tất cả các ước số của số 15(các giá trị 1, 3, 5, 15) là 225. Xây dựng chương trình tính tích các ước số lẻ của số nguyên Tìm các…

Học C/C++

Liệt kê các giá trị có toàn chữ số lẻ trong mảng một chiều các số nguyên

ByVõ Văn Tâm 30/12/2018

Bài toán: Hãy liệt kê các giá trị có toàn chữ số lẻ trong mảng một chiều các số nguyên. Nếu mảng không tồn tại phần tử chứa toàn số lẻ thì in ra màn hình dòng thông báo “Khong ton tai gia tri co toan chu so le”. Ý tưởng tìm giá trị có toàn…

Học C/C++

Tìm chữ số xuất hiện ít nhất trong một mảng bằng C++

ByVõ Văn Tâm 25/12/2018

Bài toán: Cho mảng một chiều các số nguyên. Hãy viết hàm tìm chữ số xuất hiện ít nhất trong mảng đã cho. Trong trường hợp có hai hay nhiều chữ số có số lần xuất hiện bằng nhau thì in ra chữ số nhỏ nhất. Ví dụ: Input:

1 12 13 23 51

1	1 12 13 23 51

Output:

Chu so xuat hien it nhat la: 5

1	Chu so xuat hien it nhat la: 5

Nhận xét: Chữ…

Học C/C++

Các đặc điểm mới của c++ so với c

ByVõ Văn Tâm 18/12/2018

Thường khi bắt đầu học năm nhất thì chúng ta sẽ được nhà trường dạy ngôn ngữ c hoặc c++. Vậy bài viết hôm nay mình sẽ giới thiệu những điểm mới của c++ so với c. Một số điểm mới của c++ so với c C++ bổ sung khả năng lập trình hướng đối…

Học C/C++

Bài toán chuyển đổi thời gian

ByVõ Văn Tâm 16/12/2018

Bài toán: Bạn Bình bắt đầu làm bài tập lập trình mà thầy giáo vừa ra và lúc h giờ, m phút và s giây. Thời gian làm tất cả bài tập của Bình là x giây (0 < x < 105). Bình muốn biết đồng hồ sẽ chỉ mấy giờ khi mình kết thúc việc…