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

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

23.02.2015, 17:14. Показов 4661. Ответов 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
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 19:02  [ТС]
Студворк — интернет-сервис помощи студентам
Dimension,
Цитата Сообщение от Тамика Посмотреть сообщение
Сколько будет чисел - неизвестно, это все тестируется на сервере. Известно только, что размер массива может быть от 1 до 10 в девятой степени.
Элементы массива могут быть от 1 до 10 в шестой степени.
0
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
23.02.2015, 19:11
Цитата Сообщение от castaway Посмотреть сообщение
Преобразуем все числа в 1 - готово. Чем не решение?
Цитата Сообщение от Тамика Посмотреть сообщение
castaway, тем, что в базе есть верные ответы на любую последовательность, которая задаётся. И они не совпадут.
Зачем нужно условие преобразования, если оно не соответствует "базе верных ответов"?
У меня складывается сильное ощущение, что ты сама не понимаешь что тебе необходимо.
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 19:17
Найти наименьший элемент(ы) и разбегаясь от них к началу и концу вектора ровнять.
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 19:19  [ТС]
castaway, это не я хочу, а рабочая задача. Условия придумывают довольно скудоумные ребята, потому очень часто возникают спорные моменты. Но вот что стало понятно, исходя из примеров.
Теперь ещё раз. На примере.
Есть массив(рандомно подбираю) например из 7-ми рандомно подобраных чисел(но на деле это все строит сервак и тестит на моем коде).
6 3 4 2 3 2 5.
Что должен сделать код.
Берет первые два элемента.
Это 6 и 3. Между ними разница больше единицы, значит нужно преобразовать 6 так, чтобы разница между 3 и 6 была 1. То есть - уменьшаем 6. Получаем 4 3. Записали в результат разницу между 6 и 4. Это 2.
Далее.
Следующие два числа - 3 4. Между ними разница один. Идём дальше.
4 2.
Между ними разница более одного. Значит уменьшаем 4 так, чтобы разница была 1. Получаем 3 2. Разницу записываем 2 + 1 = 3. То есть, за это время мы уменьшили числа на три единицы.
И так далее.

Если Вам что-то даст, то вот два примера, которые сто процентов правильные(с задачей пришли)
5
5 3 4 5 6 ---- ответ 1.
3
3 2 3 ---- ответ 0.
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 19:22  [ТС]
Цитата Сообщение от gru74ik Посмотреть сообщение
Найти наименьший элемент(ы) и разбегаясь от них к началу и концу вектора ровнять.
Ровнять нельзя. Должна быть минимальная разница в единицу.
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
23.02.2015, 19:23
Цитата Сообщение от Тамика Посмотреть сообщение
Если Вам что-то даст, то вот два примера, которые сто процентов правильные(с задачей пришли)
Так вам нужно получить только количество "уменьшений" или новую последовательность тоже?
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 19:24  [ТС]
S_el, только кол-во уменьшений.
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 19:32
А если соседние элементы равны? Какой надо будет изменять? Тот, что идёт первым или тот, что идёт следом за ним? И какому действию отдать предпочтение в таком случае - уменьшению или увеличению? Или можно только уменьшать?

Добавлено через 2 минуты
Цитата Сообщение от Тамика Посмотреть сообщение
Ровнять нельзя. Должна быть минимальная разница в единицу.
Но весь массив нам дан сразу? Мы ведь можем пробежаться по массиву и найти минимальное значение?
Или непременно должны начать манипуляции с первого элемента, последовательно продвигаясь в хвост массива?
1
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
23.02.2015, 19:54
Цитата Сообщение от Тамика Посмотреть сообщение
только кол-во уменьшений.
Вот сразу надо было говорить
C++
1
2
    for (int i = 1; i < cubes.size(); ++i)
    if(abs(cubes[i] - cubes[i-1])>1) result++;
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 19:59  [ТС]
gru74ik, если элементы равны, то ничего на нужно делать, потому что "не более 1" выполняется. Предпочтение - уменьшение, и только.
Массив дан сразу. А зачем искать минимальное? Тут важен критерий оптимальности. Как мне только что рассказали. То есть за меньшее кол-во шагов превратить последовательность в минимальную.
з.ы. Спасибо за то, что задаёте вопросы, вместо того, чтобы наезжать.
0
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
23.02.2015, 19:59
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <cstdint>
 
