Число раз число появляется в массиве

Question

Я нашел упражнение в книге на C++, в которой говорится: «Напишите функцию, которая будет подсчитывать количество раз, когда число появляется в массиве». Все в порядке, программа работает. Но в упражнении также говорится, что функция должна быть рекурсивной.

Как я могу сделать рекурсивную функцию таким образом?

#include <iostream> 

int count(int number, int array[], int length) 
{ 
    int counter = 0; 
    for(int i = 0; i < length; i++) 
     if(array[i] == number) 
      counter++; 
    return counter; 
} 

int main() 
{ 
    int numbers[10] = {3,4,1,2,4,5,6,5,4,5}; 
    int number_to_search = 5; 
    std::cout << number_to_search << " appears " 
       << count(number_to_search, numbers, 10) 
       << " times in the array."; 
    return 0; 
} 

Answer 1

Вместо петли и счетчик у вас есть сейчас, вернуть 0 + recursive_step или 1 + recursive_step, где recursive_step является вызов count(...), где вы увеличили указатель массива и уменьшилось length. Ваш базовый футляр есть, когда length == 0, в этот момент вы только что вернетесь 0.

Хороший способ понимания рекурсии - изучить, как выполняется расчет, шаг за шагом. В вашем примере вы будете делать что-то вроде этого:

count(5, {3,4,1,2,4,5,6,5,4,5}) 
0+count(5, {4,1,2,4,5,6,5,4,5}) 
0+0+count(5, {1,2,4,5,6,5,4,5}) 
0+0+0+count(5, {2,4,5,6,5,4,5}) 
0+0+0+0+count(5, {4,5,6,5,4,5}) 
0+0+0+0+0+count(5, {5,6,5,4,5}) 
0+0+0+0+0+1+count(5, {6,5,4,5}) 
0+0+0+0+0+1+0+count(5, {5,4,5}) 
0+0+0+0+0+1+0+1+count(5, {4,5}) 
0+0+0+0+0+1+0+1+0+count(5, {5}) 
0+0+0+0+0+1+0+1+0+1+count(5,{}) 
0+0+0+0+0+1+0+1+0+1+0 <---The last 0 is the base case 
3 

---

Если разрешено изменить спецификацию функции, вы можете сделать и что-то прохладное под названием хвостовая рекурсия. Вместо return 1 + count(...), добавьте накопленное количество в качестве счетчика, чтобы посчитать: int count(int number, int array[], int length, int acc)

И сделать return count(..., acc+1) или return count(..., acc+0). Некоторые компиляторы тогда могут сделать оптимизацию хвостового вызова, превратив его в цикл в скомпилированном коде. Это экономит память по сравнению с обычной рекурсией.

Answer 2

Как о попытке так: -

int count(int num, int* arr, int length) { 
    if (!length) 
     return 0; 
    int c = count(num, arr+1, length-1); 
    return arr[0] == num? c + 1: c; 
} 

int main(void) { 
int arr[10] = {3,4,1,2,4,5,6,5,4,5}; 

std::cout << count(2, arr, 10); 

return 0; 
} 

Answer 3

count Используйте эту функцию:

int count(int number, int array[], int length) { 
    if (length == 0) return 0; 
    return (number == *array) + count(number, array+1, length-1); 
} 

Answer 4

Вот что вы делаете (я бы не показать вам код, чтобы не портить упражнение для вас).

Во-первых, напомним, что для того, чтобы быть рекурсивным, ваша функция должна называть себя. Далее рассмотрим эти две точки:

• Когда параметр length равен нулю, то возвращаемое значение count(...) должна быть равна нулю
• Когда параметр length не равен нулю, рассмотрим возвращаемое значение count(...) для array + 1 и length-1; назовем его prior. Возвращаемое значение тока count(...) будет равно prior+1, если array[0] равно number, или prior, если array[0] не равно number.

Если вы внесли свой код из этого описания, обратите внимание, как у вас есть if в начале вашей рекурсивной функции. Этот if разбивает ваш код на базовый регистр (length == 0) и рекурсивный шаг (вычисление результата на основе рекурсивного вызова).Это общая структура рекурсивных функций: вам придется воспроизводить эту структуру каждый раз, когда вы пишете рекурсивный код.

Answer 5

#include <iostream> 

void count(int number, int array[], int length, int &occurence) 
{ 
    if (*array == number) ++occurence; 

    if (length == 1) 
     return; 
    else  
     count(number, array+1, length-1, occurence); 
} 

int main() 
{ 
    int numbers[10] = {3,4,1,2,4,5,6,5,4,5}; 
    int number_to_search = 5; 
    int occurence = 0; 
    count(number_to_search, numbers, 10,occurence); 
    std::cout << number_to_search << " appears " 
       << occurence 
       << " times in the array."; 
} 

Answer 6

#include <iostream> 
#include <ctime> 
#include <cstdlib> 
using namespace std; 
int i, j,n,c=0, k=0; 
int a[1000], b[1000]; 
class Array { 


    public: 
     void input() 
     { 
      cout<<"Enter how many values: "; 
      cin>>n; 
     } 

     void arraySeries() 
     { 
      cout<<"Array elements: "; 
      srand(time(0)); 
      for (i=0; i<n; i++) 
      { 
       a[i]=rand()%100+1; 
       cout<<a[i]<<" "; 

      } 
      cout<<endl<<endl; 
      cout<<"Odd elements of array: "; 
      for (i=0; i<n; i++) 
      { 
       if(a[i]%2==1) 
       { 
        b[i]=a[i]; 
        k++; 
        cout<<b[i]<<" "; 
       } 

      } 
     } 
     // i want to find out how many times an odd number is found in b[i] 
     // but i am not being able to do so. SOMEONE PLEASE HELP!! 
     void OddSearch() 
     { 
      cout<<endl<<endl; 
      for (int k=1;k<100;k++) 
      { 
       c=0; 
       for (i=0;i<n; i++) 
       { 

        if (b[i]==k) 
        { 
         c++; 
        } 
        cout<<b[i]<<"occurs"<<c<<"times"<<endl; 
       } 
      } 
     } 
}; 

int main() 
{ 
    Array obj; 
    obj.input(); 
    obj.arraySeries(); 
    obj.OddSearch(); 

    return 0; 
}