|
Yes, but this is not acceptable...
That code will run in a very small processor in a realtime deterministic system and I can't afford spending this amount of time in each cycle.
That's why I need to find the vmax calculating and not by decreasing the value little by little...
I can see two possible approaches:
A) graphical approach with trigonometry trying to find the intersection point of the two straight lines in a time/velocity graph.
B) trying to find the solution via quadratic equations.
In case none of them work, then, at least I would implement a sort of binary search to minimize the searching time for vmax, but I will work to avoid that.
Thank you for your suggestion though. 
|
|
|
|
|
c) dichotomy search
Expect 12 iterations for a vmax between 0 and 4000.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Yes, that would be an option, but I would prefer to solve it mathematically and with only one cycle.
Anyway, that binary (or dichotomy) search would do it more or less well.
Usually the dichotomy search is used to find exact values, in this case I should search for two states in each cycle:
vmax + 1 is not OK
vmax is ok
But that's the last resort if all the other calculations fail.
Thank you!
|
|
|
|
|
Solved... updated the initial post to show the solution.
Thank you Patrice!
|
|
|
|
|
I have to write a program that, given an array of n numbers, finds the longest contiguous subarray whose minimum is the first element of the subarray and maximum the last element of the subarray. For example, with [5, 18, 2, 12, 4, 7, 13, -2, -5, 12] the answer should be [2, 12, 4, 7, 13] (2 <= of all the elements of the subarray, 13 >= of all the elements of the subarray). If possible, the time complexity in the worst case has to be equal to O(n). If it isn't possible, could you explain me why? I already tried to find the minimums and then the maximums, but doesn't work with arrays like [-1,12,1,2,3,4]. I also tried to split the array when there is an element followed by a smaller element and then merge the subarrays, but it doesn't work for arrays like [2,15,6,10,3,20].
modified 5-Feb-17 6:11am.
|
|
|
|
|
Member 10566089 wrote: I have to write a program that
OK, go ahead then.
So what exactly is your question? What do you need help with?
The difficult we do right away...
...the impossible takes slightly longer.
|
|
|
|
|
I can't find an algorithm that solves this problem in O(n). Do you have any idea?
modified 5-Feb-17 13:06pm.
|
|
|
|
|
Member 10566089 wrote: I can't find an algorithm that solves this problem in O(n). Do you have any idea?
You have not been told it is possible, you are asked if it is possible or not. If you don't find an algorithm, the answer is 'no'.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Show what you have done so far. We will not write it for you.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
int l, l_max, u_max, u;
int A[N+1] = l_max= l =1;
u_max= u =1;
int i;
for (i=2;i<N;i++)
{
if (A[i] >= A[u])
u = i;
else if (A[i] < A[l])
{
if (u-l > u_max-l_max)
{
l_max = l;
u_max = u;
}
l = u = i;
}
}
if (u-l > u_max - l_max)
{
l_max = l;
u_max = u;
}
printf("%d %d", l_max,u_max);
But doesn't work with arrays like {1,10,5,5,5,5,1,9}
public static void main(String[] args) {
int [] arr=
int N=arr.length;
LinkedList <Subarray> subarrays=new LinkedList<Subarray> ();
Subarray s=new Subarray();
s.setStart(0);
s.setEnd(0);
for (int i=1;i<N;i++)
{
if (arr[i] < arr[i-1])
{
s.setEnd(i-1);
subarrays.add(s);
s=new Subarray();
s.setStart(i);
s.setEnd(i);
}
}
s.setEnd(N-1);
subarrays.add(s);
Iterator<Subarray> iterator = subarrays.iterator();
s=iterator.next();
Subarray nxt;
while (iterator.hasNext()) {
nxt=iterator.next();
if (arr[nxt.getEnd()]>=arr[s.getEnd()] && arr[s.getStart()]<=arr[nxt.getStart()])
nxt.setStart(s.getStart());
s=nxt;
}
iterator = subarrays.iterator();
s=iterator.next();
while (iterator.hasNext())
{
nxt=iterator.next();
if ((nxt.getEnd()-nxt.getStart()) > (s.getEnd()-s.getStart())){
s=nxt;
}
}
System.out.print("+s.getStart()+""+s.getEnd());
}
}
But doesn't work with {2,15,6,10,3,20}
public static void main(String[] args) {
int [] input=
int max = input.length - 1;
int[] aux = new int[input.length];
for(int i = input.length; i>0; i--){
if(input[i-1] > input[max])
{
max = i - 1;
}
aux[i-1] = max;
}
int l = 0;
int u = 0;
max = 0;
int lMax = 0;
int uMax = 0;
for (int i=0;i<aux.length;i++)
System.out.print(aux[i]+" ");
for(int i = 0; i< input.length; i++){
System.out.println(""+input[i]+",l: "+l+",u: "+u);
if (input[i] >= input[l] && aux[l] >= i)
{
u = i;
}
else
{
if(u-l > max)
{
lMax = l;
uMax = u;
max = u-l;
}
l = i;
u = i;
}
}
if(u-l > max){
lMax = l;
uMax = u;
}
System.out.println("l "+l+" u "+u);
}
But doesn't work with {1,2,3,4,5,15,4,-1,18}
|
|
|
|
|
Why do you have 3 different programs ?
Are you rewriting a new program every time the previous one don't work ?
Advice: Take a sheet of paper and simulate how your program should behave and how variables evolve over execution. And validate that you find the right answer.
If the simulation don't endup with the answer, algorithm is wrong.
if the simulation is ok, use the debugger to check that the program conform to simulation, if not, it will help you to find the reason.
Patrice
“Everything should be made as simple as possible, but no simpler.” Albert Einstein
|
|
|
|
|
Yes, I wrote the code and discovered that there is a type of array for which the algorithm gives the wrong answer.
|
|
|
|
|
Hi,
SOLVED.
Thanks.
modified 12-Apr-17 15:00pm.
|
|
|
|
|
(Accounts payable and receivable) "Aging" has to do with "Invoice dates" and "Due Dates" and payment terms.
Your concept of "aging" makes no sense; particularly when you start talking in terms of "years".
And when you start using the wrong term for a given accounting concept, you are in for a lot of pain (through misunderstandings).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
Excuse my lack of understanding of the accounting "Aging" method but somehow my accounting person is calling it "Aging". I hope I was able to explain and communicate my requirement on what I'm trying to achieve. I would appreciate some help with this.
Thanks.
|
|
|
|
|
You might be "forecasting"; but nailing one small amount to a given month is meaningless unless it has some significance to it, like "Mother's Day".
If anything, the accounting person may also be "depreciating" or modeling the life cycle of a marketing campaign or product.
Maybe it's all on a "need to know" basis...
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
public static int LastIndexOf<T>(this IReadOnlyList<T> s, IReadOnlyList<T> t, int startIndex,
IEqualityComparer<T> comparer) where T : IEquatable<T>
{
Validate(s, t, startIndex);
if (t.Count == 0) return 0;
if (s.Count == 0 || s.Count < t.Count) return -1;
if (comparer == null) comparer = EqualityComparer<T>.Default;
if (t.Count == 1) return LastIndexOf(s, t[0], startIndex, comparer);
var table = BuildTable(t, comparer);
var i = 0;
while (startIndex - i >= 0)
{
if (comparer.Equals(t[t.Count - i - 1], s[startIndex - i]))
{
if (i == t.Count - 1)
return startIndex - t.Count + 1;
i++;
}
else
{
if (table[i] > -1)
{
startIndex -= i;
i = table[i];
}
else
{
startIndex--;
i = 0;
}
}
}
return -1;
}
Full source code can be seen here[^].
The method works like String.LastIndexOf which searches string from the last character. The BuildTable method is exactly same with normal KMP algorithm.
I'm not sure if this is the best solution though.
|
|
|
|
|
I would have just reversed the 2 strings and compared those.
(KMP: Keep Me Partying).
"(I) am amazed to see myself here rather than there ... now rather than then".
― Blaise Pascal
|
|
|
|
|
If y'all don't mind, I'd love some input on this idea I have laid out below and an algorithm/process to make it come to life.
When you were a child did you ever making up a language with your friend so that when you wrote messages to each other only you two would be able to understand it? It was always simple stuff like a = "1", b = "!", c = "+", and etc. Basically, I want to mimic the thought process used to create a made-up language, but on a more complicated level. I would like to create a learning agent that will find correlations between a set of number strings and a set of common English words, so that the number strings and English words can be translated to and from one another. For example:
The agent would take in a set of strings of numbers like this: 010001110100111111, 10011101110, and 0111100101100000. And a set of English words like this: "banana", "apple", and "pear".
After reviewing both groups of data, the agent could match the numbers/letters like this: a = 10, b = 0100, e = 01110, l = 0011, n = 101, p = 0111, and r = 0111111
So that when translated, the numbers from above are as follows: 0100011110100111111 = "bear", 10011101110 = "ape", and 101011100111100011 = "nepal". And, when translated the words from above are as follows: "banana" = 0100101011010110, "apple" = 100111011101101110, and "pear" = 011101110100111111.
What are your thoughts on this idea? I know it would be a complicated process, if it's even possible at all. Would it be beneficial to include letter frequency statistics? Or even weight the words, for example weight "the" higher than "cat" since "the" is used so often in conversation. I realize that inevitably there would most likely be some number-to-word translations that would just result in garbage, but I hope that I could create this agent in such a way that those results don't happen very often. Would supervised learning pertain to a problem like this?
Thank you for your input! Also, this is just for a personal project - no assignments or projects or anything. I just think it'd be cool.
|
|
|
|
|
Since everything in a computer is a bunch of 0s and 1s, this already exists. For example banana = 011000100110000101101110011000010110111001100001.
|
|
|
|
|
Hi Richard, thank you for the response! I know that it's possible to translate strings into binary, as you have above, but I would like to create a new and different kind of "language" to translate strings to. I hope that makes sense?
Basically what I would like to achieve is a program that takes a string, translates that string to binary (a string of 0s and 1s), and then translates that binary string into a new string so as to make the original message look totally different. It's really like a secret code in a way! (I'm really into spy movies, so I love stuff like this haha)
The program would work like this, for example:
1. "hello world" would be translated to binary "011010000110010101101100011011000110111100100000011101110110111101110
0100110110001100100"
2. the binary string is then translated to the new string using the new translation formula created with the intelligent agent, such that (for example) "0110..." = "goodbye space"
So, I want to see if I can create an intelligent agent that can find a new correlation between a long binary string and common English words. I hope that makes sense!
|
|
|
|
|
You're talking about a cipher.
Specifically, you're talking about a sort of steganography, the classic method of hiding a message in plain sight. This can apply to text or images or even audio.
There's your google keywords. Go forth and enjoy!
"There are three kinds of lies: lies, damned lies and statistics."
- Benjamin Disraeli
|
|
|
|
|
Sweet, thank you so much!
|
|
|
|
|
Sometimes you just "go"; it's an iterative process that might lead (nowhere?).
Seems I would be looking at "primitives" and "building blocks" (in this case).
Starting with "tokens".
Then cataloging "nouns", "verbs", prepositions, etc.
Can't very well translate "verbs" to "nouns", for example.
Perhaps some readings on compilers and interpreters; particularly the "lexical analysis" phase.
|
|
|
|
|
Thank you so much for your input! I'll definitely do some research on these points.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
