[已解决]关于欧拉计划第十八问

自由深渊

从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为23.



也就是 3 + 7 + 4 + 9 = 23.

找出从以下三角形的顶端走到底端的最大总和：



提示：以上图中共有16384条路径，所以你可以用穷举法。但是第67题是同样的题目，但是拥有100层。此时你不能再靠蛮力，你需要一个更便捷的方法。

求大神教育一波，怎么用C语言解决这个问题，我的想法是用递归一个个列举出来，但是不知道究竟怎么实现，想了两天了，没解决

最佳答案

月排行榜 / 总排行榜

fc1735

2017-3-14 23:23:11

定义一个全局变量min用来存放最小值，初始化为0
void 递归函数(int i,int j,int sum) //用二维数组存放数据，以i j决定位置
{
判断i是否到底，若到底了，判断当min==0或min>sum,则让min=sum
调用自己(i+1,j,sum+a[i][j]);
调用自己(i+1,j+1,sum+a[i][j]);

}
int main()
{
int a[][]; //存放数据

调用递归函数(0,0,a[0][0]);
printf("%d",min)


}

思路大概这样，先来去睡了，如果没有解决到你的问题请见谅

跳转到最佳答案楼层

fc1735

用递归的话几行就解决了，但效率比较低，因为把所有可能都跑过，复杂度是O(2^n)
好一点的算法是，因为每往下一层都可以找出走到目前这个位置的最小和，复杂度是O(n^2)

自由深渊

fc1735 发表于 2017-3-14 22:37
用递归的话几行就解决了，但效率比较低，因为把所有可能都跑过，复杂度是O(2^n)
好一点的算法是，因为每往 ...

关键是我递归就是不会呀递归学得不好，老甲鱼又不更新作业，只能找题练习一下

fc1735

定义一个全局变量min用来存放最小值，初始化为0
void 递归函数(int i,int j,int sum) //用二维数组存放数据，以i j决定位置
{
判断i是否到底，若到底了，判断当min==0或min>sum,则让min=sum
调用自己(i+1,j,sum+a[i][j]);
调用自己(i+1,j+1,sum+a[i][j]);

}
int main()
{
int a[][]; //存放数据

调用递归函数(0,0,a[0][0]);
printf("%d",min)


}

思路大概这样，先来去睡了，如果没有解决到你的问题请见谅

0mrli0

计算没一行时 先比较在加 要比 先加在比较的方法效率高一点   

自由深渊

fc1735 发表于 2017-3-14 23:23
定义一个全局变量min用来存放最小值，初始化为0
void 递归函数(int i,int j,int sum) //用二维数组存放数 ...

额，不好意思，不知道是不是我理解能力有点问题，能不能写的清晰一点，没有看懂

人造人

自由深渊 发表于 2017-3-15 11:19
额，不好意思，不知道是不是我理解能力有点问题，能不能写的清晰一点，没有看懂

100层时就不能用递归了
现在最高支持到24层^_^

很多地方都没有注释，希望你能看懂^_^



源.c

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include <string.h>
   
4. #include "Tree.h"
   
5. 
   
6. #define LAYER 24  // 24层是最大了 ^_^
   
7. #define ITEM 9999999
   
8. 
   
9. int tmp[LAYER + 1];
   
10. unsigned long n = 0;
    
11. 
    
12. static void set_array(Tree **T, int(*((*path)[ITEM]))[LAYER + 1], int c)
    
13. {
    
14.         if((*T)->lchild == NULL)
    
15.         {
    
16.                 tmp[c++] = (*T)->data;
    
17.                 c = 1;
    
18. 
    
19.                 (*path)[n++] = malloc(sizeof(int) * (LAYER + 1)); // 数组第0个元素存储总和
    
20.                 (*path)[n] = NULL;
    
21.                 memcpy(*(*path)[n - 1], tmp, (LAYER + 1) * sizeof(int));
    
22.                 return;
    
23.         }
    
24. 
    
25.         tmp[c++] = (*T)->data;
    
26.         set_array(&(*T)->lchild, path, c);
    
27.         set_array(&(*T)->rchild, path, c);
    
28. }
    
29. 
    
30. static unsigned long get_item(int(*((*path)[ITEM]))[LAYER + 1])
    
31. {
    
32.         unsigned long ret = 0;
    
33.         unsigned long c = 0;
    
34. 
    
35.         while((*path)[c] != NULL)
    
36.         {
    
37.                 c++;
    
38.                 ret++;
    
39.         }
    
40. 
    
41.         return ret;
    
42. }
    
43. 
    
44. static void free_array(int(*((*path)[ITEM]))[LAYER + 1])
    
45. {
    
46.         for(unsigned long i = 0; i < ITEM; i++)
    
47.         {
    
48.                 if((*path)[i] == NULL)
    
49.                 {
    
50.                         break;
    
51.                 }
    
52. 
    
53.                 free((*path)[i]);
    
54.         }
    
55. }
    
56. 
    
