基金网站建设网站,郑州设计师网站大全,全国工商信息企业查询官网,常州网递归#xff1a;O(2^n) 调用自己 例题及代码模板#xff1a; 斐波那契数列 输入一个整数 n #xff0c;求斐波那契数列的第 n 项。 假定从 0 开始#xff0c;第 0 项为 0。 数据范围 0≤n≤39 样例
输入整数 n5 返回 5
#include iostream
#include cstringO(2^n) 调用自己 例题及代码模板 斐波那契数列 输入一个整数 n 求斐波那契数列的第 n 项。 假定从 0 开始第 0 项为 0。 数据范围 0≤n≤39 样例
输入整数 n5 返回 5
#include iostream
#include cstring
#include cstdio
using namespace std;int Fibonacci(int n){if(n0) return 0;if(n1) return 1;if(n2) return 1;return Fibonacci(n-1)Fibonacci(n-2);
}
int main(){int n;cinn;coutFibonacci(n)endl;return 0;
}
O(n*2^n) 递归实现指数型枚举 从 1∼n 这 n 个整数中随机选取任意多个输出所有可能的选择方案。 输入格式 输入一个整数 n。 输出格式 每行输出一种方案。 同一行内的数必须升序排列相邻两个数用恰好 1 个空格隔开。 对于没有选任何数的方案输出空行。 本题有自定义校验器SPJ各行不同方案之间的顺序任意。 数据范围 1≤n≤15 输入样例
3输出样例 3
2
2 3
1
1 3
1 2
1 2 3 #includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
const int N15;
int n;
int st[N];
void dfs(int u){if(un){for(int i0;in;i){if(st[i]1)couti1 ;}coutendl;return ;}st[u]2;dfs(u1);st[u]0;st[u]1;dfs(u1);st[u]0;
}int main(){cinn;dfs(0); return 0;
} 递归实现排列型枚举 把 1∼n这 n个整数排成一行后随机打乱顺序输出所有可能的次序。 输入格式 一个整数 n。 输出格式 按照从小到大的顺序输出所有方案每行 1 个。 首先同一行相邻两个数用一个空格隔开。 其次对于两个不同的行对应下标的数一一比较字典序较小的排在前面。 数据范围 1≤n≤9 输入样例
3输出样例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 时间复杂度 一共递归n层: 第一层是O(n) 第二层有n个分支每个分支有一个for循环即O(n*n) 第三层有n*(n-1)个分支每个分支有一个for循环即O(n*(n-1)*n) …… 第n层叶节点有n个分支每个分支有一个for循环即O(n!*n) 所以总的时间复杂度为n(1nn(n-1)……n!) (1nn(n-1)……n!)等价于n!n!/1n!/(1*2)n!/(1*2*3)……n!/(n-1)!n!/n!首先这个等式一定大于n!且小于n!n!/1n!/2n!/4……n!/2^(n-1)n!/2^n即3n! 所以这道题的时间复杂度为O3n*n!,即O(n*n!)
#includecstring
#includecstdio
#includeiostream
#includealgorithm
using namespace std;
const int N10;
int n,state[N];
bool used[N];
void dfs(int u) {if(un) {for(int i1; in; i)coutstate[i] ;coutendl;return ;}for(int i1; in; i) {if(!used[i]) {state[u]i;used[i]true;dfs(u1);state[u]0;used[i]false;}}
}
int main() {cinn;dfs(1);return 0;
}
递归实现组合型枚举
带分数
