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 2 trên tổng số 2 kết quả

Đề tài: Thắc mắc về thuật toán sinh hoán vị có điều kiện

  1. #1
    Ngày gia nhập
    09 2020
    Bài viết
    1

    Mặc định Thắc mắc về thuật toán sinh hoán vị có điều kiện

    Bài 1: Sinh ra biểu thức ngoặc đúng thứ k:

    Biểu thức ngoặc là xâu chỉ gồm các ký tự '(' hoặc ')'. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

    Biểu thức rỗng là biểu thức ngoặc đúng;
    Nếu A là biểu thức ngoặc đúng thì (A) cũng là một biểu thức ngoặc đúng;
    Nếu A và B là hai biểu thức ngoặc đúng thì AB cũng là một biểu thức ngoặc đúng.
    Ví dụ, '()(())' là một biểu thức ngoặc đúng còn '())(()' không là một biểu thức ngoặc đúng.
    Với số nguyên dương chẵn n, người ta liệt kê theo tứ tự từ điển các biểu thức ngoặc đúng độ dài n. Ví dụ, n=6, ta có các biểu thức ngoặc được liệt kê theo thứ tự từ điển như sau:

    1. ((()))
    2. (()())
    3. (())()
    4. ()(())
    5. ()()()
    Yêu cầu: Cho số nguyên dương chẵn n và số nguyên dương k (k<2^63), hãy viết chương trình tìm biểu thức ngoặc đúng thứ k.
    Đầu vào:
    Gồm một dòng chứa 2 số nguyên n, k (n≤30000).

    Đầu ra:
    Gồm một dòng là biểu thức tìm được.

    INPUT: 10 5
    OUTPUT: (((())))()
    Bài 2:

    Nhập ba số nguyên dương M, N và K. Hãy in ra tất cả các từ độ dài M gồm các chữ cái khác nhau trong phạm vi N chữ cái Latinh tiếng Anh đầu tiên bắt đầu từ a, sao cho khoảng cách của hai
    ký tự liền kề trong từ không lớn hơn K. Lưu ý các từ cần được in tăng dần theo thứ tự từ điển.

    Đầu vào:
    Một dòng duy nhất chứa ba số nguyên dương M, N, K.

    Đầu ra:
    In ra nhiều dòng, mỗi dòng là một từ thoả mãn yêu cầu đề bài.

    Lưu ý:
    Khoảng cách của hai chữ cái là khoảng cách thứ tự của chúng trong bảng chữ cái, tính bằng cách lấy trị tuyệt đối của hiệu hai vị trí trong bảng chữ cái. Ví dụ khoảng cách của 'a' và 'c' là 2,
    khoảng cách của 'f' và 'b' là 4.

    INPUT: 2 4 1
    OUTPUT:
    aa
    ab
    ba
    bb
    bc
    cb
    cc
    cd
    dc
    dd
    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
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    506

    Trích dẫn Nguyên bản được gửi bởi caokhanhtan Xem bài viết
    Bài 1: Sinh ra biểu thức ngoặc đúng thứ k:

    Biểu thức ngoặc là xâu chỉ gồm các ký tự '(' hoặc ')'. Biểu thức ngoặc đúng và bậc của biểu thức ngoặc được định nghĩa một cách đệ qui như sau:

    Biểu thức rỗng là biểu thức ngoặc đúng;
    Nếu A là biểu thức ngoặc đúng thì (A) cũng là một biểu thức ngoặc đúng;
    Nếu A và B là hai biểu thức ngoặc đúng thì AB cũng là một biểu thức ngoặc đúng.
    Ví dụ, '()(())' là một biểu thức ngoặc đúng còn '())(()' không là một biểu thức ngoặc đúng.
    Với số nguyên dương chẵn n, người ta liệt kê theo tứ tự từ điển các biểu thức ngoặc đúng độ dài n. Ví dụ, n=6, ta có các biểu thức ngoặc được liệt kê theo thứ tự từ điển như sau:

    1. ((()))
    2. (()())
    3. (())()
    4. ()(())
    5. ()()()
    Yêu cầu: Cho số nguyên dương chẵn n và số nguyên dương k (k<2^63), hãy viết chương trình tìm biểu thức ngoặc đúng thứ k.
    Đầu vào:
    Gồm một dòng chứa 2 số nguyên n, k (n≤30000).

    Đầu ra:
    Gồm một dòng là biểu thức tìm được.

    INPUT: 10 5
    OUTPUT: (((())))()
    Bài 2:

    Nhập ba số nguyên dương M, N và K. Hãy in ra tất cả các từ độ dài M gồm các chữ cái khác nhau trong phạm vi N chữ cái Latinh tiếng Anh đầu tiên bắt đầu từ a, sao cho khoảng cách của hai
    ký tự liền kề trong từ không lớn hơn K. Lưu ý các từ cần được in tăng dần theo thứ tự từ điển.

    Đầu vào:
    Một dòng duy nhất chứa ba số nguyên dương M, N, K.

    Đầu ra:
    In ra nhiều dòng, mỗi dòng là một từ thoả mãn yêu cầu đề bài.

    Lưu ý:
    Khoảng cách của hai chữ cái là khoảng cách thứ tự của chúng trong bảng chữ cái, tính bằng cách lấy trị tuyệt đối của hiệu hai vị trí trong bảng chữ cái. Ví dụ khoảng cách của 'a' và 'c' là 2,
    khoảng cách của 'f' và 'b' là 4.

    INPUT: 2 4 1
    OUTPUT:
    aa
    ab
    ba
    bb
    bc
    cb
    cc
    cd
    dc
    dd
    Code dưới đây liệt kê tất cả các biểu thức ngoặc đúng
    C++ Code:
    1. #include <string>
    2. #include <iostream>
    3. using namespace std;
    4.  
    5. namespace BieuThucNgoac
    6. {
    7.     int n;
    8.     int k;
    9.     int open;
    10.     int op;
    11.     int cls;
    12.     string bieuthuc;
    13.     void input()
    14.     {
    15.         cin >> n >> k;
    16.         open = n / 2;
    17.         bieuthuc = "";
    18.         for (int i = 0; i < n; i++) {
    19.             bieuthuc += " ";
    20.         }
    21.         op = 0;
    22.         cls = 0;
    23.     }
    24.     void setBracket(int i)
    25.     {
    26.         if (i >= n) {
    27.             cout << bieuthuc << "\n";
    28.             return;
    29.         }
    30.         if (op < open) {
    31.             op++;
    32.             bieuthuc[i] = '(';
    33.             setBracket(i+1);
    34.             op--;
    35.         }
    36.         if (cls < op) {
    37.             cls++;
    38.             bieuthuc[i] = ')';
    39.             setBracket(i+1);
    40.             cls--;
    41.         }
    42.     }
    43. }
    44. int main(int argc, char *argv[])
    45. {
    46.     BieuThucNgoac::input();
    47.     BieuThucNgoac::setBracket(0);
    48. }
    49. /*
    50. 10 5
    51. ((((()))))
    52. (((()())))
    53. (((())()))
    54. (((()))())
    55. (((())))()
    56. ((()(())))
    57. ((()()()))
    58. ((()())())
    59. ((()()))()
    60. ((())(()))
    61. ((())()())
    62. ((())())()
    63. ((()))(())
    64. ((()))()()
    65. (()((())))
    66. (()(()()))
    67. (()(())())
    68. (()(()))()
    69. (()()(()))
    70. (()()()())
    71. (()()())()
    72. (()())(())
    73. (()())()()
    74. (())((()))
    75. (())(()())
    76. (())(())()
    77. (())()(())
    78. (())()()()
    79. ()(((())))
    80. ()((()()))
    81. ()((())())
    82. ()((()))()
    83. ()(()(()))
    84. ()(()()())
    85. ()(()())()
    86. ()(())(())
    87. ()(())()()
    88. ()()((()))
    89. ()()(()())
    90. ()()(())()
    91. ()()()(())
    92. ()()()()()
    93.  
    94. [Program finished]*/
    Còn xuất ra b th thứ k là dành cho bạ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