NickAndNick

Композиция числа

Nov 16th, 2020 (edited)
257
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <string>
  4. #include <vector>
  5. using namespace std;
  6. class Composition {
  7. public:
  8.     Composition(int number) : number(number) {
  9.         box.emplace_back(to_string(number));
  10.     }
  11.     vector<string> result() {
  12.         Compare comp;
  13.         run();
  14.         sort(box.begin(), box.end(), comp);
  15.         return box;
  16.     }
  17. private:
  18.     int number;
  19.     char buffer[0xFFFF];
  20.     vector<string> box;
  21.     struct Compare {
  22.         bool operator()(const string& a, const string& b) {
  23.             return a.length() < b.length();
  24.         }
  25.     };
  26.     void decomposition(int num, int beg, int pos) {
  27.         int end = strlen(buffer);
  28.         _itoa_s(num, buffer + pos, sizeof(int), 10);
  29.         int next, limit;
  30.         buffer[end] = 0;
  31.         box.push_back(string(buffer));
  32.         for (next = beg, limit = (num >> 1); next <= limit; ++next) {
  33.             _itoa_s(next, buffer + pos, sizeof(int), 10);
  34.             end = strlen(buffer);
  35.             buffer[end] = ' ';
  36.             decomposition(num - next, next, end + 1);
  37.         }
  38.     }
  39.     void run() {
  40.         int next, limit, length;
  41.         for (next = 1, limit = (number >> 1); next <= limit; ++next) {
  42.             _itoa_s(next, buffer, sizeof(int), 10);
  43.             length = strlen(buffer);
  44.             buffer[length] = ' ';
  45.             decomposition(number - next, next, length + 1);
  46.         }
  47.     }
  48. };
  49. int main() {
  50.     int n = 10;
  51.     Composition сomposition(n);
  52.     auto result = сomposition.result();
  53.     auto x = 0;
  54.     for (const auto& item : result) {
  55.         cout << ++x << ") " << item << '\n';
  56.     }
  57.     system("pause > nul");
  58. }
Add Comment
Please, Sign In to add comment