VPF::Нахождение min и max и сумму между ними

stat007

Дата 14.5.2009, 08:33 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 521
Регистрация: 9.10.2008

Репутация: -2
Всего: -4

Нкжно найти с помощью алгоритма find или find_if, максимальное и минимальное значение последовательности (массива или вектора), а также с помошью алгоритма accumulate подсчитать сумму элементов между этими max и min значениями.
PS. Так же будет неплохо найти мести на которых стоят max и min значения.

zim22

Дата 14.5.2009, 08:40 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

выкладывайте наработки кода. или идите в Центр Помощи.

--------------------

C++ FAQ Lite

Dmi3ev

Дата 14.5.2009, 08:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 13
Всего: 41

Мне даже интересно, а что не получается?

--------------------

zim22

Дата 14.5.2009, 08:55 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(Dmi3ev @ 14.5.2009, 08:52

)

Мне даже интересно, а что не получается?

открыть MSDN

Код


#include <algorithm>
#include <numeric>
#include <iostream>
#include <vector>

int min, max;
int maxPos, minPos;

class find_max {  
public:  
  find_max() : first(true), cnt(0) { }
  bool operator()(int value) {    
    if (first) {
      min = max = value;
      first = false;      
    } else {
      if (value > max) { max = value; maxPos = cnt; }
      if (value < min) { min = value; minPos = cnt; }
    }
    ++cnt;
    return false;    
  }
private:
  bool first;
  int cnt;
};
int _tmain(int argc, _TCHAR* argv[])
{
  int a[] = {1, -5, 10, 100, 77, 14, 8};  
  std::vector<int> vi(a, a + sizeof(a) / sizeof(*a));

  //std::find_if(a, a  + sizeof(a) / sizeof(*a), find_max());
  std::find_if(vi.begin(), vi.end(), find_max());
  if (minPos > maxPos) std::swap(minPos, maxPos);
  //int sum = std::accumulate(a + minPos, a + maxPos + 1, 0);
  int sum = std::accumulate(vi.begin() + minPos, vi.begin() + maxPos + 1, 0);
  
  std::cout << "Sum: " << sum << std::endl
    << "Max position: " << maxPos << std::endl
    << "Min position: " << minPos << std::endl;
  
    return 0;
}

Это сообщение отредактировал(а) zim22 - 14.5.2009, 09:21

--------------------

C++ FAQ Lite

Dmi3ev

Дата 14.5.2009, 09:23 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 13
Всего: 41

zim22, smile

+ поставлю, хороший ты человек smile

--------------------

sdukshis

Дата 14.5.2009, 12:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 92
Регистрация: 23.3.2009

Репутация: нет
Всего: 1

Если без find, то можно использовать алгоритмы max_element и min_element (правда работать будет медленнее, чем у Zim22)

Код


#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main(){
    int a[]={-1,-10,6,8,9,5,-4,-4};
    const int n = sizeof(a)/sizeof(int);

    vector<int> v(a,a+n);
    vector<int>::iterator max,min;
    int sum;

    max = max_element(v.begin(),v.end());
    min = min_element(v.begin(),v.end());

    sum = (max >= min)?accumulate(min+1,max,0):accumulate(max+1,min,0);

    cout << "min = " << *min << ", max = " << *max << ", sum = " << sum <<endl;

    return 0;
}

Dmi3ev

Дата 14.5.2009, 13:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1698
Регистрация: 28.11.2007

Репутация: 13
Всего: 41

Цитата

Если без find

так надо было с find, зачем без него-то...

Цитата

правда работать будет медленнее, чем у Zim22

тогда зачем ваще так делать?

--------------------

sdukshis

Дата 14.5.2009, 14:09 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 92
Регистрация: 23.3.2009

Репутация: нет
Всего: 1

Цитата

тогда зачем ваще так делать?

У разных подходов есть как достоинства так и недостатки.

В данном случае в варианте zim22 я вижу следующие недостатки (2zim22 без обид, это просто моё мнение о коде, а не о программисте):
1) Глобальные переменные
int min, max;
int maxPos, minPos;
2)find_if используется немного не по назначению (по смыслу больше подходит foe_each)
Такие разногласия затрудняют чтение программы сторонними разработчиками
Если же использовать 2 функтора и 2 вызова find_if, то тогда обе версии сравняются по производительности
3) Не понравилась вот это строчка if (minPos > maxPos) std::swap(minPos, maxPos);
Не могу точно сказать почему не понравилась, просто такое впечатление
Хотя мой эквивалент тоже не блещет красотой (sum = (max >= min)?accumulate(min+1,max,0):accumulate(max+1,min,0);)

