|
cp9876 wrote: Why - has it better performance?
No, because that's the homework assignment.
|
|
|
|
|
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do?
Using both O(n^2) and O(n).
|
|
|
|
|
I do brutal
for (i=0 ; i < iMax-1; i++)
{
int temp = a[i];
if (temp > 51) continue;
for ( j=i+1; j < iMax; j++)
{
if (temp + a[j] == 51)
{
}
}
}
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
|
|
|
|
|
Good, but this is the O(n^2), do you know the n's ?
|
|
|
|
|
LongHC wrote: Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do?
First, determine how to break the number down into two numbers whose sum is the original number. Instead of 51, let's pick a smaller number, say 11. Here are the numbers whose sum is 11:
11 + 0 = 11
10 + 1 = 11
9 + 2 = 11
8 + 3 = 11
7 + 4 = 11
6 + 5 = 11
To find these numbers, we can start with two values: the original number and zero, call these x and y. Run a loop in which 1 is subtracted from x and 1 is added to y at each iteration. Continue the loop until x is less than y:
int x = 11;
int y = 0;
while(x > y)
{
x--;
y++;
}
Now, we need to search for these values in our array. It would be helpful to have our array sorted first. Then at each iteration through the loop, we perform a binary search for x an y and store the indexes to the numbers in a list, if they are in the array. We'll assume that the binary search returns -1 if the number isn't in the array:
Sort(array);
List list;
int x = 11;
int y = 0;
while(x > y)
{
int index = BinarySearch(array, x);
if(index >= 0)
{
list.Add(index);
}
index = BinarySearch(array, y);
if(index >= 0)
{
list.Add(index);
}
x--;
y++;
}
Note: this algorithm is off the top of my head. There may be better ways of doing this.
[EDIT] My algorithm doesn't take into account possible duplicates in the array. [/EDIT]
-- modified at 10:54 Friday 13th April, 2007
|
|
|
|
|
If the integers are positive, then I can think of an O(n) solution. As this sounds like homework I will just give a hint - try using an array of 51 integers.
If the integers are unbounded then I can't see an O(n) solution.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
cp9876 wrote: If the integers are positive, then I can think of an O(n) solution.
They are +ve numbers.
cp9876 wrote: As this sounds like homework
In fact this is not, I just came by this problem while reading and I tried so much in it and didn't get to any thing.
|
|
|
|
|
In that case, start with an array of 51 numbers c[i] initialised to -1.
for (int i = 0 ; i < 51 ; i++)
{
if (a[i] < 51)
{
int n = 51 - a[i];
if (c[n] >= 0)
{
}
else
{
c[n] = i;
}
}
}
Basically, for each element, store its location where its complement can find it
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Thanks for your solution and for Leslie's one.
|
|
|
|
|
A few years ago, I wrote a Skip List[^] class in C#. I've found this data structure to be handy. For one thing, it's easily adapted to a priority queue[^].
What I'd like to do is add the ability to access items in the skip list by index, e.g. give me the n'th item in the list. This is easy enough to do in O(N) time by simply starting at the beginning of the list and moving one by one through the list until you've reached the desired item. I was looking for a better way. Kunth decribes a way to do this with binary search trees. I'd like to find the equivalent algorithm for skip lists.
William Pugh, the skip list's inventor, decribes a way in his skip list cookbook[^]. But his algorithm assumes the existance of a "distance" field in each node. The distance field represents the next nodes position minus the current nodes position.
I didn't find this very helpful. It requires each node and each pointer level to know their position in the list. Well, if they know that already, then it's easy enough to search for the specified item by position to begin with.
It would be easy enough to add a position field to each node. The position would represent the node's index into the list. The problem becomes trying to maintain this field as items are added and removed from the list. Descructive operations will make the position value of all subsequent nodes invalid.
This may be a problem where there isn't a solution, at least not one that works as well as the binary search tree approach. Anyway, I'd appreciate any insights.
|
|
|
|
|
Hi,
I think the distance field is the right way to go; you can fill it while populating
the skip list at very modest cost. And its update needs are limited, whereas an
absolute index field would require expensive updating when new nodes get added.
|
|
|
|
|
Well, I'm embarrassed to say it, but I just noticed the "InsertByPosition" algorithm at the end of William Pugh's cookbook paper; I hadn't looked at it when I made my original post. Looks like the algorithm for managing the distance field is right there.
|
|
|
|
|
|
I am impressed.
I kinda wish i wasn't... but i am...
|
|
|
|
|
Guys I'm very stuck.I've searched the web for the past three weeks for a class written in C# that has low pass, high pass, Band pass filters which I could used for my third year project data analysis. I'm very desperate and my eyes are bloody red right now due to lack sleep; please help...
I believe there are alot of geniuses in this forum who cannot be stopped by anything..Looking forward to receiving your help...
Cheers
kel
|
|
|
|
|
Write your own! I did when I was in college, though we didn't have fancy languages like C#. It took all of a few hours and was a great learning tool (for filter theory, not programming).
"A Journey of a Thousand Rest Stops Begins with a Single Movement"
|
|
|
|
|
I was going to make the same comment. It is after all a project on data analysis. It shouldn't take too long to write some basic filters. Get some basic filtering routines going, initially use matlab or similar to calculate the coefficients, work up to doing your own. If you are stuck, look at some of the c++ signal processing libraries - the code should be similar.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hi all,
I have a set of integers like 3,7,4,15,... and
the problem to find is how can we find a subset
with atleaset M (>=3) intergers in it and the total
of those intergers equals to the given N
thanks in advance
========================
sorry for my english and i code in c/c++
|
|
|
|
|
What's this - an easter craze on knapsack problems?
This looks like homework, in which case I guess the number of integers in the set is modest (<= say 16), in which case you can simply search all combinations and find the best.
For other comments and a more general solution see this thread: link[^]
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
please tell me if there is any way to convert an array like 936 to an integer 936?
and how can i understand that the number the user inputs how many digits has?(for example 99999 is a 5digit number)
Khodadad Pakdaman
Pakdaman@CleanMail.it
|
|
|
|
|
array ?
if you mean string, use int.Parse() or int.TryParse()
if you mean a char array, first convert it to a string using a String constructor.
|
|
|
|
|
My suggestion for a beginner like yourself is to find a tutorial in whatever language you are using, one with some simple examples involving user i/o, get these working and then experiment with modifying them to do what you want.
Google on (language of choice) tutorial
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
if you are able to write this program please help me:
YOU KNOW THAT THE ISDN NUMBER IS A SPECIFIC NUMBER FOR EACH BOOK,AND FOR EXAMPLE AN ISDN NUMBER LIKE 964-92032-1-4 CONTAINS THIS INFORMATION:
ISDN : TheLanguageOfTheBook-PublisherCode-BookNumber-CheckDigit
the check digit number is calculated in this way,
for example for 964-92032-1-4 :
10x9 + 9x6 + 8x4 + 7x9 + 6x2 + 5x0 + 4x3 + 3x2 + 2x1 = 271
271%11=7 = Result
then the CheckDigit number should be (11-Result)
ok?
Here's the interface of the program:
Enter ISBN: 964-92032-1-4
Language: 964
Publisher: 92032
Book number: 1
Check digit: 4
This ISBN code “964-92032-1-4” is valid!
or
This ISBN code “964-92032-1-4” is invalid!
Please let me know if you understood the program well!thanks again,sorry for the english mistakes found in my text,i'm really sorry!
Khodadad Pakdaman
Pakdaman@CleanMail.it
|
|
|
|
|
Sounds like homework to me - in which case try to do it and if you run into difficulties post on one of the programming forums.
Just noticed that you have posted the same question on the Managed C++ forum. This is a BIG hint - you will get much more help here if you are seen to be making an effort yourself. If you just type your problem into the forum expecting someone else to do your work, you will not get much of a response.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
ok,dear peter,
thanks for your reccomendations,
in a simple C++ program,
please tell me if there is any way to convert an array like 936 to an integer 936?
and how can i understand that the number the user inputs how many digits has?(for example 99999 is a 5digit number)
in the case mentioned up there,i don't know how i can calculate the check digit number?because i stored the input in a string!
Thanks again for your reccomendations,
Khodadad Pakdaman,
Pakdaman@CleanMail.it
|
|
|
|