Потеря некоторых элементов массива при подсчёте рекурсивной функцией

Question

Было дано задание: для заданного одномерного массива B из N элементов найти количество элементов массива, для которых выполняется условие . В рекурсивной функции каждый раз делить рассматриваемую часть массива на две части: одну треть и две третьих, вычисляя количество с помощью этой же функции сначала в левой части (1/3), а затем и в правой части. Рекурсивные вызовы заканчивать, когда останется только один или два элемента в рассматриваемой части массива.

Написал код но в рекурсивной функции теряются некоторые элементы массива, а при больших значениях количества элементов в массиве нулевой элемент проверяется несколько раз. Не могу понять в чем ошибка, вроде бы делал всё по условию.

#include<stdio.h>
#include<conio.h>
#include<math.h>

double* createBytes(int* n) {
    printf("n = ");
    scanf("%d", n);

    double* b = malloc(sizeof(double) * *n);

    printf("b:\n");

    for (unsigned long i = 0; i < *n; ++i) {
        scanf("    %lf", &b[i]);
    }

    printf("n = %d\n", *n);
    printf("b:\n");

    for (unsigned long i = 0; i < n; ++i) {
        printf("    %lf\n", b[i]);
    }
}
void deleteBytes(double* bytes) {
    free(bytes);
}
long rec(double* b, long n, long i) {
    long _n = i + (n - i) / 3; // находим одну треть массива

    if (n - i == 1 || n - i == 2) // условие выхода из рекурсии
        return 0;
    else if (cos(pow(b[i], 2)) > 0 && b[i] > 0) // условие, по которому подсчитываем количество
        return rec(b, _n, i) + rec(B, n, _n) + 1;
    else
        return rec(b, _n, i) + rec(B, n, _n);
}

void main() {
    long n;
    double* b = createBytes(&n);
    long z = rec(b, n, 0);

    printf("z = %d", z);

    deleteBytes(b);
    getch();
}

Например если взять 6 элементов то функция не проверит 1,4,5 элементы

Answer 1

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

typedef char boolean;
typedef boolean __stdcall (*selector)(const double value);
typedef struct span {
    double* data;
    unsigned long len;
} span;

inline span slice(const span span, const unsigned long index, const unsigned long count) {
    struct span sliced = span;
    sliced.data += index;
    sliced.len = count;

    return sliced;
}
void __stdcall select(const span src, double* dest, unsigned long* selectedItems, const selector selector) {
    // checks

    if (src.len < 3) {
        for (register unsigned long i = 0; i < src.len; ++i)
            if (selector(src.data[i]))
                if (dest)
                    dest[(*selectedItems)++] = src.data[i];
                else
                    (*selectedItems)++;
    } else {
        const register unsigned long segLen = src.len / 3U;
        const register unsigned long seg2Start = segLen;
        const register unsigned long seg3Start = src.len - segLen; // результат измениться, если заменить на `segLen * 2`
        const span seg1 = slice(src, 0, segLen);
        const span seg2 = slice(src, seg2Start, segLen);
        const span seg3 = slice(src, seg3Start, segLen);

        select(seg1, dest, selectedItems, selector);
        select(seg2, dest, selectedItems, selector);
        select(seg3, dest, selectedItems, selector);
    }
}

#define SRC_LEN 100U
#define DEST_LEN 12U
#define EPSILON 1e-12

inline long dblcmp(const double a, const double b) {
    if (a > b + EPSILON)
        return 1;
    else if (a < b - EPSILON)
        return -1;
    else          // optional
        return 0; // optional
}
boolean __stdcall dblsel(const double value) {
    double _sqrt = sqrt(value);

    return dblcmp(_sqrt, (long)_sqrt) == 0; // нужно использовать нечёткое сравнение
}
int main() {
    double src[SRC_LEN];

    for (register unsigned long i = 0; i < SRC_LEN; ++i)
        src[i] = i + 1;

    double dest[DEST_LEN];
    unsigned long destLen = 0;
    span srcSpan;
    srcSpan.data = src;
    srcSpan.len = SRC_LEN;

    select(srcSpan, dest, &destLen, dblsel);

    for (register unsigned long i = 0; i < destLen; ++i)
        printf("%d ", (long)dest[i]);

    printf("\n");
}

БЛОГ НА HUSL

Потеря некоторых элементов массива при подсчёте рекурсивной функцией

Ответы (1 шт):