Форум программистов, компьютерный форум, киберфорум
Наши страницы
C для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
1

Найти сумму двух сильно разреженных матриц

24.06.2016, 10:12. Просмотров 1157. Ответов 13
Метки нет (Все метки)

Найти сумму двух сильно разреженных матриц A(m,n) и B(m,n), хранящихся в упакованном виде. Результат получить также в упакованном виде, а вывести — в обычном.
Ну упакую я матрицу в три массива, а вот как сложить их обе в таком виде? Вообще не догоняю. Помогите, товарищи.
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2016, 10:12
Ответы с готовыми решениями:

Найти сумму двух матриц
Помогите, пожалуйста написать программу найти сумму двух матриц в си (С). Размеры массива вводить с...

Найти произведение двух матриц
Добрый вечер. У меня возникла проблема с реализацией данной задачи: Найти произведение двух матриц...

Найти произведение двух симметричных матриц
Найти произведение двух симметричных матриц и . Матри- цы хранятся в одномерных массивах, где...

Найти максимальный элемент двух заданных матриц
Ввести два двумерных массива из 8 вещественных чисел. Найти максимальный эл и напечатать его номер....

Умножение треугольных матриц«Методы обработки разреженных матриц»
Нужно перемножить треугольные матрицы в обычном виде и в свёрнутом. С обычным проблем нет. Доступ...

13
Байт
Эксперт C
20977 / 13234 / 2789
Регистрация: 24.12.2010
Сообщений: 27,858
24.06.2016, 10:14 2
Typ0k, Покажите, как пакуете. Достаточно показать структуру упакованной матрицы.
0
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
24.06.2016, 10:49  [ТС] 3
В три массива. Массив ненулевых значений, массив номеров строк и массив номеров столбцов этих значений

Добавлено через 31 минуту
Допустим, имея матрицу 5х5:

0 0 0 1 1
2 2 3 0 0
0 0 8 0 0
7 0 0 6 5
0 0 10 0 0

упакую ее следующим образом:

values{1 1 2 2 3 8 7 6 5 10}(массив ненулевых значений)
vectrs(или cols){0 0 1 1 1 2 3 3 3 4}(строки)
rows{3 4 0 1 2 2 1 3 4 2}(столбцы)
0
Байт
Эксперт C
20977 / 13234 / 2789
Регистрация: 24.12.2010
Сообщений: 27,858
24.06.2016, 11:07 4
Цитата Сообщение от Typ0k Посмотреть сообщение
В три массива.
Так как вы ничего не сказали про упорядоченность этих массивов, будем считать их неупорядоченными
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
double *A1; int k1, *m1, *n1;  // k1, k2 - размер упакованных массивов
double *A2; int k2, *m2, *n2;
double *C; int kc, *mc, *nc;
C = (double *)malloc((k1+k2)*sizeof(double));
mc = (int *)malloc((k1+k2)*sizeof(int));
nc = (int *)malloc((k1+k2)*sizeof(int));
for(i=j=0; i<k1; i++) {
   s = A1[i];
   for(i2 = 0; i2<k2; i2++) {
      if (m2[i2]==m1[i] && n2[i2]==n1[i]) {
        s += A2[i2];
        break;
      }
       if (s!=0) {
          C[j++] = s; mc[j] = m1[i]; nc[j] = n1[i];
       } 
   }
}
for (i=0; i<k2; i++) {  // Собираем пропущенные из A2
   for(i1 = 0; i1<k1; i1++) {
      if (m2[i]==m1[i1] && n2[i]==n1[i1]) break;  // уже учтено
      C[j++] = A2[i1];
      mc[j] = m2[i];
      nc[j] = n2[i];
   }
}
kc = j;
C = (double *)realloc(C,kc*sizeof(double));
mc = (int *)realloc(mc, kc*sizeof(int));
nc = (int *)malloc(nc*kc*sizeof(int));
Вот как-то так. Псевдокод. Писал на коленке, не проверял. Но идея, надеюсь, понятна.
Оформление, недостающие описания переменных, ввод и прочее - оставляю вам.
Конечно, код не самый оптимальный

