来宾北京网站建设,wordpress模板如何安装教程视频教程,seo点击工具,鄞州网站制作实验1-1 斐波那契数
【问题描述】斐波那契数 #xff08;通常用 F(n) 表示#xff09;形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始#xff0c;后面的每一项数字都是前面两项数字的和。
定义#xff1a;F(0) 0, F(1) 1, F(n) F(n-1) F(n-2) 其中n1
要求计… 实验1-1 斐波那契数
【问题描述】斐波那契数 通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。
定义F(0) 0, F(1) 1, F(n) F(n-1) F(n-2) 其中n1
要求计算第n个斐波那契数。 【输入形式】输入1行包含1个整数n。 【输出形式】输出1行包含1个整数表示计算的F(n) 【样例输入1】
2 【样例输出1】
1 【样例说明1】
F(2) F(1) F(0) 1 0 1 【样例输入2】
3 【样例输出2】
2 【样例说明2】
F(3) F(2) F(1) 1 1 2 【说明】
0 n 30
递归
#includeiostream
using namespace std;int fib(int x)
{if(x 1 || x 0 ){return 1;}else{return fib(x-1) fib(x-2);}
}
int main()
{int x;cin x;cout fib(x) \n;
}
数组循环
#includeiostream
using namespace std;
const int N 1e5 10;
int f[N];int main()
{int x;cin x;f[0] 1,f[1] 1;for(int i 2 ; i x ; i ){f[i] f[i-1] f[i-2];}cout f[x] \n;
} 实验1-2 整数幂
【问题描述】实现pow(x,n)即计算实数x的非负整数n次幂。 【输入形式】输入1行包含2个实数第1个表示实数x第2个表示非负整数n。 【输出形式】输出1行一个数字表示计算结果结果保留4位小数。 【样例输入1】
2 10
【样例输出1】
1024.0000
【样例说明1】
2^10 1024 【样例输入2】
1.1 2
【样例输出2】
1.2100
【样例说明2】
1.1 ^ 2 1.21 【说明】
-100 x 100
0 n 100 【进阶】
思考如果n可以取负数 递归
#includeiostream
#includeiomanip
using namespace std;float pow(float x,int n)
{if( n 0){return 1;}else{return pow(x,n-1)*x;}
}
int main()
{float x;int n;cin x n;cout fixed setprecision(4) pow(x,n) \n;//推荐带精度的话写printf//printf(%.4f,pow(x,n) );
} 实验1-3 基数排序
【问题描述】给定一个长度为n的整数数组nums要求使用【基数排序】的方法将该数组升序排序。 【输入形式】输入的第1行中有1个数字n表示数组的长度第2行中有n个数字表示数组的元素 【输出形式】输出1行中有n个数字表示按照升序排序后的数组数字之间使用空格分割。 【样例输入】
5
35 28 9 87 56 【样例输出】
9 28 35 56 87
【说明】
1 n 10^4
0 nums[i] 10^5
#includeiostream
#includebits/stdc.h
using namespace std;
const int N 1010;
int a[N];void RadixSort(int n)
{int maxx 1;//最大值 int base 1;//基数 int tmp[N];while( maxx / base 0) //看最大值的位数 {int bucket[10] {0};for(int i 0 ; i n ; i ){bucket[ a[i] / base % 10 ] ;}for(int i 1; i 10 ; i ){bucket[i] bucket[i-1];}for(int i 0 ; i n ; i ){tmp[ bucket[a[i] / base % 10] - 1] a[i];bucket[a[i] / base % 10] -- ;}for(int i 0 ; i n ; i ){a[i] tmp[i];}base * 10;}
}
int main()
{int n;cin n;for(int i 0 ; i n ; i ){cin a[i];}RadixSort(n);for(int i 0 ; i n ; i ){cout a[i] ;}return 0;
} 实验1-4 生成排列
【问题描述】使用归纳法生成数组1,2...n的所有排列。 【输入形式】输入1行包含1个整数n。 【输出形式】输出包含若干行每行表示1个排列方式每行排列数字之间使用空格分割。可以按照任意顺序输出。 【样例输入】
3 【样例输出】
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 【样例说明】 数组1,2,3的排列共有3*2*16种可能。
【说明】
1n10
#includeiostream
#includebits/stdc.h
using namespace std;
const int N 1010;
int a[N];
bool vis[N];
void show(int n,int step)
{if(step n 1){for(int i 1 ; i n ; i ){cout a[i] ;}cout \n;}else{for(int i 1;i n ; i ){if(vis[i]false){vis[i] 1;a[step] i;show( n , step1 );vis[i] 0;}}}
}
int main()
{memset(vis,0,sizeof vis); int n;cin n;show(n,1);return 0;
} 实验1-5 寻找多数元素
【问题描述】给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。题目保证一定存在多数元素。
【输入形式】输入的第1行中有1个数字n表示数组的长度第2行中有n个数字表示数组的元素
【输出形式】输出1行一个数字表示该数组中的多数元素。 【样例输入】
3
1 2 1 【样例输出】
1
【说明】 1 n 10^5
-10^9 nums[i] 10^9
法一
upper_bound和lower_bound很好用
#includeiostream
#includebits/stdc.h
using namespace std;
const int N 1010;
int a[N];
int num;int main()
{int n;cin n;for(int i 0 ; i n ; i ){cin a[i];}sort(a,an);int mid1 a[n/2];int mid2 a[n/2 1];int num1 upper_bound(a,an,mid1) - lower_bound(a,an,mid1); //记录个数 //int num2 upper_bound(a,an,mid2) - lower_bound(a,an,mid2);if( num1 n/2)cout mid1;elsecout mid2;return 0;
} 法二
//5. 寻找多数元素
//小小暴力
#includebits/stdc.h
#includealgorithm
using namespace std;
const int N1e510;
int num[N];int main()
{int n,x;cin n;for(int i1;in;i){cinnum[i];}if(n1){coutnum[1];return 0;}sort(num1,numn1);for(int i2;in;i){if(num[i]num[i-1]){int cnt1;while(num[i]num[i-1]){cnt;i;}i-1;if(cntn/2){coutnum[i-1] ;}}}return 0;
}
