黑马程序员技术交流社区

标题: 一道编程题引起的思考 [打印本页]

作者: 黄丽慧 时间: 2012-7-2 08:44
标题: 一道编程题引起的思考
在网上看到这样一个编程题目
古典问题：有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
//这是一个菲波拉契数列问题
刚看到题目的时候觉得这么短的题目应该是非常简单，但是当我分析完题目时，脑袋里面成了一团浆糊，所以就只好看看别人写的代码——真的是非常简单：

public class lianxi01 {
public static void main(String[] args) {
System.out.println("第1个月的兔子对数: 1");
System.out.println("第2个月的兔子对数: 1");
int f1 = 1, f2 = 1, f, M=24;
   for(int i=3; i<=M; i++) {
   f = f2;
   f2 = f1 + f2;
   f1 = f;
   System.out.println("第" + i +"个月的兔子对数: "+f2);
      }
}
}

问题：该编程题是怎么分析的，如何创建变量及实现需求的，另外以后碰到这样的编程题要怎么进行分析思考？

作者: 赵志勇 时间: 2012-7-2 09:05
首先审清题意，理解题目中的关系：开始有兔子的对数是1，第10个月以后可以生10-3+1=8对；
3个月以后新生的小兔子可以生10-6+1=5对兔子；
4个月以后新生的小兔子可以生10-7+1=4对兔子；
5个月以后新生的小兔子可以生10-8+1=3对兔子；
6个月以后新生的小兔子可以生（10-9+1）×2=4对兔子；
7个月以后新生的小兔子可以生（10-10+1）×3=3对兔子．再把它们相加即可．

作者: 杨_扬 时间: 2012-7-2 09:49
//这是一个菲波拉契数列问题
这个注解是原题目给出的吗？如果是，这道题就没什么了
问题的解答就是简单的在推演Fibonacci Sequence，只要你知道这个数列是怎么来的，就很容易
Fibonacci数列的实现是在《算法导论》中讲解递归的算例
数列的基本规则是
F0=1
F1=1
F2=2
F3=3
F4=5
.
.
.
F(N)=F(N-1)+F(N-2)
当N趋向于无穷大时，Fibonacci数列后项与前向的比趋向于黄金分割
既然说到递归，就再深谈一步
递归这种编程方法在很多的公司中是明令禁止的，因为不利于调试，而且往往会引发一些无法控制的结果
另外，任何递归结构都可以改写为非递归结构

作者: 黄丽慧 时间: 2012-7-2 10:06

杨_扬发表于 2012-7-2 09:49
//这是一个菲波拉契数列问题
这个注解是原题目给出的吗？如果是，这道题就没什么了
问题的解答就是简单的在 ...

嗯，我要问的就是如何推演Fibonacci Sequence，这下子明白了，在看题目的时候觉得应该是递归，可能是对递归不是很了解，所以解题思绪比较乱。

作者: 杨_扬 时间: 2012-7-2 10:14

黄丽慧发表于 2012-7-2 10:06
嗯，我要问的就是如何推演Fibonacci Sequence，这下子明白了，在看题目的时候觉得应该是递归，可能是对递 ...

递归不了解没关系的，很多大公司的编程守则上规定禁止使用递归，比如华为，呵呵

作者: 艾衍年 时间: 2012-7-2 10:43
个人觉得遇到这类问题可以抽象的思考根据题的数量关系抽象出题目满足哪种数学关系这一题是菲波拉契数列问题就可以根据菲波拉契数列的原理考虑问题的实现和变量的创建
再比如求1+2+3+……+N的和大家都会习惯用循环解决其实分析一下这不就是数学中的数列前N项和的问题吗 1+2+3+……+N = (（1+n)*n)/2 那么可以这样用
public class Sum
{
public int getSum(int i)
{
return ((i+1)*i)/2;
}
public static void main(String[] args)
{
Sum s = new Sum();
int n = 0;
n = s.getSum(100);
System.out.println("1+2+3+……+100的和是"+n);

}
}

这样算的效率要比循环高上一些

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2