Divide and conquer counter.

[tribe]

Hey guys i've got a problem. My code should count how many times number 2 occur in "tab" array. I have to use "divide and conquer" method. The problem is that 5 pops out when there are only 4x 2 in array. Where's the problem?

#include <iostream>
#include <cstdlib>
using namespace std;
    int tab[10]={2,2,3,2,2,7,8,6,5,4};
    int l=0;  

int ile_dziel(int start, int stop, int n)
{   
     if (start==stop) return tab[start];     
     int p=(start+stop)/2;                          
     int i1=ile_dziel(start,p, n);
     int i2=ile_dziel(p+1,stop, n);
     if (i1==n) l++;
     if (i2==n) l++;   
     return l;   
}

int main()
{
        int n;                       
        cout <<     ile_dziel(0,4,2);
        system("pause");
        return 0;       
}

[ahmad khan]

From code above cant really grasp what you are doing there. Does it have to be a recursive function?

Counting occurrences in an array is fairly simple mostly. even with a recursive program. the global variable I is supposed to be counting occurrences?

[tribe]

The thing is that i have to use "divide and conquer" to count occurrences and i have no idea how to do that. I tried with code above and it counts badly. =/

[cire]

"divide and conquer" doesn't necessarily mean "divide into equal length sub-arrays and conquer".

Let's begin with line 15.

You return the global variable that contains your count.

Now, let's look at what this means for lines 11 and 12. The obvious thing is that i1 and i2 can be the value of the global count. Does it then make sense to compare i1 and i2 to n?

A similar problem:

#include <iostream>

// division:  first element / rest of the array.
unsigned count_occurrences( const char* array, unsigned size, char letter )
{
    bool is_letter = *array == letter ;

    if ( size == 1 )
        return is_letter ;

    return is_letter + count_occurrences(array+1, size-1, letter) ;
}


int main()
{
    const char letters[] = "abcdnanlailkasdilufa" ;
    const unsigned letters_size = sizeof(letters) / sizeof(letters[0]) ;

    std::cout << "There are " << count_occurrences(letters,letters_size, 'a') << " a's.\n" ;
}

[ahmad khan]

above one given by cire is a good example of a recursive program. using this approach your problem can easily be handled.
Set one base case which terminates the recursive calling do the rest in else part.