c - 数组元素乘法的二叉树方法

Question

我正在尝试递归地进行乘法。我选择这种方法是因为它比 for 循环需要更少的迭代。初始数组为:

pop[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

为了简单起见，数组值只是索引。第一个玩家的输出，即 {pop[0],pop[1]} 应该是:

resul_array[0] = pop[2]*pop[4]*pop[6]*pop[8] = 2 * 4 * 6 * 8 = 384
resul_array[1] = 2 * 4 * 6 * 9 = 432
resul_array[2] = 2 * 4 * 7 * 8 = 448
resul_array[3] = 2 * 4 * 7 * 9 = 504
resul_array[4] = 2 * 5 * 6 * 8 = 480
resul_array[5] = 2 * 5 * 6 * 9 = 540

依此类推，直到

resul_array[15] = 3 * 5 * 7 * 9 = 945

我的问题是如何更新指针ptr来实现这种模式？

这是我的代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define NELEMS(x)  (sizeof(x) / sizeof((x)[0]))

int fun(int *ptr, int resul, int n, int pl) {
    int j, leaf;    
    ptr = ptr + 2;
    leaf = *ptr; //the elements of the tree

    printf("n=%d leaf=%d resul=%dstep=%d\n", n, leaf, resul, step);
    getchar();

    if (n == pl - 2) {
        printf("resul-final=%d\n", resul * leaf);
        return resul * leaf;
    }   
    for (j = 0; j < 2; j++) {
        resul = resul * leaf;
        n++;
        fun(ptr, resul, n, pl);     
        leaf = 1;
        ptr = ptr + 1;
        n--;
    }

    printf("Im here\n");
}

int main() {
    int pop[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; //5 players
    int resul = 1;  
    int pl = NELEMS(pop) / 2;
    int *ptr; //pointer that moves along the elements of pop
    ptr = pop;
    int *resul_array = calloc(pl, sizeof(int));

    for (i = 0; i < pl; i++) {
        resul_array[i] = fun(ptr, resul, 0, pl);
        printf("resul_array[%d]=%d\n", i, resul_array[i]);
    }
}

fun(.) 使用递归来遍历 pop 的元素。该函数使用指针“ptr”一次向前移动两个元素，直到达到返回条件，即 if(n==pl-2) 那么 ptr 应该移动仅向前移动一个元素。

我得到的结果很好，直到第三次迭代跳过 448 并给出 504。我知道这是因为指针 ptr 不按照上面提到的模式向前移动。请您帮忙解决这个问题。

我会尝试描绘这棵树:

              pl
       2                3 
   4       5       4       5   
 6   7   6   7   6   7   6   7 
8 9 8 9 8 9 8 9 8 9 8 9 8 9 8 9

Answer 1

我解决了!!!

所需时间不到暴力方法的四分之一

答案:leaf = ptr[n*2+j];

享受吧!