0 / 0 / 0
Регистрация: 03.07.2018
Сообщений: 21
1

Не могу понять как написать каскадную рекурсию

02.03.2019, 23:09. Показов 2994. Ответов 3

Author24 — интернет-сервис помощи студентам
Для заданного одномерного массива A из N элементов найти значение минимального элемента массива и его номер. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.

В гугле ничего дельного не нашел.

Есть код для нахождения суммы, но как переделать на поиск минимального элемента не доходит.
C++
1
2
3
4
5
6
7
8
9
10
int Sum (int A[], int i1, int i2)
{
  int Result;
  if (i1==i2) Result = A[i1-1];
  else 
   { int center = i1+(i2-i1) / 2;
     Result = Sum (A, i1, center) + Sum(A, center+1, i2); 
   }
  return Result;
}
Помогите разобраться. В принципе, если увижу готовый код разберусь, но хотелось бы самому.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.03.2019, 23:09
Ответы с готовыми решениями:

Не могу понять как написать
Доброго времени суток. Не мог бы кто помочь в написании программ: 1. Определить имеет ли...

Не могу понять как написать правильно.
Не могу понять как это написать правильно. Оно даже не компилируется. #include<iostream>...

Теория вероятностей. Не могу понять как написать на С++
Определить вероятность того, что в семье имеющей 6 детей не больше 4 девочек. Веpоятность...

Не могу понять как написать в switch - если значение не действительно
Не могу понять как написать в switch statement "Error - the day you entered is not valid". Стоит...

3
6321 / 3498 / 1421
Регистрация: 07.02.2019
Сообщений: 8,909
03.03.2019, 00:18 2
Лучший ответ Сообщение было отмечено Алексей Чаус как решение

Решение

можно как то так:
C++
1
2
3
4
5
6
7
pair<int,int> min(int A[], int i, int j){
    if (i>=j) return pair<int,int>(A[j],j);
    int center=i+(j-i)/2;
    pair<int,int> left=min(A,i,center);
    pair<int,int> right=min(A,center+1,j);
    return (left.first<right.first)? left:right;
}
0
0 / 0 / 0
Регистрация: 03.07.2018
Сообщений: 21
03.03.2019, 11:33  [ТС] 3
Цитата Сообщение от zayats80888 Посмотреть сообщение
можно как то так:
Почему не работает? выводит ноль.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
 
using namespace std;
 
pair<int, int> min(int A[], int i, int j) {
    if (i >= j) return pair<int, int>(A[j], j);
    int center = i + (j - i) / 2;
    pair<int, int> left = min(A, i, center);
    pair<int, int> right = min(A, center + 1, j);
    return (left.first < right.first) ? left : right;
}
 
 
int main()
{
    int A[12];
    for (int i = 0; i < 12; i++)
    {
        A[i] = i;
    }
    pair<int, int> a;
     a = min(A, 0, 11);
    cout << a.second;
    system("pause");
    return 0;
 
}
Добавлено через 10 минут
Цитата Сообщение от Алексей Чаус Посмотреть сообщение
не работает
ой, извиняюсь, у меня же минимальный это ноль)
0
6321 / 3498 / 1421
Регистрация: 07.02.2019
Сообщений: 8,909
03.03.2019, 12:35 4
Алексей Чаус, для проверки небольшой массив можно, например, так инициализировать:
C++
1
int A[12]={2,5,14,-3,65,21,7,-9,85,4,6,33}
В a.second хранится индекс найденного элемента, значение хранится в a.first, хотя для вашего массива и там и там 0.
Пару я просто для примера прилепил. Для вашей задачи, думаю, достаточно, что бы функция возвращала индекс.
0
03.03.2019, 12:35
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.03.2019, 12:35
Помогаю со студенческими работами здесь

Стек на основе массива структур - эт как понять читаю литературу и не могу понять!
Стек статически (на основе массива структур). Пример структура &quot;Товар&quot; которая включает в себя: №...

Как реализовать каскадную схему суммирования?
Имеется массив, скажем, из 10 элементов. Нужно просуммировать элементы массива по каскадной схеме...

Как написать параллакс панораму не могу понять
https://vr.google.com/daydream/ как делать паралакс я понимаю Но как написать паралакс панораму...

Не могу понять как написать меню выбора задач
Здравствуйте! Cуть вопроса такова: Мне нужно написать менюшку, через которую необходимо выбирать...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru