C++ ค้นหาปัจจัยสี่ตัวของ N โดยมีผลคูณสูงสุดและผลรวมเท่ากับ N

แนวคิด

ด้วยความเคารพของจำนวนเต็ม N ที่กำหนด งานของเราคือการกำหนดปัจจัยทั้งหมดของ N พิมพ์ผลคูณของปัจจัยสี่ของ N เพื่อให้ -

• ผลรวมของปัจจัยสี่มีค่าเท่ากับ N
• ผลคูณของปัจจัยทั้งสี่มีค่ามากที่สุด

จะเห็นได้ว่าหากไม่สามารถหาปัจจัยดังกล่าวได้ 4 ประการ ให้พิมพ์ว่า "เป็นไปไม่ได้"

ควรสังเกตว่าปัจจัยทั้งสี่สามารถเท่ากันเพื่อเพิ่มผลิตภัณฑ์ให้สูงสุด

อินพุต

24

ผลลัพธ์

All the factors are -> 1 2 4 5 8 10 16 20 40 80
Product is -> 160000

เลือกตัวประกอบ 20 สี่ครั้ง

ดังนั้น 20+20+20+20 =24 และผลิตภัณฑ์สูงสุด

วิธีการ

ต่อไปนี้เป็นขั้นตอนวิธีทีละขั้นตอนในการแก้ปัญหานี้ -

• ขั้นแรกให้กำหนดตัวประกอบของตัวเลข 'N' โดยไปที่ 1 ถึงสแควร์รูทของ 'N' และตรวจสอบว่า 'i' และ 'n/i' หาร N และเก็บไว้ในเวกเตอร์หรือไม่
• ตอนนี้เราจัดเรียงเวกเตอร์และพิมพ์ทุกองค์ประกอบ
• กำหนดตัวเลขสามตัวเพื่อเพิ่มผลผลิตสูงสุดด้วยตัวเลขที่สี่ โดยใช้สามลูป
• สุดท้าย เราจะแทนที่ผลิตภัณฑ์สูงสุดถัดไปด้วยผลิตภัณฑ์ก่อนหน้า
• พิมพ์ผลิตภัณฑ์เมื่อพบปัจจัยสี่ประการ

ตัวอย่าง

// C++ program to find four factors of N
// with maximum product and sum equal to N
#include <bits/stdc++.h>
using namespace std;
// Shows function to find factors
// and to print those four factors
void findfactors2(int n1){
   vector<int> vec2;
   // Now inserting all the factors in a vector s
   for (int i = 1; i * i <= n1; i++) {
      if (n1 % i == 0) {
         vec2.push_back(i);
         vec2.push_back(n1 / i);
      }
   }
   // Used to sort the vector
   sort(vec2.begin(), vec2.end());
   // Used to print all the factors
   cout << "All the factors are -> ";
   for (int i = 0; i < vec2.size(); i++)
      cout << vec2[i] << " ";
      cout << endl;
      // Now any elements is divisible by 1
      int maxProduct2 = 1;
      bool flag2 = 1;
      // implementing three loop we'll find
      // the three maximum factors
      for (int i = 0; i < vec2.size(); i++) {
         for (int j = i; j < vec2.size(); j++) {
            for (int k = j; k < vec2.size(); k++) {
               // Now storing the fourth factor in y
               int y = n1 - vec2[i] - vec2[j] - vec2[k];
            // It has been seen that if the fouth factor become negative
            // then break
            if (y <= 0)
               break;
            // Now we will replace more optimum number
            // than the previous one
            if (n1 % y == 0) {
               flag2 = 0;
               maxProduct2 = max(vec2[i] * vec2[j] * vec2[k] *y,maxProduct2);
            }
         }
      }
   }
   // Used to print the product if the numbers exist
   if (flag2 == 0)
     cout << "Product is -> " << maxProduct2 << endl;
   else
      cout << "Not possible" << endl;
}
// Driver code
int main(){
   int n1;
   n1 = 80;
   findfactors2(n1);
   return 0;
}

ผลลัพธ์

All the factors are -> 1 2 4 5 8 10 16 20 40 80
Product is -> 160000