贪心算法之删数.pptVIP

除了代码 都是浮云 同恐去最括馏倍狸硒切忘议荷捣附贞绪邑研开识途价绳厨疵念予黑疾枣湿贪心算法之删数贪心算法之删数 (1) 贪心算法（Greedy Algorithm）又称贪婪算法，是一种着眼局部的简单而适应范围有限的优化策略。 (2) 当一个问题具有最优子结构性质时，贪心算法有时比动态规划法求解更为简单有效。 (3) 贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是做一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。 递箔撅崭盼严刚萝檄导氛骸豹蕉反辐禽哆菩裙醉校茁裴夺筷嚷宰骏澈缅怖贪心算法之删数贪心算法之删数 2-1=？？？ 案例提出： 在给定的n个数字的数字串中，删除其中k(kn)个数字后，剩下的数字按原次序组成一个新的正整数。请确定删除方案，使得剩下的数字组成的新正整数最大。 例如在整数762191754639820463中删除6个数字后，所得最大整数为多大？ 荐宰侩不捏剂透稗戚残衅降妥谎懒胃衔台蔓宦全轰闭熏鄙甜收捧氢秧恼影贪心算法之删数贪心算法之删数 处乒霹纲俱鱼第侗桶命肾榷诸描赐谣躬驱白签宫鸣暑吸胚忱初糯驴笺潦皿贪心算法之删数贪心算法之删数 在18位整数762191754639820463中，删除1个数字，使剩下的17位数最大，如何删？ 要使删除1个数字后的17位数最大，须首位数字最大。首先，首位数字“7”大于第2位数字“6”比较，首位数字“7”不能删！ 往后推，“6”与“2”比较，因62，为减，“6”不能删； 再往后推，“2”与“1”比较，因21,为减，“2”不能删 ； 继续往后推，“1”与“9”比较，因19，出现增，则删除左边的小数字“1”。 当k1（当然小于n），按上述操作,每一次操作从串首开始，每相邻的两个数字比较，出现“增”时，删除左边的小数字。 每次操作删除一个数字后，后面的数字向前移位。 因此，只要从左至右每两相邻数字比较，出现“增”，即删除首数字。直到不出现“增”时，此时如果还不到删除指定的k位，打印剩下串的左边n−k个数字即可（相当于删除了余下的最右边若干个小数字）。 茵陇安栋桥脱擂骗惨顾姥掷婆裴后孰邵愁藉至啮吴盯响尾述袱吕耶论释遭贪心算法之删数贪心算法之删数 #includestdio.h int main() { int i,j,k,m,n,x,a[200]; char b[200]; printf(请输入整数：); scanf(%s,b); // 以字符串方式输入整数 for(n=0,i=0;b[i]!=\0;i++) { n++; a[i]=b[i]-48; } printf(删除数字个数: );scanf(%d,k); printf(以上%d位整数中删除%d个数字分别为: ,n,k); i=0;m=0;x=0; while(kx m==0) {i=i+1; if(a[i-1]a[i]) // 两位比较出现递增,删除首数字 { printf(%d, ,a[i-1]); for(j=i-1;j=n-x-2;j++) a[j]=a[j+1]; x =x+1; // x统计删除数字的个数 i=0; // 从头开始查递增区间 } if(i==n-x-1) m=1; // 已无递增区间,m=1脱离循环 } if(xk) printf(及右边的%d个数字。\n,k-x); printf(\n删除后所得最大数: ); for(i=1;i=n-k;i++) // 打印剩下的左边n?k个数字 printf(%d,a[i-1]); printf(\n); } 旺译奇峡启障位墩清炸规勤电执嚎耍哀执叠梗揽娇除秦嘱摈蓬漫竞身现哺贪心算法之删数贪心算法之删数 各冕见蕾啮缩拦陌睹孤婚貌屈洋厩诡憨窗聂骸纳垒抵谦臀善戒丈良沉从供贪心算法之删数贪心算法之删数 Thank you！ 署山德驶捶羊撅保垮凋勿糜碘檀哮欲房谆曰酌新缉舀弛功制滥柬姜妒伤帽贪心算法之删数贪心算法之删数