57. int euler(Tree **T, int (**ret_path)[LAYER + 1])
    
58. {
    
59.         int(*((*path)[ITEM]))[LAYER + 1];
    
60.         path = malloc(sizeof(int) * ITEM);
    
61. 
    
62.         set_array(T, path, 1); // 数组第0个元素存储总和
    
63. 
    
64.         // 计算每条路径的和
    
65.         unsigned long item = get_item(path);
    
66.         for(unsigned long i = 0; i < item; i++)
    
67.         {
    
68.                 (*(*path)[i])[0] = 0;
    
69.                 for(int j = 1; j <= LAYER; j++)
    
70.                 {
    
71.                         (*(*path)[i])[0] += (*(*path)[i])[j];
    
72.                 }
    
73.         }
    
74. 
    
75.         // 查找最大
    
76.         int max = (*(*path)[0])[0];
    
77.         int index = 0;
    
78.         for(unsigned long i = 0; i < item; i++)
    
79.         {
    
80.                 if(max < (*(*path)[i])[0])
    
81.                 {
    
82.                         index = i;
    
83.                         max = (*(*path)[i])[0];
    
84.                 }
    
85.         }
    
86. 
    
87. 
    
88.         memcpy(*ret_path, (*path)[index], sizeof(int) * (LAYER + 1));
    
89.         free_array(path);
    
90.         free(path);
    
91. 
    
92.         return max;
    
93. }
    
94. 
    
95. int main(void)
    
96. {
    
97.         int(*ret_path)[LAYER + 1] = malloc(sizeof(int) * (LAYER + 1));
    
98. 
    
99.         Tree *T;
    
100.         InitTree(&T);
     
101.         CreateTree(&T, LAYER);
     
102.         PrintTree(&T);
     
103.         putchar('\n');
     
104. 
     
105.         printf("最大和是：%d\n", euler(&T, &ret_path));
     
106. 
     
107.         printf("输出路径：\n");
     
108.         for(int i = 1; i <= LAYER; i++)
     
109.         {
     
110.                 printf("%.3d -> ", (*ret_path)[i]);
     
111.         }
     
112. 
     
113.         // 退掉最后一个箭头
     
114.         printf("\b\b\b\b");
     
115.         printf("    ");
     
116. 
     
117.         putchar('\n');
     
118. 
     
119.         free(ret_path);
     
120.         DestroyTree(&T);
     
121. 
     
122.         return 0;
     
123. }
     

复制代码

Tree.c

1. #include "Tree.h"
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. #include <math.h>
   
5. #include <time.h>
   
6. 
   
7. static int get_rand()
   
8. {
   
9.         return 1 + (int)(999.0*rand() / (RAND_MAX + 0.0));
   
10. }
    
11. 
    
12. void InitTree(Tree **T)
    
13. {
    
14.         (*T) = malloc(sizeof(Tree));
    
15.         (*T)->data = get_rand();
    
16.         (*T)->lchild = NULL;
    
17.         (*T)->rchild = NULL;
    
18.         (*T)->degree = NULL;
    
19. 
    
20. 
    
21.         srand((unsigned)time(NULL)); // 初始化一下随机数
    
22. }
    
23. 
    
24. 
    
25. static Tree *get_lchild(Tree **T)
    
26. {
    
27.         return (*T)->lchild->rchild;
    
28. }
    
29. 
    
30. static void set_left_degree(Tree **T, Tree *rchild)
    
31. {
    
32.         (*T)->lchild->degree = rchild;
    
33. }
    
34. 
    
35. static void create_left_child(Tree **T, int layer)
    
36. {
    
37.         if(layer == 1)
    
38.         {
    
39.                 return ;
    
40.         }
    
41. 
    
42.         (*T)->lchild = malloc(sizeof(Tree));
    
43.         (*T)->lchild->data = get_rand();
    
44.         (*T)->lchild->lchild = NULL;
    
45.         (*T)->lchild->rchild = NULL;
    
46.         (*T)->lchild->degree = NULL;
    
47.         create_left_child(&(*T)->lchild, layer - 1);
    
48. }
    
49. 
    
50. static void create_right_child2(Tree **T, int layer)
    
51. {
    
52.         if(layer == 1)
    
53.         {
    
54.                 return ;
    
55.         }
    
56. 
    
57.         (*T)->rchild = malloc(sizeof(Tree));
    
58.         (*T)->rchild->data = get_rand();
    
59.         (*T)->rchild->lchild = get_lchild(T);
    
60.         (*T)->rchild->rchild = NULL;
    
61.         (*T)->rchild->degree = NULL;
    
62.         set_left_degree(T, (*T)->rchild);
    
63.         create_right_child2(&(*T)->rchild, layer - 1);
    
64. }
    
65. 
    
66. static void create_right_child(Tree **T, int layer)
    
