Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Tách chuỗi số giảm dần trong một chuỗi lớn, thuật toán xử lý như thế nào?

  1. #1
    Ngày gia nhập
    11 2007
    Bài viết
    32

    Unhappy Tách chuỗi số giảm dần trong một chuỗi lớn, thuật toán xử lý như thế nào?

    bai này em làm luc dung lúc sai, hic , xin cac Anh chi cho em 1 thuật toán tốt đi a:
    Vd: nhap la : 98765432123456789 --> xuat ra so giam dan (hoac bằng) mà lớn nhất --> KQ là: 987654322
    nhap la: 38885685685675683221 --> KQ la:8888883221
    nhap la: 67347479322 --> KQ xua la: 777322
    Em xin cam on

  2. #2
    Ngày gia nhập
    01 2009
    Nơi ở
    Hà Nội
    Bài viết
    205

    Chuyển về xâu đi bạn rồi dùng hàm so sánh trong xâu( hoặc có thể biến tấu đi 1 chút cho phù hợp bài toán).
    Thế nhé!

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    32

    Trích dẫn Nguyên bản được gửi bởi trubavuong Xem bài viết
    Chuyển về xâu đi bạn rồi dùng hàm so sánh trong xâu( hoặc có thể biến tấu đi 1 chút cho phù hợp bài toán).
    Thế nhé!
    trời? bác trả lời huề trớt????
    AI lại dùng kiểu số để chứa cái này?
    chi xau hay mảng, ai ma khong biet?
    quan trọng là THUAT TOAN xuli ra sao co mà?
    Bac Spam qua ??
    Đã được chỉnh sửa lần cuối bởi longtom : 16-02-2009 lúc 02:31 PM.

  4. #4
    Ngày gia nhập
    02 2008
    Nơi ở
    Việt Nam
    Bài viết
    577

    Vd: nhap la : 98765432123456789 --> xuat ra so giam dan (hoac bằng) mà lớn nhất --> KQ là: 987654322
    nhap la: 38885685685675683221 --> KQ la:8888883221
    nhap la: 67347479322 --> KQ xua la: 777322
    Bài tập của bạn khá hay, sẽ có một khoanh vùng cho bài như này, bất kì chuỗi nào bạn tìm được mà nó thỏa mãn điều kiện không tăng đó, có độ dài > 1/2 chuỗi ban đầu thì nó là chuỗi lớn nhất cần tìm.

    Chuỗi tìm được trong lần xét trước dài nhất là a, thì từ vị trí n-a đến n-1 không cần xét nữa.

    Có vỉ đó là những điều rất đơn giản, dễ dang nhận ra, nhưng bài này Hoàng nghĩ là chắc sẽ xét tuần tự để tìm từng chuỗi, và sẽ giảm được khá nhiều khi loại đi các TH đó.

    Việc xét tuần tự cũng không cần phải bắt đầu lại với số nhỏ hơn số lớn nhất đã xét.

    Mình sẽ thử code nó cẩn thận xem sao.

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Bài này dùng quy hoạch động, nó y chang bài trong sách của thầy Hoàng chương III về Quy Hoạch Động, cậu tìm sách đó đọc sẽ hiểu ! Dùng đệ qui bài này thì sẽ rất khủng !!

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

    Mặc định Tách chuỗi số giảm dần trong một chuỗi lớn, thuật toán xử lý như thế nào?

    oh, theo lời khuyên của ROOK thì mình cũng ráng suu tam nhung mà khó hiểu quá, với lại BT QHĐ là mảng a nguyên (-32N...+32N) trong khi bài nỳ là các giá trị chỉ từ 0...9 ?
    Nếu lấy QHD sẽ = "lấy dao mổ trâu đem đi giết gà"?
    hic mình muốn có 1 ThuatToan tốt, de hieu hon QHD cơ...
    CÁc bác ơi.....

  7. #7
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Nếu lấy QHD sẽ = "lấy dao mổ trâu đem đi giết gà"?
    Nếu cậu đọc kĩ thì cậu sẽ thấy QHD là phương nhanh nhất để giải bài này O( n^2 ).
    Giả nếu dãy số của cậu có n phần tử vậy tui hỏi cậu có bao nhiêu dãy con ?
    Câu trả lời là : 2^n
    Còn thuật toán thì chẳng có bài nào đọc vào là hiểu ngay cả, cậu phải mày mò, đọc tới đọc lui, thuật toán không phải cú pháp mà đọc vào là hiểu ngay được cậu à !
    Bài này nếu là dãy liên tục thì sẽ giải rất dễ, 1 vòng for là ra ngay nhưng cái khó là dãy không cần liên tục, cậu đọc lại cho kĩ đi.
    hic mình muốn có 1 ThuatToan tốt, de hieu hon QHD cơ...
    Trong thuật toán bước tiếp cận đầu tiên là phải làm cho ra, có được cách giải là cậu nên mừng hết lớn mới phải, cậu cứ đi tìm cái vừa dễ trong khi cậu chưa có 1 suy nghĩ gì về nó thì lấy gì mà ra ? Cơ sở nào để cậu nói rằng sẽ tồn tại 1 thuật toán nhanh gọn hơn trong khi cậu chưa hiểu không gian và thời gian của dữ liệu ?

  8. #8
    Ngày gia nhập
    11 2007
    Bài viết
    32

    Trích dẫn Nguyên bản được gửi bởi rox_rook Xem bài viết
    Trong thuật toán bước tiếp cận đầu tiên là phải làm cho ra, có được cách giải là cậu nên mừng hết lớn mới phải, cậu cứ đi tìm cái vừa dễ trong khi cậu chưa có 1 suy nghĩ gì về nó thì lấy gì mà ra ? Cơ sở nào để cậu nói rằng sẽ tồn tại 1 thuật toán nhanh gọn hơn trong khi cậu chưa hiểu không gian và thời gian của dữ liệu ?
    hic bác nói nghe căng thẳng quá...
    em xin có 1 hướng giải như sau: (vì chưa biết cách quay lui nên bị bí "ngang hông" nè)...
    lấy s[1] làm mốc xét các s[i] mà thỏa thì ghép vào --> suy ra dc cai mảng .
    VD: s=71650732
    thì sẽ lấy dc cái mảng như sau:
    7
    71
    710
    đến đây không thể lấy tiếp nên sẽ quay lên
    76
    765
    7650
    không thê di tltếp nên quay lên
    7653
    76532
    .....
    --> KQ cuoi cung la:76532

  9. #9
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    - Trường hợp cậu xét chỉ là 1 trong các trường hợp thôi. Ví dụ
    7 9 8 3 2 1
    Thì làm sao nhận S[ 0 ] làm mốc được( chú ý mãng trong C/C++ bắt đầu từ 0 không phải 1 như pascal ).
    -> dãy giảm 7 3 2 1 có độ dài ngắn hơn dãy 9 8 3 2 1.
    Vì vậy cậu bắt buộc phải duyệt đệ qui cho tất cả các dãy. Mà tổng số dãy là 2^n - 1.
    Xét abc : thì các dãy là :
    a__
    _b_
    __c
    ab_
    _bc
    a_c
    abc
    Và cậu phải xét tất cả những thằng này, nếu có tối ưu thì cậu dùng nhánh cận để cắt bớt nhánh thế thôi.
    Suy nghĩ cách của cậu thì tui mới nghiệm ra là có 1 cách khác ! Không biết có nhanh hơn thuật toán của thầy Hoàng không( linh cảm là không T_T ).
    Ý tưởng là sinh các chỉnh hợp không lặp chập K với N phần tử và chú ý là bắt đầu từ chập lớn nhất N - 1, và tay sẽ kiểm tra tính không tăng của dãy này :
    - Nếu nó không tăng thì đây chính là dãy có độ dài tối ưu vì ta xét các chập theo thứ tự giảm dần. Nhưng nói chung trong trường hợp tệ nhất thì có lẽ kết quả cũng sẽ là rất tệ. Cách này hiện giờ tui vẫn chưa suy nghĩ ra, ý tưởng là thế có gì tui sẽ suy nghĩ tiếp.
    - Còn cách này cũng dựa trên ý tưởng trên, kiểm tra các chặp tuy vậy cách sinh này lại đi không theo 1 thứ tự nào cả, nên nói chung nó vẫn còn rất chậm. Cách QHD ghép chuỗi của thầy Hoàng có lẽ là tối ưu rùi, cậu nên đọc kĩ lại cách đó trước đi đã.
    - Tui post cách này lên cho cậu tham khảo, tui quen dùng stl nên có chỗ nào không hiểu thì tui sẽ giải thích.
    Java Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <iterator>
    4. #include <algorithm>
    5. #include <climits>
    6.  
    7. using namespace std;
    8.  
    9. enum series_value {
    10.  
    11.     INCREASING,
    12.     NON_INCREASING
    13.  
    14. };
    15.  
    16. series_value is_nonincreasing( const vector< int >& series ) {
    17.  
    18.     int len = series.size();
    19.     for( int o = 0; o < len - 1; ++o ) {
    20.         if( series[ o ] < series[ o + 1 ] )
    21.             return INCREASING;
    22.     }
    23.  
    24.     return NON_INCREASING;
    25.  
    26. }
    27.  
    28. void print_result( const vector< int >& result ) {
    29.  
    30.     cout << "Maximum non-increasing sub series of length " << result.size() << endl;
    31.     copy( result.begin(), result.end(), std::ostream_iterator< int >( cout, ", " ) );
    32.  
    33. }
    34.  
    35.  
    36. vector< int > find_longest_nonincreasing_series( const vector< int >& series ) {
    37.  
    38.     int N = series.size();
    39.     vector< int > tmp( N, INT_MAX );
    40.  
    41.     int position;
    42.     int max_length = 0;
    43.     vector< int > result;
    44.     vector< int > best_result;
    45.  
    46.     do {
    47.  
    48.         for( int o = 0; o < N; ++o ) {
    49.             if( tmp[ o ] != INT_MAX ) {
    50.                 result.push_back( tmp[ o ] );
    51.             }
    52.         }
    53.  
    54.         if( ( is_nonincreasing( result ) == NON_INCREASING ) && result.size() > max_length ) {
    55.             max_length = result.size();
    56.             best_result = result;
    57.         }
    58.  
    59.         result.clear();
    60.  
    61.         position = N - 1;
    62.  
    63.         while( position >= 0 && tmp[ position ] != INT_MAX )
    64.             --position;
    65.  
    66.  
    67.         if( position >= 0 ) {
    68.             tmp[ position ] = series[ position ] ;
    69.  
    70.             for( int marked_at = position + 1; marked_at < N; ++marked_at )
    71.                 tmp[ marked_at ] = INT_MAX;
    72.  
    73.         }
    74.  
    75.     } while( position >= 0 );
    76.  
    77.     return best_result;
    78.  
    79. }
    80.  
    81. int main() {
    82.  
    83.     vector< int > series;
    84.  
    85.     series.push_back( 7 );
    86.     series.push_back( 1 );
    87.     series.push_back( 6 );
    88.     series.push_back( 5 );
    89.     series.push_back( 0 );
    90.     series.push_back( 7 );
    91.     series.push_back( 3 );
    92.     series.push_back( 2 );
    93.  
    94.     series = find_longest_nonincreasing_series( series );
    95.     print_result( series );
    96.  
    97.     return 0;
    98.  
    99. }

  10. #10
    Ngày gia nhập
    11 2007
    Bài viết
    32

    hic STD ...em mù luôn.... ( C/C++ for dos) là em có thể còn xem dc chút chút mà sao bác ROOK viết em có thấy bác QUAI LUI đâu?
    mà khó hiểu quá, đúng là fong cách ROOK ... và Rook , twist, ruhmba, tango, walt, boston, .....

Các đề tài tương tự

  1. Lập trình C Thay thế chuỗi s1 trong chuỗi s bằng chuỗi s
    Gửi bởi duytue trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 23-09-2011, 04:16 PM
  2. thay thế chuỗi con thứ i trong chuỗi mẹ bằng 1 chuỗi khác
    Gửi bởi nhat1811 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 06-08-2011, 08:25 AM
  3. Trả lời: 1
    Bài viết cuối: 29-06-2011, 12:02 AM
  4. Thuật toán băm 1 chuỗi trong C như thế nào!
    Gửi bởi bachhaiduong trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 3
    Bài viết cuối: 11-11-2010, 09:30 PM
  5. Nhập chuỗi, đếm số lần xuất hiện các từ trong chuỗi như thế nào?
    Gửi bởi VizDee trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 7
    Bài viết cuối: 23-01-2010, 01:33 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