Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
bezprincipus
0 / 0 / 0
Регистрация: 04.01.2011
Сообщений: 5
#1

определение кол-ва участков м массиве - C++

18.01.2011, 17:25. Просмотров 380. Ответов 3
Метки нет (Все метки)

Дан массив размера N. Определить количество участков, на которых его элементы монотонно возрастают1|убывают2.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.01.2011, 17:25     определение кол-ва участков м массиве
Посмотрите здесь:

Определение кол-ва одинаковых цифр в записи целого числа C++
Определение кол-ва натуральных чисел C++
C++ Определение кол-ва нечетных элементов массива с функцией
C++ подсчет кол-ва символов в массиве
C++ подсчет кол-ва символов в массиве
C++ Нужно найти максимальные и минимальные числа в массиве, причём кол-во массивов задаётся пользователем
C++ Кол-во отрицательных элементов каждой строки в двумерном массиве
C++ Кол-во отрицательных элементов в массиве
C++ Определение промежутков в массиве
Найти наименьшее количество строго возрастающих участков в массиве C++
C++ Как определить кол-во четных и отрицательных чисел в массиве одновременно
C++ Как найти кол-во различных элементов в массиве?

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
18.01.2011, 17:58     определение кол-ва участков м массиве #2
максимум таких участков N, если все элементы вразнобой, так? Значит заведем массив из N целых чисел для всех возможных участков. Значением элемента будет длина участка которому он соответствует, а его индекс это номер участка.
Заведем массив A для, собственно, выборки и заведем массив B для информации об участках в A. Заполним A выборкой, а B нулями. i счетчик для индекса A, j счетчик для индекса B.
Сначала разберемся с возрастанием. Проходим по A проверяя A[i] < A[i+1] если выполняется то увеличиваем счетчик длины на один и i++, если не выполняется записываем счетчик длины в текущий элемент B[j] и j++ , и так далее до конца массива A. После прохода будем иметь j и заполненный массив B. Первые j+1 элемента в B будут содержать длины монотонных отрезков, а, собственно, j+1 это их количество.
С убыванием точно также, только в проходе проверяем A[i] > A[i+1].

Ой, задание не дочитал, можно без B обойтись.
Mr.X
Эксперт С++
 Аватар для Mr.X
3021 / 1677 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
18.01.2011, 20:02     определение кол-ва участков м массиве #3
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//////////////////////////////////////////////////////////////////////////////////////
//Дан массив размера N. Определить количество участков, на которых его элементы 
//монотонно возрастают1|убывают2. 
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef int                 T_num;
typedef std::vector<T_num>  T_nums;
typedef std::string         T_str;
//////////////////////////////////////////////////////////////////////////////////////
void  count_increase_and_decrease_sections
    (
        const T_nums&  nums, 
        size_t&        increase_sections_counter,
        size_t&        decrease_sections_counter
    )
{
    T_nums  nums_adj_diff;
    std::adjacent_difference(nums.begin(), nums.end(), std::back_inserter(nums_adj_diff));
 
    struct  T_strictly_monotonic_sections_count
    {
        enum  T_arr_state
        {
            NEG,
            NIL,
            POS          
        };
        T_arr_state  arr_state_cur_;
        size_t&      increase_sections_counter_;
        size_t&      decrease_sections_counter_;
        //----------------------------------------------------------------------------
        T_strictly_monotonic_sections_count
            (
              size_t&  increase_sections_counter,
              size_t&  decrease_sections_counter
            ) 
            : arr_state_cur_              (NIL),
              increase_sections_counter_  (increase_sections_counter),
              decrease_sections_counter_  (decrease_sections_counter)
        {
            increase_sections_counter_ = 0;
            decrease_sections_counter_ = 0;
        }
        //----------------------------------------------------------------------------
        void   operator() (T_num  num)
        {
            switch(arr_state_cur_)
            {
            case NEG:
                if(num == 0)
                {
                    arr_state_cur_ = NIL;
                }
                else if(num > 0)
                {
                    arr_state_cur_ = POS;
                    ++increase_sections_counter_;
                }
                break;
 
            case NIL:
                if(num < 0)
                {
                    arr_state_cur_ = NEG;
                    ++decrease_sections_counter_;
                }
                else if(num > 0)
                {
                    arr_state_cur_ = POS;
                    ++increase_sections_counter_;
                }
                break;
 
            case POS:
                if(num == 0)
                {
                    arr_state_cur_ = NIL;                    
                }
                else if(num < 0)
                {
                    arr_state_cur_ = NEG;
                    ++decrease_sections_counter_;
                }
                break;
            }
        }
    };
 
    std::for_each
        (
            nums_adj_diff.begin() + 1, nums_adj_diff.end(), 
            T_strictly_monotonic_sections_count
                (
                    increase_sections_counter,
                    decrease_sections_counter
                )                
        );
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    srand(static_cast<unsigned>(time(0)));
    std::cout << "Введите размер массива: ";
    T_num  n = 0; 
    std::cin >> n;
 
    struct  T_gen_with_mod
    {
        const T_num MOD_;
        //-----------------------------------------------------------------------------
        T_gen_with_mod(T_num mod) : MOD_(mod)
        {}
        //-----------------------------------------------------------------------------
        T_num  operator() ()
        {
            return  rand() % MOD_;
        }
    };
 
    T_nums  nums;
    std::generate_n(std::back_inserter(nums), n, T_gen_with_mod(n / 2));
 
    std::cout << std::endl;
 
    std::copy(nums.begin(), nums.end(), 
              std::ostream_iterator<T_nums::value_type>(std::cout, "\t"));
 
    size_t  increase_sections_counter = 0;
    size_t  decrease_sections_counter = 0;
 
    count_increase_and_decrease_sections
        (
            nums, 
            increase_sections_counter,
            decrease_sections_counter
        );
 
    std::cout << std::endl
              << "Этот массив строго возрастает на "
              << increase_sections_counter
              << " участках и строго убывает на "
              << decrease_sections_counter
              << " участках."
              << std::endl;
}
Aye Aye
 Аватар для Aye Aye
367 / 281 / 36
Регистрация: 17.12.2009
Сообщений: 567
19.01.2011, 21:16     определение кол-ва участков м массиве #4
Mr.X, такая программа здоровая, попроще:
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>
#include <ctime>
#include <cstdlib>
using namespace std;
 
int main()
{
    const int n = 100; // всего элементов
    srand(time(0));
    int k = 0;
    int z = rand()%(n + 1);
    int A[n];
    // заполнение массива с отрезками
    while (true) {
        A[k] = rand()%101 - 50; // число от -50 до 50
        cout << "chank [" << k << ", " << (z-1) << "]\n"; // от какого до какого заполнялись элементы
        for (int i=k+1; i < z; ++i) A[i] = A[i-1] + 1;
        if (z == n) break;
        z = rand()%(n - z + 1) + (k=z);
    }
    for (int i=0; i<n; ++i) cout << A[i] << ' ';
    int count = 0;
    for (int i=0; i<n-1; ++i)
       if (A[i] > A[i+1]) count++; // подсчет возрастающих отрезков.
    cout << "\ncount = " << count + 1 << '\n';
    return 0;
}
как же тогда у тебя реальные проекты выглядят... ))
Yandex
Объявления
19.01.2011, 21:16     определение кол-ва участков м массиве
Ответ Создать тему
Опции темы

Текущее время: 00:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru