Công cụ bảo vệ mã nguồn .NET mạnh nhất, không thể unpack, miễn phí cho các khách hàng đầu tiên đăng ký.
Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: thắc mắc thuật toán trộn mảng

  1. #1
    Ngày gia nhập
    03 2015
    Bài viết
    16

    Mặc định thắc mắc thuật toán trộn mảng

    Trước hết mình tóm tắt lại thuật toán trộn một mảng a cho trước theo cách "ngây tơ" nhất có thể

    Input: an array A
    Output: a shuffled copy of A
    NAIVESHUFFLE(A)
    1 n ← length(A)
    1 for i ← 1 to n do C[i] ← 0// mang c để đánh đấu những phần tử chưa được chọn
    2 for i ← 1 to n do
    3 do
    4 j ←RANDOM(1, n)
    5 until C[j] = 0 // lặp lại cho đến khi chọn được chỉ số chưa xuất hiện
    6 C[j] ← 1
    7 B[i] ← A[j]
    8 return B

    Mình có thắc mắc là có người nói thuật toán này có thể không có kết thúc, theo mình nghĩ khi tiệm cận n, và n đủ lớn thì xs chọn được chỉ số j rất thấp có thể coi là 0 là nguyên nhân khiến cho ct bị treo , mình giải thích thế có đúng không nhỉ mọi người bổ sung, góp ý giúp mình với, thank.
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

  2. #2
    Ngày gia nhập
    01 2013
    Bài viết
    1,479

    ^ Rủi ro nằm ở chỗ đó.
    Đã được chỉnh sửa lần cuối bởi prog10 : 05-05-2016 lúc 12:41 PM.

  3. #3
    Ngày gia nhập
    01 2013
    Nơi ở
    Học viện Kỹ thuật Quân Sự
    Bài viết
    247

    Đúng vậy. Làm vậy thuật toán gần như chạy mãi không dừng, nếu n đủ lớn.
    Để trộn mảng, bạn làm như sau:
    Giả sử ta có mảng arr có kích thước n.
    - Khởi tạo các giá trị của mảng arr.
    - Chọn ngẫu nhiên số idx trong đoạn [0, n-1]. Đổi vị trí của a[idx] và a[n-1]. (đưa a[i] về cuối)
    - Chọn ngẫu nhiên số idx trong đoạn [0, n-2]. Đổi vị trí của a[idx] và a[n-2].
    - Chọn ngẫu nhiên số idx trong đoạn [0, n-3]. Đổi vị trí của a[idx] và a[n-3].
    ....
    - Thuật toán kết thúc khi lặp n-1 lần.
    C Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <time.h>
    4. #define SIZE 10
    5. int main()
    6. {
    7.     srand(time(0));
    8.     int i, tmp, idx;
    9.     int arr[SIZE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    10.     printf("Before: ");
    11.     for (i = 0; i < SIZE; i++)
    12.     {
    13.         printf("%d ", arr[i]);
    14.     }
    15.    
    16.     for (i = 0; i < SIZE-1; i++)
    17.     {
    18.         idx = rand() % (SIZE-i);
    19.         tmp = arr[idx];
    20.         arr[idx] = arr[SIZE-1-i];
    21.         arr[SIZE-1-i] = tmp;
    22.     }
    23.     printf("\nAfter:  ");
    24.     for (i = 0; i < SIZE; i++)
    25.     {
    26.         printf("%d ", arr[i]);
    27.     }
    28.    
    29.     return 0;
    30. }

    Click vào hình ảnh để lấy hình ảnh lớn

Tên:		1.JPG
Lần xem:	0
Size:		20.8 KB
ID:		47286Click vào hình ảnh để lấy hình ảnh lớn

Tên:		2.JPG
Lần xem:	0
Size:		21.2 KB
ID:		47287
    Đã được chỉnh sửa lần cuối bởi bachgist : 13-05-2016 lúc 11:46 AM.
    Nếu cần giúp đỡ, hỗ trợ:
    Bài Tập. Đồ Án. Tools. Phần mềm. Liên hệ:
    Facebook: http://www.facebook.com/thuecodedoan
    Website: https://thuecodedoan.wordpress.com
    Email: thuecodedoan@gmail.com
    Sđt: 094.76.76.854

  4. #4
    Ngày gia nhập
    07 2016
    Nơi ở
    Hà Nội
    Bài viết
    218

    Trích dẫn Nguyên bản được gửi bởi QuangTrung93 Xem bài viết
    Trước hết mình tóm tắt lại thuật toán trộn một mảng a cho trước theo cách "ngây tơ" nhất có thể

    Input: an array A
    Output: a shuffled copy of A
    NAIVESHUFFLE(A)
    1 n ← length(A)
    1 for i ← 1 to n do C[i] ← 0// mang c để đánh đấu những phần tử chưa được chọn
    2 for i ← 1 to n do
    3 do
    4 j ←RANDOM(1, n)
    5 until C[j] = 0 // lặp lại cho đến khi chọn được chỉ số chưa xuất hiện
    6 C[j] ← 1
    7 B[i] ← A[j]
    8 return B

    Mình có thắc mắc là có người nói thuật toán này có thể không có kết thúc, theo mình nghĩ khi tiệm cận n, và n đủ lớn thì xs chọn được chỉ số j rất thấp có thể coi là 0 là nguyên nhân khiến cho ct bị treo , mình giải thích thế có đúng không nhỉ mọi người bổ sung, góp ý giúp mình với, thank.
    Đúng rồi thế thì phải thắt chặt lại chỗ random nếu khi giảm thì cũng giảm khoảng random lại để tránh cho bài toán rơi vào vòng lặp vô hạn
    Công cụ bảo vệ mã nguồn .NET mạnh nhất hiện tại, miễn phí cho các khách hàng đầu tiên đăng ký.

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn