Из цифр двух натуральных чисел создать наименьшее возможное число, сохраняя порядок следования цифр

119

11 августа 2019, 23:40

Требуется написать программу, которая из цифр двух натуральных чисел создает наименьшее возможное число, сохраняя при этом порядок следования цифр в этих числах.

Входной поток содержит два натуральных числа, записанных в двух строках. Числа больше нуля и меньше 10^255. (например, 125 и 34)

В единственную строку выходного потока нужно вывести наименьшее возможное число, удовлетворяющее условию задачи. (например, 12345)

#include <iostream>
#include <string>
using namespace std;
int main()
{
  string a, b;
  cin >> a >> b;
  int x=0,y=0;
  while ((x<a.length()) && (y<b.length()))
  {
    int m,n;
    m=a[x]-48;
    n=b[y]-48;
    if (m <= n)
    {
      cout << m;
      x++;
    } else
    {
      cout << n;
      y++;
    }
  }
  if (x==a.length())
  {
    for (;y<b.length();y++)
    {
      cout << b[y];
    }
  } else {
    for (;x<a.length();x++)
    {
      cout << a[x];
    }
  }
  return 0;
}

12 и 21 неверно, но 21 и 12 работает 77 и 70 неверно, но 70 и 77 работает

Ещё к тому, входные данные - могут быть огромные числа, до 255 степени. Как с этим бороться? Что неправильно в коде? Почему примеры выше неверно обрабатывает?

Answer 1

Проще всего, мне кажется, написать такую рекурсивную функцию:

bool compare(string a, int ia, string b, int ib)
{
    if (ia == a.length()) return true;
    if (ib == b.length()) return false;
    if (a[ia] == b[ib]) return compare(a, ia+1, b, ib+1);
    return a[ia] > b[ib];
}

И использовать ее так:

int main()
{
    string a = "12";
    string b = "21";
    int ia = 0;
    int ib = 0;
    while (ia < a.length() || ib < b.length())
    {
        if (compare(a, ia, b, ib))
            cout << b[ib++];
        else
            cout << a[ia++];
    }
    return 0;
}

https://ideone.com/PPtYY0

Максимальная глубина рекурсии при этом может быть 255, думаю, памяти хватит на всё (есть ограничения на память?).

Answer 2

Давайте разбираться.

a = 12, b = 21

должно получиться 1212 - a[0]b[0]b[1]a[1], а у Вас получается 1221 - a[0]a[1]b[0]b[1].

В чем тут дело? Дело в принятии решения, по какому числу двигаться, когда цифры одинаковые. Значит, волевое решение переходить к следующей цифре первого числа - как у Вас в коде - нас не устраивает.

Чтобы принять правильное решение, надо заглянуть за эти одинаковые цифры и двигаться по тому числу, у которого за этой одинаковой цифрой следует цифра меньшая, чем у другого числа.

Но это еще не все...

Продолжаем. Интересный момент здесь состоит в том, что таких одинаковых цифр в числах может идти больше одного подряд. Таким образом, нам нужно "заглядывать" за такие цепочки одинаковых цифр в обоих числах.

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

Вам осталось перевести этот рассказ в код.

P.S. Не понимаю, что Вас смущает в размере чисел. Входные "числа" - это строки включающие в себя до 255 десятичных цифр.