今天又做了个斐波那契数列相关的题目：上台阶，每次可走一台阶和两台阶，问上10个台阶有多少种走法。 （出处：阅微堂. EMC笔试 ， 89种) 。 上次的农夫养牛问题也是个斐波那契问题。
对于斐波那契这一类问题，因为特征过于鲜明，可以一看题目就套上，用的联想的思维方式就解决了。不过如果是在不熟悉此类问题时，首先是根据题目估计可用演绎推理来解决，然后尝试 f(1), f(2), f(3) = f(2)+f(1) 之类的推理。 演绎/推理确实是一项十分重要的解题方法，尤其是在对问题领域不熟悉的时候。
延伸阅读：
- 刘未鹏：知其所以然地学习（以算法为例）
有关25马问题，目前有很多讨论，但是还没有看到真正解决问题的讨论。
TopLanguage 上我的发言：我的发言是8次，应该是正确的，但是还没有找出数学上的理由。
TopLanguage上一个较早的讨论：这个讨论是相对比较意义的，有人说：
其实这个就是kth smallest element的算法，MIT 的 Introduction to Algorithms 里有详细的分析。
参见：http://videolectures.net/mit6046jf05_demaine_lec06/
还有人说：
这个问题应该是磁盘排序的问题的变种吧 在不能计时的情况下 我觉得n * n 匹马 m 条跑道起码需要
两个Blog文章：http://fayaa.com/tiku/view/91/ （有篇评论值得研究，说到是8场）
http://blog.solrex.cn/articles/25-horses-problem.html#comment-1738 （我对他的做法做了评论）
题： 有无序的实数列V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间
题目来自CSDN论坛里的讨论，很多网友给出了他们的意见。
其实这个问题要求线性时间条件下，通常会让我们想到桶排序；接着关键是考虑怎么减少桶排序中对桶中各数的排序即可想到解决方法。我的算法如下：
- 主要是先找出最大的数与最小的数，然后构造一个n个桶，桶的下标与数的关系为： index = (v[i]-min)/(max-min/n).
- 遍历数列，将数值插入到对应的桶中。每个桶最多保留最小和最大的两个元素，不需要多余的数。
- 遍历所有的桶，记录每个桶之间有多少个空桶到数据flags中，并求出最大连续空桶数 maxGap。
- 最后遍历flags数组，对于空桶数 >= maxGap -1 的元素，计算从前面的最近的不为空的桶中的大元素与当前桶中的最小元素的差，最终找出最大差。
主算法：
max,min ← GetMaxAndMin (v)
bucks[n];
for i = 0 to n-1
buckNo ← get buck no: (v[i]-min) / (max-min/n) //计算桶下标（如果不为整数，取较小的数的绝对值）
if buck[ buckNo ] is empty: insert v[i]
if buck[buckNo].length == 1 : //insert v[i] 与原来的数构成正序关系
if buck[buckNo].length == 2 : //与原来的2元素按正序关系排列，去掉中间的数，仍然是2个元素
// 标记每个不为空的桶元素之前有多少个空桶
flags[n]; //记录每个桶之前的空桶数目
maxgaps = 0;
tempgaps = 0;
for i ← FindFirstNotEmptyBuck (bucks) to n-1
if buck[i] is empty then
tempgaps ++
else
flags[i] ← tempgaps;
maxgaps ← GetMax (tempgaps, maxgaps)
tempgaps = 0;
// 计算最大的相邻的最大值
maxNeighbor == null;
for i ← 0 to n-1
if maxgaps - flag[i] < 2 then
maxNeighbor ← GetMax(COMPUTE_MAX(bucks,i,flag[i]), maxNeighbor)
return maxNeighborCOMPUTE_MAX(bucks,i,gap) :
//常数级别，取头或取尾
return GetMinEle(bucks, i) - getMaxEle(bucks, i - gap -1)
<pre lang="c">GetMaxAndMin (v):
max, min, i
n ← v.length
if n%2 == 0 then
if V[1] > V[0] then
max ← V[1]; min ← V[0];
else
max ← V[0]; min ← V[1];
i = 2;
else
max = min = V[0];
i = 1;
for i to n-2
if v[i+1] > v[i] then
min ←GetMin(min, v[i]);
max ← GetMax(max, v[i+1])
else
min ←GetMin(min, v[i+1]);
max ← GetMax(max, v[i])
i++; //每次取两个数
return (max,min)FindFirstNotEmptyBuck (bucks)
for i ← 0 to n-1
if tempgapstart == -1 then
if buck[i] is empty then
break
else
continue;
return i;
算法题来自 CSDN ：http://topic.csdn.net/u/20091001/15/40BF4993-8ED7-45CC-968F-97C524DAE3C4.html
问题： 一个农夫养了一头牛，三年后，这头牛每年会生出1头牛，生出来的牛三年后，又可以每年生出一头牛……问农夫10年后有多少头牛?n年呢？
这个问题的数学模型是类似于斐波那契（Fibonacci）数列，其计算式为：
F(n) = 1 , n<3
或
F(n) = F(n-3) + F(n-1) , n >=3
十年后是28头牛。实现算法时该贴提到了两种实现方式，一种是用过程的方法实现该数列，另一种是面向对象的方法实现。第二种方法确实更好一些，但是原帖实现似乎并不理想。
问题：
给你n个数a[1], a[2], …, a[n]，(0[1]。
这个题目看上去与动态规划很类似，在于其解的特点。设数列的前 n 个数的最大值为 F(n)，则：
证明从略。
代码如下：
package com.feihoo.test;
public class MaxSequenceValue {
static int[] nums = { 2, 4, -3, 9, 30, -30, 20, 0, 34, -2, -45, 12, -8, 11 };
public static void main(String[] args) {
int minLen = 2;
int maxLen = 4;
int[] m = new int[nums.length];
m[minLen - 1] = 0;
for (int i = minLen; i < nums.length; i++)
compute(i, m, minLen, maxLen);
int largest = m[minLen];
for (int i = minLen + 1; i < nums.length; i++)
if (largest < m[i])
largest = m[i];
System.out.println(largest);
}
private static void compute(int n, int[] m, int minLen, int maxLen) {
m[n] = m[n - 1];
for (int len = minLen; len < maxLen && n - len >= 0; len++) {
int re = nums[n];
for (int i = n - 1; i > n - len; i--)
re += nums[i];
if (m[n] < re)
m[n] = re;
}
}
}参考：
1. 来源： 动态规划习题
最近评论