Scribd Logo
Upload

Welcome to Scribd!

  • 2K views

    Day Con Tang Dai Nhat: Tam Tat Ca To Hop Con

    Uploaded by

    cheat cheatcheat
    The document contains code snippets for several algorithms including finding the longest increasing subsequence, generating all subsets of an array, using queues and stacks, Dijkstra's algorithm for finding shortest paths, and finding the minimum element that appears at least twice in an array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Day Con Tang Dai Nhat: Tam Tat Ca To Hop Con

    Uploaded by

    cheat cheatcheat
    2K views5 pages
    The document contains code snippets for several algorithms including finding the longest increasing subsequence, generating all subsets of an array, using queues and stacks, Dijkstra's algorithm for finding shortest paths, and finding the minimum element that appears at least twice in an array.

    Original Title

    hen

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document contains code snippets for several algorithms including finding the longest increasing subsequence, generating all subsets of an array, using queues and stacks, Dijkstra's algorithm for finding shortest paths, and finding the minimum element that appears at least twice in an array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    2K views5 pages

    Day Con Tang Dai Nhat: Tam Tat Ca To Hop Con

    Uploaded by

    cheat cheatcheat
    The document contains code snippets for several algorithms including finding the longest increasing subsequence, generating all subsets of an array, using queues and stacks, Dijkstra's algorithm for finding shortest paths, and finding the minimum element that appears at least twice in an array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Day con tang dai nhat

    #include <iostream>
    #include <vector>
    using namespace std;

    vector<int> timDayConTang(const vector<int>& arr) {


    int n = arr.size();
    if (n == 0) {
    return vector<int>();
    }
    vector<int> currentSubsequence = {arr[0]};
    vector<int> maxSubsequence = {arr[0]};
    for (int i = 1; i < n; i++) {
    if (arr[i] > arr[i - 1]) {
    currentSubsequence.push_back(arr[i]);
    } else {
    currentSubsequence = {arr[i]};
    }
    if (currentSubsequence.size() > maxSubsequence.size()) {
    maxSubsequence = currentSubsequence;
    }
    }
    return maxSubsequence;
    }
    int main() {
    int n;
    cout << "Nhap so luong phan tu cua day so: ";
    cin >> n;
    vector<int> arr(n);
    cout << "Nhap cac phan tu cua day so:\n";
    for (int i = 0; i < n; i++) {
    cout << "Phan tu thu " << i << ": ";
    cin >> arr[i];
    }
    vector<int> result = timDayConTang(arr);
    cout << "Day con tang dai nhat la:\n";
    for (int num : result) {
    cout << num << " ";
    }
    return 0;
    }
    //
    Tam tat ca to hop con
    #include <iostream>
    #include <vector
    using namespace std;
    void timTatCaTongHopCon(const vector<int>& mang, vector<int>& hienTai, int viTri) {
    cout << "{ ";
    for (int i : hienTai) {
    cout << i << " ";
    }
    cout << "}\n";
    for (int i = viTri; i < mang.size(); i++) {
    hienTai.push_back(mang[i]);
    timTatCaTongHopCon(mang, hienTai, i + 1);
    hienTai.pop_back();
    }
    }
    int main() {
    int n;
    cout << "Nhap so luong phan tu cua mang: ";
    cin >> n;
    vector<int> mang(n);
    cout << "Nhap cac phan tu cua mang:\n";
    for (int i = 0; i < n; i++) {
    cout << "Phan tu thu " << i << ": ";
    cin >> mang[i];
    }
    vector<int> hienTai;
    cout << "Cac to hop con cua mang la:\n";
    timTatCaTongHopCon(mang, hienTai, 0);
    return 0;
    }

    Enqueue
    #include <iostream>
    #include <queue>
    #include <stack>

    int main() {
    std::queue<int> myQueue;
    for (int i = 1; i <= 5; i++) {
    myQueue.push(i);
    std::cout << "Enqueued: " << i << std::endl;
    }
    while (!myQueue.empty()) {
    int frontElement = myQueue.front();
    std::cout << "Dequeued: " << frontElement << std::endl;
    myQueue.pop();
    }
    std::cout << std::endl;
    std::stack<int> myStack;
    for (int i = 1; i <= 5; i++) {
    myStack.push(i);
    std::cout << "Pushed: " << i << std::endl;
    }
    while (!myStack.empty()) {
    int topElement = myStack.top();
    std::cout << "Popped: " << topElement << std::endl;
    myStack.pop();
    }
    return 0;
    }

    Dijiktra
    #include <iostream>
    #include <vector>
    #include <climits>

    using namespace std;


    struct Dinh {
    int id;
    int khoangCach;
    bool daXet;
    vector<pair<int, int>> ke;
    };

    int timDinhNhoNhat(const vector<Dinh>& graph) {


    int khoangCachNhoNhat = INT_MAX;
    int dinhNhoNhat = -1;

    for (const Dinh& dinh : graph) {


    if (!dinh.daXet && dinh.khoangCach < khoangCachNhoNhat) {
    khoangCachNhoNhat = dinh.khoangCach;
    dinhNhoNhat = dinh.id;
    }
    }

    return dinhNhoNhat;
    }

    void inDuongDi(const vector<Dinh>& graph, int dinhNguon, int dinhDich) {


    if (dinhNguon == dinhDich) {
    cout << dinhDich << " ";
    return;
    }

    inDuongDi(graph, dinhNguon, graph[dinhDich].ke[0].first);


    cout << dinhDich << " ";
    }

    void dijkstra(vector<Dinh>& graph, int dinhNguon) {


    for (Dinh& dinh : graph) {
    dinh.khoangCach = INT_MAX;
    dinh.daXet = false;
    }

    graph[dinhNguon].khoangCach = 0;

    for (int i = 0; i < graph.size() - 1; i++) {


    int dinhChon = timDinhNhoNhat(graph);
    graph[dinhChon].daXet = true;

    for (const pair<int, int>& ke : graph[dinhChon].ke) {


    int dinhKe = ke.first;
    int trongSo = ke.second;
    if (!graph[dinhKe].daXet && graph[dinhChon].khoangCach != INT_MAX &&
    graph[dinhChon].khoangCach + trongSo < graph[dinhKe].khoangCach) {
    graph[dinhKe].khoangCach = graph[dinhChon].khoangCach + trongSo;
    }
    }
    }
    }

    int main() {
    int soDinh, soCanh;
    cout << "Nhap so dinh va so canh cua do thi: ";
    cin >> soDinh >> soCanh;

    vector<Dinh> graph(soDinh);

    cout << "Nhap cac canh cua do thi (dinh nguon, dinh dich, trong so):\n";
    for (int i = 0; i < soCanh; i++) {
    int dinhNguon, dinhDich, trongSo;
    cin >> dinhNguon >> dinhDich >> trongSo;

    graph[dinhNguon].ke.push_back({dinhDich, trongSo});
    }

    int dinhNguon, dinhDich;


    cout << "Nhap dinh nguon va dinh dich: ";
    cin >> dinhNguon >> dinhDich;

    dijkstra(graph, dinhNguon);

    cout << "Khoang cach ngan nhat tu " << dinhNguon << " den " << dinhDich << " la:
    " << graph[dinhDich].khoangCach << endl;
    cout << "Duong di ngan nhat tu " << dinhNguon << " den " << dinhDich << " la: ";
    inDuongDi(graph, dinhNguon, dinhDich);

    return 0;
    }
    So xuat hien 2 lan
    #include <iostream>
    #include <vector>
    #include <unordered_map>
    #include <climits>

    using namespace std;

    int timSoNhoNhatHaiLan(const vector<int>& mang) {


    int n = mang.size();
    vector<int> prefixSums(n + 1, 0);
    unordered_map<int, int> viTriCuoi;

    int soNhoNhat = INT_MAX;

    for (int i = 1; i <= n; ++i) {


    prefixSums[i] = prefixSums[i - 1] + mang[i - 1];

    if (viTriCuoi.find(prefixSums[i]) != viTriCuoi.end()) {
    soNhoNhat = min(soNhoNhat, mang[viTriCuoi[prefixSums[i]]]);
    }

    viTriCuoi[prefixSums[i]] = i - 1;
    }

    return soNhoNhat;
    }

    int main() {
    int n;
    cout << "Nhap so luong phan tu cua mang: ";
    cin >> n;

    vector<int> mang(n);
    cout << "Nhap cac phan tu cua mang:\n";
    for (int i = 0; i < n; ++i) {
    cin >> mang[i];
    }

    int ketQua = timSoNhoNhatHaiLan(mang);

    if (ketQua != INT_MAX) {
    cout << "So nho nhat xuat hien it nhat hai lan la: " << ketQua << endl;
    } else {
    cout << "Khong co so nao xuat hien it nhat hai lan trong mang." << endl;
    }

    return 0;
    }

    You might also like