/* 因为相乘顺序会影响标量的乘法大小,所以加括号的位置非常影响乘法结果的大小 */ #include<iostream> using namespace std; void matrix_chain_order(int *p,int m[][1000],int s[][1000],int n); void print(int s[][1000],int i,int j); int main() { int p[1000];//存储第一个行,和其他的列 cout <<"请输入要输入矩阵的个数:"; int num = 0 ; cin >> num; int row = 0,column = 0; cout <<"请依次输入矩阵的行和列:"; cin >> row >> column; //因为p[0]要存第一个矩阵的行,之后的p都是存矩阵的列 //这里我刚开始 继续阅读 >>


陈文浩 18/04/09 18:32:03
i= 0表示有序数组arr1的首元素,j = 未知,表示有序数组arr2的首元素 ①首先比较第一个有序数组arr1和第二个有序数组arr2第一个元素的大小 如果arr1[i] < arr[j],i++ 否则 index记住j的位置,index就是j变化之前的位置 ②如果arr2[j] < arr[i],证明后面的元素小于后面的元素,需要进行往前的置换,所以j++,但是要保证j++不能越界 ③进行了①和②之后,已经找到了需要置换两个数组的范围,使用swap交换 ④进行i下标的更新,因为i+j-index已经排序好了,所以i要加上j-index ⑤直到while(i < j &&j < 数组的长度)不成立,程序结束 #include <iostream> #include <vector> #include <algorithm> using namespace std; template <typena 继续阅读 >>


陈文浩 18/04/08 22:40:31
1. 递归实现归并排序 基本思想: 将待排元素分成大小大致相同的2个子集,分别对2个子集合进行排序,最终将排好序的子集合合并 就会得到一个排好序的集合 即为所求 设归并排序的当前区间是R[low..high],分治法的三个步骤是: ① 分解:将当前区间一分为二,即求分裂点 ② 求解:递归地对两个子区间R[low..mid]和R[mid+1..high] 进行归并排序; ③ 组合:将已排序的两个子区间R[low..mid]和R[mid+1..high] 归并为一个有序的区间R[low..high]。 递归的终结条件:子区间长度为1(一个记录自然有序)。 2) 具体过程如下图所示: /* 数组a[]为待排序数组,数组b[]用来存放已排好序的数 left、right分别为待排序数组最左端和最右端的下标 mid为数组下标的中点 */ (算法导论版是借助两个数组,这个例子是借助了一个数组) #include<i 继续阅读 >>


陈文浩 18/04/08 19:18:18
/* 切割绳子,每段绳子都有一个最大值,给定长度为n的绳子,如何切割让利益最大化 自底而上的方法,对于任何子问题,直至它依赖的所有子问题都解决,才会去解决它。 */ #include<iostream> #include<algorithm> #include<vector> using namespace std; vector<int> max_value(100,0);//当长度为n时,最大利益 vector<int> first_cut(100,0);//当长度为n时,切割一刀的位置 vector<int> price{0,1,5,8,9,10,17,17,20,24,30};//每段绳子的价值 void cut_rope(int n) { int max; max_value[0] = 0;//长度为0,值为0; for(int j = 1;j <= n;j++)//总长度 继续阅读 >>


陈文浩 18/04/07 21:03:04
子数组换位问题 设a[0:n-1]是一个有n个元素的数组,k(0<=k<=n-1)是一个非负整数。 试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。 初步思考:最简单的方法就是循环(n-k-1)次,将a数组的末尾数字插入到a[0]之前。 具体做法: (1) 首先开辟一个额外空间temp用于存放每一次a数组的末尾数据。 (2) temp <- a[n-1] (3) 将a[0: n-2] 每个数据都依次向后移动一位赋值给a[1: n-1]。 (4) a[0] <- temp (5) 循环执行(2) -(4) 步 (n-k+1)次。 代价分析: 时间代价—— O((n-1)*(n-k+1)) 即O(n^2 继续阅读 >>


陈文浩 18/04/03 22:49:49
头文件#include<numeric> accumulate(first,last, init); first,last可以是数字也可以是字符串,将把init 和从 first 到last 指向的值进行累加,并返回累加得到的和 #include<iostream> #include<numeric> #include<vector> #include<string> using namespace std; int main() { int arr[] = {1,2,3,4,5,6}; int sum = accumulate(begin(arr),end(arr),0); cout <<sum<<endl; string word[] = {"1","2","3","4"}; vector<string> str(word,word+sizeof(wo 继续阅读 >>


陈文浩 18/03/06 17:03:38
今有7对数字:两个1,两个2,两个3,…两个7,把它们排成一行。 要求,两个1间有1个其它数字,两个2间有2个其它数字,以此类推,两个7之间有7个其它数字。如下就是一个符合要求的排列: 17126425374635 当然,如果把它倒过来,也是符合要求的。 请你找出另一种符合要求的排列法,并且这个排列法是以74开头的。 注意:只填写这个14位的整数,不能填写任何多余的内容,比如说明注释等。 思路就是for循环负责某个下标,n是负责下标之间的距离,每次i和i+n+1等于同一个值,就保证使用了两个一样的值 #include<iostream> #include<cstring> int arr[16]; int dfs(int n) { if(n > 6) return 1;//因为7距离已经确定,所以最大距离就是6 if(n == 4) n++;//因为当n=4,两者距离就是4,4的位置已经确定,所以跳过 int i = 0; fo 继续阅读 >>


陈文浩 18/03/05 22:53:49
如果x的x次幂结果为10,你能计算出x的近似值吗? 显然,这个值是介于2和3之间的一个数字。 请把x的值计算到小数后6位(四舍五入),并填写这个小数值。 注意:只填写一个小数,不要写任何多余的符号或说明。 题上说的很明确,答案是介于2到3之间的,所以暴力枚举没问题 #include<iostream> #include<cmath> #include<iomanip> using namespace std; int main() { double x = 2.0; for(;x!=3.0;x+=0.00000001)//加的时候尽量位数放大 { if(fabs(pow(x,x)-10) < 0.000001)//这里来限制范围 { cout << fixed<<setprecision(6)<<x<< 继续阅读 >>


陈文浩 18/03/05 20:18:32
#include<stdio.h> #include<stdlib.h> int maze[5][5]; int mark[5][5]={0}; typedef struct{ int x; int y; }offset; offset direct[8] = {-1,0, -1,-1, 0,-1, 1,-1, 1,0, 1,1, 0,1, -1,1}; //8个方向 typedef struct{ int x; int y; int direct; }element; element stack[26]; void add(int *top,element position); element delete(int *top); int main() { int entry_x, entry_y; int exit_x, exit_y; printf 继续阅读 >>


陈文浩 18/01/15 22:15:32
/* * 用prim算法弄最小生成树,每次一个点都会遍历所有点,找出,两点距离最短的情况 * 再改变节点的入度和最小值 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define INFINITY 1000 struct{ int adjvex; int lowcost; }closedge[31]; typedef struct { int vexnum; int arcs[11][11]; }AdjMatrix; AdjMatrix *G; void prim(AdjMatrix *G,int start); int main() { printf("请输入矩阵:"); G = (AdjMatrix *)malloc(sizeof(AdjMatrix)); for(int i=1;i<=10;i++) f 继续阅读 >>


陈文浩 18/01/15 15:14:37