【算法实验】实验2

实验2-1 二分搜索

【问题描述】给定一个包含 n?个元素有序的（升序）整型数组?nums?和一个目标值?target，要求实现搜索?nums?中的?target，如果目标值存在返回下标，否则返回?-1。题目保证nums中的所有元素都不重复。

【输入形式】输入的第1行中有1个数字n，表示数组的长度；第2行中有n个数字，表示数组的元素；第3行中有1个数字，表示要搜索的目标值。
【输出形式】输出1行中有1个数字，表示目标值在数组中出现的下标。
【样例输入1】

6

-5 0 1 5 10 12

0
【样例输出1】

1
【样例说明1】

0出现在nums中并且下标为1

【样例输入2】

6

-5 0 1 5 10 12

6
【样例输出1】

-1
【样例说明1】

6不存在于nums中因此输出-1

题目本身有序，无须排序

code1：

//实验2-1 二分
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int x;
int a[N];
int query(int low , int high)
{
	while(low < high)
	{
		int mid = (low + high) >> 1;
		if(a[mid] == x){
			return mid;
		}else if(a[mid] > x)
		{
			high = mid;
		}
		else{
			low = mid + 1;	
		}

	}
	return -1;
}
int main()
{
	int n;
	cin >> n ;
	for(int i = 0 ; i < n ; i ++ )
	{
		cin >> a[i];
	}
	cin >> x;
	cout << query(0,n-1);
	return 0;
 } 

个人更喜欢code2的风格：

//实验2-1 二分
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int x;
int a[N];
int query(int low , int high)
{
	while(low < high)
	{
		int mid = (low + high) >> 1;
		if(x <= a[mid]) high = mid;
		else low = mid + 1;
	}
	return ( a[low] == x ? low : -1);
}
int main()
{
	int n;
	cin >> n ;
	for(int i = 0 ; i < n ; i ++ )
	{
		cin >> a[i];
	}
	cin >> x;
	cout << query(0,n-1);
	return 0;
 } 

实验2-2 归并排序

MergeSort

【问题描述】给定一个长度为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>
using namespace std;
const int N = 1e4 + 10;
int a[N];

void Merge(int l,int q,int r)
{
	int tmp[N];//临时数组 
	int n = r - l + 1; //长度 
	int k = 0; //临时数组Index 
	int left = l; //左区间的第一个 
	int right = q + 1; //右区间的第一个 
	while(left <= q && right <= r )
	{
		tmp[ k ++ ] = a[left] <= a[right] ? a[left++] : a[right++];
	}
	while(left<=q)
		tmp[ k ++ ] = a[ left ++ ];
	while(right<=r)
		tmp[ k ++ ] = a[ right ++];
	//放过来 
	for(int i = 0 ; i < n ; i ++ )
	{
		a[l+i] = tmp[i];
	}
}
void MergeSort(int l,int r)
{
	if(l == r) return;
	else{
		int q = ( l + r ) / 2;
		MergeSort( l , q );
		MergeSort( q + 1 , r );
		Merge(l,q,r);
	}
}
int main()
{
	int n;
	cin >> n;
	for(int i = 0 ; i < n ; i ++ )
	{
		cin >> a[i];
	}
	MergeSort(0,n-1);
	for(int i = 0 ; i < n ; i ++ )
	{
		cout << a[i] <<" ";
	}
	return 0;
}

实验2-3 寻找数组中的第k小元素

【问题描述】给定一个长度为n的整数数组nums和整数k，输出数组中的第k小元素。要求不能对数组排序，使用分治的思想求解。

【输入形式】输入的第1行中有1个数字n，表示数组的长度；第2行中有n个数字，表示数组的元素；第3行中有1个数字k。

【输出形式】输出1行中有1个数字，表示数组中的第k小元素。
【样例输入】

6

3 2 1 4 6 5

2
【样例输出】

2
【说明】
1<=k<=n<=10^4

10^-5<=nums[i]<=10^5

PS:这题我是真想排序输出啊

44是大量推导得出来的

递归法：

#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int arr[N];
void quicksort(int arr[], int left, int right) {  
    if (left >= right) {  
        return;  
    }  
    int i = left, j = right, pivot = arr[left];  
    while (i < j) {  
        while (i < j && arr[j] >= pivot) {  
            j--;  
        }  
        if (i < j) {  
            arr[i++] = arr[j];  
        }  
        while (i < j && arr[i] < pivot) {  
            i++;  
        }  
        if (i < j) {  
            arr[j--] = arr[i];  
        }  
    }  
    arr[i] = pivot;  
    quicksort(arr, left, i - 1);  
    quicksort(arr, i + 1, right);  
}
int main(){
    int n,k;  
    cin >> n;
    for (int i=1;i<=n;++i)
    {
    	cin >> arr[i];
	}
	cin >> k;
  	quicksort(arr, 1, n); 
    printf("%d\n",arr[k]);
    
    return 0; 
}

实验2-4 整数因子分解问题

问题描述：

　大于1 的正整数n 可以分解为：n=x1*x2*…*xm。

例如，当n=12 时，共有8 种不同的分解式：

12=12；

12=6*2；

12=4*3；

