ในปัญหานี้ เราต้องหาวิธีที่ถูกต้องในการย้ายทิศทางบวกหรือลบในทิศทางที่เราอยู่ภายในขอบเขตที่กำหนดโดยผู้ใช้
ที่นี่ เราได้รับขีด จำกัด สูงสุด K ซึ่งเป็นค่าสูงสุดที่เราสามารถย้ายได้และอาร์เรย์ของค่าบวก n ค่าที่จะย้าย เราต้องส่งคืนลำดับนั่นคือทิศทางบวกหรือลบเพื่อย้ายเพื่อไม่ให้ข้ามค่า K
มาดูตัวอย่างเพื่อทำความเข้าใจหัวข้อกันดีกว่า
Input : K = 56 and the array is [25 , 14 , 31 , 16 , 5]. Output : positive positive negative positive positive.
คำอธิบาย
ก่อนอื่นเราจะตรวจสอบว่า 0 + a[0] =0+25 =25 <56 ใช่หรือไม่ จากนั้นเราจะไปในทิศทางบวก
ตอนนี้เราจะตรวจสอบว่า 25 + a[1] =25+14 =39 <56 ใช่หรือไม่ จากนั้นเราจะไปในทิศทางบวก
ตอนนี้เราจะตรวจสอบว่า 29 + a[2] =39+31 =70 <56 ไม่ จากนั้นเราจะตรวจสอบว่า 39 - a[2] =39 - 31 =8> 0 หรือไม่ จากนั้นเราจะไปในทิศทางลบ .
เราจะตรวจสอบว่า 8 + a[3] =8+16 =24 <56 ใช่หรือไม่ จากนั้นเราจะไปในทิศทางบวก
เราจะตรวจสอบว่า 16 + a[4] =16 + 5 =21 <56 ใช่หรือไม่ จากนั้นเราจะไปในทิศทางบวก
ตอนนี้ มาสร้างตรรกะเพื่อแก้ปัญหานี้กัน เราต้องตรวจสอบว่าการเคลื่อนไปในทิศทางบวกจะถึงขีด จำกัด หรือไม่ ถ้าไม่ใช่ ก็ไปในทางบวก มิฉะนั้น ให้ตรวจสอบว่าการเคลื่อนไปในทิศทางลบจะถึงขีด จำกัด ล่างเช่น 0 หรือไม่ ถ้าไม่ใช่ ให้เคลื่อนที่ไปในทิศทางลบ หากใช่ทั้งคู่ จะไม่สามารถคืนสินค้าได้
จากตรรกะนี้ อัลกอริทึมที่เราต้องปฏิบัติตามเพื่อสร้างโค้ดของเราคือ −
อัลกอริทึม
Initially set position to 0. Step 1 : for i -> 0 to n , n is the length of array. Follow step 2 - 4. Step 2 : if initial_postition + a[i] < K, initial_position + = a[i]. Print “POSITIVE”. Step 3 : else if initial_postition - a[i] > 0, initial_position - = a[i]. Print “NEGATIVE”. Step 4 : else , print “NO MORE VALID MOVES”.
ตัวอย่าง
คราวนี้มาสร้างโปรแกรมแสดงการนำอัลกอริธึมมาใช้ในการแก้ปัญหา
#include <iostream>
using namespace std;
void StepsTaken(int a[], int n, int k){
string res = "";
int position = 0;
int steps = 1;
for (int i = 0; i < n; i++) {
if (position + a[i] <= k && position + a[i] >= (-k)) {
position += a[i];
cout<<"POSITIVE \t";
}
else if (position - a[i] >= -k && position - a[i] <= k) {
position -= a[i];
cout<<"NEGATIVE \t";
} else {
cout << -1;
return;
}
}
cout << res;
}
int main(){
int a[] = { 12 , 24 , 9 , 17 , 8};
int n = sizeof(a) / sizeof(a[0]);
int k = 40;
StepsTaken(a, n, k);
return 0;
} ผลลัพธ์
POSITIVE POSITIVE NEGATIVE NEGATIVE POSITIVE
