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

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

Использовать этот count функция:

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

Answer 3

Как насчет того, чтобы попытаться так:

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 4

#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 5

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

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

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

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

Answer 6

      #include <stdio.h>

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

int main() {
 
  int array[] = {1,2,2,4,4,8,7,3,4};
  int size = sizeof(array)/sizeof(int);

  printf("%d",count(2,array,size));

  return 0;    
}

Answer 7

 #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;
 }