คำชี้แจงปัญหา
กำหนดอาร์เรย์ของจำนวนเต็ม ตัวเลข และค่าสูงสุด ภารกิจคือการคำนวณค่าสูงสุดที่จะได้รับจากองค์ประกอบอาร์เรย์ ทุกค่าบนอาร์เรย์ที่ข้ามผ่านจากจุดเริ่มต้นสามารถเพิ่มหรือลบออกจากผลลัพธ์ที่ได้รับจากดัชนีก่อนหน้าได้ ดังนั้น ณ จุดใดๆ ผลลัพธ์ที่ได้จะต้องไม่น้อยกว่า 0 และไม่เกินค่าสูงสุดที่กำหนด สำหรับดัชนี 0 ใช้ผลลัพธ์ก่อนหน้าเท่ากับตัวเลขที่กำหนด กรณีที่ตอบไม่ได้ พิมพ์ -1.
ถ้า arr[] ={3, 10, 6, 4, 5}, จำนวน =1 และค่าสูงสุด =15 ผลลัพธ์จะเป็น 9 หากทำตามลำดับการบวกและการลบด้านล่าง -
1 + 3 + 10 – 6 – 4 + 5
อัลกอริทึม
เราสามารถใช้วิธีเรียกซ้ำเพื่อแก้ปัญหานี้ได้
<ก่อน>1. ที่ตำแหน่งดัชนีทุกตำแหน่ง มีสองทางเลือก ทั้งเพิ่มองค์ประกอบอาร์เรย์ปัจจุบันให้กับค่าที่ได้รับจากองค์ประกอบก่อนหน้า หรือลบองค์ประกอบอาร์เรย์ปัจจุบันออกจากค่าที่ได้รับจนถึงองค์ประกอบก่อนหน้า2 เริ่มจากดัชนี 0 เพิ่มหรือลบ arr[0] จากหมายเลขที่กำหนดและเรียกดัชนีถัดไปซ้ำๆ พร้อมกับหมายเลขที่อัปเดต 3 เมื่อข้ามอาร์เรย์ทั้งหมดแล้ว ให้เปรียบเทียบจำนวนที่อัปเดตกับค่าสูงสุดโดยรวมของตัวเลขที่ได้รับจนถึงตอนนี้ตัวอย่าง
#includeใช้เนมสเปซ std;void getMaxValue(int *arr, int n, int num, int maxLimit, intidx, int&result){ if (idx ==n) { result =max( ผลลัพธ์จำนวน); กลับ; } if (num - arr[idx]>=0) { getMaxValue(arr, n, num - arr[idx], maxLimit, idx + 1, ผลลัพธ์); } if (num + arr[idx] <=maxLimit) { getMaxValue(arr, n, num + arr[idx], maxLimit, idx + 1, ผลลัพธ์); }}int getMaxValue(int *arr, int n, int num, int maxLimit){ ผลลัพธ์ int =0; int idx =0; getMaxValue(arr, n, num, maxLimit, idx, ผลลัพธ์); ส่งคืนผลลัพธ์;}int main(){ int num =1; int arr[] ={3, 10, 6, 4, 5}; int n =sizeof(arr) / sizeof(arr[0]); int maxLimit =15; cout <<"ค่าสูงสุด =" < ผลลัพธ์
เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ดังต่อไปนี้−
ค่าสูงสุด =9
