|
The key is to keep track of the largest number in the array of small numbers. Let its index be named L. Then the comparison is if (A[i] < xsmall[L]). When a smaller value is found, replace xsmall[L] with A[i], and search thru xsmall for a new largest element xsmall[L]. There is no reason to sort xsmall-- if m becomes large then some data structure other than an array might help (a heap?)
|
|
|
|
|
Hi all,
I am writing a program to find the closest ancestor in a binary tree (not BST). I found a sample working code:
mynode *closestAncestor(mynode* root, mynode* p, mynode* q)
{
mynode *l, *r, *tmp;
if(root == NULL)
{
return(NULL);
}
if(root->left==p || root->right==p || root->left==q || root->right==q)
{
return(root);
}
else
{
l = closestAncestor(root->left, p, q);
r = closestAncestor(root->right, p, q);
if(l!=NULL && r!=NULL)
{
return(root);
}
else
{
tmp = (l!=NULL) ? l : r;
return(tmp);
}
}
}
I am trying to do something like the following (passing only the data values and finding only the data value of ancestor, not concerned with its pointer)
int closestanc(node * root, int n1, int n2)
{
int l, r;
if(root == NULL)
return -1;
if(root->right->data == n1 || root->right->data == n2 || root->left->data == n1 || root->left->data == n2)
return root->data;
else
{
l = closestanc(root->left, n1, n2);
r = closestanc(root->right, n1, n2);
if(l!= -1 && r!= -1)
return root->data;
else
return (l != -1 ? l : r);
}
}
But this thing doesn't work. Can you please point out where I am doing it wrong ?
|
|
|
|
|
You say it doesn't work, but you don't explain how it doesn't work. Does it error, or just give the wrong answer?
From what I can see, you check to see if root = NULL, which is good. But then you compare the values of root->right->data and root->left->data against n1 and n2. But what if root->right or root->left is NULL? Then it's data will be undefined, and the compare will fail. If it doesn't error out at this point, it may just go on to the else condition, which is fine. But as I said, I don't know how it is failing.
Roy.
|
|
|
|
|
I want to know whether opcode can give me the messages besides triangle. As mesh defined in the opcode is consist of triangles, but most of my model is constructed using polygons, so before my collision qurey, I have to transform the polygons to triangles, but i want to know wether i could know which polygon the triangles detected are belong to. if the anwser is yes, how can i get the message?
I had got the resource from the OPCODE net address, and i also have read the mannual about the OPCODE, but as I wanted to learn some details about the OPCODE, I found it was difficult. And i had got the two projects "opcode" and "CDTestFramework" from that address. because i had not found the information about how to get which polygon the detected triangle is belong to in the user mannual. i hoped to find my anwser in the two projects above, but I find it was difficult to read the code in the two projects. if you had some experience about using OPCODE, i really wished you could give some suggestion about how to read the two projects. And as the most important one of my requests is to get the polygons, so if you know, can you tell me is there any manner i can get the polygons. If the answer is NO, i think I have to think about take us of other detection manners.
|
|
|
|
|
Having read this a second time. It still makes no sense. 
What is OPCODE?
Please give Links/URL so that somebody might know what you are talking about. 
|
|
|
|
|
|
Given that no one has offered a suggestion on this, you can be reasonably sure that no one has used it. You need to make use of the information on the OPCODE website, although it does not look like it has been updated for the last 10 years.
Use the best guess
|
|
|
|
|
Wow, exactly 10 years since the last update. It is possible to browse to the Main site page and get the authors email address by clicking the link in the upper left corner.
http://codercorner.com/Pierre.htm[^]
Soren Madsen
"When you don't know what you're doing it's best to do it quickly" - Jase #DuckDynasty
|
|
|
|
|
Yes, I know, hence my response to OP.
Use the best guess
|
|
|
|
|
Given that FreeSOLID is still actively maintained, it makes you wonder why the OP won't go with it. The other alternative, linked from there hasn't been updated since 1997.
Is he stuck in a timewarped VRML world?
|
|
|
|
|
dusty_dex wrote: Is he stuck in a timewarped VRML world?
Something like that.
Use the best guess
|
|
|
|
|
Do any one here know how to predict weather based on some sample data for pressure, humidity, wind speed, air temperature, etc.. ?
I am know that we can predict weather if the data for certain factors (pressure, temperature, etc..) are known.
I want an efficient algorithm or general concept on predicting weather from those data.
|
|
|
|
|
Member 10059044 wrote: Do any one here know how to predict weather based on some sample data for pressure, humidity, wind speed, air temperature, etc.. ?
I am know that we can predict weather if the data for certain factors (pressure, temperature, etc..) are known.
I want an efficient algorithm or general concept on predicting weather from those data.
Professional Meteorologists can't predict it for more than a few days, and they have vast amounts of data and computing resources.
You should read this to understand why.
|
|
|
|
|
@dusty_dex : What i am trying is to predict weather for just one specific location, and prediction for just half - one hour ahead of current time. In that case, is it possible to obtain near-to accurate prediction using atmospheric data of about 5 days prior ?
|
|
|
|
|
nootanghimire wrote: prediction for just half - one hour ahead of current time. In that case, is it possible to obtain near-to accurate prediction using atmospheric data of about 5 days prior ?
That sounds like a contradiction to me.
As explained in the link I gave, you would have to use data much more recent than 5 days. Also I believe this problem has more to do with the accumulated errors arising from limitations in floating point math.
Maybe someone else can shed light on those issues, but it's not really my area of expertise. 
|
|
|
|
|
How about this.
Can YOU predict the weather for the next hour without looking out the window??
Probably not... So how do you expect a computer to do it??
|
|
|
|
|
There is no efficient algorithm; weather prediction is much more complex. Meteorological organisations around the world use very large models in their predictions, based on historical data as well as taking into account changes that may occur as weather fronts develop. And that data is changing continually so the predictions have to change to take account of it.
Use the best guess
|
|
|
|
|
With little data I'd say that weather prediction would be achieved best by methods like flipping a coin etc.
They get around 50% chances of success over time!
Seriously though - weather prediction is one of the toughest implementations of Chaos Theory Algorithms!
Never underestimate the difference U can make in the lives of others.
∫(Edo )dx = Tzumer
∑k( this.Kid) k = this. ♥
|
|
|
|
|
Hi
What is a nice function that have the autocorrelation function very near to a dirac function?
http://en.wikipedia.org/wiki/Dirac_delta_function[^]
I mean, I know that for digital communication is often used a Backer sequence, made by -1/+1 symbols
http://en.wikipedia.org/wiki/Barker_code[^]
that gives a very low autocorrelation, and a very sharp peak in its middle point.
I need something similar but more analog-like function.
I was thinking to a chirp function http://en.wikipedia.org/wiki/Chirp[^] ... but I am asking this question to know is someone know that there is a mathematical better/optimal choice.
Thanks
Russell
modified 7-May-13 6:45am.
|
|
|
|
|
There are many programming languages that do string pattern matching, either using regular expressions or using more elegant and powerful mechanisms, like SNOBOL[^].
There are also many programming languages that do tree pattern matching, like Haskell, but you cannot easily write a pattern that attempts to match an element in a list (a right descending tree), unless it is the first element.
Many tasks involve complex, irregular and not very large structured data. The most appropriate programming languages for tackling such tasks should have this kind of pattern matching in their tool box.
Examples of application domains for such a language:
- HTML/XML validation and correction
- C++ source code analysis
- Analysis of email chains
- Automatic chaining of tools in a workflow
- Transformation from syntax to semantics in natural language processing
- Computer algebra
Starting in the eighties, I have made and maintained such a language, Bracmat (GitHub[^],Rosetta Code[^]), and I have used it for all purposes listed above. Problem is, it is not an established programming language and therefore not the right language for production software, so I'm looking for a replacement.
I hope that I am too pessimistic and that there are in fact programming languages with seizable user communities that support the pattern matching facilities that I am looking for. The programming language that I am looking for should have a pattern matching mechanism that:
- allows wild cards not only in the tail part of a pattern, but anywhere in a pattern,
- in the case of matching against a list, is capable of matching any number of consecutive elements anywhere in the list, and not just the 'head' of the list,
- is visually clean, attractive and readable,
- allows 'normal' instructions to be embedded in patterns (evaluation of variables, writing to files, function calls, other pattern match operations, etc.),
- can assign a matched part of the subject to a variable,
- can match part of a subject with the content of a variable,
- uses the same pattern syntax for string pattern matching by treating a string as a special case of a list.
It goes without saying that such a language should have data types to express trees and lists. Ideally, patterns are structured as the data they are meant to match, so it would be helpful to implement patterns as data structures themselves.
Bart Jongejan
|
|
|
|
|
|
Indeed. Bracmat would have been a better programming language if I had been a computer scientist. For software that is going to be maintained by others, Bracmat is currently not a solution. That is why I am looking for a community driven programming language that has pattern matching (on strings, lists, trees, see the list above) in its tool box.
Clarify your answer if I misunderstood you.
Bart Jongejan
|
|
|
|
|
If you posted in Algorithms then it gave the wrong impression that you are looking for help coding a solution of your own.
Try Perl
..www.perl.org
Also have a look at Scala which has a very small syntax to learn, and is suitable for creating a Domain Specific Language of your own. scala-lang.org
"It's true that hard work never killed anyone. But I figure, why take the chance." - Ronald Reagan
That's what machines are for.
Got a problem?
Sleep on it.
modified 12-Apr-13 5:39am.
|
|
|
|
|
Neither Perl or Scala can solve this simple problem with a simple pattern: Given a list of pairs, each pair consisting of a first name and a family name, give me two names of different persons that have the same family name. I think Tom[^] (a cousin of Scala, I think) can do it, but the syntax of patterns in that language is very verbose. In Bracmat, you would do:
(Abel.Hirst) (Benjamin.Foster) (Letty.Johnson) (George.Hanson) (Chris.Johnson) (Priscilla.Stein):?list;
!list:? (?name1.?familyName) ? (?name2.!familyName) ? & out$(!name1 and !name2 "have the same family name (" !familyName ")") | out$"No two persons have the same family name";
which outputs
Letty and Chris have the same family name ( Johnson )
The pattern is just ? (?name1.?familyName) ? (?name2.!familyName) ?.
Scala only allows a wild card in the tail of a pattern. Perl 6 seems to have modernized its pattern matching, but the subject is still a string, never a list. Correct me if I'm wrong.
For a perhaps more convincing, but longer, example, see Dinesman's multiple-dwelling problem[^].
|
|
|
|
|
You can do anything in C++. your example can be done as this:
std::string mystdarr[][2] = {{"Abel","Hirst"},{"Benjamin","Foster"},{"Letty","Johnson"},{"George","Hanson"},{"Chris","Johnson"},{"Priscilla","Stein"}, {"",""}};
int arrsize = sizeof(mystdarr)/sizeof(mystdarr[0]);
for (auto it=0; it < arrsize - 1; ++it) {
auto itFound = std::find_if(&mystdarr[it+1], &mystdarr[arrsize-1], [&](const std::string (&cmp)[2]) { return !cmp[1].compare(mystdarr[it][1]); });
if (itFound != (std::string (*)[2])(mystdarr[arrsize-1]))
std::cout << mystdarr[it][0].c_str() << " and " << (*itFound)[0].c_str() << " have the same family name (" << (*itFound)[1].c_str() << ")\n";
}
Or, if you'd like less cryptic code (it's cryptic because built-in arrays in C/C++ are by no means flexible), you can do this:
struct SS
{
std::string firstName;
std::string lastName;
SS(const std::string& fname, const std::string& lname) : firstName(fname), lastName(lname) {};
};
std::vector<SS> myarr;
myarr.push_back(SS("Abel", "Hirst"));
myarr.push_back(SS("Benjamin", "Foster"));
myarr.push_back(SS("Letty", "Johnson"));
myarr.push_back(SS("George", "Hanson"));
myarr.push_back(SS("Chris", "Johnson"));
myarr.push_back(SS("Priscilla", "Stein"));
for (auto it=myarr.begin(); it!=myarr.end(); ++it)
{
auto itFound = std::find_if(it + 1, myarr.end(), [&](const SS& cmp) {return !cmp.lastName.compare(it->lastName);});
if (itFound != myarr.end())
std::cout << it->firstName.c_str() << " and " << itFound->firstName.c_str() << " have the same family name (" << it->lastName.c_str() << ")\n";
}
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
