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

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

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

C++ Количество пар в массиве
Определение кол-ва одинаковых цифр в записи целого числа C++
Определение кол-ва натуральных чисел C++
C++ Определение количества столбцов матрицы, состоящих из положительных элементов
задача: в массиве A определить среднюю длину непрерывных участков отрицательных значений элементов 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
2808 / 1584 / 248
Регистрация: 03.05.2010
Сообщений: 3,698
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     определение кол-ва участков м массиве
Ответ Создать тему
Опции темы

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