กำหนดอาร์เรย์ arr[ ] ที่มีเฉพาะจำนวนเต็มและผลรวมเลขคี่ เป้าหมายคือการสร้างอาร์เรย์ผลรวม arr_2[ ] แต่ละองค์ประกอบ arr_2[i] คือผลรวมขององค์ประกอบ sum/2 ก่อนหน้าของ arr[] + arr[i] + องค์ประกอบ sum/2 ถัดไปของ arr[] ถ้าผลรวมเป็น 1 แล้ว arr_2[i]=arr[i]
ตัวอย่าง
อินพุต
arr[] = { 4, 1, 7, 5, 2, 9} sum=3 ผลลัพธ์
Construction of sum-array with sum of elements in given range are: 5 12 13 14 16 17 17 9 3
คำอธิบาย
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
อินพุต
arr[] = { 1,2,3,4,5 } sum=5 ผลลัพธ์
Construction of sum-array with sum of elements in given range are − 6 10 15 14 12
คำอธิบาย
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
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
ในแนวทางนี้ เราจะใช้แนวคิดหน้าต่างบานเลื่อน เพิ่มองค์ประกอบที่อยู่ขวาสุดถัดไปให้กับผลรวมของหน้าต่างก่อนหน้า และลบองค์ประกอบที่อยู่ซ้ายสุดออกจากสิ่งนั้น
-
ใช้อาร์เรย์จำนวนเต็ม arr[] และผลรวมของค่าเป็นอินพุต
-
ฟังก์ชัน sum_array(int arr[], int size, int sum) คืนค่า sum-array พร้อมผลรวมขององค์ประกอบในช่วงที่กำหนด
-
นับเริ่มต้นเป็น 0
-
ใช้อาร์เรย์ผลรวมเป็น arr_2[ขนาด].
-
ใช้ temp =sum / 2 + 1
-
เพิ่มจำนวนชั่วคราวขององค์ประกอบตั้งแต่ 0 ถึง temp เพื่อนับ และกำหนดให้ arr_2[0] เป็นจำนวน
-
สำหรับองค์ประกอบถัดไปของอาร์เรย์ผลรวม ให้ใช้ for loop จาก i=1 ถึง i
-
ใช้ temp_1 =i − (sum / 2) − 1. หากเป็น>=0 ให้ลบ arr[temp_1] ออกจากการนับ
-
ใช้ temp_2 =i + (ผลรวม / 2) ถ้าเป็น
-
ตั้งค่า arr_2[i] =นับ
-
ในตอนท้ายของ for loop เราจะมี arr_2[] เป็นอาร์เรย์ผลรวม
-
พิมพ์ผลรวมอาร์เรย์ arr_2[] โดยใช้ for loop
ตัวอย่าง
#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;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Construction of sum-array with sum of elements in given range are − 5 12 13 14 16 17 17 9 3
