求N个人生日相同的出现概率

Question

我有一个作业是关于找出 N 个人生日相同的次数。我必须编写一个函数 findSameBirthday ，它将生日数组作为参数 和值 K。如果出现 K 相似的情况，该函数将返回

true

N 个元素内的生日。我生成了一个名为

birthdays

的数组，其中填充了从 0 到 364 的数字。但是，当我运行代码时，我似乎没有得到输出。我哪里出错了？

我检查数组中相同生日的想法是：

1. 从

   birthdays[0]

   开始，我会用

   birthdays[1]

   ，

   birthdays[2]

   ，

   birthdays[3]

   ，...，

   birthdays[999]

   来检查。
2. 从

   birthdays[1]

   开始，我会用

   birthdays[2]

   ，...，

   birthdays[999]

   来检查。
3. 每成功找到一个，我都会将

   hit

   加 1。
4. 因此，只要

   hit

   是1或更大，我就会返回

   true

   ，否则我会从函数

   false

   返回

   findSameBirthday

   。

这是我的代码；它也在这里：http://codepad.org/JFLvUn4w

  #include <stdio.h>
  #include <stdbool.h>
  #include <stdlib.h>
  #include <time.h>
  #define SEED time(0)
  #define MAX 1000

  void fillBirthdays(int birthdays[], int N);
  bool findSameBirthday(int birthdays[], int k);

  int main(void)
  {
      int birthdays[MAX]={0};
      int hits=0, k=0, N=0;

      scanf("%d", &N);
      srand((unsigned int) SEED);
      fillBirthdays(birthdays, N);
      findSameBirthday(birthdays, k);
      printf("%d", hits);

      return 0;
  }

  /*  
      fillBirthdays fills N birthdays into the array birthdays
      by using a table-lookup method.  The indices 0 to 364
      represent the different birthdays, and the value of 
      birthdays[k] is the number of people within the group of N
      having the same birthday k.

  Precondition: none.
   */
  void fillBirthdays(int birthdays[], int N)
  {
      int i=0;

      for(i=0;i<N;i++)
      {
          birthdays[i]=rand()%365;
      }

      return;
  }

  /*  
      findSameBirthday returns true if there are k (or more)
      same birthdays, and false otherwise.

  Precondition: none.
   */
  bool findSameBirthday(int birthdays[], int k)
  {
      int N=0, i=0, j=0, hits=0;
      bool samebirthday=true;

      for(i=0;i<N;i++)
      {
          for(j=1;j<N;j++)
          {
              if(birthdays[i]==birthdays[j])
                  hits=hits+1;
          }
      }
      if(hits>0)
          return samebirthday;
      else
          return false;
  }

Answer 1

这应该可以修复您的

findSameBirthday

功能：

/* findSameBirthday returns true if there are k (or more)
   same birthdays, and false otherwise.

   Precondition: none. */
bool findSameBirthday(int birthdays[], int k)
{
    int hits = 0;

    /* We don't know how big the array is, but that's ok,
       loop to max but break out early if needed. 
       birthdays array is 0 initialized so will be filled 
       with 0's where no data is present. */
    for (int i = 0; i < MAX; i++)  
    {
        if (!birthdays[i]) {break;}     // We have reached the end of the array, break out
                                         // And check hit count
        for (int j = i+1; j < MAX; j++)  // Start from i+1 so there is no overlap
        {
            if (!birthdays[j]) {break;} // We have reached the end of the array, break out 
                                        // And check next number
            if (birthdays[i] == birthdays[j])
                {hits++;}
        }
    }
    return hits >= k; // >= means equal or more
}

您当然也可以将

N

传递到函数中。然后，您可以删除循环中的检查和中断，但我想匹配您的函数声明。

/* findSameBirthday returns true if there are k (or more)
   same birthdays, and false otherwise.

   Precondition: none. */
bool findSameBirthday(int birthdays[], int N, int k)
{
    int hits = 0;
    
    /* We don't know how big the array is, but that's ok,
       loop to max but break out early if needed. 
       birthdays array is 0 initialized so will be filled 
       with 0's where no data is present. */
    for (int i = 0; i < n; i++)  
    {
        for (int j = i+1; j < n; j++)  // Start from i+1 so there is no overlap
        {
            if (birthdays[i] == birthdays[j])
                {hits++;}
        }
    }
    return hits >= k; // >= means equal or more
}   

通过这样的输入你就明白了：

int birthdays[] = {5, 5, 2, 7, 5, 9, 5};

此算法的结果将是

sum(0 to n-1)

，其中

n

是同一天生日的人数？
（在这种情况下，结果将是

6

）。

至于为什么您没有得到任何输出，您（当前）应该看到

0

输出（参见此处）。这是因为你在main中将

hits

设置为

0

并且没有修改它。

如果你想让它只说有“k”个匹配的生日或没有，你可以将

main()

的结尾更改为：

//findSameBirthday(birthdays, k);
printf("%s", findSameBirthday(birthdays, k)?
       "No. of matching Birthdays hits threshold":
       "No. of matching Birthdays does not hit threshold"
);

如果要输出

hits

的数量：

• 将

  findSameBirthday

  的函数原型更改为

  int findSameBirthday(...)

• 从

  hits

  返回

  findSameBirthday()

• 主要：

  hits = findSameBirthday(birthdays, k);
  printf("Number of matching birthdays found: %d", hits);
  

这将输出点击次数。