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

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.

1 Like

Gợi ý: k phần tử liên tiếp bắt đầu từ vị trí i đến i+k-1 :wink: 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

3 Likes

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 :smile:

2 Likes

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

7 Likes
#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ỉ?

3 Likes

Ý 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;
}
1 Like

Đào mộ à :joy_cat: Giờ có khi chủ thớt tốt nghiệp rồi

2 Likes

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à :slight_smile:

Tại sao lại là PHP :joy: 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 à :smiley:

Mà code cũng lạc đề :slight_smile:

2 Likes

a ơi cho e hỏi trong int main lại đặt k = 3 v a hi :sweat_smile:

k = 3 là ví dụ thôi bạn.

5 Likes

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.

2 Likes

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

4 Likes

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.

à nhầm s=s+a[i] mới đúng :slightly_smiling_face:
tested & working

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

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?