Форум программистов, компьютерный форум CyberForum.ru

Номер перестановки - C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
pashazt
0 / 0 / 0
Регистрация: 18.04.2013
Сообщений: 42
17.11.2013, 14:35     Номер перестановки #1
Надо написать программу которая выдаёт номер перестановки, и при етом не генерирует сами перестановки.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.11.2013, 14:35     Номер перестановки
Посмотрите здесь:

C++ Найти порядковый номер слова максимальной длины в строке и номер позиции, с которой оно начинается
C++ Дан номер года, определить соответствующий ему номер столетия
Определить номер строки и номер столбца матрицы, на пересечении которых находятся требуемые элементы C++
C++ Необходимо найти номер строки и номер столбца, в которых находится наименьший элемент.
C++ Найти номер строки и номер столбца, в котором находится минимальный элемент матрицы
C++ Выяснить номер квартала и номер полугодия по введенному номеру месяца
Матрица двузначных чисел: первая цифра указывает на номер строки, а вторая – на номер столбца C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
VladislavTepes
 Аватар для VladislavTepes
78 / 78 / 5
Регистрация: 27.06.2012
Сообщений: 555
Записей в блоге: 1
17.11.2013, 14:45     Номер перестановки #2
pashazt, перестановки чего и куда, я не очень понимаю.
pashazt
0 / 0 / 0
Регистрация: 18.04.2013
Сообщений: 42
17.11.2013, 14:54  [ТС]     Номер перестановки #3
Yу ,например, возьмём лексикографические перестановки. Есть универсальное множество : 1234.
Вводим с клавиатуры 1342 и получаем номер перестановки - 4.
Tulosba
:)
Эксперт С++
4382 / 3225 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
17.11.2013, 15:18     Номер перестановки #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> v= {1,2,3,4};
    std::vector<int> u= {1,3,4,2};
 
    int i = 0;
    while( u != v )
    {
        std::next_permutation( std::begin(v), std::end(v) );
        i++;
    }
 
    std::cout << i << std::endl;
}
pashazt
0 / 0 / 0
Регистрация: 18.04.2013
Сообщений: 42
17.11.2013, 15:23  [ТС]     Номер перестановки #5
У вас происходит поиск номера с помощью генерации перестановок. А надо без генерации.
Tulosba
:)
Эксперт С++
4382 / 3225 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
17.11.2013, 15:27     Номер перестановки #6
Цитата Сообщение от pashazt Посмотреть сообщение
А надо без генерации.
Имхо, это как перейти от первого элемента линейного списка к последнему, не пробегая элементы между ними.
pashazt
0 / 0 / 0
Регистрация: 18.04.2013
Сообщений: 42
17.11.2013, 15:33  [ТС]     Номер перестановки #7
Вот я тоже не знаю как ето сделать, хотя преподователь чётко сказал - без генерации!
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
17.11.2013, 18:27     Номер перестановки #8
не утверждаю, но вроде логично.
идем слева направо. для позиции i вклад в ответ равен лексикографическая позиция i-ого элемента * факториал оставшейся длины. ответ только в 0-индексации.
например, 1342.
ans = 0 * 3! (1 - лексикографические первый элемент из оставшихся)
+ 1 * 2! (3 - лексикографически второй элемент из оставшихся)
+ 1 * 1! (4 - лексикографически второй элемент из оставшихся)
+ 0 * 0! (2 - лексикографически первый элемент из оставшихся).

2134. ans = 1 * 3! + 0 * 2! + 0 * 1! + 0 * 0!.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.11.2013, 19:08     Номер перестановки
Еще ссылки по теме:

Вывести на экран порядковый номер слова максимальной длины и номер позиции в строке, с которой оно начинается C++
Вывести порядковый номер слова максимальной длины и номер позиции в строке, с которой оно начинается C++
C++ При выводе массива выводить номер строки и номер столбца
Найти номер строки и номер столбца матрицы, в которых находятся максимальный элемент C++
C++ Перестановки: чтобы любые две соседние перестановки отличались только порядком двух соседних элементов

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

Или воспользуйтесь поиском по форуму:
pashazt
0 / 0 / 0
Регистрация: 18.04.2013
Сообщений: 42
17.11.2013, 19:08  [ТС]     Номер перестановки #9
Вот пытался написать, но выводит неправильно.

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
#include <iostream>
 
using namespace std;
 
int fact(int n)
{
    int fact = 1;
    for(int i = n; i > 0; i--)
    {
        fact = i * fact;
    }
    return fact;
}
 
int main()
{
    const int n = 4;
    
    int c = 0;
    int m[n] = {1,2,4,3};
    int m1[16];
    
    long int sc = 1;
 
    for(int i = 0; i<=n; i++)
    {
        int j = 1, sq = 0;
         while(j < m[i])
            {
                
                 if(j!=m1[i])
                     {
                         sq++;
                     }
                 j++;
            }
  
         m1[i] =m1[i] +  m[i];
         sc = sc + fact(n-(i+1)) * sq;   
        
    }
 
     cout << sc << endl;;
        system("pause");
}
Yandex
Объявления
17.11.2013, 19:08     Номер перестановки
Ответ Создать тему
Опции темы

Текущее время: 16:48. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru