Cho một mảng arr [] chỉ chứa các số nguyên và một tổng số lẻ. Mục đích là tạo một mảng tổng arr_2 [] sao cho mỗi arr_2 [i] là tổng của tổng trước / 2 phần tử của arr [] + arr [i] + tổng tiếp theo / 2 phần tử của arr []. Nếu tổng là 1 thì arr_2 [i] =arr [i]
Ví dụ
Đầu vào
arr[] = { 4, 1, 7, 5, 2, 9} sum=3 Đầu ra
Construction of sum-array with sum of elements in given range are: 5 12 13 14 16 17 17 9 3
Giải thích
The sum array is constructed as: arr_2[0]=arr[0]+arr[1] = 4+1 = 5 arr_2[1]=arr[0]+arr[1]+arr[2] = 4+1+7 = 12 arr_2[2]=arr[1]+arr[2]+arr[3] = 1+7+5 = 13 arr_2[3]=arr[2]+arr[3]+arr[4] = 7+5+2 = 14 arr_2[4]=arr[3]+arr[4]+arr[5] = 5+2+9 = 16 arr_2[5]=arr[4]+arr[5] = 2+9 = 11s
Đầu vào
arr[] = { 1,2,3,4,5 } sum=5 Đầu ra
Construction of sum-array with sum of elements in given range are − 6 10 15 14 12
Giải thích
The sum array is constructed as: arr_2[0]=arr[0]+arr[1]+arr[2] = 1+2+3 = 6 arr_2[1]=arr[0]+arr[1]+arr[2]+arr[3] = 1+2+3+4= 10 arr_2[2]=arr[0]+arr[1]+arr[2]+arr[3]+arr[4] = 1+2+3+4+5 = 15 arr_2[3]=arr[1]+arr[2]+arr[3]+arr[4] = 2+3+4+5= 14 arr_2[4]=arr[2]+arr[3]+arr[4]= 3+4+5 = 12
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -
Trong cách tiếp cận này, chúng tôi sẽ sử dụng khái niệm cửa sổ trượt. Thêm phần tử ngoài cùng bên phải tiếp theo vào tổng cửa sổ trước đó và xóa phần tử ngoài cùng bên trái khỏi đó.
-
Lấy một mảng số nguyên arr [] và một tổng giá trị làm đầu vào.
-
Hàm sum_array (int arr [], int size, int sum) trả về mảng tổng với tổng các phần tử trong dải ô đã cho.
-
Lấy số lượng ban đầu là 0.
-
Lấy mảng tổng là arr_2 [size].
-
Lấy tạm thời =sum / 2 + 1.
-
Thêm tạm thời số phần tử từ 0 đến tạm thời để đếm. Và đặt arr_2 [0] làm số đếm.
-
Đối với các phần tử tiếp theo của mảng tổng, hãy duyệt qua bằng vòng lặp for từ i =1 đến i
-
Lấy temp_1 =i - (sum / 2) - 1. Nếu nó> =0 thì lấy số đếm trừ arr [temp_1].
-
Lấy temp_2 =i + (sum / 2). Nếu là
-
Đặt arr_2 [i] =count.
-
Ở cuối vòng lặp for, chúng ta sẽ có arr_2 [] là một mảng tổng.
-
In mảng tổng arr_2 [] bằng vòng lặp for.
Ví dụ
#include <bits/stdc++.h>
using namespace std;
void sum_array(int arr[], int size, int sum){
int count = 0;
int arr_2[size];
int temp = sum / 2 + 1;
for (int i = 0; i < temp; i++){
count = count + arr[i];
}
arr_2[0] = count;
for (int i = 1; i < size; i++){
int temp_1 = i − (sum / 2) − 1;
if (temp_1 >= 0){
count = count − arr[temp_1];
}
int temp_2 = i + (sum / 2);
if (temp_2 < size){
count = count + arr[temp_2];
}
arr_2[i] = count;
}
cout<<"Construction of sum−array with sum of elements in given range are: ";
for (int i = 0; i < size; i++){
cout<< arr_2[i] << " ";
}
}
int main(){
int arr[] = { 4, 1, 7, 5, 2, 9, 6, 2, 1 };
int sum = 3;
int size = sizeof(arr) / sizeof(int);
sum_array(arr, size, sum);
return 0;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Construction of sum-array with sum of elements in given range are − 5 12 13 14 16 17 17 9 3