template <typename T, size_t N>
void print_array( T (&arr)[N] ) {
    for ( int64_t & i : arr ) {
        std::cout << i << ' ';
    }
    std::cout << std::endl;
}
 
int main()
{
    int64_t arr[] = { 6, 3, 4, 2, 3, 2, 5 };
 
    print_array( arr );
 
    int64_t overall_difference = 0;
    for ( size_t i = 0; i < sizeof( arr ) / sizeof( arr[0] ) - 1; ++i ) {
        int64_t difference = abs( arr[i] - arr[i + 1] );
        if ( difference > 1 ) {
            if ( arr[i] > arr[i + 1] ) {
                arr[i] = arr[i + 1] + 1;
            } else {
                arr[i + 1] = arr[i] + 1;
            }
            overall_difference += difference - 1;
        }
    }
    print_array( arr );
    std::cout << overall_difference << std::endl;
}
Только не говори что по условию не совпадает.
0
2838 / 1647 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
23.02.2015, 20:02
Цитата Сообщение от Тамика Посмотреть сообщение
Ровнять нельзя. Должна быть минимальная разница в единицу.
В каждом посте по новому условию. Скоро вообще совсем другая задача будет...
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 20:04  [ТС]
S_el, Вы не так поняли и я не так объяснила. Кол-во уменьшений - кол-во единиц, на которые были уменьшены все числа по достижении плавной последовательности.

Добавлено через 1 минуту
Somebody, это было в начальном условии.
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 20:04
А так медленно будет?
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
int resolve(std::vector<int>& vec)
{
    int result = 0;
    int a, b, c;
    for (size_t i; i < vec.size(); ++i)
    {
        a = vec.at(i);
        b = vec.at(i+1);
        if (a > b)
        {
            c = a - b + 1;
            vec.at(i) = c;      
        }
        else if (a < b)
        {
            c = b - a + 1;
            vec.at(i+1) = c;            
        }
        else
            a = c;
        
        result += a - c;
    }
    return result;
}
1
Эксперт С++
4986 / 3093 / 456
Регистрация: 10.11.2010
Сообщений: 11,170
Записей в блоге: 10
23.02.2015, 20:10
Цитата Сообщение от Тамика Посмотреть сообщение
Somebody, это было в начальном условии.
На самом деле, не было.
Тамика, как на счёт этого поста?
0
Модератор
Эксперт CЭксперт С++
 Аватар для sourcerer
5288 / 2376 / 342
Регистрация: 20.02.2013
Сообщений: 5,773
Записей в блоге: 20
23.02.2015, 20:13
Переменным a, b, c забыл сразу ноль присвоить. И в последней ветке else надо наоборот c = a.
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
23.02.2015, 20:20
Цитата Сообщение от Тамика Посмотреть сообщение
Кол-во уменьшений - кол-во единиц, на которые были уменьшены все числа по достижении плавной последовательности.
Задача остается некорректной.
Пример.
1 способ.
5 3 1 4 // исходное
2 1 0 2 =5//количество изменений
3 2 1 2 // результат
2 способ.
5 3 1 4 // исходное
0 1 2 0 =3//количество изменений
5 4 3 4 // результат

Или я снова что-то упустил?
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 20:24  [ТС]
Цитата Сообщение от castaway Посмотреть сообщение
На самом деле, не было.
Тьфу ты, под конец дня совсем не соображаю. Максимальная, а не минимальная.
Код потестирую, как до компа доберусь, ибо домой еду.
0
2444 / 1842 / 406
Регистрация: 15.12.2013
Сообщений: 8,243
23.02.2015, 20:24
Цитата Сообщение от castaway Посмотреть сообщение
как на счёт этого поста?
Code
1
2
3
5 3 1 4 
4 2 1 2 
4
после 4 по условию 2 идти не может.
0
Котовчанин
942 / 482 / 200
Регистрация: 16.02.2010
Сообщений: 3,338
Записей в блоге: 35
23.02.2015, 20:26  [ТС]
Цитата Сообщение от S_el Посмотреть сообщение
Или я снова что-то упустил?
Да.
Используем только уменьшение.

Добавлено через 1 минуту
gru74ik, через некоторое время проверю - как доберусь до компа.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
23.02.2015, 20:26

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
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