医院如何做网站策划?,网站从哪些方面来做,宣传片拍摄方案模板,开户推广竞价开户1、递归函数
#xff08;1#xff09;直接或间接调用自身的函数称为递归函数。
#xff08;2#xff09;他通常把一个大型复杂的问题层层转化成一个与原问题相似的规模较小的问题来求解。
2、递归的基本思想 问题分解#xff1a;
#xff08;1#xff09;把一个不能…1、递归函数
1直接或间接调用自身的函数称为递归函数。
2他通常把一个大型复杂的问题层层转化成一个与原问题相似的规模较小的问题来求解。
2、递归的基本思想 问题分解
1把一个不能或不好解决的大问题转化为一个或几个小问题再把这些小问题进一步分解成更小的小问题
最小问题可以直接解决。 2递归的关键在于找出递归定义和递归终止条件。
递归定义使问题向边界条件转化的规则。递归定义必须能使问题越来越简单。
递归终止条件也就是所描述问题的最简单情况它本身不再使用递归的定义。
3、递归算法解题通常有三个步骤 1分析问题、寻找递归找出大规模问题与小规模问题的关系这样通过递归使问题的规模逐渐变小。 2设置边界、控制递归找出停止条件即算法可解的最小规模问题。 3设计函数、确定参数设计函数体中的操作及相关参数。
4、递归算法的优点代码简洁。
5、欧几里得算法递归终止条件为m%n0,此时n为最大公因数。
6、欧几里得算法递归代码
gcd(m,n)gcd(n,m%n); GCD(m,n) // 约定mn // { if (n0) return(m); else return (GCD(n,m%n)); }
7、递归算法分析
求N
fact(int n)
{if(n0||n1)
return 1;
else return n*fact(n-1);
} 以n3为例调用过程如下 fact(3)-fact(2)-fact(1)-fact(2)-fact(3)
______________________ ______________________ 递 归 回 溯
8、计算半数集问题的递归算法一
int comp(int n) { int ans1; if (n1) for(int i1;in/2;i) anscomp(i); return ans;
}
计算半数集问题的递归算法—记忆式搜索二
int a[1001]; int comp(int n) { int ans1; if(a[n]0)return a[n]; //已经计算 for(int i1;in/2;i) anscomp(i); a[n]ans; //保存结果 return ans; }
9、整数因子分解的算法
int total;//全局变量
void solve(int n)
{if(n1)total;//获得一个分解
else for(int i2;in;i)
if(n%i0)solve(n/i);
}
//主函数main()中数据的读取与调用 int n; while( cinn) { total 0; solve(n); couttotalendl;
}
10、枚举型递归函数如全排列问题等恢复现场很重要。
11、递归函数中需要写终止条件出口。
12、回溯返回到调用的最近的位置调用之后逐级返回。
13、解题步骤
1先找到大规模问题和小规模问题之间的关系
2再找出最小规模问题及其答案
14、递归
1公式递归
2枚举递归把问题转化成若干小问题、若干情况
15、通常n的第一个因子在1-sqrt(n)之间若要求出所有的因子需要取1-n。
16、经典题解析算24
#include bits/stdc.h using namespace std; double a[5]; #define EPS 1e-6 bool isZero(double x) { return fabs(x)EPS; } bool count24(double a[],int n) { if(n1) { if(isZero(a[0]-24)) return true; else return false; } double b[5]; for(int i0; in-1; i) for(int ji1; jn; j) //枚举两个数的组合 { int m0; for(int k0; kn; k) //将除选中的2个数(即i,j)以外的数存到数组b[]中 { if(k!ik!j) b[m]a[k]; } b[m]a[i]a[j]; if(count24(b,m1)) return true; b[m]a[i]-a[j]; if(count24(b,m1)) return true; b[m]a[j]-a[i]; if(count24(b,m1)) return true; b[m]a[i]*a[j]; if(count24(b,m1)) return true; if(!isZero(a[i])) { b[m]a[j]/a[i]; if(count24(b,m1)) return true; } if(!isZero(a[j])) { b[m]a[i]/a[j]; if(count24(b,m1)) return true; } } return false; } int main() { while(true) { for(int i0; i4; i) cina[i]; if(isZero(a[0])isZero(a[1])isZero(a[2])isZero(a[3])) break; cout(count24(a,4) ? YES:NO)endl; } return 0; } 解析 可以从4个数中先选出2个数进行运算将得到的结果和剩下的2个数找它们的运算结果可否为24这时为3个数查找找运算结果可否为24继续从中选取2个数进行运算再将结果与剩下的一个数 进行运算这时为2个数找运算结果为24最后就变成了1个看是否为24。 一、递归的结束条件即为只剩1个数时 若为24输出YES否则输出NO 二、注意浮点数判断是否相等不能用 而要看两个数只差是否足够小比如小于1e-6. 三、枚举数组中的每一对组合可以用2个for循环
四、三目运算符为a?b:c即有三个参与运算的量。由条件运算符组成条件表达式的一般形式为
表达式1? 表达式2 表达式3 其求值规则为如果表达式1的值为真则以表达式2 的值作为条件表达式的值否则以表达式2的值作为整个条件表达式的值。 条件表达式通常用于赋值语句之中。 例如条件语句 if(ab) maxa; else maxb; 可用条件表达式写为 max(ab)?a:b; 执行该语句的语义是如ab为真则把a赋予max否则把b 赋予max。 使用条件表达式时还应注意以下几点 1条件运算符的运算优先级低于关系运算符和算术运算符但高于赋值符。因此 max(ab)?a:b可以去掉括号而写为 maxab?a:b 2 条件运算符?和是一对运算符不能分开单独使用。 3 条件运算符的结合方向是自右至左。 例如 ab?a:cd?c:d应理解为 ab?a:(cd?c:d) 这也就是条件表达式嵌套的情形即其中的表达式3又是一个条 件表达式。
