Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Lập trình C | Bài toán liệt kê | Liệt kê tất cả các dãy có độ dài n và độ sâu k??

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

    Mặc định Lập trình C | Bài toán liệt kê | Liệt kê tất cả các dãy có độ dài n và độ sâu k??

    gọi độ sâu của cặp dấu ngoặc () là 1. nếu một dãy dấu ngoặc độ sâu k nằm trực tiếp trong cặp dấu ngoặc (...) thì độ sâu của cặp dấu ngoặc này là k+1. một dãy dấu ngoặc có độ sâu bằng độ sâu max của tất cả các cặp dấu ngoặc chứa trong dãy đó.
    độ dài của một dãy dấu ngoặc là tổng số tất cả cặp dấu ngoặc có trong dãy đó.
    vd : dãy dấu ngoặc :
    ()((()())())()()
    có độ dài là 8, độ sâu là 3.
    bài toán đặt ra là cho trước 2 số nguyên dương n và k, hãy liệt kê tất cả các dãy có độ dài n và độ sâu k.

  2. #2
    Ngày gia nhập
    02 2009
    Nơi ở
    105 Lô P c/c ngô gia tự P.02 Q.10 TP.hcm
    Bài viết
    37

    tôi cho ban thuat toán bạn tự làm nhé
    như sao :mình xư lý dấu () thay 1 0
    nghĩa là "("là 1 ")" là 0;>>> lạp môt cái mãng chạy tư A[0]>>A[n*2-1]chi có sô 0 và 1 VD:n=3()()() thành 101010;hoạc có thể cho là ((())) thánh 111000 vây bạn đã chuyển sang con số để bài toán đơ giản
    còn đọ sâu : mơi vô độ sâu là d=1; ta có phép tính ktra độ S như sao
    cho chay for(i=1>>i=n*2) if(A[i-1]==A[i]==1) thi cho d++;
    d=k thì kiêm tra dúng cho return 1;else return 0;bạn thử làm nháp là hiểu ra à..
    còn ván đề nhap dấu : vd: )()()( vạy là phạm luật vạy bạn lap 1 int de kt; nếu không hiêu coi code o dưới nhé chỉ là code rợi ý
    Đã được chỉnh sửa lần cuối bởi Phamvanla19 : 10-05-2009 lúc 03:16 PM. Lý do: :D

  3. #3
    Ngày gia nhập
    02 2009
    Nơi ở
    105 Lô P c/c ngô gia tự P.02 Q.10 TP.hcm
    Bài viết
    37

    code : nè
    C Code:
    1. void in(int A[],int n)
    2. {
    3.     for(int i=0;i<n*2;i++)
    4.     {
    5.         if(A[i]==1)
    6.             cout<<"(";
    7.         else
    8.             cout<<")";
    9.     }
    10. }
    11. int dkquydinh(int A[],int n)
    12. {
    13.     int d=1;int so1=0;int so0=0;
    14.     for(int i=0;i<=n;i++)
    15.     {
    16.         if(A[i]==1)
    17.             so1++;
    18.         else
    19.             so0++;
    20.         if(so1<so0)
    21.         {
    22.             d=0;
    23.             break;
    24.         }
    25.     }
    26.     return d;
    27. }
    28. int doSauK(int A[],int n,int k)
    29. {
    30.     int dk=1;
    31.     for(int i=1;i<n*2-1;i++)
    32.     {
    33.         if(A[i-1]==1&&A[i]==1)
    34.             dk++;
    35.     }
    36.     if(dk==k)
    37.         return 1;
    38.     return 0;
    39. }

  4. #4
    Ngày gia nhập
    03 2009
    Bài viết
    5

    cái đó của bạn chỉ là kiểm tra nó hợp lệ ko thôi, còn việc liệt kê nó ra thì chả lẽ bạn cho nó sinh dãy nhị phân độ dài n phần tử rồi mỗi một cái bạn kiễm tra nó 1 lần hả, chuong trình chạy chậm lắm đấy =.=. Có cách nào tối ưu ko ?

  5. #5
    Ngày gia nhập
    03 2009
    Nơi ở
    Hà Nội
    Bài viết
    74

    bạn thử dùng đệ quy quy lui xem. với mỗi bước đi, bạn cập nhật luôn các giá trị,và thực hiện thêm các so sánh để đánh giá xem bước chạy đó có thể có kết quả không.nếu số bậc max có thể đạt được nhỏ hơn m thì quay lại,>=m thì cho chạy tiếp hoặc là bac_max==m cũng cho chạy tiếp.nếu bạn vẫn kho làm được thì mình sẽ post bài của mình lên

    http://ebook.here.vn
    trang web cung cấp đề thi,tài liệu ôn thi đại học.

  6. #6
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Mặc định Lập trình C | Bài toán liệt kê | Liệt kê tất cả các dãy có độ dài n và độ sâu k??

    Code:
    ()((()())())()()
    Ko cần đệ quy gì hết cũng ko cần phải xét gì cả, vì đây là dãy các dấu ngoặc liên tục nên chỉ cần đếm số dấu ngoặc mở liên tục nhiều nhất là xong.

  7. #7
    Ngày gia nhập
    03 2009
    Nơi ở
    Hà Nội
    Bài viết
    74

    bạn hiểu sai vấn đề rồi,bài toán là liệt kê tất cả các chuỗi có độ dài n và độ sâu m mà.bạn làm như vậy là kiểm tra độ sâu thôi.nhưng cách như vậy là chưa đúng.
    VD: ((()(())()))
    nếu làm như bạn thì có độ sau bằng 3 à.
    nhưng thực ra là bằng 4 cơ:
    ((()(())()))

    http://ebook.here.vn
    trang web cung cấp đề thi,tài liệu ôn thi đại học.

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