一根高筋拉面，中间切一刀，可以得到2根面条。 如果先对折1次，中间切一刀，可以得到3根面条。 如果连续对折2次，中间切一刀，可以得到5根面条。 那么，连续对折10次，中间切一刀，会得到多少面条呢？切面条 思路：先不考虑面条的连结
对折次数 根数（不是最终结果，折叠一次变成2根，折叠两次变成4根）
0 1
1 1*2 2^1
2 1*2*2 2^2
3 1*2*2*2 2^3
4 1*2*2*2*2
5 1*2*2*2*2*2
······························
10 1*2*2*2*2*2*2*2*2*2*2 2^10
···································
n 2^n
但是面条只在最后一次切断，所以有很多是连结在一起的
最后一刀切下去后，有2^n*2，两根连在一起 2^n*2/2
只有一整根面条的两端是不连在一起的，所以 2^n*2/2+1
#include <iostream> #include <cmath> using namespace std; int main() { int sum;//面条根数 int n;//折叠的次数 cin>> n; sum=pow(2,n)*2/2+1; cout<<sum<<endl; return 0; }
思路： 由于对折次数仅为10，数据规模并不大，可以通过手算简单的完成。 对折0次，得到2根； 对折1次，得到2 * 2 - 1 = 3 对折2次，得到3 * 2 - 1 = 5 对折3次，得到5 * 2 - 1 = 9 对折4次，得到9 * 2 - 1 = 17 对折5次，得到17 * 2 - 1 = 33 对折6次，得到33 * 2 - 1 = 65 对折7次，得到65 * 2 - 1 = 129 对折8次，得到129 * 2 - 1 = 257 对折9次，得到257 * 2 - 1 = 513 对折10次，得到513 * 2 - 1 = 1025
其实，上面的思路就是一种递归，可以把这种思想通过代码实现。 递归有基本递归与尾递归两种形式，本文分别进行了代码实现。 尾递归在一定程度上可以提高程序效率，通常比基本递归多一个参数。 递归的本质就是栈，当然可以用栈实现，在数据规模特别大的时候要显式的使用栈，以防止栈溢出。
答案：1025
基本递归：
[cpp] view plain copy print ? #include <iostream> using namespace std; int f(int n) { //基本递归 if(n == 0) { return 2; } else { return 2 * f(n - 1) - 1; } } int main(void) { cout << f(10) << endl; return 0; } #include <iostream> using namespace std; int f(int n) { //基本递归 if(n == 0) { return 2; } else { return 2 * f(n - 1) - 1; } } int main(void) { cout << f(10) << endl; return 0; }
尾递归：
[cpp] view plain copy print ? #include <iostream> using namespace std; int f2(int n, int r) { //尾递归 if(n == 0) { return r; } else { return f2(n - 1, 2 * r - 1); } } int main(void) { cout << f2(10, 2) << endl; return 0; } #include <iostream> using namespace std; int f2(int n, int r) { //尾递归 if(n == 0) { return r; } else { return f2(n - 1, 2 * r - 1); } } int main(void) { cout << f2(10, 2) << endl; return 0; }
