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

C++は数値を2つの分割可能な部分に分割します


この問題では、数値として解釈できる文字列が与えられます。次に、最初の部分がAで割り切れ、2番目の部分がBで割り切れる(2つの整数が与えられる)ように、文字列を2つの部分に分割する必要があります。例-

Input : str = "123", a = 12, b = 3
Output : YES
12 3
"12" is divisible by a and "3" is
divisible by b.

Input : str = "1200", a = 4, b = 3
Output : YES
12 00

Input : str = "125", a = 12, b = 3
Output : NO

この問題では、プログラムを高速化するための事前計算を実行します。これにより、より高い制約に対応できるようになります。

解決策を見つけるためのアプローチ

このアプローチでは、文字列を介して2つのループを実行します。最初は最初から最後まで、2番目は最後から最初までです。これで、すべてのポイントで、最初のループでaを使用し、2番目のループでbを使用して形成された整数のmodを取得すると、答えを見つけることができます。

#include <bits/stdc++.h>
using namespace std;
void divisionOfString(string &str, int a, int b){
    int n = str.length();
    vector<int> mod_a(n+1, 0); //
    mod_a[0] = (str[0] - '0')%a;
    for (int i=1; i<n; i++) // front loop for calculating the mod of integer with a
        mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a;
    vector<int> mod_b(n+1, 0);
    mod_b[n-1] = (str[n-1] - '0')%b;
    int power10 = 10; // as we have assigned answer to last index
    for (int i= n-2; i>=0; i--){ // end loop for calculating the mod of integer with b
        mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10)%b;
        power10 = (power10 * 10) % b;
    }
    for (int i=0; i<n-1; i++){ // finding the division point
        if (mod_a[i] != 0) // we can skip through all the positions where mod_a is not zero
            continue;
        if (mod_b[i+1] == 0){ // now if the next index of mod_b is also zero so that is our division point
            cout << "YES\n";
            /*******Printing the partitions formed**********/
            for (int k=0; k<=i; k++)
               cout << str[k];
            cout << " ";
            for (int k=i+1; k < n; k++)
               cout << str[k];
            return;
        }
    }
    cout << "NO\n"; // else we print NO
}
// Driver code
int main(){
    string str = "123"; // given string
    int a = 12, b = 3;
    divisionOfString(str, a, b);
    return 0;
}

出力

YES
12 3

上記のコードの説明

このアプローチでは、現在すべての部門で形成されている数の余りを計算しました。最初の数値はaで割り切れるはずなので、順方向ループを実行し、その数値のmodをaで格納します。 bを使用すると、逆方向ループを実行してmodを格納します。これは、任意の位置にあるaのmodがゼロで、次のインデックスを持つbのmodがゼロの場合、それが答えになるため、出力します。

結論

このチュートリアルでは、問題を解決して、数値を2つの分割可能な部分に分割します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ(通常)についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。


  1. C++でセットをk個のサブセットに分割する方法の数を数えます

    与えられた2つの数字eとp。目標は、セットのe個の要素をp個のパーティション/サブセットに分割できる方法の数を数えることです。 例 入力 e=4 p=2 出力 Count of number of ways to partition a set into k subsets are: 7 説明 If elements are: a b c d then ways to divide them into 2 partitions are: (a,b,c)−(d), (a,b)−(c,d), (a,b,c)−(d), (a)−(b,c,d), (

  2. C++で多数が15で除算可能かどうかを確認します

    ここでは、数値が15で割り切れるかどうかを確認する方法を説明します。この場合、その数は非常に多い数です。したがって、数値を文字列として入力します。 数値が15で割り切れるかどうかを確認するには、数値が5で割り切れるか、3で割り切れるかを確認します。したがって、5で割り切れるかどうかを確認するには、最後の数値が0または5であるかどうかを確認する必要があります。桁の合計が3で割り切れるかどうかを確認してください。 例 #include <bits/stdc++.h> using namespace std; bool isDiv15(string num){