Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++의 가장 가까운 약수

<시간/>

정수 num이 있다고 가정하고 곱이 num + 1 또는 num + 2와 같은 절대 차이에서 가장 가까운 두 정수를 찾아야 합니다. 두 정수를 임의의 순서로 찾아야 합니다. 따라서 입력이 8이면 출력은 [3, 3]이 되고 num + 1의 경우 9가 되고 가장 가까운 제수는 3과 3이 되고 num + 2 =10의 경우 가장 가까운 제수는 2와 5가 됩니다. , 따라서 3과 3이 선택됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • getDiv()라는 메서드를 정의하면 x가 입력으로 사용됩니다.

  • diff :=무한대, 크기가 2인 ret라는 배열을 만듭니다.

  • i의 경우 :=1, i^2 <=x이면 i를 1만큼 증가

    • x가 i로 나누어 떨어지면

      • a :=나는

      • b :=x / i

      • newDiff :=|a – b|

      • newDiff

        • diff :=newDiff

        • ret[0] :=a 및 ret[1] :=b

  • 리턴 렛

  • 기본 방법에서 op1 :=getDiv(num + 1) 및 op2 :=getDiv(num + 2)

    를 찾습니다.
  • |op1[0] – op[1]|일 때 op1을 반환합니다. <=|op2[0] – op2[1]|, 그렇지 않으면 op2

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector <int> getDiv(int x){
      int diff = INT_MAX;
      vector <int> ret(2);
      for(int i = 1; i * i <= x; i++){
         if(x % i == 0){
            int a = i;
            int b = x / i;
            int newDiff = abs(a - b);
            if(newDiff < diff){
               diff = newDiff;
               ret[0] = a;
               ret[1] = b;
            }
         }
      }
      return ret;
   }
   vector<int> closestDivisors(int num) {
      vector <int> op1 = getDiv(num + 1);
      vector <int> op2 = getDiv(num + 2);
      return abs(op1[0] - op1[1]) <= abs(op2[0] - op2[1]) ? op1 : op2;
   }
};
main(){
   Solution ob;
   print_vector(ob.closestDivisors(8));
}

입력

8

출력

[3,3]