12=3*4；

12=3*2*2；

12=2*6；

12=2*3*2；

12=2*2*3 。

编程任务：

　　对于给定的正整数n，编程计算n 共有多少种不同的分解式。

数据输入：

　　由文件input.txt 给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。

结果输出:

将计算出的不同的分解式数输出到文件output.txt 。

输入文件示例????????? 输出文件示例

input.txt??????????? output.txt

　12????????????????????? 8

动态规划：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N],dp[N];
int k=0;
//初始化函数，找出n的所有约数 
void init(int n)
{
	k = 0;
	int i = 1;
	for(i = 1; i < sqrt(n) ; i ++ )
	{
		if( n % i == 0 ) //如果是n的约数 存储 
		{
			a[ k ++ ] = i;
			a[ k ++ ] = n / i;
		}
	}
	if( i * i == n)
	{
		a[ k ++ ] = i;
	}
}
void solve(int n){
	dp[0] = 1;
	for(int i = 1; i < k ; i ++ )
	{
		dp[i] = 0;
		for(int j = 0; j < i ; j ++ )
		{
			if( a[i] % a[j] ==0) //还能分解 
			{
				dp[i] += dp[j]; //+
			}
		}
	}
}
int main()
{
	int n;
	cin >> n;
	init(n); //初始化n的约数
	//记得排序
	sort( a , a + k );
	solve(n);
	cout << dp[k-1];
	return 0; 
}

实验2-5 矩阵乘法

【问题描述】要求必须使用【分治策略】计算两个矩阵的乘法。nxm阶的矩阵A乘以mxk阶的矩阵B得到的矩阵C是nxk阶的。

【输入形式】输入的第一行中有3个整数n, m,k,表示A矩阵是n行m列,B矩阵是m行k列。接下来的n行，每行m个数字，表示矩阵A中的元素。接下来的m行，每行k个元素，表示矩阵B中的元素。

【输出形式】输出矩阵C,一共n行,每行k个整数，整数之间以一个空格分开。

【样例输入】

3 2 3

1 1

1 1

1 1

1 1 1

1 1 1?

【样例输出】

2 2 2?

2 2 2?

2 2 2?

【说明】

1<=n,m,k<=100

矩阵中每个元素的绝对值<=1000

#include<iostream>
using namespace std;
const int N = 110;
int juz1[N][N];
int juz2[N][N];
int res[N][N];
int main()
{
	int x , y , k;
	cin >> x >> k >> y;
	//input
	for(int i = 1 ; i <= x; i ++)
	{
		for(int j = 1 ; j <= k ; j ++ )
		{
			cin >> juz1[i][j]; 
		}
	}
	for(int i = 1 ; i <= k; i ++)
	{
		for(int j = 1 ; j <= y ; j ++ )
		{
			cin >> juz2[i][j]; 
		}
	}
	//calu
	for(int i = 1 ; i <= x ; i ++ )
	{
		for(int j = 1; j <= y ; j ++)
		{
			for(int w = 1; w <= k ; w ++)
			{
				res[i][j] += juz1[i][k] * juz2[k][j];
			}
		}
	}
	//output
	for(int i = 1 ; i <= x ; i ++ )
	{
		for(int j = 1; j <= y ; j ++ )
		{
			cout << res[i][j] << " ";
		}
		cout <<"\n";
	}
	return 0;
}

实验2-6 邮局选址问题

问题描述：

　　在一个按照东西和南北方向划分成规整街区的城市里，n 个居民点散乱地分布在不同的街区中。用x 坐标表示东西向，用y 坐标表示南北向。各居民点的位置可以由坐标(x,y) 表示。街区中任意2 点(x1,y1) 和(x2,y2) 之间的距离可以用数值|x1-x2|+|y1-y2| 度量。

居民们希望在城市中选择建立邮局的最佳位置，使n 个居民点到邮局的距离总和最小。

编程任务：

　　给定n 个居民点的位置,编程计算n 个居民点到邮局的距离总和的最小值。

数据输入：

　　由文件input.txt 提供输入数据。文件的第1 行是居民点数n，1<=n<=10000。接下来n 行是居民点的位置，每行2 个整数x 和y，-10000<=x，y<=10000。

结果输出:

　　程序运行结束时，将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居民点到邮局的距离总和的最小值。

输入文件示例?????????????? 输出文件示例

input.txt????????????????? output.txt

5????????????????????????? 10

1 2

2 2

1 3

3 -2

3 3

同货仓选址问题

code:

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x7f7f7f;

int avex,avey;
int dis(int x){
	return abs( avex - x ) ;
}
int xx[N],yy[N];
int main()
{
	int n;
	cin >> n;
	for(int i = 1 ; i <= n ; i ++ )
	{
		cin >> xx[i] >> yy[i];
	}
	sort( xx + 1 , xx + n + 1);
	sort( yy + 1 , yy + n + 1);
	avex = xx[ n/2 + 1];
	avey = yy[ n/2 + 1];
	int mindis = 0;
	for(int i = 1 ; i <= n ; i ++ )
	{
		mindis += dis(xx[i]) + dis(yy[i]);
	}
	cout << mindis;
	return 0;
}