C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++のパーフェクトスクエア

正の整数nがあると仮定して、合計がnである完全な平方数の最小数を見つけます。したがって、数値が13の場合、数値は13 =9 + 4であるため、出力は2になります。

これを解決するには、次の手順に従います-

  • 動的計画法用に長さn+1のテーブルを1つ作成し、それを無限大で埋めます
  • dp [0]：=0
  • for i：=1、when i * i <=n
    • x =i * i
    • for j：=x to n
      • dp [j]：=最小のdp[j]および1+ dp [j – x]
  • return dp [n]

理解を深めるために、次の実装を見てみましょう-

例

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
   public:
   int numSquares(int n) {
      vector < int > dp(n+1,INF);
      dp[0] = 0;
      for(int i =1;i*i<=n;i++){
         int x = i*i;
         for(int j = x;j<=n;j++){
            dp[j] = min(dp[j],1+dp[j-x]);
         }
      }
      return dp[n];
   }
};
main(){
   Solution ob;
   cout << (ob.numSquares(147));
}

入力

147

出力

3

  1. C++で長方形の正方形の数を数える

    =Bとなるように、長さL、幅Bの長方形が与えられます。目標は、サイズLXBの長方形が収容できる正方形の数を見つけることです。 上の図は、サイズ3 X 2の長方形を示しています。2、2X2の正方形、6,1X1の正方形があります。 総正方形=6+ 2=8。 サイズLXBのすべての長方形には、1X1の正方形のL*B数があります。 最大の正方形のサイズはBXBです。 L =B =1の場合、正方形=1。 L =B =2の場合、正方形=1 + 4 =5（2X2の1、1X1の4） L =B =3の場合、正方形=1 + 4 + 9 =14（3X3の​​1、2X2の4、1

  2. C++でボードを正方形にカットするための最小コスト

    コンセプト 長さp、幅qのボードが与えられたとすると、破壊のコストが最小になるように、このボードをp*qの正方形に分割する必要があります。このボードでは、各エッジの切削コストが示されます。一言で言えば、コストが最小になるように、このような一連の切断を選択する必要があります。 例 上記のボードに関して、正方形にカットする最適な方法は-です。 上記の場合の合計最小コストは65です。これは、次の手順を実行して計算され、評価されます。 Initial Value : Total_cost = 0 Total_cost = Total_cost + edge_cost * total_pi