А для этого нужна числопредставлялка...

Интересная задачка - представить натуральное число N только с помощью цифры (или числа) D и четырёх арифметических операций над D, например, при N = 5, D = 4 имеем 5 = 4/4+4 ну или для N = 2019, D = 6, имеем 2019 = ((((6*6+6+6+6)*6+6+6)*6)*6+6+6+6)/6

Требуется, чтобы цепочка была наиболее короткой из возможных. Глубина поиска ограничена значением LIMIT.

Вот небольшой класс, решающий задачу с помощью рекурсивного поиска и тесты для него. Проверено в консоли Visual Studio 2015.

#include <iostream>
#include <sstream> 
#include <stack> 
#include <map> 
#include <algorithm>
#include <climits> 
using namespace std;

class singleDigit {
 int N, D, //число для разложения, число для представления
  LIMIT, minimum; //глубина поиска, минимальная глубина
 map <int, int> numbers; //рассматриваемые числа
 stack <char> operators; //операторы
public:
 singleDigit (int N = 0, int D = 0, int LIMIT=10) {
  this->N = N; this->D = D; this->LIMIT = minimum = LIMIT;
 }
 void minLevel (int total, int N, int D, int level) {
  if (total == N) {
   minimum = min(minimum, level);
   return;
  }
  if (level == minimum) return;
  if (total % D == 0) minLevel(total / D, N, D, level + 1);
  minLevel (total + D, N, D, level + 1);
  if (total - D > 0) minLevel(total - D, N, D, level + 1);
  minLevel (total * D, N, D, level + 1);
 }
 bool generate (int total, int N, int D, int level) {
  if (total == N) return true;
  if (level == minimum) return false;
  if (numbers.find(total) == numbers.end() || numbers.find(total)->second >= level) {
   numbers[total] = level;
   int divide = INT_MAX;
   if (total % D == 0) {
    divide = total / D;
    if (numbers.find(divide) == numbers.end()) numbers[divide] = level + 1;
   }
   int addition = total + D;
   if (numbers.find(addition) == numbers.end()) numbers[addition] = level + 1;
   int subtraction = INT_MAX;
   if (total - D > 0) {
    subtraction = total - D;
    if (numbers.find(subtraction) == numbers.end()) numbers[subtraction] = level + 1;
   }
   int multiply = total * D;
   if (numbers.find(multiply) == numbers.end()) numbers[multiply] = level + 1;
   if (divide != INT_MAX) if (generate(divide, N, D, level + 1)) {
    operators.push('/');
    return true;
   }
   if (generate(addition, N, D, level + 1)) {
    operators.push('+');
    return true;
   }
   if (subtraction != INT_MAX) if (generate(subtraction, N, D, level + 1)) {
    operators.push('-');
    return true;
   }
   if (generate(multiply, N, D, level + 1)) {
    operators.push('*');
    return true;
   }
  }
  return false;
 }
 string solve () {
  minLevel(D, N, D, 1);
  if (generate(D, N, D, 1)) {
   ostringstream num;
   num << D;
   string expression;
   if (!operators.empty()) {
    expression = num.str() + operators.top();
    operators.pop();
   }
   while (!operators.empty()) {
    if (operators.top() == '/' || operators.top() == '*')
     expression = "(" + expression + num.str() + ")" + operators.top();
    else
     expression = expression + num.str() + operators.top();
    operators.pop();
   }
   expression = expression + num.str();
   return expression;
  }
  else return "Solution not found for current search deep";
 }
};


int main() {
 singleDigit a0;
 cout << a0.solve() << endl;

 singleDigit a (5,4);
 cout << a.solve() << endl;

 singleDigit b (100, 7);
 cout << b.solve() << endl;

 singleDigit c(200, 9);
 cout << c.solve() << endl;
 
 singleDigit c1(200, 9, 12);
 cout << c1.solve() << endl;

 singleDigit d(2019, 6, 14);
 cout << d.solve() << endl;

 cin.get(); return 0;
}

Выдача этой программы:

0
4/4+4
(((7+7)*7)*7+7+7)/7
Solution not found for current search deep
(((9+9)*9+9+9+9+9)*9+9+9)/9
((((6*6+6+6+6)*6+6+6)*6)*6+6+6+6)/6

(d будет считаться подольше, чем остальное)

А вот цепочки для всех возможных пар значений (N,D) в пределах от 1 до 9 включительно:

1 1 1
1 2 2/2
1 3 3/3
1 4 4/4
1 5 5/5
1 6 6/6
1 7 7/7
1 8 8/8
1 9 9/9
2 1 1+1
2 2 2
2 3 (3+3)/3
2 4 (4+4)/4
2 5 (5+5)/5
2 6 (6+6)/6
2 7 (7+7)/7
2 8 (8+8)/8
2 9 (9+9)/9
3 1 1+1+1
3 2 2/2+2
3 3 3
3 4 (4+4+4)/4
3 5 (5+5+5)/5
3 6 (6+6+6)/6
3 7 (7+7+7)/7
3 8 (8+8+8)/8
3 9 (9+9+9)/9
4 1 1+1+1+1
4 2 2+2
4 3 3/3+3
4 4 4
4 5 (5*5-5)/5
4 6 (6+6+6+6)/6
4 7 (7+7+7+7)/7
4 8 (8+8+8+8)/8
4 9 (9+9+9+9)/9
5 1 1+1+1+1+1
5 2 2/2+2+2
5 3 (3+3)/3+3
5 4 4/4+4
5 5 5
5 6 (6*6-6)/6
5 7 (7*7-7-7)/7
5 8 (8+8+8+8+8)/8
5 9 (9+9+9+9+9)/9
6 1 1+1+1+1+1+1
6 2 2+2+2
6 3 3+3
6 4 (4+4)/4+4
6 5 5/5+5
6 6 6
6 7 (7*7-7)/7
6 8 (8*8-8-8)/8
6 9 (9*9-9-9-9)/9
7 1 1+1+1+1+1+1+1
7 2 2/2+2+2+2
7 3 3/3+3+3
7 4 (4+4+4)/4+4
7 5 (5+5)/5+5
7 6 6/6+6
7 7 7
7 8 (8*8-8)/8
7 9 (9*9-9-9)/9
8 1 1+1+1+1+1+1+1+1
8 2 (2+2)*2
8 3 (3+3)/3+3+3
8 4 4+4
8 5 (5+5+5)/5+5
8 6 (6+6)/6+6
8 7 7/7+7
8 8 8
8 9 (9*9-9)/9
9 1 1+1+1+1+1+1+1+1+1
9 2 2/2+2+2+2+2
9 3 3*3
9 4 4/4+4+4
9 5 ((5+5)*5-5)/5
9 6 (6+6+6)/6+6
9 7 (7+7)/7+7
9 8 8/8+8
9 9 9

Должно работать и для значений D, больших 9, например,

singleDigit a(100, 12, 12);
cout << a.solve() << endl;

выдаст верное

((12*12-12-12-12-12)*12+12+12+12+12)/12

но не фиг же :)

Числа - едва ли не единственное, что утешает
(С)

Доктор Зло зловеще намекает:
(((13+13+13+13)*13-13)*13+13+13+13)/13 = 666
((6+6+6)*6)*6+6+6+6 = 666

15.05.2019, 10:37 [1147 просмотров]