遞歸向循環(huán) 轉(zhuǎn)化.doc

遞歸向循環(huán) 轉(zhuǎn)化/*scimenceXX采藥題目詳情:描述 XX是個(gè)天資聰穎的孩子，他的夢想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。 * 醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對他說：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。 * 我會給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大”。 * 如果你是XX，你能完成這個(gè)任務(wù)嗎？輸入格式 多組數(shù)據(jù)，每行兩個(gè)整數(shù)，用空格隔開，第一行有兩個(gè)整數(shù)T（1 = T = 1000）和M（1 = M T) return V(t, v, T, M - 1); /第M株藥材所需時(shí)間大于總時(shí)間，則計(jì)算前M-1株的最大價(jià)值 else /第M株藥材所需時(shí)間小于等于總時(shí)間時(shí)，則判斷是第M株藥材是選擇的價(jià)值更大還是不選擇的價(jià)值更大 int v1, v2; v1 = V(t, v, T - tM - 1, M - 1) + vM - 1; /第M株藥材選中后的最大價(jià)值 v2 = V(t, v, T, M - 1); /第M株藥材未選中的最大價(jià)值 return v1 v2 ? v1 : v2; /返回較大的那個(gè) / 遞歸到循環(huán)的轉(zhuǎn)化/ 由于函數(shù)的遞歸調(diào)用效率很低，我們對遞歸過程進(jìn)行逆向操作，/ 可轉(zhuǎn)化成循環(huán)過程如下：/1.觀察遞歸調(diào)用過程的參數(shù)變化規(guī)律，我們可以發(fā)現(xiàn)，四個(gè)參數(shù)中僅有兩個(gè)T和M是變化的；/2.變化規(guī)律為單向向0變化,變化梯度不定，我們?nèi)?可包含所有梯度，當(dāng)變化的兩個(gè)參數(shù)中的一項(xiàng)為零時(shí)返回結(jié)果為0，最大可以有T*M種變化；/3.我們定義VT+1,M+1大小的空間來保存各種可能遞歸變化結(jié)果；因?yàn)槭悄嫦虿僮鳎韵葘?M = 0 | T = 0)的結(jié)果也算在內(nèi)為T+1,M+1；/4.下面開始逆向轉(zhuǎn)換，將遞歸函數(shù)中的函數(shù)體部分(除3步驟的操作內(nèi)容外）/ 1)所有T替換為i, 所有M替換為j,所有return * 替換為Vi,j = *; continue; ,(有return的地方不進(jìn)入下一個(gè)分支)/ 所有的子遞歸調(diào)用部分全部替換為V*, *保留其中的變化參數(shù)（代表T和M的變量，去除其中的不變參數(shù)t與v;/ 2)將兩個(gè)變化的參數(shù)替換為i,j的目的是為了讓i,j分別從0變化到T和M,實(shí)現(xiàn)逆向操作；/ 3)補(bǔ)全變化的語法，for(i=0; i=T; i+), for(j=0到M), i與j的嵌套變化順序隨意，但必須嵌套；/ 4)最后輸出逆操作的結(jié)果VT,M, 最后可在不改變算法執(zhí)行語義的情況下進(jìn)行適當(dāng)修改/其實(shí)，這種轉(zhuǎn)換還只是模糊轉(zhuǎn)換，其中仍然包含大量不必要操作，模糊在，M、T向0的變換過程，并非以1為階梯，有很多大于1，/其實(shí)，只需定義M*(M+1)的空間大小就可以實(shí)現(xiàn)上述轉(zhuǎn)化過程，具體情況你先將ti排序，將i的變化從按ti再加一個(gè)T變化,j按ti變化運(yùn)行下面的循環(huán)過程就可以發(fā)現(xiàn)。/轉(zhuǎn)化后：，運(yùn)行時(shí)間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株藥材所需時(shí)間大于總時(shí)間，則計(jì)算前j-1株的最大價(jià)值 else /第j株藥材所需時(shí)間小于等于總時(shí)間時(shí)，則判斷是第j株藥材是選擇的價(jià)值更大還是不選擇的價(jià)值更大 int v1, v2; v1 = Vi - tj - 1, j - 1 + vj - 1; /第j株藥材選中后的最大價(jià)值 v2 = Vi, j - 1; /第j株藥材未選中的最大價(jià)值 Vi, j = v1 v2 ? v1 : v2; /返回較大的那個(gè) 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; /耗時(shí) int v = new intM; /價(jià)值 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; /輸出最大價(jià)值 /C+/C語言：/在CSDN中的解答：#include #include #include using namespace std;/問題的遞歸解答，運(yùn)行時(shí)間3.765sint V(int * &t, int * &v, int T, int M) if (M = 0 | T = 0) return 0; /若藥材總數(shù)、或總時(shí)間等于0，則最大價(jià)值為0 if (tM - 1 T) return V(t, v, T, M - 1); /第M株藥材所需時(shí)間大于總時(shí)間，則計(jì)算前M-1株的最大價(jià)值 else /第M株藥材所需時(shí)間小于等于總時(shí)間時(shí)，則判斷是第M株藥材是選擇的價(jià)值更大還是不選擇的價(jià)值更大 int v1, v2; v1 = V(t, v, T - tM - 1, M - 1) + vM - 1; /第M株藥材選中后的最大價(jià)值 v2 = V(t, v, T, M - 1); /第M株藥材未選中的最大價(jià)值 return v1 v2 ? v1 : v2; /返回較大的那個(gè) / 遞歸到循環(huán)的轉(zhuǎn)化/ 由于函數(shù)的遞歸調(diào)用效率很低，我們對遞歸過程進(jìn)行逆向操作，/ 可轉(zhuǎn)化成循環(huán)過程如下：/1.觀察遞歸調(diào)用過程的參數(shù)變化規(guī)律，我們可以發(fā)現(xiàn)，四個(gè)參數(shù)中僅有兩個(gè)T和M是變化的；/2.變化規(guī)律為單向向0變化,變化梯度不定，我們?nèi)?可包含所有梯度，當(dāng)變化的兩個(gè)參數(shù)中的一項(xiàng)為零時(shí)返回結(jié)果為0，最大可以有T*M種變化；/3.我們定義VT+1M+1大小的空間來保存各種可能遞歸變化結(jié)果；因?yàn)槭悄嫦虿僮?，所以先?M = 0 | T = 0)的結(jié)果也算在內(nèi)為T+1M+1；/4.下面開始逆向轉(zhuǎn)換，將遞歸函數(shù)中的函數(shù)體部分(除3步驟的操作內(nèi)容外）/ 1)所有T替換為i, 所有M替換為j,所有return * 替換為Vij = *; continue; ,(有return的地方不進(jìn)入下一個(gè)分支)/ 所有的子遞歸調(diào)用部分全部替換為V*保留其中的變化參數(shù)（代表T和M的變量，去除其中的不變參數(shù)t與v;/ 2)將兩個(gè)變化的參數(shù)替換為i,j的目的是為了讓i,j分別從0變化到T和M,實(shí)現(xiàn)逆向操作；/ 3)補(bǔ)全變化的語法，for(i=0; i=T; i+), for(j=0到M), i與j的嵌套變化順序隨意，但必須嵌套；/ 4)最后輸出逆操作的結(jié)果VT,M, 最后可在不改變算法執(zhí)行語義的情況下進(jìn)行適當(dāng)修改/其實(shí)，這種轉(zhuǎn)換還只是模糊轉(zhuǎn)換，其中仍然包含大量不必要操作，模糊在，M、T向0的變換過程，并非以1為階梯，有很多大于1，/其實(shí)，只需定義M*(M+1)的空間大小就可以實(shí)現(xiàn)上述轉(zhuǎn)化過程，具體情況你先將ti排序，將i的變化從按ti再加一個(gè)T變化,j按ti變化運(yùn)行下面的循環(huán)過程就可以發(fā)現(xiàn)。/轉(zhuǎn)化后：，運(yùn)行時(shí)間0.001sint MaxValue(int * &t, int * &v, int T, int M) /根據(jù)需要分配一個(gè)T+1M+1的數(shù)組 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+