【递归】【递归的优化】

100 阅读 0 评论 66 点赞

我是靠谱客的博主从容康乃馨，这篇文章主要介绍【递归】【递归的优化】，现在分享给大家，希望可以做个参考。

递归算法在工作或者各种数据结构中使用比较频繁，递归算法的简化常见有自顶向下还有备忘录法

自顶向下：

复制代码

#T(N) = T1(N) + T2(N) + T3(N) + 25C
#T1(N) = [(R11P1 + R12P2 + R13P3 + R14P4 + R15P5 + R16P6 + R17P7 + R18P8 + R19P9) - T1(N-1)] x Tau1 + T1(N-1)
#T2(N) = [(R21P1 + R22P2 + R23P3 + R24P4 + R25P5 + R26P6 + R27P7 + R28P8 + R29P9) - T2(N-1)] x Tau2 + T2(N-1)
#T3(N) = [(R31P1 + R32P2 + R33P3 + R34P4 + R35P5 + R36P6 + R37P7 + R38P8 + R39P9) - T3(N-1)] x Tau3 + T3(N-1)
#T1(0) = T2(0) = T3(0) = 0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include <sys/time.h>
#define N	10000
signed int arry_p[] = {P1,P2,P3,P4,P5,P6,P7,P8,P9};
float arry_prometheus_R1[] = {R1,R2,R3,R4,R5,R6,R7,R8,R9};
float prometheus_tau1 = tau1;
float cal_t1n(int n)
{
if(n==0){
return 0;
}
int i = 0;
float arithmetic = 0.0;
float t1n = 0.0;
for(i=0;i<sizeof(arry_p)/sizeof(arry_p[0]);i++){
arithmetic += (arry_p[i]*arry_prometheus_R1[i]);
if(arry_p[i]==1){
break;
}
}
// 首先是简化递归公式
// 其次使用自顶向下比自底向下的效率要高很多
t1n = arithmetic*prometheus_tau1+(1-prometheus_tau1)*cal_t1n(n-1);
return t1n;
}
int main()
{
clock_t c_start, c_end;
c_start = clock();
float ret = 0.0;
double space_time;
int i = 0;
struct timeval start, end;
float timeuse = 0.0;
gettimeofday(&start, NULL);
for (i=0; i<100; i++){
ret = cal_t1n(N);
}
gettimeofday(&end, NULL);
timeuse = (1000000 * ( end.tv_sec - start.tv_sec ) + end.tv_usec - start.tv_usec)/1000.0;
printf("time_use is %.2fmsn", timeuse);
printf("t1n is %.3fn", ret);
return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#T(N) = T1(N) + T2(N) + T3(N) + 25C
#T1(N) = [(R11P1 + R12P2 + R13P3 + R14P4 + R15P5 + R16P6 + R17P7 + R18P8 + R19P9) - T1(N-1)] x Tau1 + T1(N-1)
#T2(N) = [(R21P1 + R22P2 + R23P3 + R24P4 + R25P5 + R26P6 + R27P7 + R28P8 + R29P9) - T2(N-1)] x Tau2 + T2(N-1)
#T3(N) = [(R31P1 + R32P2 + R33P3 + R34P4 + R35P5 + R36P6 + R37P7 + R38P8 + R39P9) - T3(N-1)] x Tau3 + T3(N-1)
#T1(0) = T2(0) = T3(0) = 0
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include <sys/time.h>
#define N	10000
signed int arry_p[] = {P1,P2,P3,P4,P5,P6,P7,P8,P9};
float arry_prometheus_R1[] = {R1,R2,R3,R4,R5,R6,R7,R8,R9};
float prometheus_tau1 = tau1;
float cal_t1n(int n)
{
if(n==0){
return 0;
}
int i = 0;
float arithmetic = 0.0;
float t1n = 0.0;
for(i=0;i<sizeof(arry_p)/sizeof(arry_p[0]);i++){
arithmetic += (arry_p[i]*arry_prometheus_R1[i]);
if(arry_p[i]==1){
break;
}
}
// 首先是简化递归公式
// 其次使用自顶向下比自底向下的效率要高很多
t1n = arithmetic*prometheus_tau1+(1-prometheus_tau1)*cal_t1n(n-1);
return t1n;
}
int main()
{
clock_t c_start, c_end;
c_start = clock();
float ret = 0.0;
double space_time;
int i = 0;
struct timeval start, end;
float timeuse = 0.0;
gettimeofday(&start, NULL);
for (i=0; i<100; i++){
ret = cal_t1n(N);
}
gettimeofday(&end, NULL);
timeuse = (1000000 * ( end.tv_sec - start.tv_sec ) + end.tv_usec - start.tv_usec)/1000.0;
printf("time_use is %.2fmsn", timeuse);
printf("t1n is %.3fn", ret);
return 0;
}