黑马程序员技术交流社区
标题:
斐波那契兔子问题分析给大家借鉴
[打印本页]
作者:
王石
时间:
2014-7-20 23:51
标题:
斐波那契兔子问题分析给大家借鉴
代码编写完整流程(兔子问题案例)
/*************************************
****代码编写完整流程(兔子问题案例)****
*************************************/
/*************************************
*小兔子问题:
*有一对兔子，从出生后第3个月起每个月都生一对兔子，
*小兔子长到第三个月后每个月又生一对兔子，
*假如兔子都不死，问每个月的兔子对数为多少?
**************************************
* 写在前面
*
*在使用程序解决实际问题的过程中，至少包含两步：1、将实际问题转变为可用代码解决的问题 2、使用代码解决
* 将实际问题转变为可用代码解决的问题的过程实质上是分析问题的过程，这个过程的结果是-->得出解决实际问题的思想
* 使用代码解决的过程实质上是用编程语言说出解决实际问题思路的过程，这个过程的结果是-->将问题解决
*
* 其实，在思想清晰的情况下，使用代码解决问题这个过程极其简单（即使与分析得出思想的过程相比也是如此），
* 它几乎等同于“一个人想吃东西，他会说：‘有吃的吗？’ 但是现在他身边只有外国人，所以他说：‘Would you has some food？’” 这样的过程。
* 所表达的都是询问对方有没有吃的，要做的只不过是使用一种可以解决问题的语言把这个意思表达出来
* 与之相对应的，是思路模糊的情况，此时如果想直接用代码解决实际问题
* 这就相当于自己都不知道自己要说什么，但是却硬要说，这样的后果是：依旧使用刚刚举得例子，不对老外表达出“我想吃屎”的意思就不错了
*
* 之所以说“分析问题”比“表达思想”复杂是因为：这个世界上有很多中渠道去教我们使用英文，但是没有任何一种直接的渠道告诉我们“我们想说什么”
************
*使用程序解决实际问题，粗略且不负责任的总结一下：一共有两种风格
*1.泛泛的分析-->明确问题是什么-->编写代码用计算机去完整的模拟问题中的每一步（实际上分析时，我们只分析出了这个问题包含哪些步）
* 这种风格分析简单、代码表达复杂。比如1到100的求和，我们分析的过程十分少，用代码控制程序(1+2+3+4...100)就可以了。
* 当语言粗通后，多采用这种分析风格，但如果想在技术上有建树的话，个人无责任猜想:早晚要转型至另一种风格
*2.深入的分析-->得到一个更优良的思想-->用相对简单的代码实现
* 这种风格分析复杂、代码表达简单。依旧用上面的例子，用代码控制程序return 100*(1+100)/2;搞定
*打一个比方：风格1所说出来的是“TMD饿死老子了，老子要吃饭” 风格2所说出了的是“朕饥，膳”
**************************************
*
*首先，我们尝试用第一种风格去分析兔子问题
* 为了分析方便我们就把一对兔子称为一只了啊（其实是我后面都敲错了）
*
* 对于每一只兔子而言其数量变化都符合{1 1 2 3 4 5 6 7 8 9...}这一数列。
* 则设兔子出生了mon个月，兔子的数量为vol。它们满足关系mon==1时vol==1;mon==n(n!=1)时vol==(n-1);
* 分析完毕（泛泛的分析嘛），我们可以尝试用代码实现了。
* 需要注意的是，我们仅仅对于每一只兔子进行了分析，那我们的代码应该反映每一只兔子的状态，于是我们应该对于每一只兔子都建立一个实例
* 每一只兔子都是同时存活的，所以应该把每一只兔子都建立一个线程（至少要把同时出生的一窝兔子放入一个线程）
* 为了防止出现“有的兔子成长了两个月而有的兔子仅成长了一个月”的情况，
* 所有线程都应该同步且建立线程间通信保证每只兔子都在一个月中得到一个月的成长后再进行下一个月
* 然后套用我们刚刚得出的关系，然后我们只有统计有多深兔子实例就可以了
*
* 好了，我们可以编代码了，额…………
* 现在，我们遇到了“不会说外语”的情况，我们表达不出我们的思想
*
*风格1不适合我们，我们只能尝试深入分析问题然后简单表达的风格了
* 下面我们对每个月的兔子的数量展开分析
* （注意，刚刚我们只是简单的分析了每一只兔子有什么特性，题目描述的其实就是每一只兔子的特性；
* 现在我们是分析所有兔子的数量，这个题目中没说过，两种分析区别很明显）
* 我们用字母'f'表示兔子的数量(别问我为毛不用r)
* 用上标的形式表示这个月的兔子数量f(^0),上个月的兔子数量f(^-1),和上上个月的兔子数量f(^-2)
* 兔子有三种分别是刚出生（出生一个月的兔子）的兔子，出生两个月的兔子，出生三个月及三个月以上的兔子
* 这里我们用前缀的方法表示为1_f,2_f,3_f
*
* 于是有
* 总兔子数 出生一月 出生二月 三月及以上
* 当前月 f(^0) 1_f(^0) 2_f(^0) 3_f(^0)
* 上个月 f(^-1) 1_f(^-1) 2_f(^-1) 3_f(^-1)
* 上上月 f(^-2) 1_f(^-2) 2_f(^-2) 3_f(^-2)
*
* 分析开始：
* 当前月兔子数为（当前月出生一月的兔子数量）+（当前月出生二月的兔子数量）+（当前月出生三月及以上的兔子数量）
* 即 f(^0) = 1_f(^0) + 2_f(^0) + 3_f(^0)
* 同理f(^-1) = 1_f(^-1) + 2_f(^-1) + 3_f(^-1)
* f(^-2) = 1_f(^-2) + 2_f(^-2) + 3_f(^-2)
*
* 当前月一月兔子是由上个月的三月及以上兔子生出来的，另外上个月的二月兔子到这个月会变为三月兔子并生下小兔子
* 也就是说当前月一月兔子数=上月三月兔子数+上月二月兔子数
* 即1_f(^0) = 2_f(^-1) + 3_f(^-1)
* 当前月的二月兔子都是由上个月的一月兔子存活而来
* 即2_f(^0) = 1_f(^-1)
* 当前月的三月兔子是由上个月的二月兔子生长和上个月的三月兔子存活而来
* 即3_f(^0) = 2_f(^-1) + 3_f(^-1)
* 此时不难发现
* f(^0) = 1_f(^0) + 2_f(^0) + 3_f(^0) = 2_f(^-1) + 3_f(^-1) + 1_f(^-1) + 2_f(^-1) + 3_f(^-1)
*
* 因为f(^-1) = 1_f(^-1) + 2_f(^-1) + 3_f(^-1)
* 所以f(^0) = 2_f(^-1) + 3_f(^-1) + 1_f(^-1) + 2_f(^-1) + 3_f(^-1) = f(^-1) + 2_f(^-1) + 3_f(^-1)
*
* 用同样的方法分析2_f(^-1) 3_f(^-1)
* 有上个月的二月兔子为上上月一月兔子数 2_f(^-1) = 1_f(^-2)
* 上个月三月为上上月二月兔子数+上上月三月兔子数 3_f(^-1) = 2_f(^-2) + 3_f(^-2)
* 又因为f(^-2) = 1_f(^-2) + 2_f(^-2) + 3_f(^-2)
* 于是：f(^0) = f(^-1) + 2_f(^-1) + 3_f(^-1) = f(^-1) + 1_f(^-2) + 2_f(^-2) + 3_f(^-2)
* = f(^-1) + f(^-2)
*
*现在我们得到了兔子总数和月份的关系：当前月兔子总数=上两月兔子总素的和
*我们需要三个变量分别保存当前月、上个月、上上月兔子数量：r,ri,r2
*我们需要一个变量记录月份：m
*
*后续间程序注释
*************************************/
import java.util.Scanner;
class Rabbit
{
public static void main(String[] args)
{
int m=1;//从第一个月开始嘛
int max;//声明一个变量来存储显示几个月的兔子数量
System.out.println("您希望显示几个月的兔子数量？请输入： ");
max = new Scanner(System.in).nextInt();
int r=1;//第一个月只有一只兔子嘛
int r1=0,r2=0;//第一个月时哪里有上上个月嘛
/*
每个月我们都打印一下月份和兔子数
因为我们每个月都打印数量，且兔子数量是有规律的所以我们需要一个循环
如果是第一个月 数量就是1，因为第一个月没有上个月
第二个月数量还是1，因为没有上上个月
没个月打印完后（进入下一轮循环之前）这个月的兔子变成上个月的，上个月的变成上上月的
于是r2=r1;r1=r;
等到了下个月时，（下个月变成了当前月）兔子等于上个月的兔子+上上月的
r=r1+r2;
差不多了，代码开敲
*/
for(;m<=max;m++){//从一月开始到最大月份结束
if (m==1||m==2)
r = 1;//一月二月就一只
else
r=r1+r2;//三月之后为上两月的和
System.out.println("第"+m+"个月，兔子的数量为"+r+"只");//显示一下
r2=r1;
r1=r;//上个月变上上月，当前月变上个月
}
}
}
作者:
八零、玖羚
时间:
2014-7-20 23:58
貌似这个算法用到了递归思想
作者:
七弟
时间:
2014-7-20 23:58
学习一下
作者:
马超（Andy)
时间:
2014-7-21 07:29
学习了:)
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2