Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.85/75: Рейтинг темы: голосов - 75, средняя оценка - 4.85
 Аватар для Fixer_84
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337

Интересная задача на использование стека

26.08.2018, 17:36. Показов 15508. Ответов 22
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте, уважаемые форумчане! На этот раз решил немного поделиться недавно полученным опытом при решении одной несложной задачи. Само условие я сократил и изменил для выделения основной сути:

В первой строке ввода дан размер массива n. Далее идут n чисел – элементы массива. Предполагая, что элементы массива – это высоты некоторых сооружений, необходимо определить сколько таких сооружений, можно увидеть из начальной точки 0. Все остальные точки (от 1 до n) – это элементы массива.

Пример входных данных:

6
8 2 3 11 11 10

5
12 20 39 45 89

Выходные данные:

2
5

Пояснение:

В первом случае, нам видна точка 8, за ней следует 11 (2 и 3 не видно, так как они меньше 8), последние два элемента (11 и 10) также не видны так как 11 находится на том же уровне, что и 4 элемент (тоже 11), а 10 – еще ниже. Таким образом, видны только два сооружения – 8 и 11 и ответ будет 2.
Во втором случае, будут видны все элементы, так как они расположены по возрастанию и ответом будет 5.

Первым решением, которое напрашивается, будет, вероятно, что-то такое:

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
#include <iostream>
 
    using namespace std;
 
int main() {
 
    int n, k, tmp;
    cin >> n;
    int* arr = new int[n];
    for (int j = 0; j < n; j++) {
        cin >> arr[j];
    }
    k = 0;
    tmp = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > tmp) {
            k++;
            tmp = arr[i];
        }
    }
    cout << "Output of the program: " << ++k << "\n";
    delete [] arr;
    system("pause");
    return 0;
}
Но решив и сдав задачу, я наткнулся на редакционный вариант с использованием стека:

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
#include <iostream> 
#include <stack>
 
    using namespace std;
 
int main() {
    int n, x;
    stack<int> s;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (i == 0) {
            s.push(x);
        }
        if (i > 0) {
            if (x > s.top()) {
                s.push(x);
            }
        }
    }
    cout << "Output of the program: " << s.size() << "\n";
    system("pause");
    return 0;
}
Исходя из условия стек здесь будет как нельзя кстати и, на мой, взгляд, это очень хороший базовый случай его использования. Надеюсь, кому-то было интересно
2
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
26.08.2018, 17:36
Ответы с готовыми решениями:

Интересная задача
В точках A и B на высотах Н1 и Н2 соответственно находятся источники света мощностью I1 иI2 соответственно. Найти точку Х, в которой...

Интересная задача
for(j ; j &lt; array.length; j++){ for(i = 0;i &lt; array.length; i++){ $('.div_input'+i+'').text(array); ...

Интересная задача!
Нашел интересную задачу. Расскажите, пожалуйста, как решать. Спасибо. К сожеланию, по-английски. Правила, 5.18. Запрещено...

22
 Аватар для QuakerRUS
1469 / 1010 / 456
Регистрация: 30.10.2017
Сообщений: 2,799
26.08.2018, 22:20
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от IGPIGP Посмотреть сообщение
представьте
Да я ничего про "математический" подход против и не имею. Я лишь указал, что возможное дополнение условия задачи не отменяет часть уже имеющегося условия, где требуется вывести количество найденных результатов. Но все равно этот спор бессмысленен за неимением точного ТЗ.
0
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
26.08.2018, 22:23
Цитата Сообщение от QuakerRUS Посмотреть сообщение
Но все равно этот спор бессмысленен
Абсолютно и изначально. Я нигде и не спорю, но уже и не знаю как с Вами ещё согласиться, чтобы Вы это поняли.
0
28.08.2018, 19:42
 Комментарий модератора 
IGPIGP, Evg, убедительная просьба высказываться по теме. Общефилософские и физико-математические аспекты задачи, вы можете обсудить в соответствующих разделах.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
28.08.2018, 19:42

Интересная задача
Веб приложение создаются мнемосхемы на которых есть данные, не могу создать места в которые необходимо подтянуть значения из БД MySQL,...

Интересная задача
A = 9; B = -17; C = 13; D = -39; ЕСЛИ (B &gt; D) ТОГДА C=(D+B)*5; ЕСЛИ (D &gt; C) ТОГДА A=(A mod B) div 5; ЕСЛИ (B &gt; C) OR (B &gt;...

Интересная задача
9 в степени 9 в степени 9 2 последние цифры

Интересная задача
https://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=113321#1 если честно идей может кто то поможет

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


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

Или воспользуйтесь поиском по форуму:
23
Ответ Создать тему
Новые блоги и статьи
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru