目录
01背包问题
快速排序
最长公共子序列问题
排列数字
电视节目问题
归并排序
杨辉三角
01背包问题
描述：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。
输入：
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出：
输出一个整数，表示最大价值。
输入样例
4 5 1 2 2 4 3 4 4 5
输入样例
8
源代码
#include#include using namespace std; #define Max 101 int N,V; int val[Max][Max];//val[i][j]表示物品1，2，~，i，背包最大容量为j时的最大价值量 struct things{ int v[Max]; int w[Max]; }thing; void Knapsack(int N,int V,int *w,int *v){ for(int i = 0; i <= N; i++){ val[i][0] = 0; } for(int j = 0; j <= V; j++){ val[0][j] = 0; } for(int i = 1; i <= N; i++){ for(int j = 1; j <= V; j++){ if(w[i] > j){ val[i][j] = val[i-1][j]; } else{ val[i][j] = max(val[i-1][j],val[i-1][j-w[i]]+v[i]); } } } } int main() { cin >> N >> V; for(int i = 1; i <= N; i++){ cin >> thing.w[i] >> thing.v[i]; } Knapsack(N,V,thing.w,thing.v); cout << val[N][V]; }
快速排序
描述
利用快速排序算法将读入的 NN 个数从小到大排序后输出。
快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。
输入
第 1 行为一个正整数 N，第 2 行包含 N 个空格隔开的正整数 a_i ，为你需要进行排序的数，数据保证了 A_i 不超过 10^9 。
输出
将给定的 N 个数从小到大输出，数之间空格隔开，行末换行且无空格。
输入样例 1
5 4 2 4 5 1
输出样例 1
1 2 4 4 5
源代码
#include#include using namespace std; void QuickSort(int *a,int first,int last){ if(first >= last){ return; } int i = first,j = last; int k = a[first]; while(i != j){ while(k <= a[j] && i < j){ j--; } swap(a[i],a[j]); while(k > a[i] && i < j){ i++; } swap(a[i],a[j]); } QuickSort(a,first,i); QuickSort(a,i+1,last); } int main() { int n; cin>> n; int a[n]; for(int i = 0;i < n;i++){ cin >> a[i]; } QuickSort(a,0,n-1); for(int i = 0; i < n; i++){ cout << a[i] << " "; } cout << endl; }
最长公共子序列问题
描述
给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。
输入
第一行包含两个整数 N 和 M。
第二行包含一个长度为 N 的字符串，表示字符串 A。
第三行包含一个长度为 M 的字符串，表示字符串 B。
字符串均由小写字母构成。
输出
输出一个整数，表示最大长度。
输入样例 1
4 5 acbd abedc
输出样例 1
3
提示
1≤N,M≤1000
源代码
#include; #include ; #include ; #define Max 101 using namespace std; int n,N,M; char A[Max],B[Max]; int val[Max][Max]; void Mlen(char *A,char *B){ for(int i = 0; i <= N; i ++){ val[i][0] = 0; } for(int j = 0; j <= M; j++){ val[0][j] = 0; } for(int i = 1; i <= N; i++){ for(int j = 1; j <= M; j++){ if(A[i] == B[j]){ val[i][j] = val[i-1][j-1] + 1; }else{ val[i][j] = max(val[i-1][j],val[i][j-1]); } } } } int main() { cin >> N >> M; for(int i = 1; i <= N; i++){ cin >> A[i]; } for(int j = 1; j <= M; j++){ cin >> B[j]; } Mlen(A,B); cout << val[N][M] << endl; }
排列数字
描述
给定一个整数 n，将数字 1∼n 排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。
输入
共一行，包含一个整数 n。
输出
按字典序输出所有排列方案，每个方案占一行。
输入样例 1
3
输出样例 1
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
提示
1≤n≤7
源代码
#includeusing namespace std; int a[10]; bool vis[10]={0}; void dfs(int x, const int& m)//x计数以搜索的数的个数 { if(x>m)//搜索数目足够是输出所有的数 { for(int i=1;i<= m;i++) cout<>n; dfs(1,n); return 0; }
电视节目问题
源代码
//电视节目问题 #include#include using namespace std; struct Ti{ int ti_s; int ti_e; }ti[101]; int main() { int n; cin >> n; for(int i = 1; i <= n; i++){ cin >> ti[i].ti_s >> ti[i].ti_e; } //想看最多的节目，就应该找先结束的节目来看 for(int i = 1; i <= n; i++){ for(int j = i+1; j <= n; j++){ if(ti[i].ti_e > ti[j].ti_e){ swap(ti[i].ti_e,ti[j].ti_e); swap(ti[i].ti_s,ti[j].ti_s); } } } cout << endl; for(int i = 1; i <= n;i++){ cout << ti[i].ti_s << " " << ti[i].ti_e << endl; } int res = 1; int cmp = ti[1].ti_e; for(int i = 2; i <= n; i++){ if(ti[i].ti_s >= cmp) res ++; cmp = ti[i].ti_e; } cout << res << endl; }
归并排序
源代码
#includeusing namespace std; int tempArr[101]; //打印函数 void print_arr(int arr[], int n){ for(int i = 0; i < n; i++){ cout << arr[i] << " "; } cout << endl; } //合并 void merge(int arr[], int left, int mid, int right){ //标记左右半区的第一个元素 int l_pos = left; int r_pos = mid + 1; //临时数组元素的下标 int pos = left; //合并 //左右半区都有元素 while(l_pos <= mid && r_pos <= right){ if(arr[l_pos] < arr[r_pos]){ tempArr[pos++] = arr[l_pos++]; } else{ tempArr[pos++] = arr[r_pos++]; } } //合并左右半区剩余元素 while(l_pos <= mid){ tempArr[pos++] = arr[l_pos++]; } while(r_pos <= right){ tempArr[pos++] = arr[r_pos++]; } //把临时数组中合并后的元素复制回来原来的数组 while(left <= right){ arr[left] = tempArr[left]; left ++; } } //归并排序 void msort(int arr[],int left, int right){ if(left < right){ int mid = (left + right)/2; //递归划分左右半区 msort(arr,left,mid); msort(arr,mid + 1,right); //合并已经排序的部分 merge(arr,left,mid,right); } } int main() { int arr[] = {9,5,2,7,12,4,3,1,11}; int n = 9; print_arr(arr,n); msort(arr,0,n-1); print_arr(arr,n); return 0; }
杨辉三角
源代码
#includeusing namespace std; int main() { int n; int a[25][25] = {1};//设定a[0][0]=1很关键 cin >> n; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ a[i][j] = a[i-1][j] + a[i-1][j-1]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(a[i][j] != 0){ if(i == j){ cout << a[i][j]; } else{ cout << a[i][j] << " "; } } } cout << endl; } }
二分查找
源代码
#includeusing namespace std; int search(int *a,int size,int target){ int first = 0; int last = size - 1;//左边右边全部取闭区间 while(first <= last){ int mid = (first + last)/2; if(a[mid] == target){ return target; } else if(a[mid] > target){ last = mid - 1; } else{ first = mid + 1; } } return -1; } int main() { int n; cin >> n; int a[n]; for(int i = 0; i < n; i++) cin >> a[i]; int target; cin >> target; cout << search(a,n-1,target) << endl; }
