Trang 2 trên tổng số 2 Đầu tiênĐầu tiên 12
Từ 11 tới 16 trên tổng số 16 kết quả

Đề tài: Di chuyển giữa các thành phố

  1. #11
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Mặc định Di chuyển giữa các thành phố

    Một thắc mắc nữa. Nếu a(i) = i, có đường trực tiếp đi từ i đến i+1. Nếu a(i) = i+1, cũng có đường trực tiếp đi từ i đến i+1. Vậy khác biệt giữa hai dữ liệu là gì? Phải chăng trường hợp thứ nhất nói rằng chỉ có một đường, còn trường hợp thứ hai nói rằng có hai đường trực tiếp cùng xuất phát từ i và cùng đến i+1?
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  2. #12
    Ngày gia nhập
    11 2017
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    Một thắc mắc nữa. Nếu a(i) = i, có đường trực tiếp đi từ i đến i+1. Nếu a(i) = i+1, cũng có đường trực tiếp đi từ i đến i+1. Vậy khác biệt giữa hai dữ liệu là gì? Phải chăng trường hợp thứ nhất nói rằng chỉ có một đường, còn trường hợp thứ hai nói rằng có hai đường trực tiếp cùng xuất phát từ i và cùng đến i+1?
    Chỉ có 1 đường thôi bạn nhé, nó là TH1

  3. #13
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Bạn chưa trả lời thắc mắc của mình: khác biệt giữa hai dữ liệu này như thế nào.

    Ý bạn là cả hai dữ liệu a(i) = i và a(i) = i+1 đều hợp lệ nhưng đều mô tả cùng một cấu trúc (chỉ có 1 đường từ i đến i+1)?

    Hay ý bạn là a(i) = i là dữ liệu hợp lệ, còn a(i) = i+1 là dữ liệu bất hợp lệ? Xin bạn lưu ý rằng a(i) = i+2, i+3,... là hợp lệ.

    Dù ý bạn thế này hay thế kia, câu hỏi của mình vẫn là vì sao đề bài quy định như thế. Nếu quy định a(i) > i, nghĩa là loại trừ trường hợp a(i) = i, thì miền giá trị của dữ liệu a(i) sẽ là {i+1, i+2,..., n}, tương ứng với tập đích đến khả dĩ là các thành phố {i+1, i+2,..., n}, như thế ánh xạ dữ liệu -> cấu trúc vừa đơn điệu vừa liên tục, có phải là hợp lý hơn không?

    Thứ lỗi cho mình hỏi nhiều. Không phải mình nhiều chuyện đâu. Diễn giải đề bài bất hợp lý là dấu hiệu cho thấy có thể diễn giải sai. Khi ví dụ input và output mà bạn nêu ra không thể nào giải thích được nhất quán với đề bài thì dấu hiệu diễn giải sai càng bộc lộ rõ. Mà đề bài bị diễn giải sai, thì khó lòng nào ra cách giải đúng được.
    Đã được chỉnh sửa lần cuối bởi Ada : 05-12-2017 lúc 10:10 PM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  4. #14
    Ngày gia nhập
    11 2017
    Bài viết
    15

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    Bạn chưa trả lời thắc mắc của mình: khác biệt giữa hai dữ liệu này như thế nào.

    Ý bạn là cả hai dữ liệu a(i) = i và a(i) = i+1 đều hợp lệ nhưng đều mô tả cùng một cấu trúc (chỉ có 1 đường từ i đến i+1)?

    Hay ý bạn là a(i) = i là dữ liệu hợp lệ, còn a(i) = i+1 là dữ liệu bất hợp lệ? Xin bạn lưu ý rằng a(i) = i+2, i+3,... là hợp lệ.

    Dù ý bạn thế này hay thế kia, câu hỏi của mình vẫn là vì sao đề bài quy định như thế. Nếu quy định a(i) > i, nghĩa là loại trừ trường hợp a(i) = i, thì miền giá trị của dữ liệu a(i) sẽ là {i+1, i+2,..., n}, tương ứng với tập đích đến khả dĩ là các thành phố {i+1, i+2,..., n}, như thế ánh xạ dữ liệu -> cấu trúc vừa đơn điệu vừa liên tục, có phải là hợp lý hơn không?

    Thứ lỗi cho mình hỏi nhiều. Không phải mình nhiều chuyện đâu. Diễn giải đề bài bất hợp lý là dấu hiệu cho thấy có thể diễn giải sai. Khi ví dụ input và output mà bạn nêu ra không thể nào giải thích được nhất quán với đề bài thì dấu hiệu diễn giải sai càng bộc lộ rõ. Mà đề bài bị diễn giải sai, thì khó lòng nào ra cách giải đúng được.
    À ừ, đề bài thầy mình cho thì mình cx hiểu dc nhưng diễn giải ra thì hơi lằng nhằng.
    Đúng như bạn nói thì dữ liệu a(i) = i và a(i) = i+1 đều hợp lệ và chỉ mô tả cùng 1 cấu trúc.

  5. #15
    Ngày gia nhập
    01 2008
    Nơi ở
    Rất nhiều sóng gió
    Bài viết
    447

    Trích dẫn Nguyên bản được gửi bởi Silverbullet069 Xem bài viết
    À ừ, đề bài thầy mình cho thì mình cx hiểu dc nhưng diễn giải ra thì hơi lằng nhằng.
    Đúng như bạn nói thì dữ liệu a(i) = i và a(i) = i+1 đều hợp lệ và chỉ mô tả cùng 1 cấu trúc.
    OK. Vậy mình coi như dữ liệu rắc rối chỉ nhằm mục đích... gây rắc rối và làm code sai (nếu có) dễ bộc lộ hơn.

    Mình không hiểu cách của bạn nên không biết sai (nếu có) ở đâu. Nhưng đây là cách của mình, để bạn tham khảo.

    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. int main()
    4. {
    5.     int n;
    6.     cin >> n;
    7.     int a[n], f[n];
    8.     for(int i = 1; i < n; i++) {
    9.         cin >> a[i];
    10.     }
    11.     for(int i = n-1; i >= 1; i--) {
    12.         f[i] = i+2 <= a[i]  &&  a[i] < n ? f[a[i]] : a[i] == n ? 1 : 0;
    13.         f[i] += i+1 < n ? f[i+1] : 1;
    14.     }
    15.     cout << f[1];
    16.     return 0;
    17. }

    Ví dụ input (lấy của bạn khoaph):
    Code:
    9
     3
     2
     6
     4
     6
     9
     7
     8
    - - - Nội dung đã được cập nhật ngày 06-12-2017 lúc 06:10 PM - - -

    EDIT: code này chưa sạch lỗi. Nó ra kết quả khác với của khoaph trong một số trường hợp. Để mình kiểm tra lại đã.

    - - - Nội dung đã được cập nhật ngày 06-12-2017 lúc 06:28 PM - - -

    Thế này đúng hơn:
    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. int main()
    4. {
    5.     int n;
    6.     cin >> n;
    7.     int a[n], f[n];
    8.     for(int i = 1; i < n; i++) {
    9.         cin >> a[i];
    10.     }
    11.     for(int i = n-1; i >= 1; i--) {
    12.         f[i]  = i+1 < n ? f[i+1] : 1;
    13.         f[i] += i+2 <= a[i] ?  (a[i] < n ? f[a[i]] : a[i] == n ? 1 : 0) : 0;
    14.     }
    15.     cout << f[1];
    16.     return 0;
    17. }

    - - - Nội dung đã được cập nhật ngày 06-12-2017 lúc 10:04 PM - - -

    Công thức. Gọi f(i) là số cách đi từ thành phố i đến thành phố n. Gọi g(i) là số cách đi từ thành phố i đến thành phố n theo đường mặc định (qua thành phố i+1). Gọi h(i) là số cách đi từ thành phố i đến thành phố n theo đường tắt (qua thành phố a(i)). Cần chú ý ràng buộc i+2 <= a(i) <= n bởi vì những giá trị a(i) ngoài khoảng này không chỉ ra một đường tắt.

    Code:
    f(i) = g(i) + h(i)
    
    g(i) = f(i+1)  khi i+1 < n
    g(i) = 1       khi i+1 = n
    g(i) = 0       khi khác
    
    h(i) = f(a(i)) khi i+2 <= a(i) < n
    h(i) = 1       khi i+2 <= a(i) = n
    h(i) = 0       khi khác
    Do f(i) phụ thuộc vào f(i+1) và f(a(i)), mà i < i+1 và i < a(i), trình tự tối ưu để tính f(k) là tính mọi f(i) với i chạy từ n-1 giảm dần về k.

    Trình tự này rất giống như trình tự tính số Fibonacci.
    Đã được chỉnh sửa lần cuối bởi Ada : 07-12-2017 lúc 10:35 AM.
    -...- -.- .. .-.. .-.. - .... . -... . .- ... - .-.-.

  6. #16
    Ngày gia nhập
    11 2017
    Bài viết
    15

    Mặc định Di chuyển giữa các thành phố

    Trích dẫn Nguyên bản được gửi bởi Ada Xem bài viết
    OK. Vậy mình coi như dữ liệu rắc rối chỉ nhằm mục đích... gây rắc rối và làm code sai (nếu có) dễ bộc lộ hơn.

    Mình không hiểu cách của bạn nên không biết sai (nếu có) ở đâu. Nhưng đây là cách của mình, để bạn tham khảo.

    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. int main()
    4. {
    5.     int n;
    6.     cin >> n;
    7.     int a[n], f[n];
    8.     for(int i = 1; i < n; i++) {
    9.         cin >> a[i];
    10.     }
    11.     for(int i = n-1; i >= 1; i--) {
    12.         f[i] = i+2 <= a[i]  &&  a[i] < n ? f[a[i]] : a[i] == n ? 1 : 0;
    13.         f[i] += i+1 < n ? f[i+1] : 1;
    14.     }
    15.     cout << f[1];
    16.     return 0;
    17. }

    Ví dụ input (lấy của bạn khoaph):
    Code:
    9
     3
     2
     6
     4
     6
     9
     7
     8
    - - - Nội dung đã được cập nhật ngày 06-12-2017 lúc 06:10 PM - - -

    EDIT: code này chưa sạch lỗi. Nó ra kết quả khác với của khoaph trong một số trường hợp. Để mình kiểm tra lại đã.

    - - - Nội dung đã được cập nhật ngày 06-12-2017 lúc 06:28 PM - - -

    Thế này đúng hơn:
    C++ Code:
    1. #include <iostream>
    2. using namespace std;
    3. int main()
    4. {
    5.     int n;
    6.     cin >> n;
    7.     int a[n], f[n];
    8.     for(int i = 1; i < n; i++) {
    9.         cin >> a[i];
    10.     }
    11.     for(int i = n-1; i >= 1; i--) {
    12.         f[i]  = i+1 < n ? f[i+1] : 1;
    13.         f[i] += i+2 <= a[i] ?  (a[i] < n ? f[a[i]] : a[i] == n ? 1 : 0) : 0;
    14.     }
    15.     cout << f[1];
    16.     return 0;
    17. }

    - - - Nội dung đã được cập nhật ngày 06-12-2017 lúc 10:04 PM - - -

    Công thức. Gọi f(i) là số cách đi từ thành phố i đến thành phố n. Gọi g(i) là số cách đi từ thành phố i đến thành phố n theo đường mặc định (qua thành phố i+1). Gọi h(i) là số cách đi từ thành phố i đến thành phố n theo đường tắt (qua thành phố a(i)). Cần chú ý ràng buộc i+2 <= a(i) <= n bởi vì những giá trị a(i) ngoài khoảng này không chỉ ra một đường tắt.

    Code:
    f(i) = g(i) + h(i)
    
    g(i) = f(i+1)  khi i+1 < n
    g(i) = 1       khi i+1 = n
    g(i) = 0       khi khác
    
    h(i) = f(a(i)) khi i+2 <= a(i) < n
    h(i) = 1       khi i+2 <= a(i) = n
    h(i) = 0       khi khác
    Do f(i) phụ thuộc vào f(i+1) và f(a(i)), mà i < i+1 và i < a(i), trình tự tối ưu để tính f(k) là tính mọi f(i) với i chạy từ n-1 giảm dần về k.

    Trình tự này rất giống như trình tự tính số Fibonacci.

    Quá chuẩn luôn bạn ơi. Mình vừa ib thầy, bảo là đúng rồi. Cảm ơn bạn nhiều nhé
    Đã được chỉnh sửa lần cuối bởi Silverbullet069 : 07-12-2017 lúc 06:34 PM.

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