Table of Contents

问题

A,B,C,D,E五人一起去捕鱼，到第二天早上凌晨都疲惫不堪，于是各自找地方睡觉。日上三杆，A第一个醒来，他扔掉一条后恰好将鱼均分为五份，然后拿走自己的一份。B第二个醒来，扔掉一条鱼后恰好均分五份，拿走自己的一份。C,D,E依次醒来，也按同样的方法分鱼，问他们一共捕了多少条鱼？

分析

设A,B,C,D,E在分鱼时面对自己的鱼的数量分别为\(na\),$nb$,\(nc\),$nd$,$ne$。则这些数有类似\(nb= \frac{4(na-1)}{5}\) 和 $na= \frac{5(nb-1)}{4}$的递推关系。 这是本题的题眼之一，另外需要知道 \(na-1\), \(nb-1\),$nc-1$,\(nd-1\),$ne-1$都可以被5整除。 根据这两条线索即可解题。另外这道题目的答案应该不是唯一的，不过默认找满足条件的最小的数值

解决方案

1:  /** 2:   * @file   015fishing.c 3:   * @author Chaolong Zhang 
      
        4:   * @date   Wed May 15 19:21:18 2013 5:   *  6:   */ 7:   8:  #include 
       
         9:  int main(int argc, char *argv[])10:  {11:      int n,i,x,flag=1;12:      for (n=6; flag; n++)13:      {14:          for (x=n,i=1&&flag; i <= 5; ++i)15:          {16:              if (0==( x-1 )%5 )17:              {18:                  x=4*( x-1 ) /5;19:              }20:              else flag=0;21:          }22:          if (flag) break;23:          else flag=1;24:      }25:      printf ("%d \n", n);26:      return 0;27:  }
       
      

最后的结果为3121。

我对这五个人的捕鱼能力有点好奇，想知道他们倒底能捕多少鱼，为了避免计算机死机（我对他们充满信心啊），我先找出前二十种可能。稍微修改代码

1:  #include 
      
        2:  int main(int argc, char *argv[]) 3:  { 4:      int n,i,x,flag=1,time=0; 5:      for (n=6; flag&&( time<20 ); n++) 6:      { 7:          for (x=n,i=1&&flag; i <= 5; ++i) 8:          { 9:              if (0==( x-1 )%5 )10:              {11:                  x=4*( x-1 ) /5;12:              }13:              else flag=0;14:          }15:          if (flag) 16:          {17:              time++;18:              printf ("%d \n", n);19:          }20:          else flag=1;21:      }22:      printf ("%d \n", n);23:      return 0;24:  }
      

输出为

3121 6246 9371 12496 15621 18746 21871 24996 28121 31246 34371 37496 40621 43746 46871 49996 53121 56246 59371 62496

看来我的判断能力还是可以的幸亏没有把 time 设的过大。

解后语

虽然得到了3121和前20中可能的捕鱼数量，这个代码还有优化的空间主要集中在两方面

• 1）如何快速的找到3121, 代码中，n的跳动是从6开始，步长为1,其实很容易知道步长初始值6肯定不是na正确的值，6是ne的最小值。
• 2）如何快速的前二十个值。如何快速找出前二十个值不仅受n的前进步长影响，还受n的初始值影响。

接下来就试着解决这两个问题，

\(na\),$ne$ 都有一个共同特点减一之后能被5整除，所以最后的结果个位数不是1就是6,这也和之前的输出一致。

另外，na和ne有如下递推关系

\begin{equation} na = (\frac{5}{4})^{5}ne +(\frac{5}{4})^{4} + (\frac{5}{4})^{3} + (\frac{5}{4})^{2} + \frac{5}{4} + 1 \end{equation} \begin{equation} na = 3.0518ne + 2.4411 + 1.9531 + 1.5625 + 1.25 + 1 \end{equation} \(2.4411 + 1.9531 + 1.5625 + 1.25 + 1=8.2070\)

取整后为

\begin{equation} na = 3ne + 8 \end{equation}

这个递推关系对分析最小步长有没有影响呢？

所以我认为第一个 for 循环的 n++ 可以该为 n=3*n + 8 。编译运行最后结果是 165706246 。结果出来的那一刻我被吓到了，这几个人太强了。 不过为什么我的这次改动没有计算出满足条件的最小解呢？显然，问题是 n的步进没有算对，难道是取整的过程中步子迈得太大么？是不是

\(2.4411 + 1.9531 + 1.5625 + 1.25 + 1\)

取整时应该取整为

\(2 + 1 +1 +1 + 1=6\)

修改，编译，运行结果为 -261493754 溢出了也没算出个正确答案。

初步断定

那么这个最佳步长怎么设置才好呢？这是个问题。 我感觉自己走了一些弯路。停下来，干点别的什么事吧！

仔细观察

通过观察之前的20种可能的情况，我发现这些数的个位数不是1就是6,也即是说步长最小可以设为5， 赶紧试一下这个猜测。

1:  #include 
      
        2:  int main(int argc, char *argv[]) 3:  { 4:      int n,i,x,flag=1,time=0; 5:      for (n=6; flag&&( time<20 ); n=n+5) 6:      { 7:          for (x=n,i=1&&flag; i <= 5; ++i) 8:          { 9:              if (0==( x-1 )%5 )10:              {11:                  x=4*( x-1 ) /5;12:              }13:              else flag=0;14:          }15:          if (flag) 16:          {17:              time++;18:              printf ("%d \n", n);19:          }20:          else flag=1;21:      }22:      printf ("%d \n", n);23:      return 0;24:  }
      

果然输出了之前的那20个数，那么最快步长应该是5的奇数倍。 倒底是多少，我又试了15, 25, 35, 45,结果我发现有的可以有的不可以。这个步长跟起始值也有关系。我预计如果起始值选为3121，步长选为3125应该也会出同样的20个值。

1:  #include 
      
        2:  int main(int argc, char *argv[]) 3:  { 4:      int n,i,x,flag=1,time=0; 5:      for (n=3121; flag&&( time<20 ); n=n+3125) 6:      { 7:          for (x=n,i=1&&flag; i <= 5; ++i) 8:          { 9:              if (0==( x-1 )%5 )10:              {11:                  x=4*( x-1 ) /5;12:              }13:              else flag=0;14:          }15:          if (flag) 16:          {17:              time++;18:              printf ("%d \n", n);19:          }20:          else flag=1;21:      }22:      printf ("%d \n", n);23:      return 0;24:  }
      

输出为

3121 6246 9371 12496 15621 18746 21871 24996 28121 31246 34371 37496 40621 43746 46871 49996 53121 56246 59371 62496 65621

果然最快的计算出所有可能情况的设置方式是 起始值射为3121,步长设为3125 这样的设置保证每一次外部的 for 循环都

总结

最后的结论是

• 1)若要找3121, 初值为个位数为1或6的数都行，比如11,286之类的。 步长为3125的因子(625,125,25,5,1)都可以，当然是625最快。
• 2)若要快速找出所有可能数，初值3121,步长3125最快.