初版
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e6;
vector<int> mem[N];
struct node
{
int val;
node* left;
node* right;
};
//高精度
vector<int> operator+(vector<int> x, vector<int> y)
{
if (x.size() < y.size()) return y + x;
int t = 0;
vector<int> z;
for (int i = 0; i < x.size(); i++)
{
t += x[i];
if (i < y.size())
t += y[i];
z.push_back(t % 10);
t /= 10;
}
if (t)
z.push_back(t);
return z;
}
//小于30,记录路径,暴力输出
int f(int n, node* root)
{
node* left = new node;
node* right = new node;
left->left = nullptr;
left->right = nullptr;
right->left = nullptr;
right->right = nullptr;
root->left = left;
root->right = right;
if (n == 1)
{
root->left->val = 1;
root->right = nullptr;
return 1;
}
if (n == 2)
{
root->left->val = 1;
root->left->left = new node;
root->left->left->val = 1;
root->left->left->left = nullptr;
root->left->left->right = nullptr;
root->right->val = 2;
return 2;
}
root->left->val = 1;
root->right->val = 2;
return f(n - 1, root->left) + f(n - 2, root->right);
}
//大于30,记忆优化
vector<int> fplus(int n)
{
vector<int> ans;
if (!mem[n].empty())
return mem[n];
if (n == 1)
mem[1].push_back(1);
else if (n == 2)
mem[2].push_back(2);
else
mem[n] = fplus(n - 1) + fplus(n - 2);
return mem[n];
}
//树的遍历
void tree(node* root, vector<int> path)
{
if(root->val)
path.push_back(root->val);
if (!root->left && !root->right)
{
for (int i : path)
cout << i;
cout << endl;
}
if (root->left)
tree(root->left, path);
if (root->right)
tree(root->right, path);
}
int main()
{
int n;
node* root = new node;
root->val = 0;
cin >> n;
//小于三十的直接输出路径
//大于三十的我看就木有必要输出路径了吧,直接上高精度+记忆化
if (n <= 30)
{
cout << f(n, root) << endl;
vector<int> path;
tree(root, path);
}
else
{
vector<int> ans = fplus(n);
for (int i = ans.size() - 1; i >= 0; i--)
cout << ans[i];
}
}
删减版
#include <iostream>
#include <string>
using namespace std;
int f(int n, string path, string step)
{
path += step;
if (n == 1)
{
path += "1";
cout << path << endl;
return 1;
}
if (n == 2)
{
f(n - 1, path, "1");
path += "2";
cout << path << endl;
return 2;
}
return f(n - 1,path, "1") + f(n - 2, path, "2");
}
int main()
{
int n;
cin >> n;
string path;
cout << f(n, path, "") << endl;
}