[问题]学妹期末求大神帮助

第一题需要考虑 两个0~9的数字相乘进位问题、两个相乘数的长度与积的长度、两个相乘数某位相乘时得数应该放在乘积的哪一位 搞懂了应该差不多了吧 第二题 暂时只想到暴力方法，for循环遍历每种情况，取出最大值

【 在 woshikeaiduo 的大作中提到: 】 不谢~ //Question1 vector<int> multiply(vector<int> num1,vector<int> num2) { int m = num1.size(); int n = num2.size(); vector<int> dp(n+m); for(int i = m-1; i>= 0 ;i--) for(int j = n-1; j>= 0;j--){ dp[i+j+1] += num1[i] * num2[j] ; dp[i+j] += dp[i+j+1] / 10; dp[i+j+1] %= 10; } return dp; } //Question2 struct Point{ int x; int y; Point(int a,int b):x(a),y(b){} }; double TriangleArea(Point p1,Point p2,Point p3){ return abs(p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p1.x*p3.y - p2.x*p1.y - p3.x*p2.y)/2.0; } double MaxTriangleArea(vector<Point> points){ int n = points.size(); double res = 0; for(int i = 0;i<n;i++) for(int j = i+1;j<n;j++) for(int k = j+1;k<n;k++){ double tmp = TriangleArea(points[i],points[j],points[k]); if(tmp > res) res = tmp; } return res; }

旋转卡壳算法。 ============== 枚举三角形的第一个顶点i, 然后初始第二个顶点j=i+1,第三个顶点k=j+1， 循环k+1直到Area(i,j,k)>Area(i,j,k+1) 更新面积的最大值，下面就开始旋转卡壳了（旋转j,k两个点） (1)如果Area(i,j,k)<Area(i,j,k+1)且k!=i，则k=k+1，否则转(2) (2)更新面积,j=j+1,如果j=i,跳出循环 这样旋转一圈后，求得的面积就是以i为顶点的最大三角形的面积了。 时间复杂度是O(n^2) ============== 【 在 woshikeaiduo 的大作中提到: 】 : 要期末了，有两道编程题求大神指点~过了请吃饭还有妹纸作陪哦~ : 第一题：为了进行高精度计算，我们可以用一个数组表示一个正整数，一个数组元素表示整数的一位，例如396可以用数组A表示，即A[1]=6,A[2]=9,A[3]=3，编写一个函数，计算这样表示的两个整数A,B之积，积存放在数组C中。注：假定积不会超过100位。 : 第二题：平面有100个点，任意三个点可以构成一个三角形，编写一个程序，输入100个点的坐标，输出在构成的所有三角形中，最大的三角形的面积。

mark+赞~~ 【 在 gaoweiwei 的大作中提到: 】 : 旋转卡壳算法。 : ============== : 枚举三角形的第一个顶点i, : ...................

其实3楼这个方法100个点看不出来时间花费的，不过还是要点赞，那第一题还可以用FFT nlogn的方法做

第一道题用卷积

【 在 fenixlee520 的大作中提到: 】 : 第一道题用卷积 伪代码是什么样的？~！

http://blog.csdn.net/sdj222555/article/details/9786527