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

Xの特定のAおよびBに対するXの可能な最小の正の整数値=C++のP*A + Q * B

問題の説明

AとBの値が与えられた場合、方程式X =P * A + Q * Bで達成できるXの最小の正の整数値を見つけます。ここで、PとQはゼロ、または任意の正または負の整数にすることができます。

例

A=2およびB=4の場合、答えは2になります。

アルゴリズム

  • P * A> P*BおよびP*A – P*Bが最小の正の整数になるようにPとQを見つける必要があります。
  • この問題は、両方の数値のGCDを計算することで簡単に解決できます）

例

#include <iostream>
using namespace std;
int getGcd(int a, int b) {
   if (a == 0) {
      return b;
   }
   return getGcd(b % a, a);
}
int main() {
   cout << "Answer = " << getGcd(2, 4) << endl;
   return 0;
}

出力

上記のプログラムをコンパイルして実行する場合。次の出力を生成します-

Answer = 2

  1. C++で可能なすべてのサブアレイの中で可能な最小LCMおよびGCD

    サイズNの配列arrがあるとします。これにはN個の正の数があります。考えられるすべてのサブアレイの最小要素を見つける必要があります。アレイが{2、66、14、521}であり、最小LCMが2、GCDが1であるとします。 貪欲なアプローチを使用してこの問題を解決します。要素の数を減らすとLCMが少なくなり、配列サイズを増やすとGCDが少なくなります。配列から最小の要素を見つける必要があります。これは単一の要素であり、LCMが必要になります。 GCDの場合、GCDはアレイのすべての要素のGCDになります。 例 #include <iostream> #include <algor

  2. Cで割り切れる最大の正の整数であり、C ++では[A、B]の範囲にあります

    ここで、1つの興味深い問題が発生します。 3つの整数A、B、およびCがあると考えてみましょう。XmodC =0であり、Xが[A、B]の範囲にないように、1つの最小整数Xを見つける必要があります。 A、B、Cの値がそれぞれ5、10、4の場合、Xの値は4になります。解を得るには、次の手順に従う必要があります- 手順- Cが[A、B]の範囲にない場合は、結果としてCを返します それ以外の場合は、Bより大きいCの最初の倍数を取得し、その値を返します 例 #include <iostream> using namespace std; int findMinMumber(