//搜狗:有N个正实数(注意是实数,大小升序排列) x1 , x2 ... xN,另有一个实数M。
//需要选出若干个x,使这几个x的和与 M 最接近。 请描述实现算法,并指出算法复杂度。
public void FindDouble(double[] A,bool[] Exsits, int N,double M,int i,double PreCurrSum,bool Exists)
{
double theCurrSum = PreCurrSum + (Exists ? A[i - 1] : 0);
Exsits[i - 1] = Exists;
double theNewDelta = Math.Abs(theCurrSum - M);
if (theNewDelta < MinDelta)
{
MinDelta = theNewDelta;
for (int j = i + 1; j <= N; j++)
{
Exsits[j - 1] = false;
}
CopyResult(Exsits, N);
}
if (i < N)
{
FindDouble(A, Exsits, N, M, i + 1, theCurrSum,false);
FindDouble(A, Exsits, N, M, i + 1, theCurrSum,true);
}
}
private void CopyResult(bool[] Exsits, int N)
{
for (int i = 0; i < N; i++)
{
Exist[i] = Exsits[i];
}
}
private void button3_Click(object sender, EventArgs e)
{
double[] A = new double[] {1.5,2.5,3.0,5.0,8.0,9.0};
bool[] E = new bool[] { false, false, false, false, false, false };
Exist = new bool[6];
MinDelta = double.MaxValue;
FindDouble(A, E, 6, 12, 1, 0.0, false);
FindDouble(A, E, 6, 12, 1,0.0, true);
}
PS:原来这种递归处理是典型的背包问题,长见识了。
分享到:
相关推荐
此代码实现从N个数字中取出M个数字的所有组合,有两种实现方法,递归方法和非递归方法。
05_JavaSE面试题:递归与迭代
实现从M个字符中选择N个字符的递归程序!
面试题:设计和实现一个LRU Cache缓存机制.mp4 55.理论讲解: LRU Cache.mp4 54.面试题:岛屿的个数&朋友圈(下).mp4 53.面试题:岛屿的个数&朋友圈(上).mp4 52.理论讲解:并查集.mp4 51.面试题:编辑距离.mp4 50...
从N选取M个数的所有组合数C++描述 思路: 第一位可以取N中的任何一个,第二位只能取第一位后面的数字任何一个, 即第M位只能取第M-1位后面的数字任何一个,每一位递归一次
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...
试编写一段递归子程序计算ackermann函数ACK(m,n)。对于m≥0和n≥0的ACK(m,n)函数定义如下: ACK(0,n)=n+1 ACK(m,0)=ACK(m-1,1) ACK(m,n)=ACK(m-1,ACK(m,n-1)) 程序要求: ⑴ m、n在主程序从键盘输入,输入错误显示...
面试题 5:用两个栈实现队列(考点: 栈和队列) 5 面试题 6:旋转数组的最小数字(考点:查找和排序) 6 面试题 7:斐波那契数列(考点: 递归和循环) 7 面试题 8:跳台阶(考点: 递归和循环) 7 面试题 9:变态跳台阶...
IT面试题-二叉树的三种遍历的递归与非递归实现,详细代码,包含了前先序遍历,中序遍历、后序遍历的递归实现和非递归实现,文档内有详细的实现代码。
用递归法计算从n个正整数中选择k个数的不同组合数
递归实现 二种非递归实现 二叉树中序遍历: 递归实现 非递归实现 二叉树后序遍历: 递归实现 非递归实现 二叉树层次遍历 二叉树层次创建,创建方法遵循卡特兰数 http://write.blog.csdn.net/postedit/17380455
【问题描述】编写函数f,功能是用递归的方法求斐波那契数列的第n项,函数原型为 int f(int n),在主函数中输入一个正整数n,调用函数f求出斐波那契数列的第n项,并在主函数中输出。 斐波那契数列:1,1,2,3,5,8,13,...
从这N个数中任取出若干个数(不能取相邻的数),要求得到一种取法,使得到的和为最大。例如:当N=5时,有5个数分别为:13,18,28,45,21 此时,有许多种取法,如: 13,28,21 和为62 13, 45 和为58 18,45 和为63...
在数学上它以递归的方式进行定义,指这样的一个数列:0、1、1、2、3、5、8、13、21、34、55、89、144……,即前两个数为分别为0和1,从第3项开始,每项的值都等于其前两项之和。斐波那契数列Fib(n)用公式表示为: ...
递归实现十进制数从高位到低位依次输出 主要是我对递归算法的初步理解后试手制作希望对你有用
主要介绍了MyBatis之自查询使用递归实现 N级联动效果,本文给大家分享两种实现方式,需要的的朋友参考下吧
n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---递归回溯法 n后问题---...
C语言程序设计-编写main程序调用函数fact求解从m个元素选n个元素的组合数的个数;计算公式是: 组合数=m!(n!.(m-n)!);要求m不能小于n,否则应有容错处理;说明:函数fact(x)的功能是求x!;
用回溯法递归实现的输出N的全排列 如 123 132 。。。。
C语言递归实现逆序程序 C语言初学者必会