Разбор acmp — Постоянная Капрекара

  • В этой теме 0 ответов, 1 участник, последнее обновление 2 недели назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6462
      @admin

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 22%):

      Возьмем четырехзначное число, в котором не все цифры одинаковы, например 6264. Расположим цифры сначала в порядке убывания — 6642; затем, переставив их в обратном порядке, получим 2466. Вычтем последнее число из 6642. На следующем шаге с полученной разностью проделаем тоже самое. Через несколько таких действий получится число, переходящее само в себя и называемое постоянной Капрекара.

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

      Входные данные

      Входной файл INPUT.TXT содержит одну строку, в которой записано четырехзначное число.

      Выходные данные

      В выходной файл OUTPUT.TXT записываются: в первой строке постоянная Капрекара, во второй – количество шагов для ее получения.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 1234 6174
      3

      Разбор решения задачи

      Наиболее очевидный подход к решению задачи — моделирование действий, описанных в задаче. Мы должны выполнять такое моделирование пока очередное «следующее» число не совпадет с «предыдущим». Так как в конце получится константа, то можно сравнивать текущее число с «6147» — это число есть в примере к задаче.

      В моделировании нет ничего сложного, но нам нужно будет сортировать число, переворачивать его и выполнять над ним арифметические действия. Исходя из этих операций нужно выбрать наиболее подходящий формат для хранения числа. Сортировку проще всего выполнять над строкой — можно применять стандартный алгоритм sort. Выполнять вычитание удобно над целыми числами — для этого строку можно преобразовать в число одним из методов описанных в этой статье. Отдельно нужно учесть случай, когда число будет содержать незначащие нули и после вычитания окажется трехзначным. Тогда вся программа будет выглядеть так:

      #include <fstream>
      #include <string>
      #include <algorithm>
      #include <sstream>
      using namespace std;
      
      string str_minus(const string& a, const string& b) {
        int a_val, b_val;
        string result;
        stringstream sstr;
      
        sstr << a << ' ' << b;
        sstr >> a_val >> b_val;
      
        sstr.clear(); 
        sstr << a_val - b_val;
        sstr >> result;
      
        while (result.size() < 4)
          result.push_back('0');
      
        return result;
      }
      
      string action(string number) {
        string reversed;
      
        sort(number.begin(), number.end(), greater<char>());
        reverse_copy(number.begin(), number.end(), back_inserter(reversed));
      
        return str_minus(number, reversed);
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        string number;
        ifst >> number;
      
        for (int i = 0; true; ++i) {
          string next = action(number);
          if (next == number) {
            ofst << number << endl << i;
            break;
          }
          number = next;
        }
      }

      Это работает и является более гибким решением (его проще адаптировать если что-то изменится), однако в конкретно этой задаче:

      • Преобразование четырехзначного числа в строку и обратно удобнее реализовать «вручную» — без строковых потоков.
      • Вместо строки удобнее использовать вектор или из каждого символа строки предварительно вычесть '0' — сделать это можно стандартным алгоритмом transform.

      #include <fstream>
      #include <string>
      #include <algorithm>
      using namespace std;
      
      int str2int(const string& num) {
        return num[0]*1000 + num[1]*100 + num[2]*10 + num[3];
      }
      
      string int2str(int num) {
        string str({0,0,0,0});
        for (int i = 0, pow = 1; i < 4; ++i, pow*=10) {
          str[3-i] = (num/pow)%10;
        }
      
        return str;
      }
      
      string action(string number) {
        string reversed;
      
        sort(number.begin(), number.end(), greater<char>());
        reverse_copy(number.begin(), number.end(), back_inserter(reversed));
      
        return int2str(str2int(number)-str2int(reversed));
      }
      
      int char2digit(char c) {
        return c - '0';
      }
      
      int digit2char(char c) {
        return c + '0';
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        string number;
        ifst >> number;
        transform(number.begin(), number.end(), number.begin(), char2digit);
      
        for (int i = 0; true; ++i) {
          string next = action(number);
          if (next == number) {
      
            transform(number.begin(), number.end(), number.begin(), digit2char);
            ofst << number << endl << i;
            break;
          }
          number = next;
        }
      }
      

      Согласитесь, такое решение гораздо проще, хотя и менее универсально.

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.