问题虽然很朴素，但是却能够起到活跃脑筋的作用，有些问题的分析还能够有有利于我们对数学知识（例如概率）的运用，所以把这些益智题都列出来如下。
1. 有一家人父亲、母亲和儿子、女儿，当父亲和女儿独处或者母亲和儿子独处时，父亲（母亲）就会骂女儿（儿子）。现在他们要过一条河，河上有一条船，船一次只能容纳两人,并只能由大人驾船。问他们应该怎么过河才能保证女儿和儿子都不会被骂。
完全是推理分析能力，采用试错法。答案有两种，其中一种是母亲先送女儿过河，然后目前回来接父亲过河，然后父亲回去接儿子过河。
2. 我三个筐子，一个装苹果，一个装橙子，一个装苹果和橙子。你看不到筐子里的东东，而标签都贴错了，你只能任选一个筐子，拿一个水果出来，然后把标签都改正过来，怎么拿?
根据条件要一次确定最多的结果，肯定应该去挑选标签为苹果和橙子的框，选出的水果就决定了这个框的真实标签，然后决定了另外一个标签称是该水果的框里的是混合物，剩余一个自然清楚了。
3. 屋子里有三盏灯，屋外有三个开关，屋外看不到屋里。你在屋外可以任意设置三个开关，然后进屋一次，就要说出哪个开关控制哪盏灯。
? 题目似乎不太清楚。
4. 12个小球，其中有一个是坏球。有一架天平。需要你用最少的称次数来确定哪个小球是坏的并且它到底是轻还是重。
答案是3次。这是一个涉及到概率的问题，需要用概率的方法来选择。详细请参考 刘未鹏的博客 。
对于类似于此种问题， 有其特殊的规律。
- 第一，是天平有三种输出的可能，所以应该让最终的结果均分称三等分。分得越严格，最有利于最终结果。
- 第二，分组时，还应该要保证天平输出三种结果的几率是均等的。
这种方式通过构造最佳决策树来解决问题。在刘未鹏的文章中，还提到有人用信息论的方式来讨论此问题。
今天又做了个斐波那契数列相关的题目：上台阶，每次可走一台阶和两台阶，问上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. 来源： 动态规划习题
最近评论