c++ - C++ で文字配列の減算の結果を返す

Question

各 ASCII 文字が 10 進数として扱われる文字列を減算しようとしています。例えば：

"1000000000001" - "0100000000001" = "900000000000"

関数プロトタイプが次のようになっている場合、これの実装をどのように開始しますか。

char* get_sub(char* a, char* b)

Answer 1

小学校であるAlgorithms001クラスで大きな数の減算を行う方法を覚えておいてください。両方の数値の最下位桁を減算し、0より小さい場合は10を加算し、キャリーを覚えて、次の桁のペアに進みます。

Answer 2

そうは思えませんが、かなり複雑な問題です (私が年を取りすぎていない限り)。これは でのみ機能しNます。したがって、それは真実でなければなりませんa >= 0, b >= 0, a >= b。それがどのように機能するかは説明しません。私が書いたように、それは非常に複雑です:-) (そして、私は自分が書いたものに満足していません.私が考えていなかった何かがあると確信しています)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* get_sub(const char* a, const char* b);

#define MAX(a, b) (((a) > (b)) ? (a) : (b))

int main(int argc, char* argv[])
{
    char *res = get_sub("10000","9999");
    printf("%s\n", res);
    free(res);
    return 0;
}

char* get_sub(const char* a, const char* b)
{
    size_t a1len = strlen(a);
    size_t a2len = strlen(b);

    size_t max = MAX(a1len, a2len);

    /* I'm using calloc to make it easier to debug. You could use malloc, but you'll have to uncomment a line below */
    char *res = (char*)calloc(max + 1, sizeof(char));

    int carry = 0;

    char *pres = res;
    for (const char *pa = a + a1len - 1, *pb = b + a2len - 1; pa >= a || pb >= b; pa--, pb--, pres++)
    {
        int val1 = pa >= a ? (*pa - '0') : 0;
        int val2 = pb >= b ? (*pb - '0') : 0;

        int diff = val1 - carry - val2;

        if (diff >= 0)
        {
            *pres = (char)(diff + '0');
            carry = 0;
        }
        else
        {
            *pres = (char)(10 + diff + '0');
            carry = 1;
        }
    }

    if (carry != 0)
    {
        free(res);
        return (char*)calloc(1, 1);
    }

    /* *pres = '\0'; */ /* Uncomment this line to use malloc */

    pres--;

    while (pres > res && *pres == '0')
    {
        *pres = '\0';
        pres--;
    }

    strrev(res);

    return res;
}

Answer 3

これはC++ ソリューションの足場であり、問​​題を解決するものではありませんが、かなり単純な実装に必要な言語のいじくり回しを提供します。数字を逆方向に反復し、両方の数字にゼロ以外の数字がある場合は 1 を、それ以外の場合は 0 を含む結果を構築します。

#include <string>
#include <iostream>

using namespace std;

// For a more circumspect treatment of the digit/char conversion, read up:
// http://stackoverflow.com/questions/439573/how-to-convert-a-single-char-into-an-int

char charFromDigit(int d) {
    return d + '0';
}

int digitFromChar(char c) {
    return c - '0';
}

// all this routine does is iterate backward through the digits of both
// numbers and build up a result which has a 1 digit if both numbers are
// non-zero for that place value, and a 0 digit if they're both 0

string get_something(const string& a, const string& b) {

    // get reverse ("r"begin) iterators so we can index backwards
    // across the two strings.  This way we look at the last digits
    // first

    string::const_reverse_iterator a_iterator = a.rbegin();
    string::const_reverse_iterator b_iterator = b.rbegin();

    // this variable holds the result that we build

    string result;

    // simple loop that just prints digits as long as the iterators
    // haven't indicated we're out of characters by reaching their
    // respective "r"ends...

    while (a_iterator != a.rend() || b_iterator != b.rend()) {

       int a_digit = 0;
       if (a_iterator != a.rend()) {
           a_digit = digitFromChar(*a_iterator);
           a_iterator++;
       }

       int b_digit = 0;
       if (b_iterator != b.rend()) {
           b_digit = digitFromChar(*b_iterator);
           b_iterator++;
       }

       cout << "A digit " << a_digit << ", B digit " << b_digit << endl;

       int out_digit = 0;
       if ((a_digit != 0) && (b_digit !=0))
           out_digit = 1;

       result.insert(result.begin(), charFromDigit(out_digit));
    }

    return result;
}

int main(int argc, char* argv[]) {
    string a ("1000000000001");
    string b ("0100000000001");

    cout << "A is " << a << endl;
    cout << "B is " << b << endl;

    cout << "Return Value = " << get_something(a, b) << endl;

    return 0;
}

プログラムの出力は次のとおりです。

A is 1000000000001
B is 0100000000001
A digit 1, B digit 1
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 0
A digit 0, B digit 1
A digit 1, B digit 0
Return Value = 0000000000001

クラスに参加している場合、彼らが教えているフレームワークで問題を解決している場合、実際には大きな違いがあります。あなたが学んでいることがすべてそうであるなら、あなたは C を学んでいます...慣用的な C++ ではありませんchar*。strlen()C++ では、より多くの自動メモリ管理が行われ、より一般的なアルゴリズム アプローチの使用が奨励されます。

Answer 4

a と b の最下位桁から、文字 '0' の値を引いて整数に変換します。(一部の人は、これは移植可能ではないと正しく述べていますが、これが機能しない現代の実用的なシステムを見つけたら、私に連絡してください!) a 桁が b 桁より小さい場合は、a 桁に 10 を加え、「借用フラグ」を設定し、b 桁から a 桁を減算します。この値は、答えの最下位桁です。

ボロー フラグが設定されている場合は、次の最下位桁に移動し、a 桁から 1 を減算し、ボロー フラグをクリアしてから、上記を繰り返します。

一方の文字列が他方の文字列よりも先に桁を使い果たした場合 (つまり、文字列が短い場合)、対応する桁はゼロに等しいと見なされます。

これは反復または再帰的に実行できます。クラスで具体的に教えられていない限り、再帰を試みません。したがって、解決策として、または必要な解決策として受け入れられる可能性があります。