Thread: Looking not founding (the problem)

Hi Guys!

I have this little piece of code, that generates an exception if I set NUM_P to lets say 4000 or more.

Code:

#define NUM_P 2300
#define PARTY_NUM 100
#define PEOPLE_PER_PARTY NUM_P/PARTY_NUM

	for (a = 1; a<= PARTY_NUM; a++)
	{
		for (i = PEOPLE_PER_PARTY*(a-1); i < PEOPLE_PER_PARTY*a; i++)
	{
		for (k = PEOPLE_PER_PARTY*(a-1); k < PEOPLE_PER_PARTY*a -(i-PEOPLE_PER_PARTY*(a-1)); k++)
		{


			if ( k != 0)
			if (bday[i] == bday[k + i])  
				count++;
	
		}
	}
	}

This is basically a counter that checks an array to see if 2 int's match.



Before I tried to pirk it up a little the code was like this

Code:

#define NUM_P 2300
#define PARTY_NUM 100
#define PEOPLE_PER_PARTY NUM_P/PARTY_NUM

	for (a = 1; a<= PARTY_NUM; a++)
	{
		for (i = PEOPLE_PER_PARTY*(a-1); i < PEOPLE_PER_PARTY*a; i++)
	{
		for (k = PEOPLE_PER_PARTY*(a-1); k < PEOPLE_PER_PARTY*a; k++) 
		{
			if ( i != k)
			if (bday[i] == bday[k])
				count++;

	
		}
	}
	}

What I tried to do in the first algorithem is to count the array (for example for bday[10] to bday[20] so that we wouldn't count twice, or just plain wrong) because you can see that in the second algorith(second prog.) if let's say 10,14,15,16 match then we would count++ 4*3 = 12 times, but we only had 4 matches so this has to be fixed.


So now to the conclusion, what I'm askin' is if you can scan through it if you can catch the bug, because I've been looking at it for some time now and I'm starting to get delirious. I'll continue debugin' meanwhile any help will be appreciated.

PS: If you happen to find any loopholes in the algorythm be sure to mention them.

Thnx

The second number must always be larger than the first, so k needs to start, not at the beginning, but at i+1. And do you want the number of matches, or the number of people? For example 2 people give 1 match, 3 people give 3 matches, 4 people (your example) give 6 matches, et cetera.

I must say I don't understand what you mean.

The second number must always be larger than the first, so k needs to start, not at the beginning, but at i+1.

Yeah you're right that is wierd, now that I see it, I'll go with the num. of matches, more natural

In a case like this (with only 366 possibilities) you may as well use
an integer array of 366 elements for your counters. Suppose it's
called "days". Initially zero it out, then loop through the people and
do this for each:

Code:

++days[bday[i]]

Then loop through "days" to see how many elements are more than 1,
indicating a match.

The second number must always be bigger than the first. You can't go matching 10 with 11 and then 11 with 10. You need to match 10 with 11 through 20; 11 with 12 through 20 (not 10 through 20!); 12 with 13 through 20; ...; 18 with 19 and 20; 19 with 20.

The second number must always be bigger than the first. You can't go matching 10 with 11 and then 11 with 10. You need to match 10 with 11 through 20; 11 with 12 through 20 (not 10 through 20!); 12 with 13 through 20; ...; 18 with 19 and 20; 19 with 20.

I totaly agree but I don't see where I'm doing that, do you mean this line

Code:

if (bday[i] == bday[k + i])

if it is, I don't see the flaw.

Nucleon, that is a good idea, BUT not for what I'm doing, at least I think that it wouldn't work (wouldn't do the comparison with the idea on which it is based)

Originally Posted by Crazed

I totaly agree but I don't see where I'm doing that, do you mean this line

Code:

if (bday[i] == bday[k + i])

if it is, I don't see the flaw.

Nucleon, that is a good idea, BUT not for what I'm doing, at least I think that it wouldn't work (wouldn't do the comparison with the idea on which it is based)

I was looking at the second program you posted which was

Code:

for (k = PEOPLE_PER_PARTY*(a-1); k < PEOPLE_PER_PARTY*a; k++)

that. Since (I thought) that was the code that was giving you too many matches.

I would have done the coding for you on this one since the title alone gave me a smile.