问题求解05枚举.pptVIP

下载本文档

1
0
约1.63万字
约 51页
2018-01-19 发布于广东
举报
版权申诉

问题求解05枚举.ppt

1、本文档共51页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
8、VIP文档为合作方或网友上传，每下载1次，网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档

讨厌的青蛙 struct PLANT {//描述一棵被踩踏的水稻 int x; //水稻的行号 int y; //水稻的列号 } 从被踩踏的水稻中选择两棵(X1, Y1)、(X2, Y2)。判断它们是否能够作为一条青蛙路径上最先被踩踏的两颗水稻。 (X1, Y1)、(X2, Y2)唯一确定了蛙跳的方向和步长，从(X2, Y2)开始，沿着这个方向和步长在稻田内走。每走一步，判断所到达位置上(X, Y)的水稻是否被踩踏，直到走出稻田为止。如果在某一步上，(X, Y) 没有被踩踏，则表明(X1,Y1)、(X2, Y2)是一条青蛙路径上最先被踩踏的两颗水稻的假设不成立。这个判断的算法在问题求解过程中要反复使用，它的效率成为决定整个计算效率的关键。(用二分法查找) 讨厌的青蛙 int r, c, n; struct PLANT { int x, y; }; PLANT plants[5001]; PLANT plant; int myCompare( const void *ele1, const void *ele2 ); int searchPath(PLANT secPlant, int dX, int dY); 讨厌的青蛙——main() int main( ) { int i, j, dX, dY, pX, pY, steps, max = 2; scanf(%d%d, r, c); scanf(%d, n); for ( i = 0; i n; i++ ) scanf(%d %d, plants[i].x, plants[i].y); qsort(plants, n, sizeof(PLANT), myCompare); //找最长路径，见下页 if ( max == 2 ) max = 0; printf(%d\n, max); return 0; } 讨厌的青蛙——main() for ( i = 0; i n - 2; i++ ) for ( j = i + 1; j n - 1; j++ ) { dX = plants[j].x - plants[i].x; dY = plants[j].y - plants[i].y; pX = plants[i].x - dX; pY = plants[i].y - dY; if ( pX = r pX = 1 pY = c pY = 1 ) continue; if ( plants[i].x + max * dX r ) break; pY = plants[i].y + max * dY; if ( pY c || pY 1) continue; steps = searchPath( plants[j], dX, dY ); if ( steps max ) max = steps; } 讨厌的青蛙 int myCompare( const void *ele1, const void *ele2 ) { PLANT *p1, *p2; p1 = (PLANT*) ele1; p2 = (PLANT*) ele2; if ( p1-x == p2-x ) return( p1-y - p2-y ); return ( p1-x - p2-x ); } 讨厌的青蛙 int searchPath( PLANT secPlant, int dX, int dY ) { PLANT plant; int steps; plant.x = secPlant.x + dX; plant.y = secPlant.y + dY; steps = 2; while ( plant.x = r plant.x = 1 plant.y = c plant.y = 1 ) { if ( !bsearch(plant, plants, n, sizeof(PLANT), myCompare) ) { steps = 0; break; }