貪心算法習(xí)題PPT學(xué)習(xí)教案

1、會計學(xué)1貪心算法習(xí)題貪心算法習(xí)題212345678910111213141516周二周二P PP PTTTTP PTTTTP PTTTTP PTTTTTTTTP P周四周四P PP PP PP PP PP PP PP PP PP PP PP PP PP P 端午端午考試考試TT第1頁/共38頁3第2頁/共38頁4()。第3頁/共38頁5第4頁/共38頁6第5頁/共38頁72 3 13 8 80 20n輸出示例5i012345x231388020第6頁/共38頁8磁帶長i012345x238132080貪心策略：最短程序優(yōu)先貪心策略：最短程序優(yōu)先排序后的數(shù)據(jù)排序后的數(shù)據(jù)第7頁/共38頁9第8頁/

2、共38頁10532.00第9頁/共38頁111;double t=0;for(i=0;in;+i) t+=xi;t /= n;return t;i0123456789x1123355569999 2348121000加加11346 101 157 256 355 589 1401 2401定義：定義：vector x;讀取數(shù)據(jù)：讀取數(shù)據(jù)：int n;scanf(“%d”, &n);int temp;for (int i=0; i=0) printf(%dn,temp);第17頁/共38頁19第18頁/共38頁20n輸出文件示例30123456-2-10123456第19頁/共38頁210123

3、456-2-10123456第20頁/共38頁22算刪去k個數(shù)字后得到的最小數(shù)。第21頁/共38頁2313第22頁/共38頁24a.erase(i,1),k-;/每次刪除1個，最近下降點優(yōu)先while(a.size() 1 & a0 = 0) a.erase(0,1);/刪除前導(dǎo)0能使用能使用m嗎？嗎？第23頁/共38頁25第24頁/共38頁26第25頁/共38頁2701200.000.500.0010.000.0010.0020.210.000.00第26頁/共38頁2801200.000.500.0010.000.0010.0020.210.000.0001201.050.535.2512

4、.101.0510.5020.220.111.10只要搜到一個贏利就行只要搜到一個贏利就行第27頁/共38頁2901200.000.504.911.990.0010.0020.190.090.0001201.000.505.0011.991.0010.0020.190.101.00第28頁/共38頁30第29頁/共38頁31第30頁/共38頁32start152076707099 1019end100621087100 99 100 102 18第31頁/共38頁33start5679701709910120end6781899100 100 100 102 210第32頁/共38頁34n:計算出的最大乘積。n輸入示例10 n輸出示例30第33頁/共38頁35下標(biāo)下標(biāo)0123n10851a2345大數(shù)運算大數(shù)運算第34頁/共38頁36n:計算出的最大乘積。n輸入示例10n輸出示例36第35頁/共38頁37)3mod(2 32)3mod( 1 34)3mod(0 3max11 3/ )2( 3/ )4( 3/11 n n nmmm，mnnnnkiijikii則第36頁/共38頁38for(int i=1; i 0; -i) cout ti;coutend