67. {
    
68.         if((*T)->lchild == NULL)
    
69.         {
    
70.                 return ;
    
71.         }
    
72. 
    
73.         create_right_child(&(*T)->lchild, layer - 1);
    
74. 
    
75.         create_right_child2(T, layer);
    
76. 
    
77. }
    
78. 
    
79. void CreateTree(Tree **T, int layer)
    
80. {
    
81.         create_left_child(T, layer);
    
82.         create_right_child(T, layer);
    
83. }
    
84. 
    
85. void DestroyTree(Tree **T)
    
86. {
    
87.         Tree *pp = *T;
    
88.         Tree *p = pp->lchild;
    
89.         Tree *tmp;
    
90. 
    
91.         while(p != NULL)
    
92.         {
    
93.                 p = pp->lchild;
    
94.                 while(pp != NULL)
    
95.                 {
    
96.                         tmp = pp;
    
97.                         pp = pp->degree;
    
98.                         free(tmp);
    
99.                 }
    
100. 
     
101.                 pp = p;
     
102.         }
     
103. 
     
104.         *T = NULL;
     
105. }
     
106. 
     
107. static void print_space(int max_degree, int i)
     
108. {
     
109.         int n = (max_degree * 4 / 2 - 2) - (i - 1) * 4 / 2;
     
110.         while(n--)
     
111.         {
     
112.                 printf(" ");
     
113.         }
     
114. }
     
115. 
     
116. static int get_degree(Tree **T)
     
117. {
     
118.         int ret = 0;
     
119.         Tree *p = *T;
     
120. 
     
121.         while(p != NULL)
     
122.         {
     
123.                 ret++;
     
124.                 p = p->degree;
     
125.         }
     
126. 
     
127.         return ret;
     
128. }
     
129. 
     
130. static int get_max_degree(Tree **T)
     
131. {
     
132.         int ret = 0;
     
133.         Tree *p = *T;
     
134. 
     
135. 
     
136.         while(p->lchild != NULL)
     
137.         {
     
138.                 p = p->lchild;
     
139.         }
     
140. 
     
141.         while(p != NULL)
     
142.         {
     
143.                 ret++;
     
144.                 p = p->degree;
     
145.         }
     
146. 
     
147.         return ret;
     
148. }
     
149. 
     
150. 
     
151. void PrintTree(Tree **T)
     
152. {
     
153.         Tree *p = *T;
     
154.         Tree *pp = p;
     
155.         int max_degree = get_max_degree(T);
     
156. 
     
157.         while(p != NULL)
     
158.         {
     
159.                 pp = p;
     
160.                 print_space(max_degree, get_degree(&p));
     
161.                 while(pp != NULL)
     
162.                 {
     
163.                         printf("%.3d ", pp->data);
     
164.                         pp = pp->degree;
     
165.                 }
     
166.                 putchar('\n');
     
167. 
     
168.                 p = p->lchild;
     
169.         }
     
170. }
     

复制代码

Tree.h

1. #ifndef _TREE_H
   
2. #define _TREE_H
   
3. 
   
4. #define OK 1
   
5. #define ERROR 0
   
6. #define TRUE 1
   
7. #define FALSE 0
   
8. 
   
9. //typedef int Status;        /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
   
10. typedef int ElemType;
    
11. 
    
12. typedef struct Tree
    
13. {
    
14.         ElemType data;
    
15.         struct Tree *lchild;
    
16.         struct Tree *rchild;
    
17.         struct Tree *degree;
    
18. } Tree;
    
19. 
    
20. void InitTree(Tree **T);
    
21. void CreateTree(Tree **T, int layer);
    
22. void PrintTree(Tree **T);
    
23. void DestroyTree(Tree **T);
    
24. 
    
25. #endif
    

复制代码

自由深渊

人造人 发表于 2017-3-18 16:39
100层时就不能用递归了
现在最高支持到24层^_^

感谢  

求道于盲

这种题目可以用动态规划完成

1. #include <stdio.h>
   
2. int main(int argc, char *argv[])
   
3. {
   
4.         int arr[15][15] = {
   
5.                 {3},
   
6.                 {7, 4},
   
7.                 {2, 4, 6},
   
8.                 {8, 5, 9, 3}
   
9.         };
   
10.         for(int i=1; i<4; ++i)
    
11.         {
    
12.                 for(int j=0; j<=i; ++j)
    
13.                 {
    
14.                         int left = 0;
    
15.                         if(j>0)
    
16.                                 left = arr[i-1][j-1];
    
17.                         int right = 0;
    
18.                         if(j<i)
    
19.                                 right = arr[i-1][j];
    
20.                         arr[i][j] += left > right ? left : right;
    
21.                 }
    
22.         }
    
23.         int nMax = arr[3][0];
    
24.         for(int i=1; i<4; ++i)
    
25.         {
    
26.                 nMax = nMax > arr[3][i] ? nMax : arr[3][i];
    
27.         }
    
28.         printf("%d\n", nMax);
    
29.         return 0;
    
30. }

复制代码

基础代码就是这样

求道于盲

复杂度是 O(n)