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

Как реализовать перемножение перестановок - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Программирование с использованием файлов http://www.cyberforum.ru/cpp-beginners/thread1060984.html
Помогите начинающему программисту: Распечатать анкетные данные студентов-отличников из интересующей вас группы HELPPPPPPPPPPPP!!!!!!!!!!!!!!
C++ Вывести список очередности предоставления мест в общежитии. Помогите написать КОД: Для получения места в общежитии формируется список студентов, который включает ФИО студента, группу, средний балл, доход на члена семьи. Общежитие в первую очередь предоставляется тем, у кого доход на члена семьи меньше двух минимальных зарплат, затем остальным в порядке уменьшения среднего балла. Вывести список очередности предоставления мест в общежитии. И ВСЕХ С... http://www.cyberforum.ru/cpp-beginners/thread1060983.html
Реализовать поиск данных по ключевым словам на компьютере и в интернете C++
Получится ли написать программу с интерфэйсом?Ну что-то пишешь,а она отвечает ну или по словам находит то что нужно или в компе или в инете...
Данные класса C++
Ребят, подскажите пожалуйста, как проинициализировать начальными значениями данные класса, допустим у меня есть класс: class Plane { public: XMMATRIX GetWorldMatrix(); Plane(); private: XMMATRIX World; };
C++ Заданы матрицы А, В, С, D, каждая из которых содержит по три строчки и по три столбца. Перемножить матрицы Р и Q http://www.cyberforum.ru/cpp-beginners/thread1060963.html
Заданы матрицы А, В, С, D, каждая из которых содержит по три строчки и по три столбца. Перемножить матрицы Р и Q, полученные в результате сложения матриц: Р=А+В; Q=C+D. Сложение матриц оформить в виде подпрограммы. Исходные данные даны!
C++ Эксперты! Одномерный массив неповторяющихся чисел не могу понять почему криво работает Задание: Нужно вывести массив из случайных чисел. Размер массива 8. Случайные числа от 1 до 8. Числа не должны повторяться. #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main() { setlocale(LC_CTYPE,"rus"); подробнее

Показать сообщение отдельно
IrineK
Заблокирован
03.01.2014, 20:29     Как реализовать перемножение перестановок
Вот хэдер с реализацией алгоритма, описанного выше:

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
//генератор матриц представления для групп перестановок порядка 2 <= N <= 12 
 
#include <stdio.h>
#include <stdlib.h>
 
//вся группа в матричном представлении
typedef struct _MGroup
{   int dim;    //размерность группы
    int all;    //общее кво элементов (перестановок)
    int ***m;   //указатель на массив матриц всех элементов (перестановок) all x dim x dim
} MGroup;
 
//создаем квадратную матрицу NxN
int **CreateMatrixNxN (int N)
{   int i,j;
    int **res = (int**) malloc (N*sizeof(int*));
    for (j = 0; j<N; j++)                       //строим не по строкам, а по столбцам, почему - понятно из алгоритма
        res[j] = (int*) malloc (N*sizeof(int));
 
    for (j = 0; j<N; j++)       //сразу заполняем нулями
        for (i = 0; i<N; i++)
            res[i][j] = 0;
 
    return res;
}
 
//освобождаем память от матрицы NxN
void DestroyMatrixNxN (int **M, int N)
{   int j = N;
    while (--j > -1)
        free (M[j]);
    free (M);
}
 
//просто факториал )
int fact (int N)
{   if (!N)
        return 1;
    
    int res = N;
    while (--N)
        res *= N;
    return res;
}
 
//создаем группу как совокупность всех матриц перестановок - N! штук размерностью NxN
MGroup *CreateGroup (int DIM)
{   MGroup *group = (MGroup*) malloc (sizeof(MGroup));
    group->dim = DIM;
    group->all = fact (DIM);
 
    group->m = (int***) malloc (group->all * sizeof(int**));
    for (int k = 0; k<group->all; k++)
        group->m[k] = CreateMatrixNxN (DIM);
    
    return group;
}
 
//освобождаем память от группы
void DestroyGroup (MGroup *group)
{   int k = group->all;
    while (--k > -1)
        DestroyMatrixNxN (group->m[k], group->dim);
    free (group->m);
    free (group);
}
 
//вывод на экран отдельной матрицы перестановки
void ShowMatrixNxN (int **M, int N)
{   int i,j;
    for (j = 0; j<N; j++)
    {   for (i = 0; i<N; i++)
            printf("%5d", M[i][j]);
        printf("\n");
    }
    printf("\n");
}
 
//вывод на экран всей группы - всех матриц перестановок
void ShowGroup (MGroup *group)
{   int all = group->all;
    for (int k = 0; k<all; k++)
        ShowMatrixNxN (group->m[k], group->dim);
}
 
//начало итерации - заполнение двух матриц группы S2
MGroup *CreateS2 ()
{   MGroup *S2 = CreateGroup (2);
    S2->m[0][0][0] = S2->m[0][1][1] = 1;
    S2->m[1][0][1] = S2->m[1][1][0] = 1;
    return S2;
}
 
//подстановка столбцов матрицы предыдущей итерации в матрицу 
//итерации текущей
void FillColumnPrev (int *cur, int *prev, int N)
{   for (int i = 1; i<N; i++)
        cur[i] = prev[i-1];
}
 
//чисто символически )
void FillColumnOne (int *col)
{   col[0] = 1;
}
 
//собственно - решение задачи
MGroup *CreateSN (int N)
{   int indPrev = 2, indNext = 3, i, j, k, qPrev = 1, qNext;
    MGroup *prev = CreateS2 ();
    MGroup *next;
 
    while (indPrev < N)
    {   next = CreateGroup (indNext);
        for (i = 0, qNext = 0, qPrev *= indPrev; i<qPrev; i++)
        {   for (j = 0; j<indNext; j++, qNext++)
            {   FillColumnOne (next->m[qNext][j]);
                for (k = 1; k<indNext; k++)
                    FillColumnPrev (next->m[qNext][(j+k)%indNext], prev->m[i][k-1], indNext);
            }
        }
        indPrev++;
        indNext++;
        DestroyGroup (prev);
        prev = next;
    }
    return prev;
}
 
Текущее время: 12:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru