【算法实验】实验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;//inputfor(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]; }}//calufor(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];}}}//outputfor(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;
}