Cho dãy số n số nguyên a[SUB]0[/SUB], a[SUB]1[/SUB],...a[SUB]n-1[/SUB]
hãy cho biết vị trí của k phần tử có giá trị lớn nhất của dãy?
AI BIET GIUP VOI .
hãy cho biết vị trí của k phần tử có giá trị lớn nhất của dãy?
AI BIET GIUP VOI .
Cho dãy số n số nguyên a0, a1,...an-1 hãy cho biết vị trí của k phần tử có giá trị lớn nhất của dãy?
ai:biết ai hỏi làm gì bạn .
taplamhacker
♥ Thanh Trâm ♥
1: tạo biến max = a[0], vitri = 0 ;
2: duyệt so sánh max với từng phần tử của mảng
- nếu a > max thì gán max = a và vitri = i
3: xuất vitri
2: duyệt so sánh max với từng phần tử của mảng
- nếu a > max thì gán max = a và vitri = i
3: xuất vitri
taplamhacker
♥ Thanh Trâm ♥
@@ à nhầm
k phần tử lớn nhất dãy, có nghĩ là có nhiều giá trị = max, tìm max xong duyệt mảng 1 lần nữa xem cái nào == max thì xuất i ra
k phần tử lớn nhất dãy, có nghĩ là có nhiều giá trị = max, tìm max xong duyệt mảng 1 lần nữa xem cái nào == max thì xuất i ra
Vì k chung chung ko biết lớn nhỏ, nên mình nghĩ đưa bài toán của bạn về dạng tìm rank của từng phần tử. Dễ nhất là bạn có thể tạo 1 mảng nữa lưu vị trí hiện tại của những phần tử này rồi sort lại:
1) Tạo 1 mảng với pos = i cho 0 <= i <= n - 1.
2) Sort lại mảng 'a' giảm/tăng dần, tuy nhiên lúc đổi chỗ thì phải đổi luôn 2 phần tử của 'pos'. Ví dụ:
swap(a, a[j]);
swap(pos, pos[j]);
3) Lấy k phần tử ở đầu/cuối của dãy 'pos' tùy theo cách bạn sort. Ví dụ khi sort giảm dần thì nếu pos[0] = x1 thì a[x1] là phần tử lớn nhất của dãy ban đầu, nếu pos[1] = x2 thì a[x2] là phần tử lớn nhì của dãy ban đầu,...
Độ phức tạp của thuật toán O(n log n), dùng quick sort cho dễ.
Nếu bạn học Struct rồi thì có thể dùng built-in 'sort' của C++ sẽ nhanh hơn tự viết (và ngắn hơn nữa).
1) Tạo 1 mảng với pos = i cho 0 <= i <= n - 1.
2) Sort lại mảng 'a' giảm/tăng dần, tuy nhiên lúc đổi chỗ thì phải đổi luôn 2 phần tử của 'pos'. Ví dụ:
swap(a, a[j]);
swap(pos, pos[j]);
3) Lấy k phần tử ở đầu/cuối của dãy 'pos' tùy theo cách bạn sort. Ví dụ khi sort giảm dần thì nếu pos[0] = x1 thì a[x1] là phần tử lớn nhất của dãy ban đầu, nếu pos[1] = x2 thì a[x2] là phần tử lớn nhì của dãy ban đầu,...
Độ phức tạp của thuật toán O(n log n), dùng quick sort cho dễ.
Nếu bạn học Struct rồi thì có thể dùng built-in 'sort' của C++ sẽ nhanh hơn tự viết (và ngắn hơn nữa).
Sửa lần cuối:
có thể cho mh tham khảo cái Struct không bạn, cách của bạn đúng rồi
Mã:
#include <algorithm>
#include <vector>
struct dataPos {
int val, pos;
dataPos() {} // có thể không cần dòng này.
dataPos(int v, int p) : val(v), pos(p) {}
bool operator<(const dataPos& another) const { return val > another.val; }
};
int main() {
vector<dataPos> a;
// đọc dữ liệu vào, với mỗi số x thứ i thì
// a.push_back(dataPos(x, i));
std::sort(a.begin(), a.end());
// in ra k giá trị từ dataPos[i].pos.
return 0;
}Để mình ghi thật ngắn gọn.
1) Giả sử bạn đã đọc dữ liệu vào mảng a và có n phần tử từ a[0] tới a[n-1]. Bây giờ mình tạo mảng pos.
2) Sort mảng a lại theo giảm dần, nhưng khi đổi chỗ phải đổi luôn trên mảng pos.
3) In ra k phần tử đầu tiên:
1) Giả sử bạn đã đọc dữ liệu vào mảng a và có n phần tử từ a[0] tới a[n-1]. Bây giờ mình tạo mảng pos.
Mã:
int pos[MAX_N];
for (unsigned i = 0; i < n; ++i) pos[i] = i;2) Sort mảng a lại theo giảm dần, nhưng khi đổi chỗ phải đổi luôn trên mảng pos.
Mã:
void quickSort(int a[], int left, int right) {
...
...
std::swap(a[i], a[j]);
std::swap(pos[i], pos[j]);
...
...
}3) In ra k phần tử đầu tiên:
Mã:
for (unsigned i = 0; i < k; ++i) printf("%d ", pos[i]);phamthanhnhan
(｡◕‿‿◕｡) づ
Bởi vì chủ topic không nói rõ giá trị của n và k nên mình phải assume rằng nó lớn. Vì vậy, những thuật toán sort có complexity là O(n^2) đều bị bỏ qua cả. Nếu k nhỏ thì bài này chỉ cần chạy k lần, mỗi lần tìm số max là đc, ko cần phải sort để cho phức tạp. Nhưng nếu n = k = 10000 thì sẽ thấy sự chênh lệch rất lớn.
Mình viết chương trình từ trc tới giờ luôn dùng built-in sort của C++, nó nhanh hơn ít nhất cũng 5 lần mình tự viết. Nếu mình tự viết sort thì quick sort luôn là lựa chọn hàng đầu, dễ viết, gọn, 30s là xong, lại hiệu quả cao, average complexity O(n log n).
PS: 1 vấn đề quan trọng: dùng bubble sort (hay những thuật toán sort O(n^2) khác) thì cũng tương ứng với chạy k lần tìm max, như vậy sort đâu có ý nghĩa gì.
Sửa lần cuối:
#include <iostream.h>
// 5 6 1 9 8 6
void nhap(int a[], int &n);
void interchangesort(int a[], int n);
void swap(int &x, int &y);
void xuat(int a[],int n);
int main()
{
int a[1000],n,k;
nhap(a,n);
int pos[1000];
for (int i = 0; i < n; ++i)
pos = i;
interchangesort(a,n);
xuat(a,n);
cin>>k;
for (int i = 0; i <k; ++i)
cout<< pos;
}
void nhap(int a[], int &n)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a;
}
void interchangesort(int a[], int n)
{
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a<a[j])
swap(a,a[j]);
}
void swap(int &x, int &y)
{
int t =x;
x=y;
y=t;
}
void xuat(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a<<" ";
}
sao nó không xuất ra đc vị trí lúc ban đầu của chuỗi khi nhập vào bạn
// 5 6 1 9 8 6
void nhap(int a[], int &n);
void interchangesort(int a[], int n);
void swap(int &x, int &y);
void xuat(int a[],int n);
int main()
{
int a[1000],n,k;
nhap(a,n);
int pos[1000];
for (int i = 0; i < n; ++i)
pos = i;
interchangesort(a,n);
xuat(a,n);
cin>>k;
for (int i = 0; i <k; ++i)
cout<< pos;
}
void nhap(int a[], int &n)
{
cin>>n;
for(int i=0;i<n;i++)
cin>>a;
}
void interchangesort(int a[], int n)
{
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a<a[j])
swap(a,a[j]);
}
void swap(int &x, int &y)
{
int t =x;
x=y;
y=t;
}
void xuat(int a[],int n)
{
for(int i=0;i<n;i++)
cout<<a<<" ";
}
sao nó không xuất ra đc vị trí lúc ban đầu của chuỗi khi nhập vào bạn
Đoạn code của bạn viết rất tốt, chỉ có 2 chỗ cần đổi tí xíu:
1) Trong lúc sort, bạn cần đổi chỗ pos và pos[j] luôn nhé.
2) Lúc in ra thì bạn cần làm theo như post #11 của mình, chỗ ghi chú thứ 3. Một điều nhỏ khác nữa, chỗ pos = i, lúc bạn nhập giá trị của 'a' thì làm luôn, ko cần chạy lại 1 lần nữa để làm cái này.
Để mình viết cho bạn 1 đoạn code đơn giản nhất để sort cho nó nhanh. Bài này nếu dùng sort là phải sort cho nhanh mới phát huy đc thuật toán bạn ạ.
Lúc gọi thì phải thế này:
Bạn cần
C++ đã có sẵn function swap rồi, bạn ko cần viết nữa. Để kiểm tra đúng hay không thì có thể thử đoạn code sau nhé:
Sau đó cho MAXN và K lớn lên, đừng in ra gì nữa, so sánh rồi xem thử tốc độ nhanh chậm ra sao nếu sort kiểu khác hay là tìm từng phần tử max một K lần.
PS: Thật ra, bài này sẽ hay hơn nếu in ra phần tử lớn thứ K của dãy, mà không phải là K phần tử lớn nhất dãy. Giả sử K = n / 2 thì tức là in ra median của dãy. Khi đó cho dù sort cũng không phải nhanh nhất. Nhanh nhất là dùng chia để trị với độ phức tạp O
.
1) Trong lúc sort, bạn cần đổi chỗ pos và pos[j] luôn nhé.
Mã:
if (a[i] < a[j]) {
swap(a[i], a[j]);
swap(pos[i], pos[j]);
}Để mình viết cho bạn 1 đoạn code đơn giản nhất để sort cho nó nhanh. Bài này nếu dùng sort là phải sort cho nhanh mới phát huy đc thuật toán bạn ạ.
Mã:
void quickSort(int a[], int left, int right) {
if (left >= right) return;
int pivot = a[rand() % (right - left + 1) + left];
int i = left, j = right;
do {
while (a[i] > pivot) ++i;
while (a[j] < pivot) --j;
if (i <= j) {
if (i < j) {
std::swap(a[i], a[j]);
std::swap(pos[i], pos[j]);
}
++i; --j;
}
} while (i <= j);
quickSort(a, left, j);
quickSort(a, i, right);
}
Mã:
srand(time(0));
quickSort(a, 0, n - 1);
Mã:
#include <time.h>
#include <stdlib.h>
#include <algorithm>
Mã:
// Đầu tiên random ra MAXN số, mỗi số trong khoảng [0, MAXE). Để cho dễ chỉ lấy MAXN = 10.
// Khi random thì in ra mảng a ban đầu luôn.
srand(time(0));
for (int i = 0; i < MAXN; ++i) {
a[i] = rand() % MAXE;
pos[i] = i;
printf("%d ", a[i]);
}
printf("\n");
quickSort(a, 0, MAXN - 1); // sort lại theo giảm dần.
// In ra mảng a đã sort.
for (int i = 0; i < MAXN; ++i) printf("%d ", a[i]);
printf("\n");
// In ra vị trí của K phần tử lớn nhất của mảng.
// Đối chiếu với mảng a ngay trên, bạn xem ban đầu nó có phải ở vị trí đó hay không.
for (int i = 0; i < K; ++i) printf("%d ", pos[i]);PS: Thật ra, bài này sẽ hay hơn nếu in ra phần tử lớn thứ K của dãy, mà không phải là K phần tử lớn nhất dãy. Giả sử K = n / 2 thì tức là in ra median của dãy. Khi đó cho dù sort cũng không phải nhanh nhất. Nhanh nhất là dùng chia để trị với độ phức tạp O
.
Sửa lần cuối:
Bài viết mới nhất
-
Kho truyện ngắn cực hay- shopoga
-
Sách Hay Mỗi Ngày
- shopoga
-
COLORFUL công bố mini PC mang tên gọi CMNH01-12450- maychucongnghe
