Trang 1 trên tổng số 3 123 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 29 kết quả

Đề tài: Cách sử dụng list trong việc tách 1 dãy số thành nhiều dãy con

  1. #1
    Ngày gia nhập
    12 2010
    Bài viết
    23

    Angry Cách sử dụng list trong việc tách 1 dãy số thành nhiều dãy con

    Các pro làm giúp mình bài này với:
    Cho dãy số gồm n số nguyên duơng(n<20000) sắp xếp các số trên theo thứ tự ưu tiên sau: Trước hết là các số nguyên tố sau đó là các số chính phương và cuối cùng là là các số còn lại, nếu cùng loại số thì số nhỏ xếp trước.
    VD: 3 9 4 5 2 12 13 16
    Dãy sắp xếp: 2 3 5 13 4 9 16 12

    Theo mình ý tưởng viết bài này là chia dãy số thành 3 dãy con, sắp xếp 3 dãy đó rồi ghép các dãy số đã sắp xếp thành dãy số cần tìm, nhưng mà mình viết mãi ko ra, mình đang cần gấp, mong mọi người vào cho mình đoạn code để mình tham khảo nhé.

  2. #2
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi thangsoncp Xem bài viết
    Các pro làm giúp mình bài này với:
    Cho dãy số gồm n số nguyên duơng(n<20000) sắp xếp các số trên theo thứ tự ưu tiên sau: Trước hết là các số nguyên tố sau đó là các số chính phương và cuối cùng là là các số còn lại, nếu cùng loại số thì số nhỏ xếp trước.
    VD: 3 9 4 5 2 12 13 16
    Dãy sắp xếp: 2 3 5 13 4 9 16 12

    Theo mình ý tưởng viết bài này là chia dãy số thành 3 dãy con, sắp xếp 3 dãy đó rồi ghép các dãy số đã sắp xếp thành dãy số cần tìm, nhưng mà mình viết mãi ko ra, mình đang cần gấp, mong mọi người vào cho mình đoạn code để mình tham khảo nhé.
    Cách của bạn hơi lãng phí quá Bạn hoàn toàn có thể đổi chỗ trực tiếp 2 phần tử
    - Xây dựng hàm kiểm tra nguyên tố, chính phương
    - Bạn duyệt từ đầu mảng tới cuối mảng. Đổi chỗ trực tiếp 2 phần tử luôn. Có nghĩa là gặp nguyên tố thì đổi chỗ với phần tử gần đầu nhất ko phải nguyên tố. Còn số chính phương thì đổi chỗ với phần tử gần đầu nhất ko phải nguyên tố và số chính phương --> ...
    Hoặc bạn có thể so sánh và sắp xếp luôn . Tuy nhiên sẽ phức tạp khi xây dựng hàm . Làm đơn thuần thì dễ xây dựng hơn
    ------ > ......
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  3. #3
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi thangsoncp Xem bài viết
    Các pro làm giúp mình bài này với:
    Cho dãy số gồm n số nguyên duơng(n<20000) sắp xếp các số trên theo thứ tự ưu tiên sau: Trước hết là các số nguyên tố sau đó là các số chính phương và cuối cùng là là các số còn lại, nếu cùng loại số thì số nhỏ xếp trước.
    VD: 3 9 4 5 2 12 13 16
    Dãy sắp xếp: 2 3 5 13 4 9 16 12

    Theo mình ý tưởng viết bài này là chia dãy số thành 3 dãy con, sắp xếp 3 dãy đó rồi ghép các dãy số đã sắp xếp thành dãy số cần tìm, nhưng mà mình viết mãi ko ra, mình đang cần gấp, mong mọi người vào cho mình đoạn code để mình tham khảo nhé.
    Mình code cho bạn phần sắp xếp và chuyển số nguyên tố về đầu. Phần sau code tương tự thôi
    bạn hoàn thành nốt nhé

    C++ Code:
    1. #include <iostream>
    2. #include <math.h>
    3.  
    4. using namespace std;
    5.  
    6. int ktnguyento(int n)
    7. {
    8.     int i;
    9.     int m, y;
    10.     if(n == 2 || n == 3)
    11.         return 1;
    12.     if (n == 1||n % 2 == 0||n % 3 == 0)
    13.         return 0;
    14.     m = (int)sqrt(n);
    15.     y = 2;
    16.     for(i=5;i<=m;i=i+y, y = 6 - y)
    17.         if(n % i == 0) return 0;
    18.         return 1;
    19. }
    20.  
    21. int chinhphuong(int n)
    22.     {
    23.         if (n==int(sqrt(n))*int(sqrt(n))) return 1;
    24.                     else return 0;
    25.     }
    26. void swap (int &a, int &b)
    27. {
    28.     int tam = a; a = b; b = tam;
    29. }
    30. int main ()
    31. {
    32.     int arr[50];
    33.     int n;
    34.     int nt, cp, bt;
    35.     cout << "So pt: ";
    36.     cin >> n;
    37.     for (int i = 0; i < n; i ++)
    38.     {
    39.         cout << "Pt " << i+1 << ": ";
    40.         cin >> arr[i];
    41.     }
    42.  
    43.     if (ktnguyento(arr[0])==1)
    44.         nt = arr [0];
    45.     else if (chinhphuong(arr[0])==1)
    46.         cp = arr [0];
    47.     else bt = arr [0];
    48.     for (int i = 0; i < n; i ++)
    49.         for (int j = i+1; j < n; j ++)
    50.         {
    51.             if (ktnguyento(arr[j])==1){
    52.                 if (ktnguyento(arr[i])!=1)
    53.                     swap (arr[i], arr[j]);
    54.                 else if((ktnguyento(arr[i])==1))
    55.                     if (arr[i]>arr[j])
    56.                         swap (arr[i], arr[j]);
    57.             }
    58.         }
    59.  
    60.     for (int i = 0; i < n; i ++)
    61.         cout << " " << arr[i];
    62.     return 0;
    63. }



    Trích dẫn Nguyên bản được gửi bởi G.Perelman Xem bài viết
    Là tôi thì tôi sẽ làm theo ý tưởng của chủ thớt.
    Cái này thì tùy bạn thôi . Nếu đơn giản về cách thực hiện. Thì sẽ tốn bộ nhớ. Còn xét về nhanh chậm thì còn chưa rõ
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

  4. #4
    Ngày gia nhập
    09 2009
    Nơi ở
    Hoa sơn tuyệt đỉnh
    Bài viết
    407

    Thời gian chạy thì ngang nhau thôi, nếu dùng quick sort cũng vậy

    my houses
    my school
    tỐnG lÊ cHâN mAnG kỶ nIệM bUồN cHo AnH...

  5. #5
    Ngày gia nhập
    12 2010
    Bài viết
    23

    Cám ơn bạn beautiful..84 :d, và mọi người đã vào cho ý kiến, mình sẽ thử code theo ý tưởng của bạn beautiful..., nhưng mà nếu bạn nào code được theo ý tưởng của mình thì cho mình đoạn code với để mình tham khảo với

  6. #6
    Ngày gia nhập
    11 2010
    Nơi ở
    Black Hole
    Bài viết
    824

    Mặc định Cách sử dụng list trong việc tách 1 dãy số thành nhiều dãy con

    Trích dẫn Nguyên bản được gửi bởi thangsoncp Xem bài viết
    Các pro làm giúp mình bài này với:
    Cho dãy số gồm n số nguyên duơng(n<20000) sắp xếp các số trên theo thứ tự ưu tiên sau: Trước hết là các số nguyên tố sau đó là các số chính phương và cuối cùng là là các số còn lại, nếu cùng loại số thì số nhỏ xếp trước.
    VD: 3 9 4 5 2 12 13 16
    Dãy sắp xếp: 2 3 5 13 4 9 16 12

    Theo mình ý tưởng viết bài này là chia dãy số thành 3 dãy con, sắp xếp 3 dãy đó rồi ghép các dãy số đã sắp xếp thành dãy số cần tìm, nhưng mà mình viết mãi ko ra, mình đang cần gấp, mong mọi người vào cho mình đoạn code để mình tham khảo nhé.
    vấn đề đặt ra là làm sao bạn biết chắc 3 dãy con là 3 dãy cần tìm mà sắp xếp ? Mà nếu đã xác định dc 3 dãy con cần tìm thì việc chia ra 3 dãy con là vô nghĩa vì khi này chúng ta đã biết lượng phần tử mỗi dãy nhỏ, 1 cái quick sort là xong.
    Come as guest...... stay as family......... because we're smiling together.

  7. #7
    Ngày gia nhập
    12 2010
    Bài viết
    23

    Trích dẫn Nguyên bản được gửi bởi clamvn Xem bài viết
    vấn đề đặt ra là làm sao bạn biết chắc 3 dãy con là 3 dãy cần tìm mà sắp xếp ? Mà nếu đã xác định dc 3 dãy con cần tìm thì việc chia ra 3 dãy con là vô nghĩa vì khi này chúng ta đã biết lượng phần tử mỗi dãy nhỏ, 1 cái quick sort là xong.
    Thì 3 dãy đó nó có quy luật còn gì, 1 dãy là các p.tử là số nguyên tố, 1 dãy là p.tử các số chính phương, còn dãy thứ 3 là gồm các p.tử ko thỏa mãn cả 2 dãy trên.

  8. #8
    Ngày gia nhập
    03 2010
    Nơi ở
    Nơi nào đó trong vũ trụ
    Bài viết
    550

    @beautifulsoul84hung: Code sắp xếp hình như bị sai. Em kiểm tra thử với phần tử nguyên tố, cuối cùng (phía sau nó thì ko có phần tử nào là số nguyên tố nữa). Với phần tử này thì code của em không hề có sự sắp xếp.
    Làm như chủ thớt có vẻ là ổn hơn đấy, chỉ mất 1 lần quét từ đầu đến cuối mảng để kiểm tra loại phần tử. Còn sau khi đã tách ra làm 3 mảng rồi thì dùng thuật toán sắp xếp nào đó ổn ổn 1 tí là được.
    - Cách làm của beautifulsoul84hung hơi rối thì phải và rắc rối trong việc tối ưu.
    Gió thu lạnh lẽo hắt hiu lòng!

  9. #9
    Ngày gia nhập
    11 2010
    Nơi ở
    Black Hole
    Bài viết
    824

    Trích dẫn Nguyên bản được gửi bởi thangsoncp Xem bài viết
    Thì 3 dãy đó nó có quy luật còn gì, 1 dãy là các p.tử là số nguyên tố, 1 dãy là p.tử các số chính phương, còn dãy thứ 3 là gồm các p.tử ko thỏa mãn cả 2 dãy trên.
    Đề bài là cho 1 dãy lộn xộn, đâu có biết có bao nhiêu phần tử của dãy 1 hay dãy 2 hay dãy 3
    Nếu 3 dãy mà có rồi thì ko cần bàn nữa.
    Ý của Beautyful là chia dãy giống như bạn nhưng chỉ thực hiện trên dãy đầu chứ ko phải chia ra 3 dãy nhỏ (nghĩa là khi này sẽ có 4 dãy : 1 dãy đầu và 3 dãy con ).
    Cách của beautyful là tránh trường hợp ko biết dãy nguyên tố có bao nhiêu phần tử và tương tự như dãy số còn lại. Nên bạn ấy đã đưa ra cách xử lý trực tiếp trên dãy đầu để tránh trường hợp nên trên. Tuy hơi rắc rối nhưng nếu thấy và hiểu thì ko rắc rối.
    Come as guest...... stay as family......... because we're smiling together.

  10. #10
    Ngày gia nhập
    01 2011
    Nơi ở
    -Mountain-
    Bài viết
    768

    Trích dẫn Nguyên bản được gửi bởi birthis Xem bài viết
    @beautifulsoul84hung: Code sắp xếp hình như bị sai. Em kiểm tra thử với phần tử nguyên tố, cuối cùng (phía sau nó thì ko có phần tử nào là số nguyên tố nữa). Với phần tử này thì code của em không hề có sự sắp xếp.
    Làm như chủ thớt có vẻ là ổn hơn đấy, chỉ mất 1 lần quét từ đầu đến cuối mảng để kiểm tra loại phần tử. Còn sau khi đã tách ra làm 3 mảng rồi thì dùng thuật toán sắp xếp nào đó ổn ổn 1 tí là được.
    - Cách làm của beautifulsoul84hung hơi rối thì phải và rắc rối trong việc tối ưu.
    Em đã test lại. Code ko hề bị lỗi
    Hoặc là em ko phát hiện ra. Mong anh chỉ rõ hơn.
    Còn ngôn ngữ C ưu điểm là quản lý bộ nhớ tốt hơn ngôn ngữ khác
    Vậy ai chỉ ra cách nào nhanh hơn + tiết kiệm bộ nhớ hơn thì em nghe
    Đã được chỉnh sửa lần cuối bởi beautifulsoul84hung : 23-09-2011 lúc 11:28 AM.
    Hướng dẫn C++: https://www.youtube.com/watch?v=BwLodoQdoY4&list=PL1c9Uxlo-mplJDRGdONNupgo5OCBTyGGn

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

  1. giúp mình cái bài tập list của list này với (còn 24 tiếng))
    Gửi bởi pipipo102 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 10-06-2012, 11:36 AM
  2. Socket Làm thế nào sử dụng webbrowser để navigate list url lấy về nhiều HtmlDocument?
    Gửi bởi bdangvnt trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 2
    Bài viết cuối: 01-11-2011, 09:06 PM
  3. Phương thức Add trong list có phải là thêm đối tượng vào list không?
    Gửi bởi princehai trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 20-09-2011, 01:14 PM
  4. hàm hủy(list::~list()) trong danh sách móc nối đối tượng xử lý những gì?
    Gửi bởi Emerald214 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 0
    Bài viết cuối: 29-12-2010, 09:05 AM
  5. Chuyển các phần tử từ list này sang list kia. Sửa giúp mình?
    Gửi bởi Vaanres trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 1
    Bài viết cuối: 25-07-2010, 09:45 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