淘宝 做网站空间 条件,东莞设计网站,公众号怎么制作链接,电商网站改版实验2-1 二分搜索
【问题描述】给定一个包含 n 个元素有序的#xff08;升序#xff09;整型数组 nums 和一个目标值 target#xff0c;要求实现搜索 nums 中的 target#xff0c;如果目标值存在返回下标#xff0c;否则返回 -1。题目保证nums中的所有元素都不重复。
【…
实验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 二分
#includebits/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 二分
#includebits/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
【说明】
1n10^4
0nums[i]10^5
#includeiostream
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(leftq)tmp[ k ] a[ left ];while(rightr)tmp[ k ] a[ right ];//放过来 for(int i 0 ; i n ; i ){a[li] 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 【说明】 1kn10^4
10^-5nums[i]10^5
PS:这题我是真想排序输出啊 44是大量推导得出来的 递归法
#include algorithm
#includebits/stdc.h
using namespace std;
const int N1e510;
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 i1;in;i){cin arr[i];}cin k;quicksort(arr, 1, n); printf(%d\n,arr[k]);return 0;
} 实验2-4 整数因子分解问题
问题描述 大于1 的正整数n 可以分解为nx1*x2*…*xm。
例如当n12 时共有8 种不同的分解式
1212
126*2
124*3
123*4
123*2*2
122*6
122*3*2
122*2*3 。 编程任务 对于给定的正整数n编程计算n 共有多少种不同的分解式。 数据输入 由文件input.txt 给出输入数据。第一行有1 个正整数n (1≤n≤2000000000)。 结果输出: 将计算出的不同的分解式数输出到文件output.txt 。 输入文件示例 输出文件示例
input.txt output.txt 12 8 动态规划
#includebits/stdc.h
using namespace std;
const int N 1e5 10;
int a[N],dp[N];
int k0;
//初始化函数找出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
【说明】
1n,m,k100
矩阵中每个元素的绝对值1000
#includeiostream
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 行是居民点数n1n10000。接下来n 行是居民点的位置每行2 个整数x 和y-10000xy10000。 结果输出: 程序运行结束时将计算结果输出到文件output.txt 中。文件的第1 行中的数是n 个居民点到邮局的距离总和的最小值。 输入文件示例 输出文件示例
input.txt output.txt
5 10
1 2
2 2
1 3
3 -2
3 3
同货仓选址问题
code:
#includeiostream
#includealgorithm
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;
}
