|
To start with, I would think about a brute force approach, and narrow it down by adding more rules.
Make your algorithm start with 123456789
In the next iteration, make your algorithm obtain: 12345678*9
Next obtain, 12345678+9
and 1234567*89, 1234567+89, 1234567*8*9, 1234567*8+9,... and so on
If you write an algorithm to fill this series, you can easily see that there are 3^8 possibilities! It might look long enough but it actually is not! I took "three" because there are three possible states: 1. No operation, 2. addition, 3. multiplication. And there are 8 ways you can insert the arithmetic symbols, which is always in-between two numbers.
Now, though the value 3^8 = 6561 is very less, computing huge values won't do any good. What other information do we have? There can't be a '-' sign! That's a good clue. Because, now we know for sure that the value can't reduce and computing values such as 12345*6789 can't be always feasible. So, if there is a number in the expression greater than the required number, from your example, if there is a number greater than 100 in the expression, you don't have to compute the expression to know it is not equal. Simply checking for the "greater than" would help.
Now, we have made the problem shorter, starting with an inefficient brute force algorithm! Now lets make it even shorter. Did you observe that if the entered number is 100, the first few elements in the series would definitely not hold? Let's create a function,
term f(int x) // returns the term, given the term number.
to which if you pass on the term-number you could automatically obtain the element in O(1) time. I call it O(1) because the moment you convert the base-10 number passed on as an integer to the function f to a base-3 number, you have your term! Now each digit of the newly obtained number either becomes + or * or "nothing", and with this we may construct our term. Let's now define rules to skip every term containing numbers greater than 100. To do this, lets speculate and find the term that is at the 1000'th place in the series. Depending on whether the series is greater or lesser, move forwards or backwards in the series (if you are willing to find at-least one solution, or switch to brute force if you want to find all the possible answers).
This is how I would start with the problem. And I would write a quick code and test my hypothesis, and add on more rules to it and make it even more optimized.
|
|
|
|
|
I see that numbers are in order is it allowed to change order ?
Like using 100 = 1×2+38+4+5+6×7+9
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
modified 8-Oct-15 18:01pm.
|
|
|
|
|
ppolymorphe wrote: is it allowed to change order I'd guess not, or else the original solution would have had more than 7 possibilities. If they can, then the possible solution space is over 300000 times bigger!
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
I do not know why order can not be changed. If we change order, mostly we get different result, because multiplication precedes summation. Of course, here are some options as X*1+2+3 or X*3+2+1 and so on. But if we mix multiplication and summation, then results are different. If we will follow standard rules then mentioned X examples are the same option/solution.
EDIT
I mean X*1+2+3 or X*1+3+2 not mixing multiplication with summation
modified 16-Oct-15 11:32am.
|
|
|
|
|
The issue comes with the adjacency "operator" where adjacent digits of the input sequence can be interpreted as a multi-digit number. In the original example there was:
100 = 12+34+5×6+7+8+9
where the 1 and 2 were combined into 12 and the 3 and 4 were combined into 34.
If the order could be rearranged, then there are more possible multi-digit numbers:
51, 72, 43, etc.
This increases the complexity of the problem space and the number of possible solutions.
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
I have been reading this:https://en.wikipedia.org/wiki/Dijkstra's_algorithm[^]. It says,
Dijkstra's original algorithm does not use a min-priority queue and runs in time O(|V|^2) (where |V| is the number of nodes). The idea of this algorithm is also given in (Leyzorek et al. 1957). The implementation based on a min-priority queue implemented by a Fibonacci heap and running in O(|E|+|V|\log|V|) (where |E| is the number of edges) is due to (Fredman & Tarjan 1984). This is asymptotically the fastest known single-source shortest-path algorithm for arbitrary directed graphs with unbounded non-negative weights.
But whether or not we use a min-priority queue, shouldn't it be O(|V|^2) ?
Lets consider the situation where every node in the graph is connected to every other node. And each of this node is double ended (i.e., if there is a link from A to B then there is also a link from B to A). If we were to make the algorithm update the distance of every node (from the source) then shouldn't we obviously be checking |V| nodes for each node in the graph? We need to compulsorily check each node for every other node we visit!
Now following this algorithm from Wikipedia:
1 function Dijkstra(Graph, source):
2 dist[source] ← 0 // Initialization
3
4 create vertex set Q
5
6 for each vertex v in Graph:
7 if v ≠ source
8 dist[v] ← INFINITY // Unknown distance from source to v
9 prev[v] ← UNDEFINED // Predecessor of v
10
11 Q.add_with_priority(v, dist[v])
12
13
14 while Q is not empty: // The main loop
15 u ← Q.extract_min() // Remove and return best vertex
16 for each neighbor v of u: // only v that is still in Q
17 alt = dist[u] + length(u, v)
18 if alt < dist[v]
19 dist[v] ← alt
20 prev[v] ← u
21 Q.decrease_priority(v, alt)
22
23 return dist[], prev[]
We can obviously see that the loop continues until all nodes in Q are visited. During each visit, every neighbor of v is checked. So this clearly checks every other node in the graph for each node that's visited (if we assume that every node is connected to every other node). So now we have,
O(|V|^2)
instead of,
O(|E|+|V|log|V|)
Where did I go wrong?
|
|
|
|
|
I guess, by know I got to know the answer myself! The mistake I initially did was, I neglected the |E| in O(|E|+|V|log|V|). In the worst case, we can consider O(|E|) to be O(|V|^2). But still, we treat |E| as a separate variable because, |E| <= (|V|^2- |V|)/2. Though there is an upper bound for |E|, it is still independent of |V|. I have explained this well in my blog: http://www.creativitymaximized.com/2015/10/shortest-path-algorithm-elaborated.html[^]
|
|
|
|
|
Hello,I understand Shell Sort definition but I can not understand
this C# code:
public void shellSort()
{
int inner, outer;
long temp;
int h = 1;<br />
while(h <= nElems/3)
h = h*3 + 1;
while(h>0)<br />
{
for(outer=h; outer<nElems; outer++)
{
temp = theArray[outer];
inner = outer;
while(inner > h-1 && theArray[inner-h] >= temp)
{
theArray[inner] = theArray[inner-h];
inner -= h;
}
theArray[inner] = temp;
} // end for
h = (h-1) / 3;<br />
} // end while(h>0)
} // end shellSort()
please help me thx!
|
|
|
|
|
Member 11760977 wrote: but I can not understand
this C# code:
You'll have to give us a specific question if we're going to help you.
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
Member 11760977 wrote: but I can not understand this C# code:
Why don't you let the code show you how it works ?
Use the debugger ! You will see the code doing its stuff. Run the code step by step and inspect variables.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
|
Why do you give me this link ?
I know how it works !
My previous message was giving a way to see the program doing its stuff.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Quisiera saber quien tiene el algoritmo de Ford y Fulkerson , he estado buscando en varias paginas este algoritmo, pero no logro conseguir.Si alguien lo puede conseguir lo antes posible o hacerlo estaría muy agradecido.
|
|
|
|
|
This is an English language site. You'll get few responses for postings in other languages.
Bing Translator:
I would like to know who has the algorithm of Ford and Fulkerson, I've been searching several pages this algorithm, but I can not get. If someone can obtain as soon as possible or make it I would be very grateful.
Ford--Fulkerson_algorithm[^] on Wikipedia has an explanation as well as a Python implementation. For other languages, you're on your own...
(This "smells" a bit like homework. If so, you really need to do it yourself!)
"Fairy tales do not tell children the dragons exist. Children already know that dragons exist. Fairy tales tell children the dragons can be killed."
- G.K. Chesterton
|
|
|
|
|
This is still an English language site, and the answers haven't changed since last Thursday[^].
"These people looked deep within my soul and assigned me a number based on the order in which I joined."
- Homer
|
|
|
|
|
A directed graph is called a unique-path graph if given vertices v and w, there is at most one path from v to w. Now, I am given a graph G in which there exists a vertex x that has paths to all other vertices. (The vertex x is not known to us initially) How do I check that G is a unique path graph in O(|E| + |V|) time?
Using the concept of strongly connected components, I can find the vertex x in O(|E|+|V|) time. How do I proceed after that? How does x help us in checking multiple paths between a pair of vertices?
|
|
|
|
|
What data do you have about the graph ? got a example ?
Have you tried something ?
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Hi All,
I am trying to come up with an algorithm to get following three piece of information to plot a chart:
1. Start : Should be close to the minimum value of the dataset
2. Stop : Should be close to the maximum value of the dataset
3. Interval : Should be such that it will have "0" on the axis when interval traverses from minimum to maximum.
Example: dataset{-266,-17.6,0.5,2000,6000}
My final return values should be:
Start: 400
Stop: 6000
Interval:200
Note: Since start is 400 and interval is 200, we will have 0 as a point on the x-axis.
|
|
|
|
|
How did you choose 400 to be 'close' to -266? Plotting the values from 400 to 6000 in intervals of 200 is a simple straight line. Your question is not clear.
|
|
|
|
|
400 value is in example. I came up with those numbers to explain what I am trying to achieve.
Actually, I did figure this out.
Thanks.
|
|
|
|
|
Hi all!
when this impulse based equation can equal to zero:
w'=w+(j/I)*r*n;
n normal contact;j impulse;I inertia;
modified 1-Sep-15 19:43pm.
|
|
|
|
|
What is your question ?
And I guess more details will be welcomed.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
as you know: https://en.wikipedia.org/wiki/Collision_response[^]
just that w will never be zero, and need always two points of contact to be;(the eqation above is elastic collision with rotation no friction)!
__________ \/__________
a triangle can never stand like this!(in a real world or can it!?)
see here(http://i.stack.imgur.com/o9P7V.png[^]
what if the ball was heading the center of the bar, the bar won't spin right!
but we know that a force in a direction in a center of mass mmake angular velocity zero right!
but this equation from wiki never make it until there is two points of contact, is that is!?
modified 2-Sep-15 8:34am.
|
|
|
|
|
Ok, the wording is not obvious for not English native people.
A couple of sentences explaining what you are looking for will not arm.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|