0 / 0 / 0
Регистрация: 22.03.2014
Сообщений: 16
1

Структуры данных для С++. Перестановки

02.04.2015, 13:14. Показов 2323. Ответов 11
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Не получается решить задачу

На столе лежит стопка из N книг, условно пронумерованных сверху вниз от 1 до N.
Некто решил перепутать все книги в стопке и действует следующим образом: берёт стопку из K верхних книг, переворачивает и помещает её в низ стопки, затем снова делает то же самое, и так M раз. Например, если N=5, K=3, M=2, то у нас получается такая последовательность: 1 2 3 4 5 -> 4 5 3 2 1 -> 2 1 3 5 4.
Исходные данные
3 числа N, K, M, разделенные пробелами.
Ограничения: N от 1 до 10000, K от 1 до 100, K<=N, M от 1 до 10000.
Результат
Перестановка, которая получится в результате
Пример
Исходные данные - 5 3 2
Результат - 2 1 3 5 4
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.04.2015, 13:14
Ответы с готовыми решениями:

Понятие структуры данных. Элементарные структуры данных. Простые структуры данных
Понятие структуры данных. Элементарные структуры данных. Простые структуры данных: методы...

Функция swap перестановки значений двух переменных для данных разных типов. Используйте template
не могу решить ( честно говоря вообще не понимаю его ) ((((( Напишите функцию swap перестановки...

Описать класс для структуры данных
Описать структуру с именем AEROFLOT, содержащую следующие поля: 1. Описать структуру с именем...

Структуры данных для хранения и работы с матрицами
Доброго времени суток! Есть матрица, у которой надо периодически удалять то столбец целиком, то...

11
1 / 1 / 2
Регистрация: 06.02.2015
Сообщений: 5
02.04.2015, 14:24 2
если коротко:
создать ещё один массив и записать туда перечень К-книг;
в N массиве сдвинуть элементы на +К;
массив книг К вставить в освободившееся пространство в начале массива N;
повторять перечисленное М раз;

или в чем сложность?
0
0 / 0 / 0
Регистрация: 28.03.2018
Сообщений: 16
30.01.2019, 14:40 3
DeadXipster удалось в итоге решить задачу?
Сам тоже ищу ответ, неравнодушные помогите дураку
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
30.01.2019, 15:54 4
Вообще-то это задача на циклический сдвиг массива. Немного усложненная переворотом.
Каждое действие разбивается на 2.
- Переворот верхних K элементов (совсем просто)
- Циклический сдвиг на K элементов (рассматривалась на форуме многократно, будет время - поищу)
Но, конечно, можно обойтись без дополнительного массива.
1
2456 / 1061 / 481
Регистрация: 17.11.2018
Сообщений: 2,740
31.01.2019, 00:17 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
26
27
28
int main()
{    
    int * ar, N, K, M;
 
    cin >> N >> K >> M;
    ar = new int[N];
 
    for( int i = 0; i < N; i++ )
        ar[i] = i + 1;
    do
    {
        for( int k = K - 1; k >= 0; k-- )
        {
            int tmp = ar[k];
            for( int i = k; i < N - 1; i++ )
                ar[i] = ar[i + 1];
            ar[N - 1] = tmp;
        }
 
    } while( --M );
 
    for( int i = 0; i < N; i++ )
        cout << ar[i] << ' ';
    cout << endl;
 
    delete [] ar;
    return 0;
}
1
0 / 0 / 0
Регистрация: 28.03.2018
Сообщений: 16
06.02.2019, 22:41 6
Большое спасибо за решение и подсказки. Теперь думаю как упростить решение отменой переворота К элементов.
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.02.2019, 23:02 7
Цитата Сообщение от razorvaka Посмотреть сообщение
думаю как упростить решение отменой переворота К элементов.
В каком смысле? То есть в твоей задаче вообще перевороты не происходят? Тогда все более чем просто! Или я неправильно понял тебя?
0
0 / 0 / 0
Регистрация: 28.03.2018
Сообщений: 16
06.02.2019, 23:17 8
верно, в моей задаче перевороты не происходят. выше представленный код от analogov net решает правильно и с переворотами, мне бы упростить решение
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
06.02.2019, 23:43 9
razorvaka,
C++
1
2
3
int knew = (K*M)%N;
// И сдвинуть циклически на это knew
// хорошие алгоритмы циклических сдвигов (без knew-кратного сдвига на 1) на форуме есть
Тут может возникнуть маленькая проблемка. Если K*M может вылезти за допустимые значения int-а. Но она легко и непринужденно решается
0
0 / 0 / 0
Регистрация: 28.03.2018
Сообщений: 16
09.02.2019, 22:36 10
Помогите оптимизировать, решает за 2,99 сек, предел времени - 1 сек.

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
#include <iostream>
 
using namespace std;
int main()
{
    int * ar, N, K, M;
 
    cin >> N >> K >> M;
    if (N >= 1 && N <= 10000 && M >= 0 && M <= 10000 && K >= 0 && K <= 101 && K <= N)
    {
        ar = new int[N];
 
        for (int i = 0; i < N; i++)
            ar[i] = i + 1;
        do
        {
            for (int k = K; k < N; k++)
            {
                int tmp = ar[N - 1];
                for (int i = N - 1; i > 0; i--)
                    ar[i] = ar[i - 1];
                ar[0] = tmp;
            }
 
        } while (--M);
 
        for (int i = 0; i < N; i++)
            cout << ar[i] << ' ';
        cout << endl;
    }
    else if (std::cout << "chislo" << N << "ne vhodit v diapazon" << std::endl);
 
    system("pause");
}
0
Диссидент
Эксперт C
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
09.02.2019, 22:53 11
razorvaka, В чем задача-то? И какое она имеет отношение?

Добавлено через 3 минуты
razorvaka, то что тебе сказали в посте 9 ты или не прочитал или не понял.
Задача другая. Создавай другую тему. Найдутся доброхоты.
0
0 / 0 / 0
Регистрация: 28.03.2018
Сообщений: 16
09.02.2019, 23:19 12
Создал тему: Оптимизировать задачу на перестановки
0
09.02.2019, 23:19
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.02.2019, 23:19
Помогаю со студенческими работами здесь

Функция для диалогового заполнения данных структуры
имеется вот такая структура #include &lt;windows.h&gt; #include &lt;iostream&gt; using namespace std;...

Структуры: Организовать базу данных для спортивного клуба
Организовать базу данных для спортивного клуба со следующей информацией про штангистов: – ФИО; –...

Динамические структуры данных. Программа ввода в структуры и вывода информации из неё.
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об...

Выбор структуры данных для вставки, удаления и поиска минимума за log(n)
Добрый день!Подскажите какую нибудь структуру, чтобы были операции: вставка,удаление,и поиск...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru