Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
#1

Порядок перестановок - C++

25.10.2011, 21:58. Просмотров 1234. Ответов 6
Метки нет (Все метки)

Ребят, если сделайте одну задачку, буду очень вам признателен, спасибо заранее вам!
Дано число N и K. Выведите K-ую перестановку в лексикографическом порядке из всех N! N-элементных перестановок.

Входные данные
В первой строке входного файла записано натуральные числа N, K (1 <= N <= 20, 1 <= K <= 2000000000). Гарантируется, что 1 <= K <= N!.

Выходные данные
Выведите искомую перестановку.

Пример

Ввод
3 2

Вывод
1 3 2

Потратьте немного вашего времени, если можете, спасибо!
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.10.2011, 21:58
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Порядок перестановок (C++):

Порядок отрицательных членов изменить на обратный, порядок неотрицательных сохранить - C++
Задача (нужно все 3 пункта в 1 программе сделать) Прошу Помочь В условиях задания 3 а) порядок отрицательных членов изменить на...

Количество перестановок - C++
Здравствуйте! Как подсчитать количество сделанных перестановок в результате сортировки массива методом вставки? Буду очень благодарен. ...

Лексикографическое порождение перестановок - C++
Первая ячейка массива получает значение из -1 ячейки массива в строке while (A &gt; A) i--; Как исправить? генерация работает нормально, но...

Задача на количество перестановок - C++
На вход подаем число предметов, которые человек берет с разных мест. На выход должно выдать число - количество способов вернуть каждое из...

Число перестановок QuickSort - C++
Здравствуйте! Подскажите пожалуйста, как можно посчитать число перестановок QuickSort. Имеется массив на 10,000 элементов

Выведение всех перестановок - C++
Драсте, я вот все время писал на паскале и мне с трудом дается переход на c++. Не могу сделать и простых вещей, просто не разбираюсь в...

6
PointsEqual
ниначмуроФ
838 / 522 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
25.10.2011, 22:02 #2
пример корректен?
1
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
25.10.2011, 22:35  [ТС] #3
Цитата Сообщение от PointsEqual Посмотреть сообщение
пример корректен?
да, точно

Добавлено через 26 минут
Не получается?
0
PointsEqual
ниначмуроФ
838 / 522 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
25.10.2011, 22:39 #4
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
41
42
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
std::string Sequence(int n)
{
    stringstream d;
 
    for (int i = 1; i < n + 1; ++i)
        d << i;
    return d.str();
}
 
std::string PermutationK(int n, int k)
{
    std::string seq = Sequence(n);
 
 
    int i = 1;
    //while(i < k)
    //{
        while (next_permutation(seq.begin(), seq.end()))
        {
 
 
        ++i;
        //cout << seq << endl;
        //cin.get();
        if (i >= k)
            return seq;
        }
    //}
}
 
int main()
{
    cout << "Res = " << PermutationK(3,2);
    return 0;
}
потестируй
1
Shato
2 / 2 / 0
Регистрация: 16.03.2011
Сообщений: 82
25.10.2011, 22:50  [ТС] #5
чет не получается через пробел вывод сделать
0
PointsEqual
ниначмуроФ
838 / 522 / 33
Регистрация: 12.10.2009
Сообщений: 1,915
25.10.2011, 22:54 #6
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
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
std::string Sequence(int n)
{
    stringstream d;
 
    for (int i = 1; i < n + 1; ++i)
        d << i;
    return d.str();
}
 
 
std::string WithSpace(std::string const & str)
{
    std::string res = "";
    int SIZE = str.size();
    for (int i = 0; i < SIZE; ++i)
        res = res + str[i] + " ";
 
    return res;
}
 
 
void PermutationK(int n, int k)
{
    std::string seq = Sequence(n);
 
 
    int i = 1;
 
        while (next_permutation(seq.begin(), seq.end()))
        {
            ++i;
            if (i >= k)
            {
                cout << "Res = " << WithSpace(seq) << endl;
                break;
            }
        }
}
 
int main()
{
    PermutationK(5,2);
    return 0;
}
1
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
25.10.2011, 23:04 #7
PointsEqual, эта задача на комбинаторику. При тех значениях N и К, которые заданы - вычисление затянется на долго.

Shato, Вот почти Ваша задача:
Отличие только в том, в Вашем варианте нужно использовать __int64.
Вот код для той задачи (когда-то давно делал):
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
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
int fac(int a)
{
    if(a==0 || a==1)
        return 1;
    int temp=1;
    for(int i=2; i<=a; i++)
        temp*=i;
    return temp;
}
 
int main(){
    int N, K, *mas_rez, *mas, i, j, col, temp;
  freopen("input.txt","r",stdin);
 freopen("output.txt","w",stdout);
 scanf("%d %d", &N, &K);
 mas_rez=new int[N];
 mas=new int[N];
 for(i=0; i<N; i++)
     mas[i]=0;
 for(i=0; i<N; i++)
 {
     if(i<N-1)
     {
     temp=fac(N-i);
     temp/=(N-i);
     temp=((K-1)/temp)%(N-i);
     col=0;
     temp++;
     for(j=0; j<N && temp!=0; j++)
     {
         if(mas[j]==0)
            temp--;
         if(temp==0)
             col=j;
     }
     mas_rez[i]=col+1;
     mas[col]=1;
     }
     else
     {
         for(j=0; j<N; j++)
             if(!mas[j])
                 mas_rez[N-1]=j+1;
     }
 }
 for(i=0; i<N; i++)
     printf("%d ", mas_rez[i]);
   return 0;
}
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.10.2011, 23:04
Привет! Вот еще темы с ответами:

Рекурсивный алгоритм перестановок - C++
Подскажите, почему не происходит замусоривания массива used, в котором хранятся данные об использованных элементах начальной строки, и...

Формула подсчета перестановок - C++
Здравствуйте, уважаемые пользователи! На этот раз, обращаюсь к гуру комбинаторики, за простым советом. Есть вот такая несложная задача: ...

Генерация перестановок. Что не так? - C++
Подскажите, пожалуйста, почему не работает, эта программа должна генерировать все перестановки #include &lt;iostream&gt; #include &lt;vector&gt;...

Подсчет количества операций и перестановок - C++
помогите пожалйуста как написать в с++ дан массив в нем идет на выбор сортировка 1.простыми вставками 2. сортировка шелла. чтобы программа...


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

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

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