Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.78/18: Рейтинг темы: голосов - 18, средняя оценка - 4.78
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35

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

23.02.2015, 17:14. Показов 4664. Ответов 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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
23.02.2015, 17:14
Ответы с готовыми решениями:

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

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

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

72
28 / 28 / 5
Регистрация: 23.04.2014
Сообщений: 130
23.02.2015, 20:30
Студворк — интернет-сервис помощи студентам
считаем сумму, меняем всё на нули - профит!
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 20:53
Не, мой код не работает. Буду думать.
0
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
23.02.2015, 21:13
Цитата Сообщение от S_el Посмотреть сообщение
после 4 по условию 2 идти не может.
Не может. Но, что самое удивительное, условие поставлено так, что программа работает по заданному алгоритму из 24-го поста. Парадокс, тебе так не кажется!?)

Цитата Сообщение от gru74ik Посмотреть сообщение
Не, мой код не работает. Буду думать.
Твой код, как и мой, не работает и работать не будет, пока не будет четко-поставленной-задачи.
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.02.2015, 21:15
Если я правильно понял эту сильно расплывчатую постановку, то это делается тривиально за один проход массива - получаем из одного входного 2 выходных массива - первый с диапазоном скачков [-1;1] а второй - почленная разность его с исходным.
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
23.02.2015, 21:25
Цитата Сообщение от castaway Посмотреть сообщение
Парадокс, тебе так не кажется!?)
Обычное дело для некорректных задач

Цитата Сообщение от castaway Посмотреть сообщение
Твой код, как и мой, не работает и работать не будет, пока не будет четко-поставленной-задачи.
Судя по количеству встреченных постановок её и не будет.Разве что кто-то возьмется переформулировать с учетом всех уточнений.
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 21:28
Тамика, давай, ещё раз.
Вот, скажем, дан массив из 10 элементов:

57 75 21 59 67 31 66 24 75 78

Как должен будет выглядеть правильно обработанный массив в итоге?
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.02.2015, 21:29
Я не ТС, но вангую результат: 57 58 57 58 59 58 59 58 59 60
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
23.02.2015, 21:44
Цитата Сообщение от gru74ik Посмотреть сообщение
57 75 21 59 67 31 66 24 75 78
Ну а я предположу:
1 2 1 2 3 2 1 2 3
хотя мне больше нравится
21 22 21 22 23 22 23 22 23 24

Цитата Сообщение от _Ivana Посмотреть сообщение
Я не ТС, но вангую результат: 57 58 57 58 59 58 59 58 59 60
увеличивать нельзя

Добавлено через 1 минуту
Цитата Сообщение от gru74ik Посмотреть сообщение
Как должен будет выглядеть правильно обработанный массив в итоге?
Это знает только алгоритм тест-программы
0
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
23.02.2015, 21:57
Я даже гадать не буду. Предлагаю не флудить и покинуть тему, пока не будет чёткой поставленной задачи.
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
23.02.2015, 21:57
S_el, Ваш второй вариант совпадает с моим навангованным с точностью до постоянного смещения, что непринципиально.
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 22:18
Я почему и спрашивал про нахождение минимального элемента. Потому как, если можно только уменьшать элементы, то:
1) надо найти минимальный элемент массива
2) использовав его как отправную точку, "бежать" от него к началу и концу массива, уменьшая остальные элементы, согласно условию (с разницей в единицу).

Тогда в моём примере получилось бы такая картина:
исходный массив:
57 75 21 59 67 31 66 24 75 78
Находим минимальный элемент (в нашем случае, это третий элемент со значением 21). Уменьшаем его соседей:
конечный массив:
23 22 21 22 23 24 25 24 25 26
Добавлено через 5 минут
Хмм... а ведь и "уменьшать соседей" можно по разному... Можно чтобы они были больше на единицу, а можно чтобы меньше. А как надо? Ну найду я минимальный элемент (21). Соседей надо уменьшить до 22 или до 20?

Добавлено через 11 минут
Возможно, отношения в конечном массиве должны быть такие же, как в исходном массиве... То есть, если в исходном массиве первый элемент был больше второго, то и в конечном должно быть так же. Тогда мой пример будет выглядеть так:
исходный массив:
57 75 21 59 67 31 66 24 75 78
конечный массив:
21 22 21 22 23 22 23 22 23 24
1
Комп_Оратор)
Эксперт по математике/физике
 Аватар для IGPIGP
