1 Câu hỏi: Bắt lỗi phân đoạn của hoàng tử: 11 số 11 khi tìm thấy số lần đảo ngược bằng cách sử dụng phép hợp nhất trong C ++

câu hỏi được tạo ra tại Wed, May 8, 2019 12:00 AM

Tôi đang viết chương trình C ++ tìm thấy số lượng nghịch đảo trong một vectơ bằng cách sử dụng sắp xếp hợp nhất. Một sự đảo ngược xảy ra khi phần tử i'th lớn hơn phần tử j'th, trong đó i < j. Ví dụ: vectơ là { 1, 3, 5, 2 }, sau đó có 2 phần tử là {3,2} Hàm {5,2} tiếp tục đệ quy và phân chia vectơ cho đến khi chiều dài của bộ con chỉ là một phần tử. Hàm countNsort thực hiện sắp xếp hợp nhất để sắp xếp và đếm số lần đảo.

Tôi đã thử:

  1. Các cách khác nhau để khởi tạo vectơ đầu vào. countNsortSplit, vector<int> a{2,1};vector<int> a; a={2,1};.
  2. Các cách khác nhau để phân tách vectơ đầu vào thành các phần tử con. vector<int> a(2); a={2,1};vector<int> c(a.begin()+half, a.begin()+n);, trong đó n là kích thước của vectơ.
  3. Các IDE khác nhau. Các nguyên tử mang lại cho tôi cái này: vector<int> c(a.begin()+half, a.end());, CodeBlocks cho tôi cái này: bash: line 1: 13763 Segmentation fault: 11 /tmp/cpp.out [Finished in 20.57s] cho dòng này: error: expected expression.
a={2,1}:     
1
  1. Thông tin bổ sung: Sự đảo ngược xảy ra khi phần tử thứ i lớn hơn phần tử thứ j, trong đó i < j. Ví dụ: giả sử vectơ là {1,3,5,2}, sau đó có 2 nghịch đảo: {3,2} và {5,2}. Hàm CountNsort tiếp tục đệ quy và chia vectơ cho đến khi độ dài của bộ con chỉ là một phần tử. Hàm CountNsortSplit thực hiện sắp xếp hợp nhất để sắp xếp và đếm số lượng nghịch đảo.
    2019-05-08 15: 59: 17Z
  2. Bạn đang gọi hành vi không xác định tại đây
    #include <stdio.h>
    #include <vector>
    #include <iostream>
    
    using namespace std;
    
    struct returnVal {
        int count;
        vector<int> sorted_array;
    };
    
    returnVal countNsortSplit(vector<int> left, vector<int> right, int n) {
        returnVal output;
        int count = 0;
        vector<int> merge;
        int i = 0;
        int j = 0;
        for (int k = 0; k < n; k++) {
            if (left[i] < right[j]) {
                merge[k] = left[i];
                i++;
            } else {
                merge[k] = right[j];
                j++;
                // increment count by the # of remaining elements in left
                count += left.size()-i;
            }
        }
        output.sorted_array = merge;
        output.count = count;
        return output;
    }
    
    returnVal countNsort(vector<int> a, int n) {
        returnVal output;
        if (n == 1) {
            output.sorted_array = a;
            output.count = 0;
            return output;
        } else {
            returnVal left;
            returnVal right;
            returnVal split;
            int half = n / 2;
            vector<int> b(a.begin(), a.begin() + half);
            vector<int> c(a.begin() + half, a.begin() + n);
            left = countNsort(b, half);
            right = countNsort(c, n - half); // need n-n/2 in case of odd length
            split = countNsortSplit(left.sorted_array, right.sorted_array, n);
            output.sorted_array = split.sorted_array;
            output.count = left.count + right.count + split.count;
            return output;
        }
    }
    
    int main() {
        vector<int> a(2);
        //a = {1,3,5,2};
        //a = {1,3,5,2,4,6};
        a = {2, 1};
        returnVal result;
        result = countNsort(a, a.size());
        cout << result.count << endl;
    }
    
    trước tiên bạn phải thay đổi kích thước vectơ trước khi bạn có thể truy cập nó bằng toán tử lập chỉ mục. Cũng đừng đưa thêm thông tin vào bình luận. Bạn luôn có thể chỉnh sửa câu hỏi của bạn.
    2019-05-08 16: 01: 45Z
  3. Gợi ý: A merge[k] có kích thước bằng 0 khi khởi tạo. Để thêm các yếu tố: std::vector hoặc push_back. Đối với kích thước cố định: emplace_back.
    2019-05-08 16: 22: 22Z
  4. Đề xuất chạy các chương trình như vậy với asan hoặc valgrind. Đôi khi họ bắt gặp vấn đề sớm hơn nhiều, trước khi segfault thực sự xuất hiện. YMMV
    2019-05-08 16: 26: 17Z
