【算法实验】实验1

实验1-1 斐波那契数

【问题描述】斐波那契数?（通常用?F(n)?表示）形成的序列称为?斐波那契数列?。该数列由?0?和?1?开始，后面的每一项数字都是前面两项数字的和。

定义：F(0) = 0, F(1)= 1, F(n) = F(n-1) + F(n-2) 其中n>1

要求计算第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

递归

#include<iostream>
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";
}

数组循环

#include<iostream>
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可以取负数

递归

#include<iostream>
#include<iomanip>
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

#include<iostream>
#include<bits/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*1=6种可能。

【说明】

1<=n<=10

#include<iostream>
#include<bits/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 , step+1 );
				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

#include<iostream>
#include<bits/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,a+n);
	int mid1 = a[n/2];
	int mid2 = a[n/2 + 1];
	int num1 = upper_bound(a,a+n,mid1) - lower_bound(a,a+n,mid1); //记录个数 
	//int num2 = upper_bound(a,a+n,mid2) - lower_bound(a,a+n,mid2);
	if( num1 > n/2)
			cout << mid1;
	 else
	 	cout << mid2;
	return 0;
}

法二

//5. 寻找多数元素
//小小暴力
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int num[N];

int main()
{
	
	int n,x;
	cin >> n;
	for(int i=1;i<=n;++i)
	{
		cin>>num[i];
	}
	if(n==1){
		cout<<num[1];
		return 0;
	}
	sort(num+1,num+n+1);
	for(int i=2;i<=n;++i)
	{
		if(num[i]==num[i-1])
		{
			int cnt=1;
			while(num[i]==num[i-1])
			{
				cnt++;
				i++;
			}
			i-=1;
			if(cnt>n/2)
			{
				cout<<num[i-1]<<" ";
			}
		}
	}
	return 0;
}