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

完全な平方の数を数えるプログラムが追加され、C++で数を形成します

正の数nがあるとすると、合計がnと同じである完全な平方数の最小数を見つける必要があります。したがって、数値が10の場合、数値は10 =9 + 1であるため、出力は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 solve(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.solve(10);
}

入力

10

出力

2

  1. サイズdで作成できる十二角形の数をカウントするC++プログラム

    数dがあるとします。正方形のタイルと辺の長さが1の通常の三角形のタイルが無数にあると考えてください。これらのタイルを使用して、側面dの通常の十二角形（12辺の多角形）を形成できる方法をいくつ見つける必要があります。答えが大きすぎる場合は、結果mod998244353を返します。 ステップ これを解決するために、次の手順に従います- b := floor of d/2 - 1 c := 1 for initialize i := 2, when i < d, update (increase i by 1), do:    b := b * (floor of

  2. 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