Вернуть результат вычитания символьных массивов в C ++

Question

Я пытаюсь вычесть строки, где каждый символ ASCII рассматривается как десятичная цифра.Например:

"1000000000001" - "0100000000001" = "900000000000"

Как бы я начал реализацию этого, если бы мой прототип функции выглядел так:

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

Answer 1

Просто помните, как вы научились делать вычитание больших чисел в своем классе Алгоритмы 001, начальной школе.Вычтите наименее значимые цифры обоих чисел, добавьте 10, если меньше 0, запомните перенос, переходите к следующей паре цифр.

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:
// /388338/kak-preobrazovat-odin-simvol-v-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

Действительно, это имеет большое значение, если вы в классе, если вы решаете это в рамках, о которых они вас учат. Если все, что вы изучаете, это char* и strlen() и так далее, вы изучаете C ... не идиоматический C ++. В C ++ у вас гораздо более автоматическое управление памятью и поощрение использования более общих алгоритмических подходов.

Answer 4

Взяв наименьшую значащую цифру a и b, преобразуйте их в целое число, вычтя значение символа '0'. (Некоторые правильно скажут, что это не переносимо, и я говорю, вернитесь ко мне, когда вы нашли практичную систему в современном использовании, на которой это не будет работать!). Если цифра меньше цифры b, добавьте 10 к цифре, установите «флаг заимствования» и вычтите цифру из цифры b. Это значение является наименее значимой цифрой ответа.

Перейти к следующей младшей цифре, если установлен флаг заимствования, вычесть 1 из цифры и очистить флаг заимствования, а затем повторить, как указано выше.

Если в одной строке заканчиваются цифры раньше другой (то есть короче), то соответствующая цифра должна быть принята равной нулю.

Это может быть выполнено итеративно или рекурсивно; Я не буду пытаться проводить рекурсию, если она не была специально изучена в классе и, следовательно, вероятно, будет принята в качестве решения или даже требуемого решения.