资源描述：
《递归向循环 转化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《递归向循环转化》/scimenceXX采药题目详情:描述XX是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大”。如果你是XX，你能完成这个任务吗？输入格式多组数据，每行两个整数，用空格隔开，第一
2、行有两个整数T（1<=T<=1000）和M（1<=M<=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出格式输出包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。答题说明:样例输入：703711006911221598421182226144982613939...样例输出：3674///C#实现：usingSystem;usingSy
3、stem.Collections.Generic;usingSystem.Linq;usingSystem.Text;namespaceV2{classProgram{//问题的递归解答，运行时间3.765sstaticintV(int[]t,int[]v,intT,intM){if(M==0T==0)return0;//若药材总数、或总时间等于0，则最大价值为0if(t[M-1]>T)returnV(t,v,T,M-1);//第M株药材所需时间大于总时间，则计算前M-1株的最大价值else{//第M株药材所需
4、时间小于等于总时间时，则判断是第M株药材是选择的价值更大还是不选择的价值更大intv1,v2;v1=V(t,v,T-t[M-1],M-1)+v[M-1];//第M株药材选中后的最大价值v2=V(t,v,T,M-1);//第M株药材未选中的最大价值returnv1>v2?v1:v2;//返回较大的那个}}//《递归到循环的转化》//由于函数的递归调用效率很低，我们对递归过程进行逆向操作，//可转化成循环过程如下：//1.观察递归调用过程的参数变化规律，我们可以发现，四个参数中仅有两个T和M是变化的；//2.变化规
5、律为单向向0变化,变化梯度不定，我们取1可包含所有梯度，当变化的两个参数中的一项为零时返回结果为0，最大可以有TM种变化；//3.我们定义V[T+1,M+1]大小的空间来保存各种可能递归变化结果；因为是逆向操作，所以先将(M==0T==0)的结果也算在内为[T+1,M+1]；//4.下面开始逆向转换，将递归函数中的函数体部分(除3步骤的操作内容外）//1)所有T替换为i,所有M替换为j,所有return替换为{V[i,j]=;continue;},(有return的地方不进入下一个分支)//所有的子递归调用部分
6、全部替换为V[,]保留其中的变化参数（代表T和M的变量，去除其中的不变参数t与v;//2)将两个变化的参数替换为i,j的目的是为了让i,j分别从0变化到T和M,实现逆向操作；//3)补全变化的语法，for(i=0;i<=T;i++),for(j=0到M),i与j的嵌套变化顺序随意，但必须嵌套；//4)最后输出逆操作的结果V[T,M],最后可在不改变算法执行语义的情况下进行适当修改//其实，这种转换还只是模糊转换，其中仍然包含大量不必要操作，模糊在，M、T向0的变换过程，并非以1为阶梯，有很多大于1，//其实，只
7、需定义M(M+1)的空间大小就可以实现上述转化过程，具体情况你先将t[i]排序，将i的变化从按t[i]再加一个T变化,j按t[i]变化运行下面的循环过程就可以发现。//转化后：，运行时间0.001sstaticintV2(int[]t,int[]v,intT,intM){int[,]V=newint[T+1,M+1];for(inti=0;i<=T;i++)for(intj=0;j<=M;j++){if(j==0i==0){V[i,j]=0;continue;}//若药材总数、或总时间等于0，则最大价值为0if
8、(t[j-1]>i){V[i,j]=V[i,j-1];continue;}//第j株药材所需时间大于总时间，则计算前j-1株的最大价值else{//第j株药材所需时间小于等于总时间时，则判断是第j株药材是选择的价值更大还是不选择的价值更大intv1,v2;v1=V[i-t[j-1],j-1]+v[j-1];//第j株药材选中后的最大价值v2=V[i,j-1];//第j株药材未选中的最大
