โจทย์ C++ Sum Array Puzzle

อาร์เรย์ (Array) คือโครงสร้างข้อมูลที่เก็บสมาชิกหลายตัวที่มีชนิดข้อมูลเดียวกัน สามารถเก็บชุดค่าได้ครั้งเดียว แต่ต้องกำหนดความยาวล่วงหน้า

ในโจทย์ Sum Array Puzzle เราได้รับอาร์เรย์ A1 ขนาด n สร้างอาร์เรย์ S1 ที่เก็บผลรวมของสมาชิกทั้งหมดใน A1 ยกเว้น สมาชิกที่อยู่ตำแหน่งเดียวกัน ตัวอย่างเช่น ถ้าคำนวณ S1[3] จะหาผลรวมของทุกสมาชิกใน A1 ยกเว้นสมาชิกตำแหน่ง 4

ตัวอย่าง

Array A1 = {1,2,3,4,6} Output S1 = {15,14,13,12,10}

คำอธิบาย — คำนวณอาร์เรย์ผลรวมโดยบวกสมาชิกทั้งหมดของอาร์เรย์ต้นทาง ยกเว้นค่าที่มีดัชนีตรงกัน สำหรับสมาชิกแรกของอาร์เรย์ผลรวม จะคำนวณผลรวมของทุกสมาชิกยกเว้นสมาชิกแรกของอาร์เรย์ และทำเช่นนี้ทุกตำแหน่ง

Sum[0] = 2+3+4+6 = 15
Sum[1] = 1+3+4+6 = 14
Sum[2] = 1+2+4+6 = 13
Sum[3] = 1+2+3+6 = 12
Sum[4] = 1+2+3+4 = 10

อาร์เรย์ผลรวมคือ {15,14,13,12,10}

อัลกอริทึม

ขั้นตอนที่ 1: กำหนดอาร์เรย์ผลรวม sum[n] = 0 โดย n = ขนาดอาร์เรย์ต้นทาง
ขั้นตอนที่ 2: วนลูป sum[] และทำ:
    ขั้นตอนที่ 2.1: สำหรับ sum[i] วนลูป j จาก 0 ถึง n
    ขั้นตอนที่ 2.2: ถ้า (i != j) { sum[i] += arr[j] }
ขั้นตอนที่ 3: พิมพ์อาร์เรย์ผลรวม

ตัวอย่างโค้ด (วิธีมีประสิทธิภาพมากกว่า)

#include <iostream>
using namespace std;

int main() {
    int arr[] = { 3, 6, 4, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int leftSum[n], rightSum[n], Sum[n], i, j;
    leftSum[0] = 0;
    rightSum[n - 1] = 0;
    cout<<"The original array is : \n";
    for (i = 0; i < n; i++)
        cout << arr[i] << " ";
    for (i = 1; i < n; i++)
        leftSum[i] = arr[i - 1] + leftSum[i - 1];
    for (j = n - 2; j >= 0; j--)
        rightSum[j] = arr[j + 1] + rightSum[j + 1];
    for (i = 0; i < n; i++)
        Sum[i] = leftSum[i] + rightSum[i];
    cout<<"\nThe sum array is : \n";
    for (i = 0; i < n; i++)
        cout << Sum[i] << " ";
    return 0;
}

ผลลัพธ์

The original array is : 3 6 4 8 9
The sum array is : 27 24 26 22 21