| 按上述思想写成程序如下：
public static void comb(int n, int r)
{
int i=0, j=0;
for (j = 0; j < r; j++)
c[j] = j+1;
for (j = 0; j < r; j++)
{
Console.Write(c[j].ToString() + ' ');
}
Console.WriteLine(' ');
i = r - 1;
do
{
if (c[i]-i < n - r+1)
{
c[i]++;
for (j = i + 1; j < r; j++)
c[j] = c[j - 1] + 1;
for (j = 0; j < r; j++)
{
Console.Write(c[j] + ' ');
}
Console.WriteLine(' ');
i = r - 1;
}
else --i;
} while (i >= 0);
}
3、比较小结：
运行环境:本机Mcrosoft windwos XP版本2002 Service Pack 2 , CPU 2.13GHZ,760M RAM
用时秒
使用方法
在10个数中
取5个
在20个数中取5个
在30个数中取5个
在40个数中取5个
用递归算法
4.32
107.39
960.61
3529.49
用回溯算法
4.37
102.70
955.47
3094.56
用时秒
使用方法
在1000个数中取2个
在100个数中取2个
在20个数中取8个
在30个数中取25个
用递归算法
1270.47
190.73
1232.32
912.41
用回溯算法
1856.73
280.96
1157.57
898.77
从运行的情况来看,当选出数字个数较少时递归算法相对较快些,当选出数据量相对较大时用回溯法相对会快些。而使用递归法，代码更加简洁、明了。
递归方法中递归调用的空间复杂度是O（k – m） 的线性阶,因此其时间复杂度为O(log m),而回溯算法的空间复杂度为O( m2 )它的时间复杂度为O（m x k）．
递归方法适用于问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。递归法的关键是必须有一个递归终止条件，即要有递归出口。无条件的递归是毫无意义的。递归方法设计算法的策略不仅适用于计算数学问题，而且也适用于非数值运算领域。
递归法的优点是结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。其缺点是递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。而回溯法的优点适用于不可能使用实验研究法的许多情形；可获得关于某现象之性质的有关资料；由于近年的技术与统计方法以及部分控制设计的改进，便得很多研究结果，具有可防卫性等。其缺点是缺乏对自变项的控制；难确定有关的因素；事件的发生，原因可能不只一个；导致现象的原因是多元的；决定两个变项何者为因，何者为果是很困难的；两个以上有关的因素，未必具有因果关系；基于比较的目标，把受试者硬分为两组，常常导致发生问题；受试者不能随机分派到处理组等。
参考文献:
[1]朱战立.数据结构(C++语言描述) [M].北京:高等教育出版社,2004.
[2]谭浩强.C 程序设计(第2 版)[M].北京:清华大学出版社,2003.
[3] Anany Levitin. introduction to The Design and Analysis of Algorithms.USA [M] . 北京:清华大学出版社,2005
[4] 朱玉龙,任文岚. 递归程序设计的公式化方法[J ] .小型微型计算机系统,2001 ,22 (11) :1 389～1 390.
[5]M.H.Alsuwaiyel. Algorithms design Techniques and Analysis 沙特吴伟旭.方世昌等译 电子工业出版社,2004.
2/2 首页 上一页 1 2 |
