Tìm giá trị lớn thứ k trong mảng.

[bills_khoa]

Đâ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.

#include<stdio.h>#include<conio.h>const int maxn=100;void InputArray(int a[maxn],int &k){int i;for (i=0;i<k;i++){printf("nhap phan tu thu a[%d]",i);scanf("%d",&a[i]);}}////////////////////////////////////int Median(int a[maxn],int &k){int s,i;s=0;for (i=0;i<k;i++)s=s+a[i];return s/k;}///////////////void SortArray(int a[maxn],int k){int i,j,tam;for(i=0;i<k-1;i++) for(j=i+1;j<k;j++)  if(a[i]>a[j]){  tam=a[i];  a[i]=a[j];  a[j]=tam;  }  }////////////////////////////void FindK(int a[maxn],int sl[], int sv[], int sr[], int k){int i,v,l,r,tt;    l=0;v=0;r=0;for (i=0;i<k;i++){ if (a[i]<Median(a,k)){    sl[l]=a[i];    l=l+1;    } else     if(a[i]==Median(a,k)){        sv[v]=a[i];        v=v+1;        }    else {         sr[r]=a[i];        r=r+1;        }        } printf("can tim so lon thu may?:");scanf("%d",&tt);    if(tt<=l){        SortArray(&sl[l],l);        printf("so can tim la %d",sl[tt-1]);    }    else    if ((tt>l)&&(tt<l+v))        printf("so can tim la%d",sv[1]);    else    if (tt>l+v){    SortArray(&sr[r],r);    tt=tt-v-l-1;    printf("so can tim la %d",sr[tt]);    } } void main(){int a[maxn];int sl[maxn],sv[maxn],sr[maxn]; int n;printf("nhap so phan tu cua mang:"); scanf("%d",&n);InputArray(a,n);printf("Median la %d",Median(a,n));printf("\n");SortArray(a,n);for (int i=0;i<n;i++) printf("%d",a[i]);printf("\n");FindK(a,sl,sv,sr,n);}///////////////////

Vui lòng để code trong tag . Xin cảm ơn

[hacker_mubaohiem]

- 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é...

[bills_khoa]

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ỗ

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.

[hacker_mubaohiem]

- 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ì.

[bills_khoa]

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??????

[#include#]

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