Форум » C/C++ для начинающих (C/C++ for beginners) » Рекурсивное вычисление суммы элементов массива, предшествующих заданному значению. » Ответить
Рекурсивное вычисление суммы элементов массива, предшествующих заданному значению.
Сыроежка: В программировании существует такой принцип под названием KISS - Keep It Simple Stupid, который можно перевести как Делай проще, тупица. Это означает, что написанный код должен быть логически ясным и простым для понимания. Однако, когда сталкиваешься с примерами кода даже порой профессиональных программистов или с тем, как программисты иногда рассуждают, воплощая свои мысли в коде, то возникает сомнение в том, а знают ли они вышеуказанный принцип и понимают ли его смысл. Написать эту тему меня побудил простой вопрос, очевидно, начинающего программиста на Stackoverflow: calculate sum of all elements before “x” element recursive Код, приведенный автором вопроса, естественно, является абсурдным. [pre2]#include <stdio.h> int SumBeforeX(int a[], int n, int x) { int i = 0; static int s = 0; if (n == 0) return 0; if (a == x) s+=SumBeforeX(a, i -1, x) +a[i-1]; return s; } void main() { int a[] = {2,6,13,17,47,8}; printf("%d",SumBeforeX(a,6,13)); _getch(); } [/pre2] Но удивляет не код этого начинающего программиста, а тот код, который приводится в ответах. Так, например, участник с ником @Felix Palmen, который, судя по его профилю на SO, является профессиональным программистом, предлагает такое решение [pre2]int sumBeforeX(const int *a, int x) { if (x == *a) return 0; // termination condition return *a + sumBeforeX(a+1, x); // recursive step }[/pre2] Начнем с того, что объявление функции по количеству параметров не соответствует объявлению этой функции в вопросе. Отсутствует параметр, который соответствует значению количества элементов в массиве. В результате функция будет иметь неопределенное поведение, если в массиве не имеется элемента со значением равным значению параметра с именем x. То есть функция имеет предусловие, что в массиве обязательно должен быть элемент со значением равным x. Но такого предусловия к функции в вопросе нет. Более того, чтобы воспользоваться этой функцией, необходимо иметь еще одну функцию, которая будет проверять, имеется ли в заданном массиве элемент со значением равным x. А что делать, если такого элемента нет? Ответ на этот вопрос в написанном @Felix Palmen ответе нет. Я не могу назвать размышления, которыми руководствовался автор данного ответа, логически ясными и простыми для понимания. На мой взгляд, так как сумма элементов вычисляется последовательно, переходя от предшествующего элемента к последующему элементу массива, то если значение x до сих пор не найдено, то продолжаем процедуру суммирования, пока не будут исчерпаны все элементы массива или пока, наконец, не встретится элемент с заданным значением. Есть и некоторые технические замечания к предложенной реализации функции. Например, желательно, чтобы аккумулятор имел целочисленный тип с большим размером, чем тип int, так как при суммировании нескольких значений может возникнуть переполнение. Поэтому тип аккумулятора следует задать по крайней мере как long long int. Исходную задачу можно разбить на две задачи или функции. Первая функция ищет заданное значение в целочисленном массиве и возвращает индекс соответствующего элемента массива или размер массива в случае, если заданное значение не найдена. Вторая функция просто безусловно суммирует n элементов массива, где n - это количество элементов в массиве, предшествующих заданному значению, и которое возвратила первая функция. То есть исходную функцию, которую было бы правильно объявить следующим образом [pre2]long long int SumBeforeX( const int a[], size_t n, int value );[/pre2] Можно логически заменить на две другие функции [pre2]size_t find( const int a[], size_t n, int value ); long long int accumulate( const int a[], size_t n ); [/pre2] Их реализацию я представлю ниже в конце этой темы. Другой участник форума с ником @H.S. предложил такую реализацию функции [pre2]int SumBeforeX(const int *a, int n, int x, int sum) { if (n == 0) return 0; if (x == *a) return sum; return SumBeforeX(a + 1, n - 1, x, sum + *a); }[/pre2] Здесь совершенно неуместно вводится дополнительный параметр int sum, который, например, при n равным 0 даже не используется. Опять-таки, имеем ситуацию, что если среди n элементов массива не найден элемент со значением x, то будет возвращен 0. Но исходная задача - не определить, существует ли элемент в массиве с заданным значением, а вычислить сумму всех элементов до наступления заданного условия или пока все элементы массива не будут перебраны. Можно, конечно объявить эту функцию с дополнительным параметром, который будет задавать начальное значение суммы, то есть сумма будет вычисляться, начиная не с 0, а с некоторого уже заданного значения. Но такая функция не должна игнорировать это значение даже, если n равно 0. В исходном вопросе не было указания на необходимость задания такого начального значения, а потому данную реализацию функции также нельзя назвать адекватной. Более того, для количества элементов в массиве следует указывать тип size_t, а не int, так как объект типа int может быть не в состоянии хранить значение размера массива в виду того, что размеры объектов в C определяются объектами типа size_t. Так как написать рекурсивную функцию, которая вычисляет суммы элементов массива, предшествующих заданному значению? Эта функция может выглядеть следующим образом. [pre2]long long int SumBeforeX( const int a[], size_t n, int value ) { return n == 0 || a[0] == value ? 0 : a[0] + SumBeforeX( a + 1, n - 1, value ); }[/pre2] Как я выше указал, исходную задачу и, соответственно, функцию можно логически разбить на две задачи, каждая из которых решается отдельной функцией. Первая функция ищет заданное значение в массиве и возвращает индекс элемента, равного заданному значению, или "индекс" элемента за последним элементом в массиве, если значение в массиве не найдено. А вторая функция просто безусловно вычисляет сумму указанного числа элементов в массиве. Вот как такие функции в свою очередь могут быть реализованы с помощью рекурсии. [pre2]size_t find( const int a[], size_t n, int value ) { return n == 0 || a[0] == value ? 0 : 1 + find( a + 1, n - 1, value ); } long long int accumulate( const int a[], size_t n ) { return n == 0 ? 0 : a[0] + accumulate( a + 1, n - 1 ); } [/pre2] Ниже приведена демонстрационная программа, которая показывает работу исходной функции и работу заменяющих ее логически адекватных двух других функций. [pre2]#include <stdio.h> long long int SumBeforeX( const int a[], size_t n, int value ) { return n == 0 || a[0] == value ? 0 : a[0] + SumBeforeX( a + 1, n - 1, value ); } size_t find( const int a[], size_t n, int value ) { return n == 0 || a[0] == value ? 0 : 1 + find( a + 1, n - 1, value ); } long long int accumulate( const int a[], size_t n ) { return n == 0 ? 0 : a[0] + accumulate( a + 1, n - 1 ); } int main(void) { int a[] = { 2, 6, 13, 17, 47, 8 }; const int N = sizeof( a ) / sizeof( *a ); for ( size_t i = 0; i < N; i++ ) { int value = a; printf( "Before %d - %lld\n", value, SumBeforeX( a, N, value ) ); } putchar( '\n' ); for ( size_t i = 0; i < N; i++ ) { int value = a; printf( "Before %d - %lld\n", value, accumulate( a, find( a, N, value ) ) ); } putchar( '\n' ); return 0; } [/pre2] Вывод программы на консоль будет выглядеть следующим образом: [pre2]Before 2 - 0 Before 6 - 2 Before 13 - 8 Before 17 - 21 Before 47 - 38 Before 8 - 85 Before 2 - 0 Before 6 - 2 Before 13 - 8 Before 17 - 21 Before 47 - 38 Before 8 - 85[/pre2]
Ответов - 0
полная версия страницы