Như tiêu đề anh em ai có ý tưởng về bài toán này cho mình xin với,nghĩ mãi không ra đc ý tưởng nào hợp lý.Toàn mấy ý tưởng vớ vẩn tào lao thôi.huhuhu
Cảm ơn mọi người đã đọc.
Bài toán tìm tổng lớn nhất của k phần tử liên tiếp trên mảng
Gợi ý: k phần tử liên tiếp bắt đầu từ vị trí i đến i+k-1 nếu mảng có n phần tử thì có n-k+1 tập con k phần tử liên tiếp
tạo 1 mảng chứa toàn bộ tổng của k phần từ liên tiếp, số phần tử của mảng là n-k+1, chạy for thôi
Tưởng tưởng có 1 khung nhìn có độ dài K
giả sử mảng ban đầu là
a[0] a[1] a[2] ... a[n]
và k=3
để tính tổng k
phần tử liên tiếp khung nhìn sẽ bắt đầu từ index=0
index: 0 1 2 3 4 5
lúc ban đầu [0 1 2] 3 4 5
sau đó khung hình dịch lên 1 đơn vị: 0 [1 2 3] 4 5
Lần lượt làm như trên nhận thấy nếu tính được khung nhìn thứ i( gọi là S[i]) thì S[i+1]=S[i]-a[i-k]+a[i]
Do đó mảng chứa k phần tử liên tiếp =
S[0] =a[0]+…a[k-1]
for i=k to n do
S[i] =S[i-1]+a[i]-a[i-k]
sau đó tính max(S[i])
là dc
#include<iostream>
using namespace std;
void NhapMang(int a[],int n)
{
for(int i = 0; i < n; i++)
{
cout << "a[" << i << "] = " ;
cin >> a[i];
}
}
void XuatMang(int a[],int n)
{
for(int i = 0; i < n; i++)
{
cout <<
a[i] << " ";
}
cout << endl;
}
int TongKPhanTu(int a[],int n,int k)
{
int i = 0;
int S[10];
for(int i = 0 ; i < k ; i++)
{
S[0] += a[i];
}
for(int i = 0 ; i < n - k + 1 ; i++)
{
S[i+1] = S[i] - a[i-1] + a[i+k-1];
}
int Max = S[0];
for(int i = 0 ; i < n - k + 1 ; i++)
{
if(S[i] > Max )
Max = S[i];
}
return Max;
}
int main()
{
int a[100];
int n;
cout << " Nhap n : ";
cin >> n;
NhapMang(a,n);
XuatMang(a,n);
int k = 3;
int max = TongKPhanTu(a,n,k);
cout << max <<endl;
system("pause");
return 0;
}
Mình chỉ nghĩ đc nhiu đây thôi.
Cho mình hỏi tại sao khi mình cout S[0] thì nó lại ra cái số âm linh tinh nhỉ?
Ý bạn muốn tính tổng phần tử liên tiếp?
thì dùng chính cái tổng liên tiếp đó so sánh với tổng liên tiếp khác.
cái nào lớn hơn thì return nó.
mình code php sơ sơ thế này:
function find_max_sum_element($array_input){
// muốn liên tiếp thì phải từ 2 phần tử trở lên.
if (count($array_input) >= 2){
for ($i = 1, $max = $array_input[0] + $array_input[1]; $i < count($array_input); $i++){
if ($max < $array_input[$i] + $array_input[$i+1]){
$max = $array_input[$i] + $array_input[$i+1];
}
}
}
return $max;
}
Đào mộ à Giờ có khi chủ thớt tốt nghiệp rồi
cũng tốt mà bạn, biết đâu có ai đó cũng đang cần. bạn này ra trường lại có bạn khác vào trường mà
Tại sao lại là PHP Trong khi ở trên có thuật toán rõ ràng rồi
Với lại PHP thì cái server chạy à
Mà code cũng lạc đề
a ơi cho e hỏi trong int main lại đặt k = 3 v a hi
k = 3 là ví dụ thôi bạn.
cho minh hỏi nếu ko cho biết trước k thì tính như thế nào ạ?
Công thức không đổi với các k khác nhau nhé. k = 3 là ví dụ thôi.
Đây là chỉ code để đáp ứng yêu cầu đề bài, có thể là chưa tối ưu nhất, mong mọi người góp ý thêm nha
Đây là chỉ code để đáp ứng yêu cầu đề bài, có thể là chưa tối ưu nhất, mong mọi người góp ý thêm nha
int TimMaxSumKphantulientiep(int a[], int n, int k)
{
if (k >= n)
{
cout << "K phai be hon hoac bang n:";
return 0;
}
int MaxSum = 0, Sum = 0; // Max sum là tổng lớn nhất,Sum là tổng của k phần tử liên tiếp
int count; // biến đếm tạm để tí gán bằng k.
int tempI; // biến đếm tạm để tí gán bằng i
for (int i = 0;i < n;i++)
{
count = k; //gán
tempI = i; //gán
Sum = 0; //Reset Sum;
while (count > 0) // thực hiện cộng count lần.. tức là k lần
{
Sum += a[tempI]; //
tempI++; // cộng xong tăng mảng, nhưng chỉ tempI tăng, còn i ở bên ngoài vẫn không tăng
count--; // giảm biến điếm count để có dk thoát while
}
if (Sum > MaxSum ) // nếu tổng phía trên vừa cộng lớn hơn MaxSum
{
MaxSum = Sum; // gán MaxSum = Sum
}
}
return MaxSum;
}
Thật sự bài này vòng while
ko phù hợp vì ta biết trước là lặp k
lần.
Dùng 2 for thì mỗi cặp phần tử liên tiếp sẽ tham gia phép cộng k
lần (và do tính kết hợp) nên ta dùng cửa sổ trượt.
như vầy đúng không anh
lúc đầu ta sẽ xét các mảng con có độ dài k từ vị trí 0 đến vị trí n-k, sau đó ta sẽ tạo ra thêm vòng lập bắt đầu từ vị trí j là vị trí bắt đầu của từng mảng con đến j+k là vị trí kết thúc của từng mảng con, ta sẽ tiến hành tính tổng của từng phần tử trong mảng con và sau khí tính xong sẽ ra ngoài vòng lập so sánh cái nào lớn nhất và lập lại khi chạm đến mảng con cuối cùng, ta sẽ gán max = s và vị trí bằng j từ đó có thể xuất dãy con.
-Phương pháp này còn được gọi là phương pháp vét cạn, nó có thể đc sử dụng để làm những bài nâng cao hơn như tìm dãy con lớn nhất giống bài này nhưng sẽ không có độ dài cố định
void tong_k_lon_nhat(int a[],int n,int k)
{
int vitri=0,max=0,s;
for(int j=0;j<=n-k;j++)
{
s=0;
for(int i=j;i<j+k;i++)
{
s=s+a[j];
}
if(s>max)
{
max=s;
vitri=j;
}
}
for(int q = vitri;q<vitri+k;q++)
{
cout<<a[q]<<" ";
}
}
Mời bạn đọc lại lần nữa.
Sao bạn không thử sắp xếp k phần tử theo thứ tự giảm dần ? Mình nghĩ tổng lớn nhất sẽ là tổng của các phần tử đấy luôn. Tổng lớn nhất là tổng của các phần tử lớn nhất, hợp lý nhỉ ?