分鱼问题

题干：分鱼问题

用数组 num[5]表示每人醒来看到的鱼的数目：

num[1] : A
num[2] : B
num[3] : C
num[4] : D
num[5] : E

num[i + 1] = (num[i] - 1) / 5 * 4

注意：物理意义下， num[i] - 1 应该为 5 的倍数。

#include <iostream>
using namespace std;
int main()
{
  // 定义数组，每个人看到鱼的数目
  int num[5];
  // 枚举num[0]
  for(num[0] = 1; ; num[0]++)
  {
    if(num[0] % 5 != 1)
      continue;
    num[1] = (num[0] - 1) / 5 * 4;
    if(num[1] % 5 != 1)
      continue;
    num[2] = (num[1] - 1) / 5 * 4;
    if(num[2] % 5 != 1)
      continue;
    num[3] = (num[2] - 1) / 5 * 4;
    if(num[3] % 5 != 1)
      continue;
    num[4] = (num[3] - 1) / 5 * 4;
    if(num[4] % 5 != 1)
      continue;
    break;
  }
  // 输出答案
  for(int i = 0; i < 5; i++)
    cout << num[i] << endl;
}

优化：

#include <iostream>
using namespace std;
int main()
{
  // 定义数组，每个人看到鱼的数目
  int num[5];
  // 枚举num[0]
  // num[0]至少是 6*(5/4)^4约等于15，可以从16开始枚举
  for(num[0] = 16; ; num[0]++) // 从5开始，减少自增次数，删掉num[0] % 5 != 1判断
  {
    int i;
    for(i = 1; i <= 4; i++)
    {
      num[i] = num[i - 1] / 5 * 4; // 考虑到整数相除
      if(num[i] % 5 != 1)
        break;
    }
    if(i <= 4)
      continue;
    break;
  }
  // 输出答案
  for(int i = 0; i < 5; i++)
    cout << num[i] << endl;
}

反向递推优化：

num[i+1] = (num[i] - 1) / 5 * 4 => num[i] = num[i + 1] / 4 * 5 +1

#include <iostream>
using namespace std;
int main()
{
  // 定义数组，每个人看到鱼的数目
  int num[5];
  for(num[4] = 6; ; num[4] += 5)
  {
    if(num[4] % 4 != 0)
      continue;
    num[3] = num[4] / 4 * 5 + 1;
    if(num[3] % 4 != 0)
      continue;
    num[2] = num[3] / 4 * 5 + 1;
    if(num[2] % 4 != 0)
      continue;
    num[1] = num[2] / 4 * 5 + 1;
    if(num[1] % 4 != 0)
      continue;
    num[0] = num[1] / 4 * 5 + 1;
    break;
  }
  // 输出答案
  for(int i = 0; i < 5; i++)
    cout << num[i] << endl;
}

优化：

#include <iostream>
using namespace std;
int main()
{
  // 定义数组，每个人看到鱼的数目
  int num[5];
  for(num[4] = 6; ; num[4] += 5)
  {
    int i = 4;
    for(; i >= 1; i--)
    {
      if(num[i] % 4 != 0)
        break;
      num[i - 1] = num[i] / 4 * 5+ 1;
    }
    if(i >= 1)
      continue;
    break;
  }
  // 输出答案
  for(int i = 0; i < 5; i++)
    cout << num[i] << endl;
}