Добавлено через 4 минуты
Цитата Сообщение от Typ0k Посмотреть сообщение
В три массива
Удобнее, конечно, использовать структуру типа
C
1
2
3
4
5
typedef struct {
  double value;
  int cols;
  int row;
} CELL;
Но сути алгоритма это не меняет
1
24.06.2016, 11:07
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
24.06.2016, 11:11  [ТС] 5
Байт, спасибо, буду разбираться, если что, обращусь
0
Байт
Эксперт C
20977 / 13234 / 2789
Регистрация: 24.12.2010
Сообщений: 27,858
24.06.2016, 11:32 6
Typ0k, вообще, работа с разреженными матрицами - довольно серьезный и хорошо разработанный раздел вычислительной математики
https://ru.wikipedia.org/wiki/%D0%A0...B8%D1%86%D0%B0
0
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
24.06.2016, 11:35  [ТС] 7
Байт, самое интересное, что вычислительная математика у меня еще не началась, а в летней практике уже попадаются задания из нее
0
Байт
Эксперт C
20977 / 13234 / 2789
Регистрация: 24.12.2010
Сообщений: 27,858
24.06.2016, 11:46 8
Цитата Сообщение от Typ0k Посмотреть сообщение
вычислительная математика у меня еще не началась, а в летней практике уже попадаются задания из нее
Ничего страшного. Обычная практика высших учебных заведений. Программирование ведь проходили? А грань между ВМ и Программированием очень размыта. Да и что такое ВМ - я бы с ходу не сказал.

Не по теме:

У нас был случай на 1-м курсе. На одной из первых лекций по физике нам рассказывают про функцию Дирака. А мозг мехматского первокурсника устроен уже так, что этот дирачье чудище никак в качестве функции в него не лезет. А физикам - плевать! Только на третьем курсе нам стало ясно, что это - функционал.:D

0
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
24.06.2016, 20:45  [ТС] 9
Байт,
Цитата Сообщение от Байт Посмотреть сообщение
C
1
2
3
4
5
6
7
8
9
10
11
12
for(i=j=0; i<k1; i++) {
  s = A1[i];
  for(i2 = 0; i2<k2; i2++) {
    if (m2[i2]==m1[i] && n2[i2]==n1[i]) {
     s += A2[i2];
     break;
    }
    if (s!=0) {
      C[j++] = s; mc[j] = m1[i]; nc[j] = n1[i];
    } 
  }
}
Объясните пожалуйста этот кусок, просто здесь, как мне видится, будут записываться одинаковые числа друг за другом в наш массив значений
0
Байт
Эксперт C
20977 / 13234 / 2789
Регистрация: 24.12.2010
Сообщений: 27,858
24.06.2016, 22:52 10
Цитата Сообщение от Typ0k Посмотреть сообщение
как мне видится, будут записываться одинаковые числа друг за другом в наш массив значений
Да, кажись, ошибся. Строчки надо немного переставить
C
1
2
3
4
5
6
7
8
9
10
11
12
for(i=j=0; i<k1; i++) {  // Просматриваем А1
   s = A1[i];
   for(i2 = 0; i2<k2; i2++) {  // Ищем в А2 такой же индекс
      if (m2[i2]==m1[i] && n2[i2]==n1[i]) { // Нашли.
        s += A2[i2];  // Суммируем
        break;  // Вываливаенмся из цикла - чего еще искать-то?
      }
   }
    if (s!=0) {  // Если получился не 0, создаем новый элемент
         C[j++] = s; mc[j] = m1[i]; nc[j] = n1[i];
    } 
}
Добавлено через 1 минуту

Не по теме:

За поправку с меня спасибка!

0
easybudda
Модератор
Эксперт JavaЭксперт CЭксперт С++
10537 / 6239 / 1567
Регистрация: 25.07.2009
Сообщений: 11,881
25.06.2016, 03:44 11
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Для разнообразия другой вариант разряженной матрицы. Велосипед делать было лень, взял GHashTable из GLib
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
#include <stdio.h>
#include <glib.h>
 
typedef struct SPARSE_ARRAY {
    gsize rows;
    gsize columns;
    GHashTable * hash;
} sparse_array_t;
 
