https://www.luogu.com.cn/problem/P1335C++代码
时间: 2023-06-22 11:27:59 浏览: 51
以下是一份参考代码,可以用于计算 $f(n)$ 的值:
```c++
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int f1 = 1, f2 = 2, f3;
if (n == 1) {
cout << f1 << endl;
} else if (n == 2) {
cout << f2 << endl;
} else {
for (int i = 3; i <= n; i++) {
f3 = 2 * f2 - f1 + 2;
f1 = f2;
f2 = f3;
}
cout << f3 << endl;
}
return 0;
}
```
代码中使用了三个变量 $f1,f2,f3$ 分别表示 $f(n-2),f(n-1),f(n)$ 的值,通过递推计算得出 $f(n)$ 的值。
需要注意的是,当 $n=1$ 或 $n=2$ 时,需要特判处理。
相关问题
做一下https://www.luogu.com.cn/problem/P1001
题目链接:[https://www.luogu.com.cn/problem/P100](https://www.luogu.com.cn/problem/P1001)
题目描述:
给定两个整数A和B,计算A+B的结果。
输入:
输入包含两个整数A和B,每个整数占一行。(-10^9 <= A, B <= 10^9)
输出:
输出A+B的结果。
示例输入:
```
1
2
```
示例输出:
```
3
```
解题思路:
这道题非常简单,只需要读取输入的两个整数,然后将它们相加并输出结果即可。
算法步骤:
1. 读取输入的整数A和B。
2. 计算A+B的结果。
3. 输出结果。
下面是使用C++语言实现的代码:
```cpp
#include <iostream>
using namespace std;
int main() {
int A, B;
cin >> A >> B;
cout << A + B << endl;
return 0;
}
```
这段代码会首先读取输入的两个整数A和B,然后计算它们的和,并将结果输出到标准输出流中。最后返回0表示程序正常结束。
https://www.luogu.com.cn/problem/P1933
这是一道经典的组合数学题目,需要用到组合数的性质。
我们可以先考虑 $n=5$ 的情况。这时,一共有 $2^n=32$ 种可能的抛硬币的结果,其中正面朝上的硬币数为 $0,1,2,3,4,5$ 的情况分别有 $1,5,10,10,5,1$ 种。
接下来,我们考虑 $n$ 的任意情况。可以证明,当 $n$ 为偶数时,正面朝上的硬币数的种数与 $n=5$ 时是相同的;当 $n$ 为奇数时,正面朝上的硬币数的种数比 $n=5$ 时多一种。这是因为当抛硬币的次数为偶数时,正反面的数量是相等的,因此正面朝上的硬币数的种数与 $n=5$ 时相同;当抛硬币的次数为奇数时,正反面的数量不相等,因此正面朝上的硬币数的种数比 $n=5$ 时多一种。
因此,需要分别处理 $n$ 为奇数和偶数的情况。当 $n$ 为偶数时,正面朝上的硬币数的种数与 $n=5$ 时相同,因此答案为:
$$ \sum_{i=0}^{n/2} \binom{n}{i} $$
当 $n$ 为奇数时,正面朝上的硬币数的种数比 $n=5$ 时多一种,因此答案为:
$$ \sum_{i=0}^{n/2} \binom{n}{i} + \sum_{i=0}^{n/2} \binom{n}{i+1} $$
需要注意的是,当 $n$ 为 $0$ 时,只有一种可能的结果,即所有硬币都是反面朝上,因此答案为 $1$。
以下是一份参考代码,可以用于计算答案:
```c++
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
if (n == 0) {
cout << "1" << endl;
} else {
int ans = pow(2, n);
if (n % 2 == 0) {
for (int i = 0; i <= n / 2; i++) {
ans -= 2 * pow(-1, i) * pow(2, n - i) * (1 << i) / (i + 1);
}
} else {
for (int i = 0; i <= n / 2; i++) {
ans -= 2 * pow(-1, i) * pow(2, n - i) * (1 << i) / (i + 1);
}
for (int i = 0; i <= n / 2; i++) {
ans -= 2 * pow(-1, i) * pow(2, n - i - 1) * (1 << i) / (i + 1);
}
}
cout << ans << endl;
}
return 0;
}
```
代码中使用了数学公式计算答案,其中 $\binom{n}{i}$ 使用了移项后再计算的方式,避免了复杂的组合数计算。