Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/9: Рейтинг темы: голосов - 9, средняя оценка - 5.00
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
#1

Странная последовательность

23.02.2015, 17:14. Просмотров 1679. Ответов 72
Метки нет (Все метки)

Добрый день, дорогие мои.
В невероятном раздражении обращаюсь к Вам, потому могут быть резкие выпады гнева.
У меня следующий вопрос - есть задание "создать странную последовательность".
Это такая последовательность, в которой элементы отличаются между собой не более, чем на 1.
То есть, если у нас массив - 5 3 1 4, то нужно сделать из него - 3 2 1 2. При этом, нужно посчитать, на сколько единиц я каждый раз уменьшала каждый элемент.
Я решила эту задачу таким способом.
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
#include <iostream>
#include <vector>
#include <cmath>
 
void resolve(std::vector<int>& cubes, int& result)
{
    int count  = 0;
    for (int i = 1; i < cubes.size(); ++i)
    {
        if ( std::abs(cubes[i - 1] - cubes[i]) > 1 )
        {
            ++count;
            if (cubes[i - 1] < cubes[i]) cubes[i] -= 1;
            else cubes[i - 1] -= 1;
        }
    }
    if (count != 0)
    {
        result += count;
        resolve(cubes, result);
    }
}
 
int main()
{
    int result = 0;
    int turrents = 0;
    std::cin >> turrents;
    std::vector <int> cubes;
    cubes.resize(turrents);
    for (int i = 0; i < turrents; ++i)
        std::cin >> cubes[i];
 
    resolve(cubes, result);
    std::cout << result;
     return 0;
}
Но... Оказалось, что это плохое решение, потому что слишком много времени занимает подсчёт результата длинных массивов... Может кто-то из Вас подскажет алгоритм решения, чтобы код выполнялся быстрее?
Буду очень благодарна.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.02.2015, 17:14
Ответы с готовыми решениями:

странная последовательность
Во входном файле записана последовательность чисел в странном формате: у...

Странная(или не странная, незнаю) реакция на буквы, знаки операций
Всем добрый день. Делаю маленькую наработку, пока есть только начало. Ниже...

Построить последовательность из 0 и 1, в которой Bi=1 если элементы i-го столбца образуют убывающую последовательность
Дана действительная квадратная матрица порядка n. Построить последовательность...

Вставить в последовательность действительное число b так, чтобы последовательность осталась неубывающей
Дана последовательность действительных чисел a1 &lt;= a2&lt;= ... &lt;=an вставить...

Задана последовательность слов. Определить частоту вхождения каждого слова в последовательность.
Доделать программу, чтобы работала как надо Задана последовательность слов....

72
S_el
2138 / 1668 / 353
Регистрация: 15.12.2013
Сообщений: 6,625
23.02.2015, 17:39 #2
Тамика, тестовые данные прикрепите,чтобы можно было провести замер.
0
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 18:10  [ТС] #3
S_el, в том-то и дело, что у меня нет этих данных. Код уходит в базу и там теститься. Потому у меня только минимальные тестовые данные...

Добавлено через 8 минут
S_el, нашла максимально возможные значения. Длинна массива от 1 до 10 в степени 9.
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
23.02.2015, 18:23 #4
Только уменьшать можно что ли? Тогда так:
C++
1
2
3
4
5
6
7
vector<int> b(a);
int c = b.front();
for_each(b.begin() + 1, b.end(), [&c](int& x) { x = c = min(x, c + 1); });
c = b.back();
for_each(b.rbegin() + 1, b.rend(), [&c](int& x) { x = c = min(x, c + 1); });
transform(a.begin(), a.end(), b.begin(), b.begin(), [](int x, int y) { return x - y; });
auto result = accumulate(b.begin(), b.end(), 0);
0
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 18:29  [ТС] #5
Somebody, можно что угодно делать. Уменьшать, менять.
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
23.02.2015, 18:32 #6
Цитата Сообщение от Тамика Посмотреть сообщение
Уменьшать, менять.
OK, меняем все элементы на нули.
Цитата Сообщение от Тамика Посмотреть сообщение
При этом, нужно посчитать, на сколько единиц я каждый раз уменьшала каждый элемент.
Будет 0 уменьшений, потому что все элементы поменяли, а не уменьшали.
1
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 18:37  [ТС] #7
Somebody, данные входные менять нельзя, я даже их не знаю. А уж если всё заменять нулями, то по-Вашему результат будет корректный?
0
castaway
Эксперт С++
4929 / 3036 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
23.02.2015, 18:39 #8
Цитата Сообщение от Тамика Посмотреть сообщение
То есть, если у нас массив - 5 3 1 4, то нужно сделать из него - 3 2 1 2.
На самом деле, по каким правилам получаются такие метаморфозы?
Задания как такового нет. Если знаешь - опиши, если нет - так и скажи, тогда не будем тратить время..

