C++ number 出现在数组中的次数

Number of times number appears in an array

提问by mitya221

I found an exercise in a C++ book that says "Write a function that will count the number of times a number appears in an array.". Everything is fine, the program is working. But the exercise also says that the function should be recursive.

我在一本 C++ 书中找到了一个练习，上面写着“编写一个函数来计算一个数字在数组中出现的次数。”。一切正常，程序运行正常。但是练习也说这个函数应该是递归的。

How can I make a recursive function working like this?

如何使递归函数像这样工作？

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

采纳答案by Emil Vikstr?m

Instead of the loop and counter you have now, return 0 + recursive_stepor 1 + recursive_step, where recursive_stepis a call to count(...)where you have increased the array pointer and decreased length. Your base caseis when length == 0, at which point you just return 0.

而不是你现在拥有的循环和计数器， return 0 + recursive_stepor 1 + recursive_step， whererecursive_step是对count(...)你增加数组指针和减少的地方的调用length。您的基本情况是 when length == 0，此时您只需 return 0。

A nice way of understanding recursion is to study how the calculation is carried out, step by step. In your example you will do something like this:

理解递归的一个好方法是逐步研究计算是如何进行的。在您的示例中，您将执行以下操作：

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

---

---

If you are allowed to change the function specification, you can do also something cool called tail recursion. Instead of return 1 + count(...), add the accumulated number so far as a paremeter to count: int count(int number, int array[], int length, int acc)

如果您被允许更改函数规范，您还可以做一些很酷的事情，称为尾递归。取而代之的是return 1 + count(...)，将累计数作为参数添加到计数中：int count(int number, int array[], int length, int acc)

And do return count(..., acc+1)or return count(..., acc+0). Some compilers are then able to do tail call optimization, transforming it into a loop in the compiled code. This saves memory compared to a regular recursion.

并做return count(..., acc+1)或return count(..., acc+0)。一些编译器然后能够进行尾调用优化，将其转换为编译代码中的循环。与常规递归相比，这可以节省内存。

回答by mvp

Use this countfunction:

使用这个count功能：

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

回答by Rahul Tripathi

How about trying like this:-

试试这样怎么样：-

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

回答by dasblinkenlight

Here is what you do (I wouldn't show you any code to avoid spoiling an exercise for you).

这就是你要做的（我不会向你展示任何代码以避免破坏你的练习）。

First, recall that in order to be recursive your function needs to call itself. Next, consider these two points:

首先，请记住，为了递归，您的函数需要调用自身。接下来，考虑以下两点：

• When the lengthparameter is equal to zero, the return value of count(...)must be zero
• When the lengthparameter is not zero, consider the return value of count(...)for array + 1and length-1; let's call it prior. The return value of the current count(...)will be equal to prior+1if array[0]is equal to number, or to priorwhen array[0]is not equal to number.

• 当length参数为零时，返回值count(...)必须为零
• 当length参数不为零时，考虑count(...)for array + 1and的返回值length-1；让我们称之为prior。当前的返回值count(...)将等于prior+1if array[0]is equal tonumber或 to priorwhenarray[0]不等于number。

When you make your code out of this description, observe how you have an ifat the beginning of your recursive function. This ifsplits your code into the base case (length == 0) and the recursive step (computing the result based on a recursive call). This is a common structure of recursive functions: you will have to reproduce this structure every time you write recursive code.

当您根据此描述编写代码时，请注意if递归函数的开头是如何使用的。这if将您的代码分为基本情况 ( length == 0) 和递归步骤（根据递归调用计算结果）。这是递归函数的常见结构：每次编写递归代码时都必须重现此结构。

回答by cpp

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

回答by SAH

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