算法設(shè)計(jì)與分析作業(yè)34.docx

算法設(shè)計(jì)與分析作業(yè)作業(yè)一：問題：給定一組硬幣，找出若干的硬幣，使得他們的值最大，但不能選擇相鄰的硬幣代碼：CoinProblem.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/給定一組硬幣，找出若干的硬幣，使得他們的值最大，但不能選擇相鄰的硬幣/#include stdafx.hconst int coinNum = 100;int coinValuecoinNum; /硬幣值數(shù)組int maxValue; /得到的硬幣最大值/位置選擇表struct nodeint totalValue;int prePos=-1; /前一個(gè)節(jié)點(diǎn)的位置,-1表示結(jié)束了;node coinPoscoinNum;void exchangeValue(int &a,int &b)int temp = a;a = b;b = temp;/產(chǎn)生一個(gè)有順序數(shù)組，隨機(jī)交換一組值，擾亂順序,得到一個(gè)隨機(jī)數(shù)組void makeCoinValue(int size,int maxValue)/產(chǎn)生1-max的數(shù)組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; /當(dāng)前累計(jì)最大為int maxEndPos = 0; /當(dāng)前最大鏈的結(jié)束點(diǎn)for (int i = 0; i coinNum; i+) int maxPrePos = maxPreValue(i); if (maxPrePosmaxValue)maxValue = coinPosi.totalValue; /如果當(dāng)前值大于最大值，更新最大值和結(jié)束點(diǎn)maxEndPos = i;printResult(maxEndPos); int _tmain(int argc, _TCHAR* argv)makeCoinValue(10, 20);selectCoin();return 0;運(yùn)行結(jié)果：作業(yè)二：來自leetcode：/ CombinationSum.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/* 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向量可以加引用也可以不加，加上引用則不會(huì)在遞歸的時(shí)候產(chǎn)生副本，降低的內(nèi)存的需求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,可以大大減少循環(huán)if (n - i 0) break; /n-i如果小于0，則不是遞增順序temp.push_back(i);combination(vvReslut, temp, k-1, n - i); /對(duì)k-1位的n-i進(jìn)行操作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;運(yùn)行結(jié)果：作業(yè)三：來自leetcode：/ KthLargestElement.cpp : 定義控制臺(tái)應(yīng)用程序的入口點(diǎn)。/* 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; /把值放入優(yōu)先級(jí)隊(duì)列const int s(nums.size();for (int i = 0; i length;cin