116 lines
3.1 KiB
C++
116 lines
3.1 KiB
C++
/*
|
||
* Code: 算法分析与程序设计 实验报告二
|
||
* Date: 2024-04-21
|
||
* Design by JRNitre
|
||
*
|
||
* Function:
|
||
* * 构造函数
|
||
* * 析构函数
|
||
* */
|
||
|
||
#include <iostream>
|
||
using namespace std;
|
||
|
||
/*
|
||
* [题干]
|
||
* 猴子第一天摘下若干个桃子，当即吃了2/3，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉2/3，又多吃了一个。以后每天早上都吃了前一天剩下的2/3再多吃一个。到第n天早上想再吃时，发现只剩下k个桃子了。求第一天共摘了多少桃子。用递推法、递归法两种方法实现。
|
||
* Input
|
||
* 首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组数据输入两个正整数n，k（1≤n，k≤15）。
|
||
* Output
|
||
* 对于每组测试数据，在一行上输出第一天共摘了多少个桃子。
|
||
*/
|
||
int function_01 (int t, int n, int k){
|
||
int i,j;
|
||
for (i = 0; i < t; i++){
|
||
int peaches[n+1];
|
||
peaches[n] = k;
|
||
for (j = n; j > 1; j--){
|
||
peaches[j-1] = (peaches[j] + 1) * 3 / 2;
|
||
}
|
||
return peaches[1];
|
||
}
|
||
}
|
||
|
||
// 分别从键盘输入数据x和y，计算x的y次幂并输出。
|
||
int function_02 (int x, int y){
|
||
if (y == 1){
|
||
return x;
|
||
}
|
||
if (y >= 2){
|
||
int result = 1;
|
||
for (int i = 0; i < y; i++){
|
||
result *= x;
|
||
}
|
||
return result;
|
||
}
|
||
}
|
||
|
||
/*
|
||
* [题干]
|
||
* 若一头小母牛从第4个年头开始每年生育一头母牛，按照此规律，第n年时有多少头母牛？要求编写两个函数，分别以递推、递归的方法进行求解。
|
||
* Input
|
||
* 测试数据有多组，处理到文件尾。每组测试输入一个正整数n（1≤n≤40）。
|
||
* Output
|
||
* 对于每组测试，输出第n年时的母牛总数。
|
||
* Sample Input
|
||
* 15
|
||
* Sample Output
|
||
* 129
|
||
*/
|
||
int function_03_recursion(int n) {
|
||
int dp[n+1];
|
||
dp[1] = 1;
|
||
dp[2] = 2;
|
||
dp[3] = 3;
|
||
for (int i = 4; i <= n; i++) {
|
||
dp[i] = dp[i-1] + dp[i-3];
|
||
}
|
||
return dp[n] / 2;
|
||
}
|
||
|
||
int function_03_recursion2(int n){
|
||
if (n == 1 || n == 2 || n == 3) {
|
||
return n;
|
||
}
|
||
return function_03_recursion2(n-1) + function_03_recursion2(n-3);
|
||
}
|
||
|
||
/*
|
||
* [题干]
|
||
* 欧洲数学家伯努利收到一位朋友的来信，打开一看信不是写给他的，但是信封上的地址、姓名都没有问题。
|
||
* 五封信装入写有不同地址和姓名的五个信封，全部装错的可能性有多少种?
|
||
* 请根据递推关系式，用递归法求解。
|
||
*/
|
||
int function_04(int n) {
|
||
if (n == 1) {
|
||
return 0;
|
||
} else if (n == 2) {
|
||
return 1;
|
||
} else {
|
||
return (n - 1) * (function_04(n - 1) + function_04(n - 2));
|
||
}
|
||
}
|
||
|
||
/*
|
||
* [题干]
|
||
* 万花筒的初始形状如下图所示，其中的圆圈代表万花筒的闪烁点。
|
||
* 每旋转一次万花筒形状就演变一次，演变的规则是在末端再生出同样的形状。
|
||
* 求第 n 次旋转后有多少个闪烁点？
|
||
* */
|
||
int function_05 (int n){
|
||
if (n == 1){
|
||
return 0;
|
||
}
|
||
if (n == 2){
|
||
return 1;
|
||
}
|
||
if (n > 2){
|
||
return (n - 1) * (function_05(n - 1) + function_05(n - 2));
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
|
||
return 0;
|
||
}
|