递归向循环 转化.doc

递归向循环 转化/*scimenceXX采药题目详情:描述 XX是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。 * 医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。 * 我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大”。 * 如果你是XX，你能完成这个任务吗？输入格式 多组数据，每行两个整数，用空格隔开，第一行有两个整数T（1 = T = 1000）和M（1 = M T) return V(t, v, T, M - 1); /第M株药材所需时间大于总时间，则计算前M-1株的最大价值 else /第M株药材所需时间小于等于总时间时，则判断是第M株药材是选择的价值更大还是不选择的价值更大 int v1, v2; v1 = V(t, v, T - tM - 1, M - 1) + vM - 1; /第M株药材选中后的最大价值 v2 = V(t, v, T, M - 1); /第M株药材未选中的最大价值 return v1 v2 ? v1 : v2; /返回较大的那个 / 递归到循环的转化/ 由于函数的递归调用效率很低，我们对递归过程进行逆向操作，/ 可转化成循环过程如下：/1.观察递归调用过程的参数变化规律，我们可以发现，四个参数中仅有两个T和M是变化的；/2.变化规律为单向向0变化,变化梯度不定，我们取1可包含所有梯度，当变化的两个参数中的一项为零时返回结果为0，最大可以有T*M种变化；/3.我们定义VT+1,M+1大小的空间来保存各种可能递归变化结果；因为是逆向操作，所以先将(M = 0 | T = 0)的结果也算在内为T+1,M+1；/4.下面开始逆向转换，将递归函数中的函数体部分(除3步骤的操作内容外）/ 1)所有T替换为i, 所有M替换为j,所有return * 替换为Vi,j = *; continue; ,(有return的地方不进入下一个分支)/ 所有的子递归调用部分全部替换为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)最后输出逆操作的结果VT,M, 最后可在不改变算法执行语义的情况下进行适当修改/其实，这种转换还只是模糊转换，其中仍然包含大量不必要操作，模糊在，M、T向0的变换过程，并非以1为阶梯，有很多大于1，/其实，只需定义M*(M+1)的空间大小就可以实现上述转化过程，具体情况你先将ti排序，将i的变化从按ti再加一个T变化,j按ti变化运行下面的循环过程就可以发现。/转化后：，运行时间0.001sstatic int V2(int t, int v, int T, int M) int, V = new intT + 1, M + 1; for(int i=0; i=T; i+) for (int j = 0; j i) Vi, j = Vi, j - 1; continue;/第j株药材所需时间大于总时间，则计算前j-1株的最大价值 else /第j株药材所需时间小于等于总时间时，则判断是第j株药材是选择的价值更大还是不选择的价值更大 int v1, v2; v1 = Vi - tj - 1, j - 1 + vj - 1; /第j株药材选中后的最大价值 v2 = Vi, j - 1; /第j株药材未选中的最大价值 Vi, j = v1 v2 ? v1 : v2; /返回较大的那个 continue; return VT, M; static void Main(string args) int T, M; T = 215; M = 98; int tv = 42, 1, 182, 22, 61, 44, 98, 26, 139, 39, 140, 83, 112, 36, 159, 2, 58, 8, 172, 22, 37, 91, 57, 9, 24, 15, 49, 100, 25, 58, 25, 58, 149, 76, 67, 15, 31, 56, 166, 40, 133, 17, 84, 97, 173, 73, 146, 53, 1, 37, 47, 81, 54, 20, 23, 31, 83, 76, 40, 85, 34, 52, 4, 3, 57, 65, 5, 46, 153, 83, 88, 69, 109, 36, 173, 75, 136, 98, 60, 90, 33, 96, 110, 42, 133, 19, 188, 90, 211, 6, 62, 76, 65, 88, 210, 66, 80, 67, 173, 67, 122, 13, 47, 58, 78, 2, 200, 47, 50, 49, 15, 8, 149, 96, 5, 26, 104, 41, 105, 88, 96, 67, 158, 46, 43, 16, 83, 22, 97, 32, 30, 7, 66, 25, 77, 75, 98, 73, 192, 7, 143, 65, 191, 28, 78, 27, 47, 64, 51, 34, 162, 89, 118, 9, 214, 49, 20, 61, 201, 67, 126, 91, 185, 29, 205, 5, 109, 43, 11, 87, 159, 95, 168, 46, 149, 57, 76, 28, 61, 93, 192, 83, 175, 46, 59, 62, 109, 45, 143, 40, 6, 26, 183, 92, 24, 11 ; int t = new intM; /耗时 int v = new intM; /价值 for (int i = 0; i M; i+) /获取每株药材的信息 ti = tv2 * i; vi = tv2 * i + 1; Console.WriteLine(V2(t, v, T, M); Console.ReadLine(); /cout V2(t, v, T, M) endl; /输出最大价值 /C+/C语言：/在CSDN中的解答：#include #include #include using namespace std;/问题的递归解答，运行时间3.765sint V(int * &t, int * &v, int T, int M) if (M = 0 | T = 0) return 0; /若药材总数、或总时间等于0，则最大价值为0 if (tM - 1 T) return V(t, v, T, M - 1); /第M株药材所需时间大于总时间，则计算前M-1株的最大价值 else /第M株药材所需时间小于等于总时间时，则判断是第M株药材是选择的价值更大还是不选择的价值更大 int v1, v2; v1 = V(t, v, T - tM - 1, M - 1) + vM - 1; /第M株药材选中后的最大价值 v2 = V(t, v, T, M - 1); /第M株药材未选中的最大价值 return v1 v2 ? v1 : v2; /返回较大的那个 / 递归到循环的转化/ 由于函数的递归调用效率很低，我们对递归过程进行逆向操作，/ 可转化成循环过程如下：/1.观察递归调用过程的参数变化规律，我们可以发现，四个参数中仅有两个T和M是变化的；/2.变化规律为单向向0变化,变化梯度不定，我们取1可包含所有梯度，当变化的两个参数中的一项为零时返回结果为0，最大可以有T*M种变化；/3.我们定义VT+1M+1大小的空间来保存各种可能递归变化结果；因为是逆向操作，所以先将(M = 0 | T = 0)的结果也算在内为T+1M+1；/4.下面开始逆向转换，将递归函数中的函数体部分(除3步骤的操作内容外）/ 1)所有T替换为i, 所有M替换为j,所有return * 替换为Vij = *; continue; ,(有return的地方不进入下一个分支)/ 所有的子递归调用部分全部替换为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)最后输出逆操作的结果VT,M, 最后可在不改变算法执行语义的情况下进行适当修改/其实，这种转换还只是模糊转换，其中仍然包含大量不必要操作，模糊在，M、T向0的变换过程，并非以1为阶梯，有很多大于1，/其实，只需定义M*(M+1)的空间大小就可以实现上述转化过程，具体情况你先将ti排序，将i的变化从按ti再加一个T变化,j按ti变化运行下面的循环过程就可以发现。/转化后：，运行时间0.001sint MaxValue(int * &t, int * &v, int T, int M) /根据需要分配一个T+1M+1的数组 int * * V = new int * T+1; for(int j=0; j=T; j+) Vj = new int M+1; for(int i=0; i=T; i+) for(int j=0; ji) Vij = Vij-1; continue; else int v1, v2; v1 = V i-tj-1j-1+