Рекурсия: Найти произведение элементов массива, кроме тех, чей индекс кратен А.

@JohnBlack123 · Регистрация: 09.12.2017

Author24 — интернет-сервис помощи студентам

Здравствуйте!
Вот задача:
Дан одномерный массив целых чисел и целое число A.
Найти произведение элементов массива, кроме тех, чей индекс кратен А.
Нужно решить это рекурсивной функцией.

Я попробовал сделать это так, но выхожу за границы массива:

C++
1
2
3
4
5
6
7
8
9
10
11
12
int ProductOfNotEvenElementsByIndex(int n, int *Array, int a) 
{
    if (n == 1) 
        return Array[n];
 
    if (n%a != 0) {
        return ProductOfNotEvenElementsByIndex(n - 1, Array, a) * Array[n]; // вот тут, так как нет элемента Array[n]
    }
 
    return ProductOfNotEvenElementsByIndex(n - 1, Array, a);
    
}

Мои попытки исправить ситуацию были неудачны.

Не подскажите, как же сделать эту задачу ?

@valen10 · 24.01.2019, 14:50

Передавать не количество элементов в массиве n, а текущий индекс i. Граничное условие i == 0

C++
1
2
3
4
5
6
7
8
9
10
11
int ProductOfNotEvenElementsByIndex(int i, int *Array, int a)
{
    if (i == 0)
        return 1; // 0 кратен любому числу.
 
    if (i%a != 0) {
        return ProductOfNotEvenElementsByIndex(i - 1, Array, a) * Array[i];
    }
 
    return ProductOfNotEvenElementsByIndex(i - 1, Array, a);
}

@JohnBlack123 · 24.01.2019, 15:05 **[ТС]**

valen10, спасибо!
Но программа все же дает не правильный результат.

Code
1
2
3
n : 5
Array : 20 8 13 19 7
a : 2

Тут она должна вывести 8*19=256 (ведь их индексы не кратны а)
Программа выдает следующее : 20*13*7=3040

Я вызываю функцию со следующими параметрами :

Code
1
cout << " " << ProductOfNotEvenElementsByIndex(n-1, Array, a) << endl;

последний индекс - это n-1

Подскажите, пожалуйста, что здесь не верно?

@valen10 · 24.01.2019, 15:36

Сообщение от JohnBlack123

должна вывести 8*19=256

Программируете вы так же, как и считаете? $https://www.cyberforum.ru/cgi-bin/latex.cgi?8 \cdot 19 = 152$

Рекурсия: Найти произведение элементов массива, кроме тех, чей индекс кратен А.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int ProductOfNotEvenElementsByIndex(int i, int *Array, int a)
{
    if (i == 0)
        return 1; // 0 кратен любому числу.
 
    if (i%a != 0) {
        return ProductOfNotEvenElementsByIndex(i - 1, Array, a) * Array[i];
    }
 
    return ProductOfNotEvenElementsByIndex(i - 1, Array, a);
}
 
int main() {
    int arr[] = {20, 8, 13, 19, 7};
    int a = 2;
    cout << ProductOfNotEvenElementsByIndex(sizeof(arr)/sizeof(arr[0]) - 1, arr, a) << endl;
    return 0;
}

@valen10 · 24.01.2019, 15:45

Сейчас внимательно посмотрел, ваш вариант был абсолютно такой же, за исключением граничного индекса. Ищите ошибку в другой части кода.

@JohnBlack123 · 24.01.2019, 21:29 **[ТС]**

Здравствуйте, valen10, в том случае я ошибся.
Попробуйте запустить Ваш код со следующими параметрами :

Code
1
2
3
n : 5;
Array : { 20, 8, 13, 19, 7 };
a : 3;

Нужно найти произведение всех индексов не кратных a (3).

Code
1
20*8*13*7 = 14560

Программа же из-за этой строки

Сообщение от valen10

if (i == 0) return 1;

не заметит 20 (она заменит его на 1) и результат будет другим:

Code
1
1*8*13*7 = 728

У меня есть идея несколько изменить эту часть кода :

C++
1
2
3
4
if (i == 0 && a < 2)
    return 1; 
else if (i == 0)
    return Array[i];

Как считаете, это хорошее решение или можно лучше? Если можно, то как?
Спасибо!

Добавлено через 17 минут

Сообщение от valen10

Программируете вы так же, как и считаете?

Ну зачем Вы так? Всем свойственно ошибаться !

@valen10 · 24.01.2019, 21:32

Сообщение от JohnBlack123

У меня есть идея несколько изменить эту часть кода

Не понял, зачем это. 0 и так меньше 2. Вопрос только в том, считаете ли вы индекс 0 кратным другим числам? С точки зрения математики при делении нуля на ненулевое число в остатке всегда будет ноль, т.е. ноль кратен любому числу. Приведите нормальный пример входных данных и опишите результат, который необходимо получить.

Добавлено через 1 минуту

Сообщение от JohnBlack123

Ну зачем Вы так? Всем свойственно ошибаться

Погорячился. Прошу прощения.

@JohnBlack123 · 24.01.2019, 22:01 **[ТС]**

Сообщение от valen10

Не понял, зачем это.

Допустим, мы имеем массив {2, 3, 4, 5, 6, 7, 8}. Нужно найти произведение элементов, индексы которых кратны A. Рассмотрим под А значение 3.

Сообщение от valen10

if (i == 0) return 1;

Эта часть кода нам сообщает, что при достижении нулевого индекса вернуть 1. Но по сути, это значит, что теперь вместо этого элемента в умножении будет участвовать 1. Т.е.:
Дано :

Code
1
2
Array : {2, 3, 4, 5, 6, 7, 8};
a : 3;

