|
Seems like you need a lot of test cases (random data could be considered) and a good
definition of what your primary measure of size "n" is.
Lacking these, your "I think it is O(n*log(n))..." seems a bit premature.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Worst case that I can think of is if you have a string like 0101010...10 of length m = 2^i-1 where i is a + int, and another of all 1's of length n where n is any + int > m. Then this algorithm will perform approximately (m / 2) * 2 * n * log2(m + 1) = m*n*i operations, or O(n*n*log(n)). So I guess that solves whether or not it is O(n * log(n))! It still should outperform almost any other algorithm when 1) The alphabet over which you are performing the search is reasonably large, 2) The expected overlap between the two strings is reasonably large. Ultimately, I don't really care what the final time is on this algorithm. I am really only looking for any advice on how I can improve it. Thanks,
Jeff
|
|
|
|
|
Sorry for this late posting, but I have just been reading old forums and ran into this.
If you are still interested in this, I have an algorithm that runs pretty quickly, abet, written in MASM, but the method could be written in C# (I think it could, I have never coded in C#). I have a complete working program - source and EXE and a method to enter test cases via a file with the strings. It is quite lengthy, but mostly commentary. The source with comments is about 2250 lines. The MaxSubstring function is 472 lines with comments. Assembled with MASM 6.15.
Dave Augustine
|
|
|
|
|
It's been a long time since i did any really hard maths and a friend of mine just asked me the following question:
"How can I easily find all possible solutions for
3125r = 1024x - 8404
where r and x are both integers, and r is divisible by 5"
Any very intelligent people out there who know of an answer?
|
|
|
|
|
Hi,
there is an infinite number of solutions, given by:
r=1020+5120t
x=3121+15625t
where any value of t will do.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
I thought there would be any number of solutions (with no particular grounding or proof). But that's certainly a faster way of finding them...
|
|
|
|
|
Would it be an impudent question to ask how you arrived at this solution? Trying to work back from your solution leaves me a bit stumped...
|
|
|
|
|
Hi Paddy,
there are several ways to find the solution(s) of ax+by=c.
First of all a single, linear equation in two variables has either no solution
at all (say 2x + 4y = 1) or an infinite number, by adding the second coefficient
to the first number and subtracting the first coef from the second number.
So the main problem is to find a first solution.
Method 1: write a little prog, assume x=u+bt and y=v-at and have it try a lot
of values u (keep t at 0) and calculate real v until it happens to be integer.
Method 2: follow the strict mathematical approach; that's what you would need
if decent code is required to solve such problems in general
Method 3: the way in-between, with a couple of shortcuts, the ideal way
to solve a single problem manually. Like so:
3125r = 1024x - 8404 with constraint r=multiple of 5
lets try to replace variables by other variables and reduce the size of the
constants:
right hand side is multiple of 4, hence r must be multiple of 20, say r=20a
3125 * 20a = 1024x - 8404
15625a = 256x - 2101
lets ignore all multiples of the smallest coef, 256
15625=61*256+9
-2101=-9*256+203
9a = 203 (modulo 256)
try a couple of numbers 203 + 256k until a multiple of 9 is found;
this is bound to happen in 9 tries !
one immediately sees a solution is a=(203+256)/9=51
(this is where the mathematician would go more formally !)
hence r=1020, then calculate the x that goes with it, and add one variable t
with the right coefs.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Thanks very much for your time  )
|
|
|
|
|
Paddy Boyd wrote: r is divisible by 5
Then use r=5*y, then:
3125*5*y = 1024x - 8404
where y and x are both integers
It is a nice start point
Russell
|
|
|
|
|
Just in case Luc's asleep (seems to be never) you could use this applet[^] and solve
-1024x + 15625y + 8404 = 0
then use r = 5y.
If you tick the box 'Step-by-step' it even shows all working!
The source code for this applet is 3742 lines long! (mostly to do with the quadratic problem I guess)
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: seems to be never
Really? Gee I must be sleeptyping again. 
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
i want to make a schedule for distributing employees over a month ,using genetic algorithm & C#
can anyone tell me plz how to proceed ?
|
|
|
|
|
|
In excel there is function COMBIN(number,number_chosen)
COMBIN(7,6) WILL RETURN TOTAL 7 COMBINATION
COMBIN(20,6) WILL RETURN TOTAL 38760 COMBINATION
I need the total combintions generated the when the values are given in sql server stored procedure
|
|
|
|
|
You can calculate factorial with FACT function so calculation a combination shouldn't be a problem
|
|
|
|
|
COMBIN(x,y) is simply calculed as x!/(y!(x-y)!)
where x! = 1*2*3*4...*x
(this is simple to implement)
a faster way to solve x!/(y!(x-y)!) is (x*(x-1)*(x-2)*...(x-y+1))/y!
(in this way you have to do some * less)
Russell
|
|
|
|
|
Just discovered that there is Combin function in excel 2007
|
|
|
|
|
Hey Friends
I want to Draw Arc/Pie/Circle without using MFC methode...
I neeed proper algorithm to draw these object using SetPixel.
plz help me.//
|
|
|
|
|
This sounds like homework, did you try typing "circle drawing algorithm" into google before asking here?
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."
|
|
|
|
|
No my dear friend "cp9876"
these methodes are not supported in WinCE and i want to Draw Arc/pie/circle in WinCE....
So i need that Algo.
|
|
|
|
|
I think WinCE Version 3 supports them, or do you have to be compatible with previous versions
http://msdn2.microsoft.com/en-us/library/ms902019.aspx[^]
If you google on "circle drawing algorithms c++" you seem to get lots of samples, but I guess you must have done that.
You also continually cross-post.
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."
|
|
|
|
|
himuskanhere wrote: So i need that Algo.
sin() and cos()
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
|
El Corazon wrote: sin() and cos()
that would be very expensive.
Bresenham draws lines and circles.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Luc Pattyn wrote: Bresenham draws lines and circles.
Naturally, but I find Xiaolin Wu cancels out Breshenham, don't you?
Unless, the enemy has studied his EG reports[^], which I have.  (all apologies to William Goldman)
he asked for an algorithm, I gave one. I could have given a dozen more.
_________________________
Asu no koto o ieba, tenjo de nezumi ga warau.
Talk about things of tomorrow and the mice in the ceiling laugh. (Japanese Proverb)
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