9007 / 4708 / 630
Регистрация: 04.12.2011
Сообщений: 14,003
Записей в блоге: 16
24.02.2015, 00:29
Цитата Сообщение от Тамика Посмотреть сообщение
То есть, если у нас массив - 5 3 1 4, то нужно сделать из него - 3 2 1 2. При этом, нужно посчитать, на сколько единиц я каждый раз уменьшала каждый элемент.
Тамика, доброй ночи.
Мне кажется, что изменять следует только следующий элемент. Потому, что если изменять уже принятый, то нет гарантии, что не придётся бежать обратно. Смотрите:
8, 5, 3, 25, 23, 20,
6,5, ...
делая 5->4 чтобы 4,3 нужно вернутся и уменьшить 6->5
получили: 5, 4,3
далее 25 что делать? опять назад бежать или уменьшать 25?
Вообще, в такой задаче нужно бы знать каков доступ к исходной последовательности. Из Ваших слов, пока, можно предположить, что последовательный. Правильно?
Похоже также, что нельзя сделать никаких допущений о средней величине данных в потоке. Тогда, возможно, чтобы исключить хотя бы возвратно колебательные итерации имеет смысл модифицировать всегда, именно, следующий элемент. Это иногда может быть не самым быстрым путём, но зато порождает простое и однозначно воспроизводимое правило. Тогда:
8, 5, 3, 25, 23, 20...
породит:
8, 7, 6, 7, 8, 9
при этом количество единиц:
0, 2, 3, -18, -15, -11...
я привёл со своими знаками, потому как не понял как их считать. Реализовать такое несложно.
Не сердитесь если я не понял о чём речь.
1
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
24.02.2015, 09:35  [ТС]
Цитата Сообщение от gru74ik Посмотреть сообщение
Я почему и спрашивал про нахождение минимального элемента. Потому как, если можно только уменьшать элементы, то:
1) надо найти минимальный элемент массива
2) использовав его как отправную точку, "бежать" от него к началу и концу массива, уменьшая остальные элементы, согласно условию (с разницей в единицу).
Окей, а как же критерий оптимальности?
Вы уверенны, что если свести каждый элемент ближе к минимальному, то получится меньше уменьшений? Можно попробовать, конечно. Может Ваш способ правильный.

Добавлено через 6 минут
Цитата Сообщение от IGPIGP Посмотреть сообщение
далее 25 что делать? опять назад бежать или уменьшать 25?
В данном случае - уменьшать 25. Потому как менять числа можно только путем уменьшения.
Цитата Сообщение от IGPIGP Посмотреть сообщение
Вообще, в такой задаче нужно бы знать каков доступ к исходной последовательности. Из Ваших слов, пока, можно предположить, что последовательный. Правильно?
Совершенно верно.

Цитата Сообщение от IGPIGP Посмотреть сообщение
Похоже также, что нельзя сделать никаких допущений о средней величине данных в потоке.
Мне известно только, что диапазон значений от 1 до 10 в шестой степени... Все генерируется случайно, потому может быть последовательность даже такая --- 1 1000 654 2654 8 555
Цитата Сообщение от IGPIGP Посмотреть сообщение
породит:
Только уменьшать.
Цитата Сообщение от IGPIGP Посмотреть сообщение
Не сердитесь если я не понял о чём речь.
Да мне самой, помимо ворчунов вокруг, не очень понятна постановка задачи. Но что дали, с тем и приходится работать. Некоторые поправки нам периодически по почте высылают(когда кто-то из сотрудников закипает от недостатка информации), потому не сердитесь, если что-то не так объяснила.

Добавлено через 8 минут
Цитата Сообщение от gru74ik Посмотреть сообщение
Хмм... а ведь и "уменьшать соседей" можно по разному... Можно чтобы они были больше на единицу, а можно чтобы меньше. А как надо? Ну найду я минимальный элемент (21). Соседей надо уменьшить до 22 или до 20?
Вопрос, однако....
Раз речь об оптимальности, думаю что нужно так, чтобы кол-во уменьшений было как можно меньше. То есть, если уменьшив до 22, кол-во уменьшеных единиц будет меньше, чем уменьшив до 20, то этот способ и применить.

Добавлено через 7 минут
Цитата Сообщение от castaway Посмотреть сообщение
Я даже гадать не буду. Предлагаю не флудить и покинуть тему, пока не будет чёткой поставленной задачи.
Окей.
0
19506 / 10109 / 2464
Регистрация: 30.01.2014
Сообщений: 17,834
24.02.2015, 09:36
Цитата Сообщение от Тамика Посмотреть сообщение
Только уменьшать.
А если последовательность такая?
[2 5 7 1 1 3]
Если меньше единицы быть не может, то одну из единиц таки придется увеличить.
1
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
24.02.2015, 09:40
Тамика,
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 <ctime>
#include <vector>
#include <iostream>
using namespace std;
 
