ลดผลรวมรากของพหุนามให้น้อยที่สุดใน C++

ได้รับอาร์เรย์สัมประสิทธิ์พหุนาม ขนาด n (ชั้น = n-1) จัดเรียงสัมประสิทธิ์ใหม่เพื่อให้ผลรวมราก (sum of roots) น้อยที่สุด โดยใช้สูตร Vieta: ผลรวมราก = -a_{n-1} / a_n

ตัวอย่าง

Input: arr[] = {2, -1, 4, 9, -1, 10, -5}

Output: Minimize the sum of roots of a given polynomial is: -1 -5 2 4 9 -1 10

คำอธิบาย: พหุนามชั้น 6: -1x⁶ -5x⁵ + 2x⁴ + 4x³ + 9x² -1x + 10 → ผลรวมราก = -(-5)/(-1) = -5 (น้อยที่สุด)

Input: arr[] = {3, -2, -1, 4}

Output: Minimize the sum of roots of a given polynomial is: -1 -2 3 4

คำอธิบาย: พหุนามชั้น 3: -1x³ -2x² + 3x + 4 → ผลรวมราก = -(-2)/(-1) = -2

อัลกอริทึม

• แยก index ของค่าบวก (vec_2) และค่าลบ (vec_3)
• ถ้าทั้งสองมี ≥ 2 ตัว:
  • หา max/min ของค่าบวก (max_val, min_val) และ max/min ของ |ค่าลบ| (N_max, N_min)
  • คำนวณ vec_2_data = -max_val/min_val, vec_3_data = -N_max/N_min
  • เลือกคู่ที่ให้ค่าน้อยกว่า (น้อยกว่า → sum of roots น้อยกว่า) วางไว้ 2 ตำแหน่งแรก ต่อด้วยที่เหลือ
• ถ้ามีแค่ค่าบวก ≥ 2: ใช้คู่ max/min ของค่าบวก
• ถ้ามีแค่ค่าลบ ≥ 2: ใช้คู่ max/min ของ |ค่าลบ|
• มิฉะนั้น → Not Possible

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void Minimize_root(int arr[], int size) {
    vector<int> vec_1, vec_2, vec_3;
    for (int i = 0; i < size; i++) {
        if (arr[i] > 0) vec_2.push_back(i);
        else if (arr[i] < 0) vec_3.push_back(i);
    }
    int vec_2_size = vec_2.size(), vec_3_size = vec_3.size();
    if (vec_2_size >= 2 && vec_3_size >= 2) {
        int max_val = INT_MIN, temp = -1, min_val = INT_MAX, temp_2 = -1;
        int N_max = INT_MIN, N_temp = -1, N_min = INT_MAX, N_temp_2 = -1;
        for (int i = 0; i < vec_2.size(); i++)
            if (arr[vec_2[i]] > max_val) { temp = vec_2[i]; max_val = arr[temp]; }
        for (int i = 0; i < vec_2.size(); i++)
            if (arr[vec_2[i]] < min_val && vec_2[i] != temp) { temp_2 = vec_2[i]; min_val = arr[temp_2]; }
        for (int i = 0; i < vec_3.size(); i++)
            if (abs(arr[vec_3[i]]) > N_max) { N_temp = vec_3[i]; N_max = abs(arr[N_temp]); }
        for (int i = 0; i < vec_3.size(); i++)
            if (abs(arr[vec_3[i]]) < N_min && vec_3[i] != N_temp) { N_temp_2 = vec_3[i]; N_min = abs(arr[N_temp_2]); }
        double vec_2_data = -1.0 * max_val / min_val;
        double vec_3_data = -1.0 * N_max / N_min;
        if (vec_2_data < vec_3_data) {
            vec_1.push_back(arr[temp_2]); vec_1.push_back(arr[temp]);
            for (int i = 0; i < size; i++) if (i != temp_2 && i != temp) vec_1.push_back(arr[i]);
        } else {
            vec_1.push_back(arr[N_temp_2]); vec_1.push_back(arr[N_temp]);
            for (int i = 0; i < size; i++) if (i != N_temp_2 && i != N_temp) vec_1.push_back(arr[i]);
        }
        for (int v : vec_1) cout << v << " ";
    } else if (vec_2_size >= 2) {
        // ... คล้ายกันแต่ใช้ค่าบวกอย่างเดียว
    } else if (vec_3_size >= 2) {
        // ... คล้ายกันแต่ใช้ค่าลบอย่างเดียว
    } else {
        cout << "Not Possible";
    }
}

int main() {
    int arr[] = {2, -1, 4, 9, -1, 10, -5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimize the sum of roots of a given polynomial is: ";
    Minimize_root(arr, size);
    return 0;
}

ผลลัพธ์

Minimize the sum of roots of a given polynomial is: -1 -5 2 4 9 -1 10