Nếu cần xây dựng thuật toán cho bài toán sắp xếp dãy không tăng thì sẽ khác gì so với thuật toán sắp xếp dãy không giảm . GIÚP VỚI MỌI NGƯỜI ƠI!
Với thuật toán sắp xếp bằng tráo đổi (Exchange sort). Muốn sắp xếp dãy theo thứ tự không tăng thì cần đổi dấu bước nào sau đây?
A. i>M
B. M<2
C. ai>ai+1
D. i>N
Xây dựng thuật toán sắp xếp bằng tráo đổi một dãy số ko tăng.
-Xác định input, output
-Xác định ý tưởng
-Xác định thuật toán
#include <bits/stdc++.h>
using namespace std;
long long a[100],n,i,j;
int main()
{
cin>>n;
for (i=1; i<=n; i++)
cin>>a[i];
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
if (a[i]<a[j]) swap(a[i],a[j]);
for (i=1; i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
Mô phỏng thuật toán sắp xếp dãy số không giảm với N = 10 và dãy A : 6,1,5,3,7,8,10,7,12,4 . Hãy cho biết với lần duyệt thứ mấy để sắp xếp thành 1,3,4,5,6,7,7,8,10,12
#include <bits/stdc++.h>
using namespace std;
long long a[1000],i,n;
int main()
{
cin>>n;
for (i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+n+1);
for (i=1; i<=n; i++) cout<<a[i]<<" ";
return 0;
}
Cho dãy số N=8 , tìm x 15,7,21,30,9,18,50,6 Sắp xếp dãy số theo chiều không tăng của thuật toán sắp xếp nổi bọt
Cho Dãy A gồmN=8.Dãy A gồm các số nguyênlà : 9 ,11, 3, 25, 1, 18,20, 2.Hãy sử dụng thuật toán sắp xếp tráo đổi( sắp xếp dãy A thành dãy không tăng)
Cách làm: Làm theo thứ tự các bước:
1.Xác định bài toán
2.Ý tưởng
3.Thuật toán( làm 1 trong 2 cách:Liệt kê và sơ đồ khối)
4.Ápdụng làm dãy số trên theo các lần duyệt như trong sách giáo khoa
#include <bits/stdc++.h>
using namespace std;
long long a[8],n,i,j;
int main()
{
n=8;
for (i=1; i<=n; i++) cin>>a[i];
for (i=1; i<=n-1; i++)
for (j=i+1; j<=n; j++)
if (a[i]<a[j]) swap(a[i],a[j]);
for (i=1; i<=n; i++) cout<<a[i]<<" ";
return 0;
}
Câu 2: Cho dãy A gồm N số nguyên a1, a2,…,an . Em hãy sắp xếp dãy số A thành dãy không tăng(KHÔNG GIẢM).Câu 3: Cuối năm học lớp 10 các bạn trong lớp đều có điểm trung bình môn. Ví dụ bạn A: 8.5, B:9.4, C: 7.8 ..., em hãy xây dựng thuật toán tìm ra bạn có điểm cao nhất.
2:
#include <bits/stdc++.h>
using namespace std;
long long a[1000],i,n;
int main()
{
cin>>n;
for (i=1; i<=n; i++) cin>>a[i];
sort(a+1,a+n+1);
for (i=1; i<=n; i++) cout<<a[i]<<" ";
cout<<endl;
for (i=n; i>=1; i--) cout<<a[i]<<" ";
return 0;
}
Nếu dãy ban đầu đã được sắp xếp thì thuật toán sắp xếp chèn sẽ thực hiện như thế nào?
THAM KHẢO!
Nếu dãy ban đầu đã được sắp xếp, thì thuật toán sắp xếp chèn sẽ không thực hiện thay đổi nào trên dãy vì mỗi phần tử trong dãy đã đứng đúng vị trí của nó. Cụ thể, các bước của thuật toán sẽ được thực hiện như sau:
Xác định phần tử đầu tiên trong dãy là phần tử thứ 2 (i = 1), không cần thực hiện bất kỳ thay đổi nào vì phần tử này đã đứng đúng vị trí của nó trong dãy đã được sắp xếp.
Kiểm tra phần tử thứ 3 (i = 2) so với các phần tử trước nó trong dãy. Nếu phần tử này đã đứng đúng vị trí, không cần thực hiện thay đổi nào.
Tiếp tục kiểm tra và so sánh từng phần tử còn lại trong dãy với các phần tử trước nó. Nếu phần tử đang xét đã đứng đúng vị trí, không cần thực hiện thay đổi nào.
Sau khi kiểm tra hết các phần tử trong dãy, thuật toán kết thúc mà không có bất kỳ thay đổi nào được thực hiện trên dãy ban đầu, vì dãy đã được sắp xếp.
Mô tả thuật toán: bài toán cần khai báo những biến nào, xác định kieur dữ liệu của từng biến. VỚi bài toán sắp xếp thì ta cần biến trung gian để làm gì? Sử dụng vòng lặp for lồng nhau so sánh 2 số với nhau để sắp xếp tăng dần. Với toán Tìm Max sử dụng 1 biến Max để gán với giá trị nào ? so sánh giá trị nào? Để tìm ra số lớn nhất ? Trình bày các bước mô tả thuật toán ở dạng liệt kê hoặc sơ đồ khối?
Trong Nhiệm vụ 2, nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn được không?
Nếu dãy A đã được sắp xếp theo thứ tự tăng dần thì có thể cải tiến thuật toán tốt hơn.