Go语言视频零基础入门到精通

zj905

算法是一组(有限个)规则，它为某个特定问题提供了解决问题的运算序列；也就是计算机解题的过程，在这个过程中，无论是形成解题思路还是编写程序， 都是在实施某种算法；前者是推理实现的算法，后者是操作实现的算法。

　　 计算机解题的核心是算法没汁。一个算法应该具有以下五个重要特征：
(1)有穷性：一个算法必须保证执行有限步之后结束；

(2)确切性：算法的每一步骤必须确切定义；

(3)输入：一个算法有0个或多个输入，所谓0个输入是指算法本身定出初始条件；

(4)输出： 一个算法有一个或多个输出，以反映对输人数据加工后的结果，没有输出的算法是毫无意义的；

(5)能行性：算法原则上能够精确地运行，做有限次即可完成。


  
　　递推法:递推法实际上是一种递推关系，就是为了得到问题的解，把它推到比原问题简单的问题求解，可分为顺推法和倒推法。
i.顺推法，就是先找到递推关系式，然后从初始条件出发，一步步地按递推关系式递推，直至求出最终结果

ii.倒推法，就是在不知道初始条件的情况下，经某种递推关系而获知问题的解，再倒过来，推知它的初始条件。



示例：猴子分食桃子

   五只猴子采得一堆桃子，猴子彼此约定隔天早起后再分食。不过，就在半夜里，一只猴子偷偷起来，把桃子均分成五堆后，发现还多一个，它吃掉这桃子，并拿走了其中一堆。第二只猴子醒来，又把桃子均分成五堆后，还是多了一个，它也吃掉这个桃子，并拿走了其中一堆。第三只，第四只，第五只猴子都依次如此分食桃子。那么桃子数最少应该有几个呢？

编程简析

   怎样编程呢？先要找一下第N只猴子和其面前桃子数的关系。如果从第1只开始往第5只找，不好找，但如果思路一变，从第N到第1去，可得出下面的推导式：

第N只猴    第N只猴分桃之前桃子数目
5               s(5)=x          //这个数x必需是4的倍数，且x-1必须是5的倍数。
4               s(4)=s(5)*5/4+1
3               s(3)=s(4)*5/4+1
2               s(2)=s(3)*5/4+1
1               s(1)=s(2)*5/4+1

s1即为所求。可以用循环语句加以解决。

综观程序的整体结构，最外是一个循环，其结束条件则是找到第一个符合条件的数。为了做出上面循环的结束条件，还需进一步分析上述规律的特点，要符合题目中的要求，s2-s5四个数必须全部为4的倍数，这个可作为条件。具体实现请参看源程序。

程序：

public class Monkeys{
   public static void main(String args[]){
   
    int i=0;

   for(int y=16;;y+=4){
      if((y-1)%5!=0) continue;
       int x=y;
    for(i=4;i>=1&&x%4==0;i--){
         x=(x/4)*5+1;
      
        }
      if(i==0) {
         System.out.println("第五个猴子分桃前的桃子数="+y);
         System.out.println("桃子数="+x);
         break;
      }
   
   
   }
  }
   
}
      

运行：

C:\java>java Monkeys
第五个猴子分桃前的桃子数=1276
桃子数=3121

附：另二种解法：

public class Test {
   
    public static void main(String[] args) {
        System.out.println(d());
       System.out.println(f(0.0));
    }
   
    /**
     * 循环算法
     * peach 分配完毕后剩余的桃子数
     * count 分配之前的桃子数
     * @return
     */
    private static double d() {
        double count = 0.0;
        //死循环,一直到找到这个数为止
        while (true) {
            //每次循环都要桃子数加一
            count++;
            //由桃子总数算出第五个猴子分完后剩下的桃子数,而这个数必须是整数
            double peach = count;
            for (int monkey = 5; monkey > 0; monkey--) {
                peach = (peach - 1) * 0.8;
            }
            //如果peach是整数,就返回桃子的总数量
            if (peach % 1 == 0.0)
                return count;
        }
    }
   
    /**
     * 递归算法
     * peach 分配完毕后剩余的桃子数
     * count 分配之前的桃子数
     * @param count
     * @return
     */
    private static double f(double count) {
        count++;
        double peach = count;
        for (int monkey = 5; monkey > 0; monkey--) {
            peach = (peach - 1) * 0.8;
        }
        if (peach % 1 == 0.0)
            return count;
        else
            return f(count);
    }
}