《算法设计与分析作业34.docx》由会员分享，可在线阅读，更多相关《算法设计与分析作业34.docx（7页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析作业作业一：问题：给定一组硬币，找出若干的硬币，使得他们的值最大，但不能选择相邻的硬币代码：CoinProblem.cpp : 定义控制台应用程序的入口点。/给定一组硬币，找出若干的硬币，使得他们的值最大，但不能选择相邻的硬币/#include stdafx.hconst int coinNum = 100;int coinValuecoinNum; /硬币值数组int maxValue; /得到的硬币最大值/位置选择表struct nodeint totalValue;int prePos=-1; /前一个节点的位置,-1表示结束了;node coinPoscoinNum;vo
2、id exchangeValue(int &a,int &b)int temp = a;a = b;b = temp;/产生一个有顺序数组，随机交换一组值，扰乱顺序,得到一个随机数组void makeCoinValue(int size,int maxValue)/产生1-max的数组int *temp = new intmaxValue;for (int i = 0; i maxValue; i+)*(temp + i) = i+1;srand(unsigned( time_t(NULL) );/交换多次int times = size;for (int j = 0; j times; j+
3、)int pos1 = rand() % maxValue;int pos2 = rand() % maxValue;exchangeValue(*(temp + pos1), *(temp + pos2);for (int k = 0; k size; k+)coinValuek = *(temp + k);cout 硬币的面值序列：;for (int k = 0; k size ; k+)cout coinValuek ;cout = 0)node tempMax = coinPospos;for (int j = pos; j = 0; j-)if (coinPosj.totalValu
4、e tempMax.totalValue)tempMax = coinPosj;pos = j;return pos;void printResult(int endPos)int currentPos = endPos;cout = 0)cout currentPos+1 : coinValuecurrentPos ;currentPos = coinPoscurrentPos.prePos; cout endl;cout 最大的和为： maxValueendl;void selectCoin()maxValue = 0; /当前累计最大为int maxEndPos = 0; /当前最大链的
5、结束点for (int i = 0; i coinNum; i+) int maxPrePos = maxPreValue(i); if (maxPrePosmaxValue)maxValue = coinPosi.totalValue; /如果当前值大于最大值，更新最大值和结束点maxEndPos = i;printResult(maxEndPos); int _tmain(int argc, _TCHAR* argv)makeCoinValue(10, 20);selectCoin();return 0;运行结果：作业二：来自leetcode：/ CombinationSum.cpp :
6、定义控制台应用程序的入口点。/* Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.Ensure that numbers within the set are sorted in ascending order.Example 1:Input : k = 3, n = 7Output :1, 2,
7、4Example 2 :Input : k = 3, n = 9Output :1, 2, 6, 1, 3, 5, 2, 3, 4*/#include stdafx.h/temp向量可以加引用也可以不加，加上引用则不会在递归的时候产生副本，降低的内存的需求void combination(vectorvector & vvReslut, vector& temp, int k,int n)if (0=k & 0=n)vvReslut.push_back(temp);return;if (0k)for (int i = (temp.empty() ? 1:temp.back()+1); i =
8、n/k; i+) /i的值不可能大于n/k,可以大大减少循环if (n - i 0) break; /n-i如果小于0，则不是递增顺序temp.push_back(i);combination(vvReslut, temp, k-1, n - i); /对k-1位的n-i进行操作temp.pop_back(); vectorvector combinationSum3(int k, int n) vectorvector result;vector sol;combination(result, sol, k, n);return result;int _tmain(int argc, _TC
9、HAR* argv)vectorvector vv = combinationSum3(3, 12);int length = vv.size();for (int i = 0; i length; i+)int vlength = vvi.size();for (int j = 0; j vlength; j+)cout vvij ;cout endl;return 0;运行结果：作业三：来自leetcode：/ KthLargestElement.cpp : 定义控制台应用程序的入口点。/* Find the kth largest element in an unsorted array
10、.Note that it is the kth largest element in the sorted order, not the kth distinct element.For example,Given3, 2, 1, 5, 6, 4 and k = 2, return 5.Note:You may assume k is always valid, 1 k arrays length.*/#include stdafx.hint findKthLargest(vector& nums, int k) priority_queue p; /把值放入优先级队列const int s(nums.size();for (int i = 0; i length;cin k;vector v;srand(unsigned(time(NULL);for (int i = 0; i length; i+)v.push_back(rand() % 20);cout vi ;cout endl;cout findKthLargest(v, k);cout endl;return 0;运行结果：