void resolve(vector<int>& values, vector<int>& reduce){
    for( size_t elem = 0; elem < values.size(); elem++ )
        if( elem )
        {
            reduce.push_back(values[elem] - values[elem - 1] - 1);
            values[elem] -= reduce[elem];
        }
        else
            reduce.push_back(0);
}
 
void show(vector<int>& values){
    for( size_t elem = 0; elem < values.size(); elem++ )
        cout<<values[elem]<<" ";
    cout<<endl;
}
 
int main(){
    srand(time(0));
    vector<int> values;
    vector<int> reduce;
    for( size_t elem = 0; elem < 15; elem++ )
           values.push_back(rand() % 30 - 15);
    cout<<"INPUT : "<<endl;
    show(values);
    resolve(values, reduce);
    cout<<"OUTPUT : "<<endl;
    show(values);
    cout<<"REDUCE : "<<endl;
    show(reduce);
    return 0;
}
http://codepad.org/G7rPiQR8
INPUT :
-14 6 5 0 -14 9 -1 -2 -8 3 3 -13 7 -1 7
OUTPUT :
-14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0
REDUCE :
0 19 17 11 -4 18 7 5 -2 8 7 -10 9 0 7
2
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
24.02.2015, 09:40
DrOffset, если элементы равны, то ничего делать не надо (просто переходишь к следующему элементу), поскольку соблюдается условие:
Цитата Сообщение от Тамика Посмотреть сообщение
элементы отличаются между собой не более, чем на 1
2
Автор FAQ
 Аватар для -=ЮрА=-
6614 / 4256 / 401
Регистрация: 08.08.2009
Сообщений: 10,325
Записей в блоге: 24
24.02.2015, 09:43
Вот вариант с выбором направления нормализации
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
#include <ctime>
#include <vector>
#include <iostream>
using namespace std;
 
void resolve(vector<int>& values, vector<int>& reduce){
    for( size_t elem = 0; elem < values.size(); elem++ )
        if( elem )
        {
            if( values[elem] > values[elem - 1] )
            reduce.push_back(values[elem] - values[elem - 1] - 1);
            else
            reduce.push_back(values[elem] - values[elem - 1] + 1);
            values[elem] -= reduce[elem];
        }
        else
            reduce.push_back(0);
}
 
void show(vector<int>& values){
    for( size_t elem = 0; elem < values.size(); elem++ )
        cout<<values[elem]<<" ";
    cout<<endl;
}
 
int main(){
    srand(time(0));
    vector<int> values;
    vector<int> reduce;
    for( size_t elem = 0; elem < 15; elem++ )
           values.push_back(rand() % 30 - 15);
    cout<<"INPUT : "<<endl;
    show(values);
    resolve(values, reduce);
    cout<<"OUTPUT : "<<endl;
    show(values);
    cout<<"REDUCE : "<<endl;
    show(reduce);
    return 0;
}
http://codepad.org/98C514G9
INPUT :
8 3 -12 -1 -2 3 -14 2 13 -10 14 9 1 -7 -6
OUTPUT :
8 7 6 5 4 3 2 1 2 1 2 3 2 1 0
REDUCE :
0 -4 -18 -6 -6 0 -16 1 11 -11 12 6 -1 -8 -6
Выбор направления
C++
1
2
3
4
if( values[elem] > values[elem - 1] )
            reduce.push_back(values[elem] - values[elem - 1] - 1);
            else
            reduce.push_back(values[elem] - values[elem - 1] + 1);
2
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
24.02.2015, 09:47  [ТС]
DrOffset, gru74ik верно ответил.

Добавлено через 4 минуты
-=ЮрА=-, воу... Круто! Огромное спасибо.
Единственный нюанс - нельзя увеличивать числа... То есть, плавную последовательность строить можно только уменьшением.
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
24.02.2015, 09:52
Цитата Сообщение от Тамика Посмотреть сообщение
Окей, а как же критерий оптимальности?
Я себе твою последовательность представляю себе как ползунки на эквалайзере.
Тебе в любом случае придётся все ползунки "двигать" относительно минимального, иначе условие не будет выполнено. Только если ты найдёшь минимальный, то не придётся вперёд-назад по массиву бегать.
1) Один проход - ищем минимальный.
2) Второй проход - упорядочиваем относительно минимального.
2
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
24.02.2015, 09:55  [ТС]
gru74ik, вот да, сейчас как раз переделываю код. Поняла, что Ваш вариант таки крут.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
24.02.2015, 09:55

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
60
Ответ Создать тему
Новые блоги и статьи
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru