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

自由深渊

从下面的三角形的顶端开始，向下面一行的相邻数字移动，从顶端到底端的最大总和为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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Tree.h"

#define LAYER 24  // 24层是最大了 ^_^
#define ITEM 9999999

int tmp[LAYER + 1];
unsigned long n = 0;

static void set_array(Tree **T, int(*((*path)[ITEM]))[LAYER + 1], int c)
{
        if((*T)->lchild == NULL)
        {
                tmp[c++] = (*T)->data;
                c = 1;

                (*path)[n++] = malloc(sizeof(int) * (LAYER + 1)); // 数组第0个元素存储总和
                (*path)[n] = NULL;
                memcpy(*(*path)[n - 1], tmp, (LAYER + 1) * sizeof(int));
                return;
        }

        tmp[c++] = (*T)->data;
        set_array(&(*T)->lchild, path, c);
        set_array(&(*T)->rchild, path, c);
}

static unsigned long get_item(int(*((*path)[ITEM]))[LAYER + 1])
{
        unsigned long ret = 0;
        unsigned long c = 0;

        while((*path)[c] != NULL)
        {
                c++;
                ret++;
        }

        return ret;
}

static void free_array(int(*((*path)[ITEM]))[LAYER + 1])
{
        for(unsigned long i = 0; i < ITEM; i++)
        {
                if((*path)[i] == NULL)
                {
                        break;
                }

                free((*path)[i]);
        }
}

int euler(Tree **T, int (**ret_path)[LAYER + 1])
{
        int(*((*path)[ITEM]))[LAYER + 1];
        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)[i])[0] = 0;
                for(int j = 1; j <= LAYER; j++)
                {
                        (*(*path)[i])[0] += (*(*path)[i])[j];
                }
        }

        // 查找最大
        int max = (*(*path)[0])[0];
        int index = 0;
        for(unsigned long i = 0; i < item; i++)
        {
                if(max < (*(*path)[i])[0])
                {
                        index = i;
                        max = (*(*path)[i])[0];
                }
        }


        memcpy(*ret_path, (*path)[index], sizeof(int) * (LAYER + 1));
        free_array(path);
        free(path);

        return max;
}

int main(void)
{
        int(*ret_path)[LAYER + 1] = 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)[i]);
        }

        // 退掉最后一个箭头
        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层^_^

感谢  

求道于盲

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

#include <stdio.h>
int main(int argc, char *argv[])
{
        int arr[15][15] = {
                {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[i-1][j-1];
                        int right = 0;
                        if(j<i)
                                right = arr[i-1][j];
                        arr[i][j] += left > right ? left : right;
                }
        }
        int nMax = arr[3][0];
        for(int i=1; i<4; ++i)
        {
                nMax = nMax > arr[3][i] ? nMax : arr[3][i];
        }
        printf("%d\n", nMax);
        return 0;
}

基础代码就是这样

求道于盲

复杂度是 O(n)