个人简介
小公司研发总监，既当司令也当兵！
文章分类
相关博文
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
- ·
分类： linux
2016-07-14 09:21:30
经典c面试题-凯发app官方网站
此题目咋一看没有什么思路，根据以往经验可能是个递归、分治类似的问题，随着这个思路想：
（1）先不凑一元（100分），先凑1角（10分）怎么解？
（2）先凑5分怎么解？
（3）先凑一分：这个好办，只有一种解法，就是一个一分硬币。
（4）如果已经凑到99分时的方法为f(99)，那么在此基础上凑齐100分的方法只要一种，就是添加一个一分硬币；同理，如果先凑到98分时的方法种类为f(98)，那么在此基础上凑齐一百分的方法有两种，要么使用两个一分硬币，要么使用一个两分硬币。
分析至此，我就想到了之前做过的一个题目：
有一个台阶总共100阶，每次可以跨1阶或2阶，问从地面到台阶顶部总共有多少走法？
要想一步到达第100阶台阶上，只有两种走法，其一是从第99阶上夸一阶到第100；其二是从第98台阶上跨2阶到达100阶。所以有
f(100) = f(99) f(98)
更一般的：
f(k) = f(k-1) f(k-2), 其中k >= 2
有此通项公式，那么编码实现就很简单了，最简单实现的莫过于递归。但这类算法用递归实现效率非常差，因为有大量重复计算，建议采用累加计算的方式。本文就不贴代码了。
类比于上面的台阶跳，如果将本题看着是一个台阶问题，那么步长有1,2,5三种，则
f(100) = f(99) f(98) f(95)
更一般的：
f(k) = f(k-1) f(k-2) f(k-5)
咋一看，上述分析没有问题，按照此通项公式编码也非常容易。但仔细琢磨有感觉不对味（笔者开始也以为到此结束了），进一步分析：
假设f(97)表示已经凑到97分时的总方法数，那么基于此凑到一百分有多少种方法？
[f(97)] [1,1,1]
[f(97)] [1,2]
[f(97)] [2,1]
从这里我们看明白了，上面方法2和方法3在台阶跳中是不同走法，但在凑硬币的时候，是同一种方式。
即，台阶跳是属于排列，而凑硬币则属于组合！按照台阶跳的算法，会存在大量的重复...
重新考虑：假设已经凑足了100分硬币，其中1分硬币有x个，2分硬币有y个，5分硬币有z个，则
x 2*y 5*z = 100， 其中x,y,z ∈n
求上述表达是的非负整数解的组数。
int coindivide(int sum)
{
int cnt = 0;
int i,j;
for(i = 0; i <= sum; i )
{
for(j= 0; j <= (sum - i) / 2; j )
{
if ( (sum - i - 2 * j) % 5 == 0)
{
printf("%d -- %d -- %d\n", i, j, (sum -i - 2*j) / 5);
cnt ;
}
}
}
return cnt;
}
另外，上述实现的时候，采用了1分和2分硬币的个数做循环，外循环是101次，内循环是依次[50...0]（步长2）；但如果采用5分，2分做循环的话，外循环次数21次，内循环依次[50...0]（步长5）。可见要少许多次循环。
编码时如果能够注意这类细节，会增色不少。
（1）先不凑一元（100分），先凑1角（10分）怎么解？
（2）先凑5分怎么解？
（3）先凑一分：这个好办，只有一种解法，就是一个一分硬币。
（4）如果已经凑到99分时的方法为f(99)，那么在此基础上凑齐100分的方法只要一种，就是添加一个一分硬币；同理，如果先凑到98分时的方法种类为f(98)，那么在此基础上凑齐一百分的方法有两种，要么使用两个一分硬币，要么使用一个两分硬币。
分析至此，我就想到了之前做过的一个题目：
有一个台阶总共100阶，每次可以跨1阶或2阶，问从地面到台阶顶部总共有多少走法？
要想一步到达第100阶台阶上，只有两种走法，其一是从第99阶上夸一阶到第100；其二是从第98台阶上跨2阶到达100阶。所以有
f(100) = f(99) f(98)
更一般的：
f(k) = f(k-1) f(k-2), 其中k >= 2
有此通项公式，那么编码实现就很简单了，最简单实现的莫过于递归。但这类算法用递归实现效率非常差，因为有大量重复计算，建议采用累加计算的方式。本文就不贴代码了。
类比于上面的台阶跳，如果将本题看着是一个台阶问题，那么步长有1,2,5三种，则
f(100) = f(99) f(98) f(95)
更一般的：
f(k) = f(k-1) f(k-2) f(k-5)
咋一看，上述分析没有问题，按照此通项公式编码也非常容易。但仔细琢磨有感觉不对味（笔者开始也以为到此结束了），进一步分析：
假设f(97)表示已经凑到97分时的总方法数，那么基于此凑到一百分有多少种方法？
[f(97)] [1,1,1]
[f(97)] [1,2]
[f(97)] [2,1]
从这里我们看明白了，上面方法2和方法3在台阶跳中是不同走法，但在凑硬币的时候，是同一种方式。
即，台阶跳是属于排列，而凑硬币则属于组合！按照台阶跳的算法，会存在大量的重复...
重新考虑：假设已经凑足了100分硬币，其中1分硬币有x个，2分硬币有y个，5分硬币有z个，则
x 2*y 5*z = 100， 其中x,y,z ∈n
求上述表达是的非负整数解的组数。
int coindivide(int sum)
{
int cnt = 0;
int i,j;
for(i = 0; i <= sum; i )
{
for(j= 0; j <= (sum - i) / 2; j )
{
if ( (sum - i - 2 * j) % 5 == 0)
{
printf("%d -- %d -- %d\n", i, j, (sum -i - 2*j) / 5);
cnt ;
}
}
}
return cnt;
}
另外，上述实现的时候，采用了1分和2分硬币的个数做循环，外循环是101次，内循环是依次[50...0]（步长2）；但如果采用5分，2分做循环的话，外循环次数21次，内循环依次[50...0]（步长5）。可见要少许多次循环。
编码时如果能够注意这类细节，会增色不少。
给主人留下些什么吧！~~