sparse_array_t * sparse_array_new(gsize rows, gsize columns) {
    sparse_array_t * sa = g_new(sparse_array_t, 1);
    
    sa->rows = rows;
    sa->columns = columns;
    sa->hash = g_hash_table_new_full(g_direct_hash, g_direct_equal, NULL, g_free);
    
    return sa;
}
 
void sparse_array_free(sparse_array_t * sa) {
    g_hash_table_destroy(sa->hash);
    g_free(sa);
}
 
void sparse_array_set_at(sparse_array_t * sa, const gsize row, const gsize column, const gdouble value) {
    if ( row >= sa->rows )
        g_error("row index out of bounds\n");
    else if ( column >= sa->columns )
        g_error("column index out of bounds\n");
    else {
        gdouble * pVal = g_new(gdouble, 1);
        *pVal = value;
        g_hash_table_insert(sa->hash, GSIZE_TO_POINTER(row * sa->columns + column), (gpointer)pVal);
    }
}
 
gdouble * sparse_array_get_at(sparse_array_t * sa, const gsize row, const gsize column) {
    if ( row >= sa->rows )
        g_error("row index out of bounds\n");
    else if ( column >= sa->columns )
        g_error("column index out of bounds\n");
    else
        return (gdouble*)g_hash_table_lookup(sa->hash, GSIZE_TO_POINTER(row * sa->columns + column));
}
 
/*****************************************************************/
 
const char * menuItems[] = {
    "help", "insert", "retrive", "exit", NULL
};
 
int main(void) {
    int rows, columns, choise;
    gboolean finish;
    sparse_array_t * sa;
    
    printf("Space separated rows and columns: ");
    if ( scanf("%d%d", &rows, &columns) != 2 )
        g_error("Wrong input!\n");
    
    sa = sparse_array_new(rows, columns);
    
    finish = FALSE;
    while ( ! finish ) {
        printf("[0 = help]> ");
        if ( scanf("%d", &choise) != 1 )
            g_error("Wrong input!\n");
        
        switch(choise) {
            case 0: {
                int i;
                
                for ( i = 0; menuItems[i]; ++i )
                    printf("%d - %s\n", i, menuItems[i]);
                printf("\n");
                
                break;
            }
            case 1: {
                int row, column;
                double val;
                
                printf("Space separated row, column and value: ");
                if ( scanf("%d%d%lf", &row, &column, &val) != 3 )
                    g_error("Wrong input!\n");
                sparse_array_set_at(sa, row, column, val);
                
                break;
            }
            case 2: {
                int row, column;
                double * valptr;
                
                printf("Space separated row and column: ");
                if ( scanf("%d%d", &row, &column) != 2 )
                    g_error("Wrong input!\n");
                
                valptr = sparse_array_get_at(sa, row, column);
                if ( ! valptr )
                    printf("NULL\n");
                else
                    printf("%f\n", *valptr);
                
                break;
            }
            case 3: {
                finish = TRUE;
                
                break;
            }
            default:
                g_printerr("Unknown option!\n");
        }
    }
    
    sparse_array_free(sa);
    
    return 0;
}
Код
andrew@debppc:~/workspace/c/class$ gcc -Wall sparse_array.c `pkg-config --cflags --libs glib-2.0`
andrew@debppc:~/workspace/c/class$ ./a.out 
Space separated rows and columns: 4 5
[0 = help]> 0
0 - help
1 - insert
2 - retrive
3 - exit

[0 = help]> 1
Space separated row, column and value: 1 2 3.14
[0 = help]> 2
Space separated row and column: 1 2
3.140000
[0 = help]> 2
Space separated row and column: 3 3
NULL
[0 = help]> 3
andrew@debppc:~/workspace/c/class$
3
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
26.06.2016, 23:54  [ТС] 12
Байт, в набросал пробный код ч кучей переменных, так что особо не ругайтесь:

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
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#include <malloc.h>
 
void read_mas(int t[], int m)
{
    int i;
    for (i=0; i<m; i++)
        scanf("%d", &t[i]);
}
 
