I want to create a 2D dynamic bool array (or char is fine too). I'm doing the n-queens problem and I've figured everything out except for this part. Any help?
Name:
Anonymous2006-01-11 9:17
>>35
Everything that can be done as iteration can also be done as tail recursion.
Name:
Anonymous2006-01-11 9:21
As far as gcc4 is concerned these two functions are equivalent (they literally produce the same assembler). As far as gcc3 is concerned the first one sucks donkey balls. extern int cities[];
int distance(int a, int b)
{
if(a==b)
return 0;
else
return (cities[b-1] + distance(a, b-1));
}
int distanceii(int a, int b)
{
int x = 0;
while (a != b)
x += cities[--b];
return x;
}Still, both of them are a flawed solution to the problem.
Name:
Anonymous2006-01-11 12:44
So, can you tell me what is not a flawed solution?
Name:
Anonymous2006-01-11 13:07
And give away the answer to someone's homework? Fuck no.
Name:
Anonymous2006-01-11 13:08
haha, well it's obvious you dont know the answer.
Name:
Anonymous2006-01-11 15:27 (sage)
>>45
Oh noes, I have been insulted over the internets! Now I must listen to Nightwish and cut myself.
Name:
Anonymous2006-01-11 16:44
bare grace misery is my favorite. okay guys, if the solution should some sort of recursion type then let me know. if its iterative tell me. i posted just to know genreally speaking which method would be more efficient.
Name:
Anonymous2006-01-11 17:04
orz...I wasted too much time on this. Not that the original poster would understand this... Not that I tested this either.
int N = 5;
int cities[N] = {5,3,2,6,7};
int *distances;
int sum (int a, int b) { return ((b*(b+1) - a*(a-1))/2); }
int index (int a, int b) { return (a*N - a*(a+1)/2 - 1 + b); }
int distance (int a, int b) { return (a==b ? 0 : distances[index(a,b)]); }
void make_distances (int a, int b) {
distances = malloc (sum(a,b));
int i=0,acc;
for (a=0; a++; a<N) {
acc = cities[a];
for (b=a+1; b++; b<=N) {
distances[i] = acc;
acc += cities[b];
}
}
}
Name:
Anonymous2006-01-11 17:26
>>48
You may have halved memory usage, but you're still in O(n^2). I assure you it can be done in memory O(n), initial calculation time O(n), and lookup time O(1).
>>47
Which means use either recursion or iteration -- but preferably iteration -- for the precalculation and use neither recursion not iteration for lookup.
Name:
Anonymous2006-01-11 17:42
Damnit, there is a mistake in my code in >>48. It should be void make_distances () {
distances = malloc (sum(0,N));
int a,b,i=0,acc;
for (a=0; a++; a<N) {
acc = cities[a];
for (b=a+1; b++; b<=N) {
distances[i] = acc;
acc += cities[b];
}
}
}Memory and initial calculatiion time is still O(n*(n+1)/2) though.
Name:
Anonymous2006-01-12 0:01
well, looking at it again, i got it. int N = 5;
int cities[N] = {5,3,2,8,7};
int *ctsums;
int distance (int a, int b) { return (ctsums[b-1]-ctsums[a-1]); }
void make_ctsums () {
ctsums = malloc(N);
int i,acc=0;
for (i=0; i++; i<N) {
acc += cities[i];
ctsums[i] = acc;
}
}O(n) space and init time. O(1) lookup. the solution was just staring at me...i can't believe i didn't see it before.
Name:
Anonymous2006-01-12 4:19
haha, damn i didn't even think about that. what a fool i am.