|
I think that is along the lines of what I described in my Physics Forum post (see above). But a TSP solution will generically work for both lines and polylines with minimum complication.
|
|
|
|
|
I answered that as well in the last paragraph  . I'm assuming that the black lines are in some known direction, otherwise you have to pick a direction vector ... but just choosing the perpendicular to any one of the lines should work fine. It doesn't actually matter whether the order ends up as ABCD or DCBA, and picking a perpendicular will guarantee one of those will be the case if the lines are close to parallel. (The average perpendicular for all the lines will be better but probably unnecessary.)
|
|
|
|
|
I have to write a program in java for wordwrap with minimum regard...
for example if we have "aaa bb cc ddddd" and want to wrap it in lines with this method the final form should be like this :
------ Line width: 6
aaa Remaining space: 3 (cost = 3 squared = 9)
bb cc Remaining space: 1 (cost = 1 squared = 1)
ddddd Remaining space: 1 (cost = 1 squared = 1)
attention that we don't know number of lines...I don't understand the algorithm which is in wikipedia ,in this link :
http://en.wikipedia.org/wiki/Word_wrap[^]
but unfortunately I still have problem with understanding the algorithm...can some one explain it with example for me ?
|
|
|
|
|
You have already asked this question in Q&A. Read the guidelines, and ask your question ONCE if you don't want to annoy people who might otherwise have an answer for you.
Software rusts. Simon Stephenson, ca 1994.
|
|
|
|
|
Hi...I wanna write a program in java that can count the number of balanced matrix of N*N...the only way that I know is to consider all the possible assginments for the matrix and then choose the answers...I searched the topic and found something about it in wikipedia...it solved the problem with dynamic programming but unfortunately I don't understand exactly the algorithm...can anyone help and explain completely with example for me what to do ?
this is the link that I found :
http:
|
|
|
|
|
Dynamic programming can be used when optimal solutions are composed of optimal sub-solutions. You start with the smallest optimal sub-solutions, and use them to build up optimal solutions to larger sub-problems.
This typically runs in polynomial time, which is faster than trying all possible solutions, which would take exponential time.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
plz can anyone tell me how to store the data in text file using file handling in java...
plx Mail me comprehensive program of file handling, explain with comment and few of explanation...
asadali.nazir@gmail.com
|
|
|
|
|
See here[^] for all the information you need.
Unrequited desire is character building. OriginalGriff
I'm sitting here giving you a standing ovation - Len Goodman
|
|
|
|
|
Unless you want a lot of spam in your inbox, please do not put your e-mail address in a message posted publicly.
"Science is facts; just as houses are made of stones: so, is science made of facts. But, a pile of stones is not a house, and a collection of facts is not, necessarily, science." Henri Poincare
|
|
|
|
|
This article: Graphical solution to eight queen problem[^] mentions "the old algorithm from Horowitz-Sahani". Does anyone here have more information on this? I haven't found anything online, I'm thinking it's only in a text book.
|
|
|
|
|
|
Ah, good, thanks. That first one still just shows the snippet* posted in the article I mentioned, I was hoping to see more on the algorithm.
* And that's what I came up with on my own last week.
Also, I note in the second one that he's using recursion -- my algorithm is non-recursive.
P.S. I just ordered a used copy of that book from Amazon. 
modified 1-Jan-12 10:27am.
|
|
|
|
|
I would be interested in seeing your algo to see how it stacks up with some of my algos for removing recursion.
Dave.
|
|
|
|
|
Once I've seen what's in the book I'll decide whether or not mine is unique enough to form an article.
|
|
|
|
|
The book arrove today. My code is very much like the code they show on page 338 with two main differences:
0) They have the test in a separate function and therefore a global array.
(Which also has a needless call to ABS.)
1) They have an extra while loop.
public static System.Collections.Generic.IEnumerable<System.Collections.Generic.IList<int>>
nQueens
(
int HowMany
)
{
int[] board = new int [ HowMany ] ;
int row = 0 ;
board [ row ] = -1 ;
while ( row >= 0 )
{
board [ row ]++ ;
if ( board [ row ] == HowMany )
{
row-- ;
}
else
{
int i ;
for ( i = 0 ; i < row ; i++ )
{
int diff = board [ row ] - board [ i ] ;
if ( ( diff == 0 ) || ( System.Math.Abs ( diff ) == ( row - i ) ) )
{
break ;
}
}
if ( i == row )
{
row++ ;
if ( row == HowMany )
{
yield return ( System.Array.AsReadOnly ( board ) ) ;
row-- ;
}
else
{
board [ row ] = -1 ;
}
}
}
}
yield break ;
}
|
|
|
|
|
Thank you for your reply. I gather that this is your algorithms since it only has one "while" loop. It may take me a while to digest this, I am primarily a MASM developer, but come here for algorithms.
Do you have any guesses as to how large "HowMany" can be and not run out of memory, i.e., what would be the maximum n for nQueens with this algo?
Dave. (Another Desert Rat from West Phoenix)
|
|
|
|
|
Oh, yes, that's mine. The book uses a Pascal-like language the authors created called SPARKS.
On my system (Win 7 32bit, 4GB RAM), somewhere around 438330000 depending on what else is going on:
C:\Projects>nQueens 438330000
^C
C:\Projects>nQueens 438335000
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.
at PIEBALD.Lib.LibMth.<nQueens>d__0.MoveNext()
at PIEBALD.Utilities.nQueens.Main(String[] args)
I have heard that .net limits the size of a structure (e.g. an array) to two gigabytes.
Member 4194593 wrote: Desert Rat from West Phoenix
Ah, then I invite you to join the Tosche Station group. http://www.codeproject.com/Members/Tosche-Station[^]
modified 11-Jan-12 16:22pm.
|
|
|
|
|
Does .net limit you if the /3GB switch is used in c:\boot.ini.bat?
Dave.
|
|
|
|
|
I expect so, but I haven't tried it.
|
|
|
|
|
If you go to try it, be aware if the pitfalls:
Boot.ini is System,Hidden,Readonly.
I think you need to be Administrator.
Change the permissions to R/W.
Even as Admin you cannot edit boot.ini with ordinary editors, use RUN NOTEPAD.
Open boot.ini
Change [OS] multi(0)... and add /3GB.
Save boot.ini
For your own safety, change permissions back to RO.
Boot the system.
Also, you do have a good disk image backup don't you?
Dave.
|
|
|
|
|
Ah, thanks, but I'm not going to try it.
|
|
|
|
|
Turing Machine Simulator
Write a program that simulates a Turing machine (Tm). A Tm is a primitive model of a general purpose computer. Programs for a Tm consist of a collection of quadruples, each of the following form:
<state> <symbol> <action> <nextstate>
where
<state> ::= a non-negative integer
<symbol> ::= 1 | B
<action> ::= <symbol> | L | R
<nextstate> ::= a non-negative integer
A Tm stores data on a tape divided into squares, each of which contains one symbol, either 1 or B. Only one square can be inspected at a time. Initially, a sequence of symbols is written on the tape (this is the input to the Tm), the Tm's "read/write head" is positioned over the leftmost symbol, and the state of the Tm is set to some "start state".
At any point in a Tm computation, the Tm is in a particular state with its read/write head scanning the symbol in a particular square. What happens next depends on whether the Tm's program contains a quadruple whose <state> is the Tm's current state and whose <symbol> is the symbol contained in the square currently being scanned. If such a quadruple exists (there cannot be more than one such), the <action> part of this quadruple controls what happens next:
if <action> specifies a symbol, then that symbol replaces whatever symbol is in the square currently under scan
if <action> is L, the Tm's read/write head is moved one square to the left (the symbol in the square previously under scan is not changed)
if <action> is R, the Tm's read/write head is moved one square to the right (the symbol in the square previously under scan is not changed)
After one of the above actions is done, the Tm changes to state <nextstate> and we repeat the process of searching for an appropriate quadruple to "execute". This is continued until no quadruple matches the current state and symbol under scan, in which case the Tm halts and we consider its output to be the sequence of symbols between the first and last 1's on the tape, inclusive (if no 1's remain, we consider the output to be just B).
The input is a sequence of Tm instruction quadruples followed by a "start" line that specifies the initial state for the Tm, followed by the sequence of symbols that make up the initial value stored on the Tm's tape. Generically:
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
...
start <state>
<symbol>
<symbol>
<symbol>
<symbol>
<symbol>
...
For example:
0 1 R 0
0 B 1 1
start 0
1
1
1
1
Given the above input, the output should be:
11111
Note
If a quadruple requires moving left from the leftmost symbol on the tape, or right from the rightmost symbol, a square containing the symbol B must be added to the appropriate end of the tape (which is thus "finite, but unbounded")
|
|
|
|
|
Nobody is going to write your homework for you.
Unrequited desire is character building. OriginalGriff
I'm sitting here giving you a standing ovation - Len Goodman
|
|
|
|
|
Ooooohhh... Turing Machines. I love Turing Machines, I played with writing them a few different ways* a year ago and was thinking of writing an article. I also read The Annotated Turing/[^] last summer. 
But I won't do your homework for you.
* One of my favorites is written in XML / XSLT; what language are you supposed to use?
|
|
|
|
|
Hi out there,
I am writing a component which parses current html-data.
This data contains a list of elements depending on a date time. Unfortunately this date time is given in the following format: "Day.Month DayOfWeek" - e.g. "22.12 Thursday".
Now, in december, the list contains elements with a date time set in the next year, e.g. "5.1 Thursday", so the parser has to decide which year he use to return an unique date time (2011 or 2012 or others).
Since the data could be in the past too (20010), my idea is the following:
The last YPast and the next YFuture years are checked whether the given day in the given month is actually the given day of week (e.g. if the 22.12.2012 actually is a thursday) and the year with the smallest distance to today which meets this condition is used.
Because it is very important, that the parsed date time is correct, the algorithm has to be as good as possible.
So my question: Are there any better ideas than mine or any improvements? In which circumstances it comes to collisions? Which value should be selected for YPast and YFuture?
If you find spelling- or grammer-mistakes, please let me know, so that I can correct them (at least for me) - english is not my first language...
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
