Answer the question
In order to leave comments, you need to log in
How to write a program "Arrange signs of arithmetic operations and brackets so that equality is fulfilled"?
Somewhere I found a ready-made solution, but now I can not find it.
Maybe someone has left.
The task, in principle, is a standard one for enumeration. But mother is lazy.
Answer the question
In order to leave comments, you need to log in
If in the wording "arrange signs to get 100", then I have something like this:
https://www.dropbox.com/s/vktq0cllod4d34s/LuckyTic...
And such a sickly sorter turns out.
In the option "arrange signs and brackets on the left side so that equality is true":
Let the string of digits on the left side have length n.
1. Break the string into numbers in all possible ways. That is, we get from 1 to n numbers. The number of options for splitting a string of n digits into m numbers is
2. Since the condition says about brackets, the operations can be performed in a different order. To specify the order of operations on each array of m numbers, you can build a binary tree using the elements of the array as leaves. Each tree will contain m-1 vertices. The number of such trees (Catalan number) is
3. Each of the vertices defines one of the four mathematical operations (+, -, *, /). Thus, the number of possible formulas for one tree
4. If you add unary minuses, then they can be placed for each of the m leaves
Total options
After that, by traversing the tree, we perform the calculation and, if the result is correct, we display the tree as an expression with brackets. Here is the number of options for different n (although some of them will turn out to be doubles or mathematically incorrect due to division by 0).
+----+---------------------+---------------------+
| n | без унарных минусов | с унарными минусами |
+----+---------------------+---------------------+
| 1 | 1 | 2 |
| 2 | 5 | 18 |
| 3 | 41 | 290 |
| 4 | 320 | 5'938 |
| 5 | 5'073 | 136'770 |
| 6 | 64'469 | 3'379'794 |
| 7 | 859'385 | 87'547'746 |
| 8 | 11'853'949 | 2'345'800'050 |
| 9 | 167'763'361 | 64'477'920'386 |
| 10 | 2'422'342'053 | 1'807'930'569'874 |
+----+---------------------+---------------------+
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question