1 Câu trả lời                              1                         

Có nhiều vấn đề trong mã của bạn:

  • Bạn không xác định vectơ đích với kích thước phù hợp
  • Bạn không kiểm tra xem các vectơ std::array hoặc i có đạt kích thước của vectơ jleft không.
  • Trình khởi tạo cho vectơ right trong a có cú pháp không hợp lệ.

Lưu ý rằng bạn không cần chuyển các kích thước vectơ thành main()countNsort.

Đây là phiên bản đã sửa:

countNsortSplit Tuy nhiên,

Lưu ý rằng sẽ hiệu quả hơn và thành ngữ hơn khi sắp xếp vectơ tại chỗ và trả về số lượng đảo ngược:

#include <iostream>
#include <vector>

using namespace std;

struct returnVal {
    int count;
    vector<int> sorted_array;
};

returnVal countNsortMerge(vector<int> left, vector<int> right) {
    int leftSize = left.size();
    int rightSize = right.size();
    int n = leftSize + rightSize;
    int count = 0;
    vector<int> merge(n);
    int i = 0;
    int j = 0;
    for (int k = 0; k < n; k++) {
        if (i < leftSize && (j == rightSize || left[i] < right[j])) {
            merge[k] = left[i++];
        } else {
            merge[k] = right[j++];
            // increment count by the # of remaining elements in left
            count += leftSize - i;
        }
    }
    returnVal output;
    output.sorted_array = merge;
    output.count = count;
    return output;
}

returnVal countNsort(vector<int> a) {
    int n = a.size();
    if (n <= 1) {
        returnVal output;
        output.sorted_array = a;
        output.count = 0;
        return output;
    } else {
        int half = n / 2;
        vector<int> b(a.begin(), a.begin() + half);
        vector<int> c(a.begin() + half, a.begin() + n);
        returnVal left = countNsort(b);
        returnVal right = countNsort(c);
        returnVal result = countNsortMerge(left.sorted_array, right.sorted_array);
        result.count += left.count + right.count;
        return result;
    }
}

int main() {
    //int values[] = { 1, 3, 5, 2 };
    //int values[] = { 2, 1 };
    int values[] = { 1, 3, 5, 2, 4, 6 };
    vector<int> a(values, values + sizeof values / sizeof *values);
    returnVal result = countNsort(a);
    cout << result.count << endl;
    return 0;
}
    
1
2019-05-08 18: 05: 21Z
#include <iostream>
#include <vector>

size_t countNsortMerge(std::vector<int>& a, size_t start, size_t middle, size_t end) {
    std::vector<int> temp(a.begin() + start, a.begin() + middle);
    size_t i = 0;
    size_t leftSize = middle - start;
    size_t j = middle;
    size_t count = 0;
    for (size_t k = start; k < end; k++) {
        if (i < leftSize && (j == end || temp[i] < a[j])) {
            a[k] = temp[i++];
        } else {
            a[k] = a[j++];
            // increment count by the # of remaining elements in left
            count += leftSize - i;
        }
    }
    return count;
}

size_t countNsort(std::vector<int>& a, size_t start, size_t end) {
    if (end - start <= 1) {
        return 0;
    } else {
        size_t middle = start + (end - start) / 2;
        size_t leftCount = countNsort(a, start, middle);
        size_t rightCount = countNsort(a, middle, end);
        return leftCount + rightCount + countNsortMerge(a, start, middle, end);
    }
}

int main() {
    //int values[] = { 1, 3, 5, 2 };
    //int values[] = { 2, 1 };
    int values[] = { 1, 3, 5, 2, 4, 6 };
    std::vector<int> a(values, values + sizeof values / sizeof *values);
    size_t result = countNsort(a, 0, a.size());
    std::cout << result << std::endl;
    return 0;
}
nguồn đặt đây