int sum_matr(int A1[],int A2[],int C[],int k1,int k2,int kc,int m1[],int m2[],int n1[],int n2[],int mc[],int nc[], int b[5][5])
{
    int i,j=0,i2,i1,t,p,k;
    int s;
 
    for(i=0; i<k1; i++)
    {
        s = A1[i];
        for(i2 = 0; i2<k2; i2++)
        {
             if (m2[i2]==m1[i] && n2[i2]==n1[i])
             {
                 s+= A2[i2];
                 break;
             }
        }
               if (s!=0)
             {
                C[j] = s;
                mc[j] = m1[i];
                nc[j] = n1[i];
                j++;
             }
    }
    for (i=0; i<k2; i++)
    {
         for(i1 = 0; i1<k1; i1++)
         {
              if (m2[i]==m1[i1] && n2[i]==n1[i1])
                  break;
         }
              C[j++] = A2[i];
              mc[j] = m2[i];
              nc[j] = n2[i];
 
    }
    kc = j;
    k=0;
    i=j=0;
    while(k!=kc)
    {
        i=mc[k];
        j=nc[k];
        b[i][j]=C[k];
        k++;                               //формируем и выводим матрицу
    }
 
     for (i=0; i<5; i++)
    {
        for (j=0; j<5; j++)// до 5, так как матрицу по идее беру 5х5
            printf("%d ", b[i][j]);
        printf("\n");
    }
 
return kc;
}
 
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
 
    int A1[20]; int k1, m1[20], n1[20],k,i;
    int A2[20]; int k2, m2[20], n2[20];
    int C[150]={0}; int kc, mc[150]={0}, nc[150]={0}, b[5][5]={0};
 
    printf("Введите кол-во элементов массива значений матрицы а: ");
    scanf("%d",&k1);
    printf("Введите массив значений матрицы a: ");
    read_mas(A1,k1);
    printf("Введите массив номеров строк матрицы a: ");
    read_mas(m1,k1);
    printf("Введите массив номеров столбцов матрицы a: ");
    read_mas(n1,k1);
    printf("Введите кол-во элементов массива значений матрицы b: ");
    scanf("%d",&k2);
    printf("Введите массив значений матрицы b: ");
    read_mas(A2,k2);
    printf("Введите массив номеров строк матрицы b: ");
    read_mas(m2,k2);
    printf("Введите массив номеров столбцов матрицы b: ");
    read_mas(n2,k2);
    k=sum_matr(A1,A2,C,k1,k2,kc,m1,m2,n1,n2,mc,nc,b);
     for (i=0; i<k; i++)
        printf("%d ", C[i]);
    printf("\n");
    for (i=0; i<k; i++)
        printf("%d ", mc[i]);
    printf("\n");
    for (i=0; i<k; i++)
        printf("%d ", nc[i]);
    return 0;
}
при попытке сложить две одинаковые матрицы выдает вот что
0
Миниатюры
Найти сумму двух сильно разреженных матриц  
Typ0k
0 / 0 / 0
Регистрация: 24.06.2016
Сообщений: 7
26.06.2016, 23:56  [ТС] 13
последние три строки-это соответственно значения строки и столбцы

Добавлено через 1 минуту
ответ вроде в массивах выдает, но с лишними числами, а матрица вообще пишется криво
0
Байт
Эксперт C
20977 / 13234 / 2789
Регистрация: 24.12.2010
Сообщений: 27,858
27.06.2016, 08:46 14
Typ0k, Есть у тебя такой параметр kc. Так вот, его использование у тебя совершенно неправильно. В Си параметры передаются по значению. Впрочем, все это компенсируется другими неграмотностями и на конечный результат влияния не имеет.

Добавлено через 7 минут
Typ0k, Посмотрел еще. Похоже, моя вина.
В строчках 31-34 ты совершенно справедливо мой код изменил. Сначала C[]=, mc[j]=, nc=, а только потом j++
А в строчках 43-46 ты эту мою ошибку не поправил
0
27.06.2016, 08:46
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.06.2016, 08:46

Найти сумму двух матриц
Найти сумму двух матриц.

Найти сумму двух матриц
Найти сумму двух матриц розмер 4х4, и вычислить сумму диагональных элементов полученной матрицы

Найти сумму двух матриц
Нужно найти сумму двух матриц. Нужна помощь.


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

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

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