Добавлено через 1 минуту
Цитата Сообщение от Тамика Посмотреть сообщение
то по-Вашему результат будет корректный?
Он по-Вашему будет корректный. Т.е. по вашим условиям.
0
DrOffset
7970 / 4635 / 1127
Регистрация: 30.01.2014
Сообщений: 7,531
23.02.2015, 18:40 #9
Цитата Сообщение от Тамика Посмотреть сообщение
Это такая последовательность, в которой элементы отличаются между собой не более, чем на 1
А крайние с концов массива элементы между собой тоже должны отличаться на 1?
И что значит "не более"? Т.е. могут и на ноль отличаться (т.е. быть равными)?
0
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
23.02.2015, 18:40 #10
Где условие, чётко написанное? Что можно делать с числами и что нужно посчитать?
Да, если всё заменить нулями, то все соседние элементы будут отличаться на 0, то есть не более чем на единицу.
0
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 18:44  [ТС] #11
castaway, я же объяснила. Есть массив из элементов. Числа произвольные, больше нуля, целые(не знаю куда детальней). Нужно его так преобразовать(уменьшая элементы), чтобы получилась "плавная" последовательность - то есть такая последовательность, при которой соседние элементы отличаются не более чем на 1.
Сколько будет чисел - неизвестно, это все тестируется на сервере. Известно только, что размер массива может быть от 1 до 10 в девятой степени.
Элементы массива могут быть от 1 до 10 в шестой степени.
Что ещё объяснить? Если для Вас это не "условие", то спасибо за внимание, буду ждать кого-то, кто поймет и поможет.

Добавлено через 42 секунды
DrOffset, Somebody, расписала выше.
Это все, что мне дано.
0
S_el
2138 / 1668 / 353
Регистрация: 15.12.2013
Сообщений: 6,625
23.02.2015, 18:46 #12
Тамика, уже предложенные варианты пробовали?
0
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 18:50  [ТС] #13
S_el, пока пытаюсь понять, что там вообще делается. Не приверженка STL, потому многого не знаю.
Пока выдает рантайм еррор "vector iterator not dereferencable".
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
23.02.2015, 18:53 #14
почему бы не кинуть ссылку на задачу
0
castaway
Эксперт С++
4929 / 3036 / 453
Регистрация: 10.11.2010
Сообщений: 11,116
Записей в блоге: 10
Завершенные тесты: 1
23.02.2015, 18:53 #15
Цитата Сообщение от Тамика Посмотреть сообщение
Есть массив из элементов. Числа произвольные, больше нуля, целые(не знаю куда детальней). Нужно его так преобразовать(уменьшая элементы), чтобы получилась "плавная" последовательность - то есть такая последовательность, при которой соседние элементы отличаются не более чем на 1.
Преобразуем все числа в 1 - готово. Чем не решение?
0
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 18:55  [ТС] #16
Не уверенна, что права, но вроде чутка разобралась с ошибкой. Но постоянно результат ноль.

Добавлено через 1 минуту
castaway, тем, что в базе есть верные ответы на любую последовательность, которая задаётся. И они не совпадут.

Добавлено через 32 секунды
Dimension, потому что это задача заботливо придумана у нас на работе. Была бы ссылка - наверное уже скинула бы.
0
S_el
2138 / 1668 / 353
Регистрация: 15.12.2013
Сообщений: 6,625
23.02.2015, 18:57 #17
Цитата Сообщение от Тамика Посмотреть сообщение
тем, что в базе есть верные ответы на любую последовательность, которая задаётся. И они не совпадут.
так согласно сформулированному условию,последовательность равных чисел,тоже будет верной.

Цитата Сообщение от Тамика Посмотреть сообщение
пока пытаюсь понять, что там вообще делается. Не приверженка STL, потому многого не знаю.
Не обязательно понимать,чтобы попробовать "скормить" вариант системе.
0
Dimension
Dimension
573 / 443 / 221
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
23.02.2015, 19:00 #18
Цитата Сообщение от Тамика Посмотреть сообщение
потому что это задача заботливо придумана у нас
тогда хоть ограничения киньте
0
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 31
23.02.2015, 19:02  [ТС] #19
S_el, код этот тестируется. На сервере. Ему даются РАЗНЫЕ последовательности с РАЗНЫМИ размерами. И это все рандомно. И это никак от меня не зависит.

Цитата Сообщение от S_el Посмотреть сообщение
Не обязательно понимать,чтобы попробовать "скормить" вариант системе.
Согласна, но для фикса баги нужно знать, что фиксить.
0
IrineK
Заблокирован
23.02.2015, 19:02 #20
Цитата Сообщение от Тамика Посмотреть сообщение
Длинна массива от 1 до 10 в степени 9
Цитата Сообщение от Тамика Посмотреть сообщение
в базе есть верные ответы на любую последовательность
Из обрывков и намёков на алгоритм.
От каждого узла - три ветки: -1,0,1
При количестве шагов 109 количество вариантов 3^109. Однако.
0
23.02.2015, 19:02
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2015, 19:02

Вводится последовательность из N вещественных чисел. Определить, является ли последовательность знакочередующе
Вводится последовательность из N вещественных чисел. Определить, является ли...

Массив: Вставить в последовательность действительное число b так, чтобы последовательность осталась неубывающей.
дана последовательность действительных чисел. вставить в нее действительное...

Если последовательность отсортирована по возрастанию, оставить ее без изменения. Иначе получить иную последовательность
Дана последовательность действительных чисел X1,X2,X3,…,Xn (n&gt;2, заранее...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru