关于欧拉计划第十八问
从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为23.也就是 3 + 7 + 4 + 9 = 23.
找出从以下三角形的顶端走到底端的最大总和：
提示：以上图中共有16384条路径，所以你可以用穷举法。但是第67题是同样的题目，但是拥有100层。此时你不能再靠蛮力，你需要一个更便捷的方法。
求大神教育一波，怎么用C语言解决这个问题，我的想法是用递归一个个列举出来，但是不知道究竟怎么实现，想了两天了，没解决 用递归的话几行就解决了，但效率比较低，因为把所有可能都跑过，复杂度是O(2^n)
好一点的算法是，因为每往下一层都可以找出走到目前这个位置的最小和，复杂度是O(n^2) fc1735 发表于 2017-3-14 22:37
用递归的话几行就解决了，但效率比较低，因为把所有可能都跑过，复杂度是O(2^n)
好一点的算法是，因为每往 ...
关键是我递归就是不会呀{:10_282:}递归学得不好，老甲鱼又不更新作业，只能找题练习一下 定义一个全局变量min用来存放最小值，初始化为0
void 递归函数(int i,int j,int sum) //用二维数组存放数据，以i j决定位置
{
判断i是否到底，若到底了，判断当min==0或min>sum,则让min=sum
调用自己(i+1,j,sum+a);
调用自己(i+1,j+1,sum+a);
}
int main()
{
int a[][]; //存放数据
调用递归函数(0,0,a);
printf("%d",min)
}
思路大概这样，先来去睡了，如果没有解决到你的问题请见谅 计算没一行时 先比较在加 要比 先加在比较的方法效率高一点 fc1735 发表于 2017-3-14 23:23
定义一个全局变量min用来存放最小值，初始化为0
void 递归函数(int i,int j,int sum) //用二维数组存放数 ...
额，不好意思，不知道是不是我理解能力有点问题，能不能写的清晰一点，没有看懂 自由深渊 发表于 2017-3-15 11:19
额，不好意思，不知道是不是我理解能力有点问题，能不能写的清晰一点，没有看懂
100层时就不能用递归了
现在最高支持到24层^_^
很多地方都没有注释，希望你能看懂^_^
源.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Tree.h"
#define LAYER 24// 24层是最大了 ^_^
#define ITEM 9999999
int tmp;
unsigned long n = 0;
static void set_array(Tree **T, int(*((*path))), int c)
{
if((*T)->lchild == NULL)
{
tmp = (*T)->data;
c = 1;
(*path) = malloc(sizeof(int) * (LAYER + 1)); // 数组第0个元素存储总和
(*path) = NULL;
memcpy(*(*path), tmp, (LAYER + 1) * sizeof(int));
return;
}
tmp = (*T)->data;
set_array(&(*T)->lchild, path, c);
set_array(&(*T)->rchild, path, c);
}
static unsigned long get_item(int(*((*path))))
{
unsigned long ret = 0;
unsigned long c = 0;
while((*path) != NULL)
{
c++;
ret++;
}
return ret;
}
static void free_array(int(*((*path))))
{
for(unsigned long i = 0; i < ITEM; i++)
{
if((*path) == NULL)
{
break;
}
free((*path));
}
}
int euler(Tree **T, int (**ret_path))
{
int(*((*path)));
path = malloc(sizeof(int) * ITEM);
set_array(T, path, 1); // 数组第0个元素存储总和
// 计算每条路径的和
unsigned long item = get_item(path);
for(unsigned long i = 0; i < item; i++)
{
(*(*path)) = 0;
for(int j = 1; j <= LAYER; j++)
{
(*(*path)) += (*(*path));
}
}
// 查找最大
int max = (*(*path));
int index = 0;
for(unsigned long i = 0; i < item; i++)
{
if(max < (*(*path)))
{
index = i;
max = (*(*path));
}
}
memcpy(*ret_path, (*path), sizeof(int) * (LAYER + 1));
free_array(path);
free(path);
return max;
}
int main(void)
{
int(*ret_path) = malloc(sizeof(int) * (LAYER + 1));
Tree *T;
InitTree(&T);
CreateTree(&T, LAYER);
PrintTree(&T);
putchar('\n');
printf("最大和是：%d\n", euler(&T, &ret_path));
printf("输出路径：\n");
for(int i = 1; i <= LAYER; i++)
{
printf("%.3d -> ", (*ret_path));
}
// 退掉最后一个箭头
printf("\b\b\b\b");
printf(" ");
putchar('\n');
free(ret_path);
DestroyTree(&T);
return 0;
}
Tree.c
#include "Tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
static int get_rand()
{
return 1 + (int)(999.0*rand() / (RAND_MAX + 0.0));
}
void InitTree(Tree **T)
{
(*T) = malloc(sizeof(Tree));
(*T)->data = get_rand();
(*T)->lchild = NULL;
(*T)->rchild = NULL;
(*T)->degree = NULL;
srand((unsigned)time(NULL)); // 初始化一下随机数
}
static Tree *get_lchild(Tree **T)
{
return (*T)->lchild->rchild;
}
static void set_left_degree(Tree **T, Tree *rchild)
{
(*T)->lchild->degree = rchild;
}
static void create_left_child(Tree **T, int layer)
{
if(layer == 1)
{
return ;
}
(*T)->lchild = malloc(sizeof(Tree));
(*T)->lchild->data = get_rand();
(*T)->lchild->lchild = NULL;
(*T)->lchild->rchild = NULL;
(*T)->lchild->degree = NULL;
create_left_child(&(*T)->lchild, layer - 1);
}
static void create_right_child2(Tree **T, int layer)
{
if(layer == 1)
{
return ;
}
(*T)->rchild = malloc(sizeof(Tree));
(*T)->rchild->data = get_rand();
(*T)->rchild->lchild = get_lchild(T);
(*T)->rchild->rchild = NULL;
(*T)->rchild->degree = NULL;
set_left_degree(T, (*T)->rchild);
create_right_child2(&(*T)->rchild, layer - 1);
}
static void create_right_child(Tree **T, int layer)
{
if((*T)->lchild == NULL)
{
return ;
}
create_right_child(&(*T)->lchild, layer - 1);
create_right_child2(T, layer);
}
void CreateTree(Tree **T, int layer)
{
create_left_child(T, layer);
create_right_child(T, layer);
}
void DestroyTree(Tree **T)
{
Tree *pp = *T;
Tree *p = pp->lchild;
Tree *tmp;
while(p != NULL)
{
p = pp->lchild;
while(pp != NULL)
{
tmp = pp;
pp = pp->degree;
free(tmp);
}
pp = p;
}
*T = NULL;
}
static void print_space(int max_degree, int i)
{
int n = (max_degree * 4 / 2 - 2) - (i - 1) * 4 / 2;
while(n--)
{
printf(" ");
}
}
static int get_degree(Tree **T)
{
int ret = 0;
Tree *p = *T;
while(p != NULL)
{
ret++;
p = p->degree;
}
return ret;
}
static int get_max_degree(Tree **T)
{
int ret = 0;
Tree *p = *T;
while(p->lchild != NULL)
{
p = p->lchild;
}
while(p != NULL)
{
ret++;
p = p->degree;
}
return ret;
}
void PrintTree(Tree **T)
{
Tree *p = *T;
Tree *pp = p;
int max_degree = get_max_degree(T);
while(p != NULL)
{
pp = p;
print_space(max_degree, get_degree(&p));
while(pp != NULL)
{
printf("%.3d ", pp->data);
pp = pp->degree;
}
putchar('\n');
p = p->lchild;
}
}
Tree.h
#ifndef _TREE_H
#define _TREE_H
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
//typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType;
typedef struct Tree
{
ElemType data;
struct Tree *lchild;
struct Tree *rchild;
struct Tree *degree;
} Tree;
void InitTree(Tree **T);
void CreateTree(Tree **T, int layer);
void PrintTree(Tree **T);
void DestroyTree(Tree **T);
#endif
人造人 发表于 2017-3-18 16:39
100层时就不能用递归了
现在最高支持到24层^_^
感谢{:10_250:} 这种题目可以用动态规划完成
#include <stdio.h>
int main(int argc, char *argv[])
{
int arr = {
{3},
{7, 4},
{2, 4, 6},
{8, 5, 9, 3}
};
for(int i=1; i<4; ++i)
{
for(int j=0; j<=i; ++j)
{
int left = 0;
if(j>0)
left = arr;
int right = 0;
if(j<i)
right = arr;
arr += left > right ? left : right;
}
}
int nMax = arr;
for(int i=1; i<4; ++i)
{
nMax = nMax > arr ? nMax : arr;
}
printf("%d\n", nMax);
return 0;
}
基础代码就是这样 复杂度是 O(n)
页:
[1]