На мой взгляд вторая версия исправляет эти недостатки + она короче

Это сообщение отредактировал(а) sdukshis - 14.5.2009, 14:11

zim22

Дата 14.5.2009, 15:19 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(sdukshis @ 14.5.2009, 14:09

)

В данном случае в варианте zim22 я вижу следующие недостатки (2zim22 без обид, это просто моё мнение о коде, а не о программисте):

так лучше?

Код


#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

template <typename InputIterator, class ValueType>
class Search {
public:  
  Search(InputIterator b, InputIterator e) : begin(b), end(e) { }
  std::pair<ValueType, ValueType> min() const;  
  std::pair<ValueType, ValueType> max() const;  
  ValueType sum() const;
private:
  InputIterator begin, end;  
};

template <typename InputIterator, class ValueType>
std::pair<ValueType, ValueType> Search<InputIterator, ValueType>::min() const {
  InputIterator it = std::min_element(begin, end);
  return std::make_pair(std::distance(begin, it), *it);
}

template <typename InputIterator, class ValueType>
std::pair<ValueType, ValueType> Search<InputIterator, ValueType>::max() const {
  InputIterator it = std::max_element(begin, end);
  return std::make_pair(std::distance(begin, it), *it);
}

template <typename InputIterator, class ValueType>
ValueType Search<InputIterator, ValueType>::sum() const {
  return std::accumulate(begin, end, ValueType());  
}

int main()
{    
  int arr[] = {1, -5, 10, 15, 8, 911, 2, -3};
  const int size = sizeof(arr) / sizeof(*arr);
  std::vector<int> vi(arr, arr + size);

  Search<int*, int> s1(arr, arr + size);  
  std::pair<int, int> min = s1.min();
  std::pair<int, int> max = s1.max();
  int sum = s1.sum();
  
  std::cout << "CArray: " << std::endl;
  std::cout << "Min position: " << min.first  << std::endl
            << "Min value: "    << min.second << std::endl
            << "Max position: " << max.first  << std::endl
            << "Max value: "    << max.second << std::endl
            << std::endl;
             

  Search<std::vector<int>::iterator, int> s2(vi.begin(), vi.end());
  min = s2.min();
  max = s2.max();
  sum = s2.sum();

  std::cout << "vector: " << std::endl;
  std::cout << "Min position: " << min.first  << std::endl
            << "Min value: "    << min.second << std::endl
            << "Max position: " << max.first  << std::endl
            << "Max value: "    << max.second << std::endl
            << std::endl;


    return 0;
}

--------------------

C++ FAQ Lite

sdukshis

Дата 14.5.2009, 19:40 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 92
Регистрация: 23.3.2009

Репутация: нет
Всего: 1

Цитата

так лучше?

Если честно, то не совсем.
1) Используется 2 прохода по массиву для поиска min и max (в первом варианте был 1)
2) Зачем хранить значения min и max, когда их легко получить по итераторам (указателям)
3) Не очень разбирающийся пользователь может в дальнейшем много раз вызывать min() max() и sum(), не понимая почему падает производительность.
4) Кажется sum() будет возвращать сумму всех элементов, а не искомых.

Зато есть очень большое плюс
Благодаря обобщённому решению можно реализовать задачу всего одной строчкой для любых последовательных контейнеров.
Правда это же можно сделать и используя for_each() с соответствующим функтором.

Это сообщение отредактировал(а) sdukshis - 14.5.2009, 19:43

zim22

Дата 14.5.2009, 20:30 (ссылка)

(нет голосов)

Загрузка ...

depict1

Профиль
Группа: Завсегдатай
Сообщений: 2682
Регистрация: 15.1.2009
Где: Украина

Репутация: 29
Всего: 69

Цитата(sdukshis @ 14.5.2009, 19:40

)

Если честно, то не совсем.

замечания справедливые. но если убрать эти недостатки, то получится очень даже ничего smile

--------------------

C++ FAQ Lite

Rififi

Дата 14.5.2009, 21:01 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1254
Регистрация: 9.3.2008

Репутация: 3
Всего: 36

sdukshis,
На мой взгляд вторая версия исправляет эти недостатки + она короче
boost::minmax_element исправяет недостатки в виде двух проходов, + он ещё короче. :gigi:

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »