算法设计与分析作业34.docx

算法设计与分析作业作业一：问题：给定一组硬币，找出若干的硬币，使得他们的值最大，但不能选择相邻的硬币代码：CoinProblem.cpp : 定义控制台应用程序的入口点。/给定一组硬币，找出若干的硬币，使得他们的值最大，但不能选择相邻的硬币/#include stdafx.hconst int coinNum = 100;int coinValuecoinNum; /硬币值数组int maxValue; /得到的硬币最大值/位置选择表struct nodeint totalValue;int prePos=-1; /前一个节点的位置,-1表示结束了;node coinPoscoinNum;void 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+)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.totalValue 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; /当前最大链的结束点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 : 定义控制台应用程序的入口点。/* 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, 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 = 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, _TCHAR* 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.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