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

Đề tài: Tìm giá trị lớn thứ k trong mảng.

  1. #1
    Ngày gia nhập
    02 2008
    Bài viết
    21

    Mặc định Tìm giá trị lớn thứ k trong mảng.

    Đây là bài toán tìm số lớn thứ k trong mảng. Mình đã làm ra rồi up lên cho các bạn xem. Bạn nào giúp mình chuyển cái hàm FindK này thành đệ quy cái. Sao mình dốt đê quy wa.


    C Code:
    1. #include<stdio.h>
    2. #include<conio.h>
    3. const int maxn=100;
    4. void InputArray(int a[maxn],int &k){
    5. int i;
    6. for (i=0;i<k;i++){
    7. printf("nhap phan tu thu a[%d]",i);
    8. scanf("%d",&a[i]);
    9. }
    10. }
    11. ////////////////////////////////////
    12. int Median(int a[maxn],int &k){
    13. int s,i;
    14. s=0;
    15. for (i=0;i<k;i++)
    16. s=s+a[i];
    17. return s/k;
    18. }
    19. ///////////////
    20. void SortArray(int a[maxn],int k){
    21. int i,j,tam;
    22. for(i=0;i<k-1;i++)
    23.  for(j=i+1;j<k;j++)
    24.   if(a[i]>a[j]){
    25.   tam=a[i];
    26.   a[i]=a[j];
    27.   a[j]=tam;
    28.   }
    29.   }
    30. ////////////////////////////
    31. void FindK(int a[maxn],int sl[], int sv[], int sr[], int k){
    32. int i,v,l,r,tt;
    33.     l=0;v=0;r=0;
    34. for (i=0;i<k;i++){
    35.  if (a[i]<Median(a,k)){
    36.     sl[l]=a[i];
    37.     l=l+1;
    38.     }
    39.  else
    40.  
    41.     if(a[i]==Median(a,k)){
    42.         sv[v]=a[i];
    43.         v=v+1;
    44.         }
    45.     else {
    46.  
    47.         sr[r]=a[i];
    48.         r=r+1;
    49.         }
    50.         }
    51.  printf("can tim so lon thu may?:");scanf("%d",&tt);
    52.     if(tt<=l){
    53.         SortArray(&sl[l],l);
    54.         printf("so can tim la %d",sl[tt-1]);
    55.     }
    56.     else
    57.     if ((tt>l)&&(tt<l+v))
    58.         printf("so can tim la%d",sv[1]);
    59.     else
    60.     if (tt>l+v){
    61.     SortArray(&sr[r],r);
    62.     tt=tt-v-l-1;
    63.     printf("so can tim la %d",sr[tt]);
    64.     }
    65.  }
    66.  
    67. void main(){
    68. int a[maxn];int sl[maxn],sv[maxn],sr[maxn];
    69.  
    70. int n;
    71. printf("nhap so phan tu cua mang:"); scanf("%d",&n);
    72. InputArray(a,n);
    73. printf("Median la %d",Median(a,n));
    74. printf("\n");
    75. SortArray(a,n);
    76. for (int i=0;i<n;i++) printf("%d",a[i]);printf("\n");
    77. FindK(a,sl,sv,sr,n);
    78. }
    79. ///////////////////

    Vui lòng để code trong tag . Xin cảm ơ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ý.
    Đã được chỉnh sửa lần cuối bởi comeonbaby : 14-03-2008 lúc 06:55 PM.

  2. #2
    Ngày gia nhập
    03 2008
    Bài viết
    78

    - Bạn ơi, sao bạn ko cho code vào tag CODE - thế nào cũng bị nhắc nhở cho xem.Xem hướng dẫn ở trên ấy...
    - Bạn chỉ nêu đề bài, bạn đưa ra một chương trình thì phải kèm theo cả ý tưởng chứ - người đọc dễ hiểu và quan sát.
    - Chưa nói mình test bài của bạn nó ra kết quả ko như đề bài nêu:"in ra giá trị lớn thứ k" sao ko thấy nhập k vào nhỉ.
    + Mình xin đóng góp thêm cho bạn một ý như thế này...
    * Thứ nhất sắp mảng theo thứ tự giảm dần.
    * Duyệt mảng vừa sắp và dùng một biến đếm. Khi A[i] khác A[i-1] thì
    dem = dem + 1; đếm đến lúc nào thấy dem = k thì in ra phần tử mảng A tại ví trí thứ i đó (A[i]).Xong!Mình thấy bạn làm cái hàm median làm jì đó nhỉ...

    + Một bài toán nhiều cách làm...mình học ở bạn cách này và bạn học ở mình cách khác.
    Chúc bạn thành công.

    Lưu ý:nếu bạn sắp mảng tăng dần thì mình duyệt mảng để tìm số lớn thứ k là phải duyệt ngược từ phải qua trái nhé...
    Đã được chỉnh sửa lần cuối bởi hacker_mubaohiem : 14-03-2008 lúc 05:10 PM.
    No way, No success..

  3. #3
    Ngày gia nhập
    02 2008
    Bài viết
    21

    Chào Hacker_mubaohiem. Bài toán của mình là rõ ràng rùi. Tìm giá trị lớn thứ k của mảng.
    code tren mình đã kiểm tra rùi và nó chạy đúng. Tuy nhiên bạn sửa lại chỗ
    Code:
    if (tt<=l) bạn sửa thành if(tt<l)
    vậy là bạn chạy sẽ thấy kết quả.

    Cách làm của mình rất hay vì mình học được. Tuy nhiên yêu cầu là viết nó thành đệ quy chứ không viết như thế.
    Nếu bạn nhìn vào bài thì bạn biết ý tưởng rùi chứ. Còn không thì mình nói thế này:

    Cho một mảng A nào đó có n phần tử. Nhập k là là số lớn thứ mấy cần tìm. Ví dụ A={2,4,1,6,8,5,9,2,4,2,8,6} và k là số lớn thứ 5 thì kết quả là: 4 vì 4 là giá trị lớn thứ 5.
    Thuật toán của mình tìm Median là để tách mảng ra làm 3 mảng nhỏ.
    Một mảng sl[l] sẽ chứa giá trị <Median và sẽ có chiều dài là l
    Một mảng sv[v] chứa gia trị =Median và có chiều dài là v
    Mảng còn lại sr[r] chứa giá trị lớn hơn Median và sẽ có chiều dài là r.
    Nếu k< l thì mình chỉ cần tìm ở mảng sl[l]
    Nếu k>l và k<l+v thì chính là phần tử của sv[v]
    Nếu k>l+v thì tìm ở vị trí thứ k=k-l-v-1.
    Đó là thuật toán hoàn toàn chính xác 100% và mình muốn chuyển wa đệ qui. Mình dốt đệ qui wa.

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

    - Rồi,cái thuật toán của bạn jống như tam phân ấy nhỉ (bắt chước nhị phân hi) nhưng mà cái nào cũng đòi hỏi phải sắp xếp cái đã...

    - Nhưng khi đã sắp xếp rồi mà muốn tìm ra vị trí lớn thứ k dễ dàng bằng cách duyệt mảng thui chứ cái thuật toán tìm Median làm chi ấy nhỉ.

    - Lúc đầu tui tưởng bạn ko cần sắp xếp.Ai ngờ nhìn lại cũng sắp xếp.Thuật toán đó chỉ nên áp dụng các bài phức tạp thui.Bài này dễ thì mình ra lun chứ vòng vo làm jì.
    No way, No success..

  5. #5
    Ngày gia nhập
    02 2008
    Bài viết
    21

    Uh. Tớ làm vậy là sẽ it tốn chi phí hơn. Sort cũng sẽ sort một phần mảng sau khi tách chứ đâu có sort toàn mảng. Sort toàn mảng thì lâu lắm nếu mảng qá lớn nhưng tìm lại dễ. Ai có thể giúp mình chuyển qua đệ quy thuật toán trên ko??????

  6. #6
    Ngày gia nhập
    03 2008
    Bài viết
    126

    Mặc định Tìm giá trị lớn thứ k trong mảng.

    bài này của bill_khoa minh test thủ và thấy chưa ổn lắm
    khi user nhập vào 1 mảng thì bill_khoa sắp xếp mảng theo chiều tăng dần nhưng khi sắp xếp tăng dần thì bạn lại quên ko xóa các phần tử cùng nhau
    vd như nhập mảng 5phần tử là 1 5 3 5 6 thì bạn sắp xếp là 13556 nên khi bạn muốn lấy phần tử lớn thứ 3 thì nó sẻ ra kết quả là 5 mà kq đúng phải là 3
    Đây chỉ là ý kiến của mình thôi ko biết đúng ko nữa
    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