Подсчеты :
Не кратные 3-м тут следующие элементы :
[0] = 2, [1] = 3, [2] = 4,
[4] = 6, [5] = 7,
их и будем перемножать.
Казалось бы, все просто, сейчас все эти элементы перемножаться и мы получим верный результат.
Но, вместо этого

Code
1
2*3*4*6*7 = 1008,

У нас выйдет следующее :

Code
1
1 * 3*4*6*7 = 504.

Поскольку при достижении нулевого индекса мы возвращаем именно единицу.

Следующие две строчки решают эту проблему (вроде бы). Так как возвращать единицу надо, только когда а = 2 (ну и собственно 1), чтобы не умножить лишний нулевой элемент на остальные не кратные 2.
В остальном случае (мы убедились в этом на примере с тройкой) нужно проверить является ли индекс нулевым и вернуть этот элемент (домножить на следующие).

C++
1
2
3
4
5
if (i == 0 && a < 2)
    return 1; 
else if (i == 0)
    return Array[i];
// дальше ничего не менялось, тот же код остался :)

Сообщение от valen10

Приведите нормальный пример входных данных и опишите результат, который необходимо получить.

Примеры :
1. { 3 4 12 7 0 4 -1}, a=2,
4*7*4 = 112;
2. { 20 -3 1 3 5 6 8 }, a=3,
20*(-3)*1*5*6 = -1800;
3. { 1 4 2 6 9 2 -1 3 5 6 }, a=4,
1*4*2*6*2*(-1)*3*6 = -1728.

Благодарю за помощь!

@valen10 · 24.01.2019, 22:10

JohnBlack123, что-то я совсем запутался

Почему i=0 кратен 2, но не кратен 3 и 4? Вся проблема в этом.

@JohnBlack123 · 24.01.2019, 22:36 **[ТС]**

valen10, простите, что запутал Вас! Т.к. 0 кратен любому числу, Ваше решение абсолютно правильно! Большое спасибо за время, потраченное на помощь мне!

Новые блоги и статьи Все статьи Все блоги /
Очередные открытия мега простых чисел, сделанные добровольцами с помощью домашних компьютеров Programma_Boinc 21.04.2025 Очередные открытия мега простых чисел, сделанные добровольцами с помощью домашних компьютеров. 3 марта 2025 года, в результате обобщенного поиска простых чисел Ферма в PrimeGrid был найден. . .	Система статов в Unity GameUnited 20.04.2025 Статы — фундаментальный элемент игрового дизайна, который определяет характеристики персонажей, предметов и других объектов в игровом мире. Будь то показатель силы в RPG, скорость передвижения в. . .	Статические свойства и методы в TypeScript run.dev 20.04.2025 TypeScript прочно занял своё место в системе современной веб-разработки. Этот строго типизированный язык программирования не просто расширяет возможности JavaScript — он делает разработку более. . .	Batch Transform и Batch Gizmo Drawing API в Unity GameUnited 20.04.2025 В мире разработки игр и приложений на Unity производительность всегда была критическим фактором успеха. Создатели игр постоянно балансируют между визуальной привлекательностью и плавностью работы. . .	Звук в Unity: Рандомизация с Audio Random Container GameUnited 20.04.2025 В современных играх звуковое оформление часто становится элементом, который либо полностью погружает игрока в виртуальный мир, либо разрушает атмосферу за считанные минуты. Представьте: вы исследуете. . .
Максимальная производительность C#: Советы, тестирование и заключение stackOverflow 20.04.2025 Погружение в мир микрооптимизаций C# открывает перед разработчиком целый арсенал мощных техник. Но как определить, где и когда их применять? Ответ начинается с точных измерений и профилирования. . . .	Максимальная производительность C#: Предсказание ветвлений stackOverflow 20.04.2025 Третий ключевой аспект низкоуровневой оптимизации — предсказание ветвлений. Эта тема менее известна среди разработчиков, но её влияние на производительность может быть колоссальным. Чтобы понять. . .	Максимальная производительность C#: Векторизация (SIMD) stackOverflow 20.04.2025 Помимо работы с кэшем, другим ключевым аспектом низкоуровневой оптимизации является векторизация вычислений. SIMD (Single Instruction, Multiple Data) позволяет обрабатывать несколько элементов данных. . .	Максимальная производительность C#: Процессорный кэш stackOverflow 20.04.2025 Знакомство с внутренним устройством процессорного кэша — ключевой шаг в написании по-настоящему быстрого кода на C#. Этот слой архитектуры компьютера часто ускользает от внимания разработчиков, но. . .	Максимальная производительность C#: Введение в микрооптимизации stackOverflow 20.04.2025 В мире разработки на C# многие привыкли полагаться на . NET Runtime, который "магическим образом" сам оптимизирует код. И часто это работает - современные JIT-компиляторы творят чудеса. Но когда речь. . .

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	24.01.2019, 15:45
	Сейчас внимательно посмотрел, ваш вариант был абсолютно такой же, за исключением граничного индекса. Ищите ошибку в другой части кода. 0

@valen10 Параллельный Кот 1905 / 827 / 350 Регистрация: 25.03.2016 Сообщений: 2,045
	24.01.2019, 22:10
	JohnBlack123, что-то я совсем запутался Почему i=0 кратен 2, но не кратен 3 и 4? Вся проблема в этом. 0

@JohnBlack123 215 / 162 / 52 Регистрация: 09.12.2017 Сообщений: 520
	24.01.2019, 22:36 [ТС]
	valen10, простите, что запутал Вас! Т.к. 0 кратен любому числу, Ваше решение абсолютно правильно! Большое спасибо за время, потраченное на помощь мне! 0

Рекурсия: Найти произведение элементов массива, кроме тех, чей индекс кратен А.

Решение