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ố 20 kết quả

Đề tài: Thuật toán đếm các phần tử của mà mỗi phần tử chỉ lặp lại một lần ?

  1. #1
    Ngày gia nhập
    07 2011
    Bài viết
    22

    Wink Thuật toán đếm các phần tử của mà mỗi phần tử chỉ lặp lại một lần ?

    Giúp mình thuật toán đếm các phần tử của mảng mà mỗi phần tử chỉ lặp lại một lần?
    Mình đang gặp rắc rối ở hàm đếm có phân biệt này giúp mình với!!
    Code:
    int demphanbiet(int a[], int n)
    {
    	int dem=0;
    	int i,j;
    	for(i=0;i<n-1;i++)
    		for(j=i+1;j<n;j++)
    			if(a[i]==a[j])
    				continue;
    			else
    				dem++;
    		return dem;
    
    }

  2. #2
    Ngày gia nhập
    12 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    687

    không biết có đúng ý của bạn không ?
    dùng phương pháp đếm phân phối !

    C++ Code:
    1. #include<iostream>
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     int a[10] = { 3 , 4 , 2, 1 ,1 , 1 ,4,6,7,8};
    7.     int c[10] , dem = 0;
    8.     for ( int i = 0 ; i < 10 ; i++)
    9.     {
    10.         c[i] = 0 ; // mang c nay dung de dem cac phan tu cua mang, khoi tao mang do = 0;
    11.     }
    12.     for ( int i = 0 ; i < 10 ; i++)
    13.     {
    14.         // dem cac phan tu cua mang
    15.         c[a[i]]+=1;
    16.     }
    17.     // kiem tra neu ma c[i] = 1 tuc la phan tu i xuat hien dung 1 lan vaf dem no
    18.     cout <<"\nCac phan tu xuat hien dung 1 lan la : ";
    19.     for ( int i = 0 ; i < 10 ; i++)
    20.     {
    21.         if ( c[i] == 1)
    22.         {
    23.             dem++;
    24.             cout << i << " , ";
    25.         }
    26.     }
    27.     cout << "\nVay tong phan tu xuat hien dung 1 lan la : " << dem << endl;
    28.     cin.get();
    29.     return 0;
    30. }

  3. #3
    Ngày gia nhập
    07 2011
    Bài viết
    17

    Cách như bạn chỉ áp dụng cho mảng có giá trị các phần tử nằm trong khoảng 0 --> 9. Cách giải tổng quát hơn có lẽ phải dùng tới hash table. Cách này về lý thuyết là O(n).

    Ngoài ra còn có cách khác là sort mảng, sau đó duyệt từ đầu tới cuối. Cách này tốn thời gian hơn, khoảng O(nlogn)
    Mọt sách

  4. #4
    Ngày gia nhập
    07 2011
    Bài viết
    22

    trong mảng nhập số bất kì mà bạn ? đâu phải giá trị từ 0->9 đâu!!!!

  5. #5
    Ngày gia nhập
    12 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    687

    Trích dẫn Nguyên bản được gửi bởi bookworm Xem bài viết
    Cách như bạn chỉ áp dụng cho mảng có giá trị các phần tử nằm trong khoảng 0 --> 9. Cách giải tổng quát hơn có lẽ phải dùng tới hash table. Cách này về lý thuyết là O(n).

    Ngoài ra còn có cách khác là sort mảng, sau đó duyệt từ đầu tới cuối. Cách này tốn thời gian hơn, khoảng O(nlogn)
    cách của mình vẫn đúng với các số lơn hơn lớn hơn 9, đây mình chỉ mô tả cách làm thôi , bạn có thể khai báo 1 mảng c [300000] , các số sẽ nằm trong khoảng đó sẽ thực hiện được !

  6. #6
    Ngày gia nhập
    04 2010
    Nơi ở
    Recycle Bin
    Bài viết
    358

    Mặc định Thuật toán đếm các phần tử của mà mỗi phần tử chỉ lặp lại một lần ?

    Mình thấy cách của chủ pic là khá ổn rồi. Chắc ý bạn này hỏi có giải thuật nào đơn giản hơn không? mình thì cũng chưa thấy cách nào tối ưu hơn.
    @xuyen: bài của bạn chỉ dùng cho bài toán số nhập vào từ 0-9 nếu số nhập vào chênh lệch nhiều thì không tốt chút nào
    C Code:
    1.  for ( int i = 0 ; i < 10 ; i++)
    2.     {
    3.         if ( c[i] == 1)
    4.         {
    5.             dem++;
    6.             cout << i << " , ";
    7.         }
    8.     }

    p/s: Bài của bạn loveboom3012 sửa lại chút là được
    C Code:
    1. int demphanbiet(int a[], int n)
    2. {
    3.     int dem=0;
    4.     int i,j,flag;
    5.     for(i=0;i<n;i++)
    6.     {
    7.         flag=1;
    8.         for(j=i+1;j<n;j++)
    9.             if(a[i]==a[j]) {flag=0;break;}
    10.         if(flag) dem++;
    11.     }
    12.     return dem;
    13.  
    14. }
    Đã được chỉnh sửa lần cuối bởi conrongchautien : 01-08-2011 lúc 06:19 PM.
    YH : lobuocphuudu_218
    Phone : 0126 463 5095

    http://forums.congdongcviet.com/signaturepics/sigpic55872_2.gif

  7. #7
    Ngày gia nhập
    12 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    687

    Trích dẫn Nguyên bản được gửi bởi conrongchautien Xem bài viết
    Mình thấy cách của chủ pic là khá ổn rồi. Chắc ý bạn này hỏi có giải thuật nào đơn giản hơn không? mình thì cũng chưa thấy cách nào tối ưu hơn.
    @xuyen: bài của bạn chỉ dùng cho bài toán số nhập vào từ 0-9 nếu số nhập vào chênh lệch nhiều thì không tốt chút nào



    p/s: Bài của bạn loveboom3012 sửa lại chút là được
    C Code:
    1. int demphanbiet(int a[], int n)
    2. {
    3.     int dem=0;
    4.     int i,j;
    5.     for(i=0;i<n;i++)  ///////
    6.         for(j=i+1;j<n;j++)
    7.             if(a[i]==a[j])
    8.                 break; ///// cotinue; //bad
    9.             else
    10.                 dem++;
    11.         return dem;
    12.  
    13. }
    1 thuật toán có độ phức tạp là 0(n) và 1 cái là 0(n^2 ) cái nào tốt hơn nhỉ ?
    mềnh code như thế này cho hoàn chỉnh nhé !
    nếu bạn muốn số nhiều hơn thì cứ khai báo 1 độ dài của mảng c !


    C Code:
    1. #include<iostream>
    2. using namespace std;
    3.  
    4. int main()
    5. {
    6.     int a[10] = { 2, 1 ,15 , 1 ,4,6,7,8,11,1};
    7.     int c[30000] , dem = 0;
    8.     for ( int i = 0 ; i < 30000 ; i++)
    9.     {
    10.         c[i] = 0 ; // mang c nay dung de dem cac phan tu cua mang, khoi tao mang do = 0;
    11.     }
    12.     for ( int i = 0 ; i < 10 ; i++)
    13.     {
    14.         // dem cac phan tu cua mang
    15.         c[a[i]]+=1;
    16.     }
    17.     // kiem tra neu ma c[i] = 1 tuc la phan tu i xuat hien dung 1 lan vaf dem no
    18.     cout <<"\nCac phan tu xuat hien dung 1 lan la : ";
    19.     for ( int i = 0 ; i < 30000 ; i++)
    20.     {
    21.         if ( c[i] == 1)
    22.         {
    23.             dem++;
    24.             cout <<i << " , ";
    25.         }
    26.     }
    27.     cout << "\nVay tong phan tu xuat hien dung 1 lan la : " << dem << endl;
    28.     cin.get();
    29.     return 0;
    30. }
    Đã được chỉnh sửa lần cuối bởi xuyenit55 : 01-08-2011 lúc 06:17 PM.

  8. #8
    Ngày gia nhập
    04 2010
    Nơi ở
    Recycle Bin
    Bài viết
    358

    Tớ nhập vào 2 số 1 và 30000 thì bài của bạn cũng mất 30000 bước lặp và tốn bộ nhớ 300000*sizeoff(int) rồi. Chẳng khác nào dùng kim mổ voi.
    Bạn đánh giá độ phức tạp theo kiểu gì vậy. Thử suy nghĩ lại xem nhé xuyen
    YH : lobuocphuudu_218
    Phone : 0126 463 5095

    http://forums.congdongcviet.com/signaturepics/sigpic55872_2.gif

  9. #9
    Ngày gia nhập
    12 2010
    Nơi ở
    Hanoi, Vietnam, Vietnam
    Bài viết
    687

    Trích dẫn Nguyên bản được gửi bởi conrongchautien Xem bài viết
    Tớ nhập vào 2 số 1 và 30000 thì bài của bạn cũng mất 30000 bước lặp và tốn bộ nhớ 300000*sizeoff(int) rồi. Chẳng khác nào dùng kim mổ voi.
    Bạn đánh giá độ phức tạp theo kiểu gì vậy. Thử suy nghĩ lại xem nhé xuyen
    mỗi thuật toán có 1 ưa điểm ji , bây h mình giả sử số phần tử của bạn lớn thì với thuật toán chạy 0(n^2 ) thì thời gian chạy bao lâu so với 0(n) ,
    bài của bạn kia chạy với ít số phần tử nhưng bài của mình chạy với số lượng phân từ khá lớn hơn bạn kia
    chính bạn mới cần xem lại nhé , những thuật toán đc đưa ra chả phải cái nào cũng vô nghĩa đâu bạn ! :|

  10. #10
    Ngày gia nhập
    04 2010
    Nơi ở
    Recycle Bin
    Bài viết
    358

    Tớ không tranh cãi với cậu. Nhưng mà thuật toán của cậu không phải là 0(n) như cậu nghĩ.
    Tớ chỉ làm những gì mà tớ thấy chắc chắn thôi. 0(n^2) còn hơn là Không Xác Định
    YH : lobuocphuudu_218
    Phone : 0126 463 5095

    http://forums.congdongcviet.com/signaturepics/sigpic55872_2.gif

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

  1. Trả lời: 6
    Bài viết cuối: 31-07-2013, 07:51 PM
  2. Những điều không thể bỏ qua khi phẫu thuật nâng ngực
    Gửi bởi deptoandien.com trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 02-01-2013, 12:17 PM
  3. Công ty phần mềm HOSCO tuyển Kỹ thuật viên phần mềm
    Gửi bởi hosgroup trong diễn đàn Tuyển dụng - Việc làm CNTT
    Trả lời: 1
    Bài viết cuối: 29-10-2011, 04:06 PM
  4. Phần mềm mô phỏng các thuật toán sắp xếp
    Gửi bởi OWickedFox trong diễn đàn Sản phẩm phần mềm của bạn
    Trả lời: 5
    Bài viết cuối: 08-06-2010, 11:56 PM
  5. Thuật toán trên C | Xóa phần tử trong dãy phần tử tăng dần?
    Gửi bởi quangphuit 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: 09-03-2010, 01:57 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