Заготовки для С++

nogala

У кого- нить есть готовые програмки? Интересует прога для вычисления определителя n*n.
Поделитесь, если не жалко

okunek

не жалко
http://alglib.sources.ru/matrixops/general/det.php

nogala

Что-то у меня не так.
Уже на размерности= 15 глохнет.
Может у кого-нить все-таки есть нормальная прога.
Или может ошибку найдете:
#include <stdio.h>
#include <alloc.h>
#include <stdlib.h>
#include <math.h>
#define N 15 // matrix size
int matrix[N][N];
 заполняю матрицу
void ini_matrix(int *matrix, int size)
{int k=1;
 for(int i=0;i<size;i++)
 {
   for(int j=0;j<size;j++)
   *(matrix+i*size+j)=fmod(j+k,N);
   k++;
   }
 }
  вывожу её
void show_matrix(int *matrix, int size) // this functions displays matrix
{
 for(int i=0;i<size;i++)
 {
   for(int j=0;j<size;j++)
     printf("%d ",*(matrix+i*size+j;
   printf("\n");
 }
 printf("\n");
}
  нахожу определитель
int Det(int *matrix, int const size)
{
  int *submatrix;
  int det=0;
  if (size>1)
  {
    submatrix=(int *)malloc(sizeof(int)*(size-1)*(size-1;
    for (int i=0;i<size;i++)
    {
     // creating new array (submatrix)
     for (int j=0;j<size-1;j++)
     for (int k=0;k<size-1;k++)
     *(submatrix+j*(size-1)+k)=*(matrix+(j+1)*size+(k<i?k:k+1;
     det+=*(matrix+i)*(i/2.0==i/2?1:-1)*Det(submatrix,size-1);
    }
    free(submatrix);
  } else det=*matrix;
  return det;
}
 собсно сама прога
void main(void)
{
  ini_matrix(matrix[0], N);
  show_matrix(matrix[0],N);
  // calculating determinante and displaying the result
  printf("det A = %d",Det(matrix[0],N;
}
 

Maurog

а на размерностях 2,3,4 как себя ведет?
если хорошо, то скорее всего на 15 уже переполнение идет..слишком большие числа, наверное

nogala

там все тип топ
а числа небольшие от 0 до (размерность-1)

a10063

глохнет

это как?
кстати, зачем изобретать велосипед и не воспользоваться lu-разложением? твоя прога будет значительно медленнее работать...
другое дело, если пытаться найти определитель не портя матрицу, используя O(n) доп. памяти и разумное число операций - интересно, возможно ли?

Maurog

если числа небольшие, то это не значит, что дискриминант будет маленьким...
предлагаю сделать переменную Det типом double. хотя на размерности 15 и double может не выдержать, но попробывать стоит

evgen5555

Смотрю я на идиотов и просто диву даюсь.
У чувака рекурсионный вызов вычисления определителя на порядке 15 дает 15!=1307674368000 вызовов процедуры Det, что естественно переполняет стек.

evgen5555

Приводи матрицу линейными преобразованиями к треугольному виду, чтобы выполнялось условие a_ij=0, i>j

okunek

Там вглубь 15 вызовов. С чего стеку переполняться-то?

lipa

i/2.0==i/2

я плакал

okunek

Если сама процедура с маллоками, циклами и прочей херней работает ну пусть одну миллисикунду, то твоя прога несколько веков этот определитель считать будет. Чем тебе не подошла ссылка-то?

vertyal17

Посчитай, сколько времени считает при n=14,
потом умножь это время на 15, и получишь примерно сколько будет считать для 15.
Стек вроде переполниться не должен, и если память правильно выделяется - освобождается, то ошибок времени исполнения (таких как переполнение стека) быть не должно (хотя может быть изза фрагментации - хз). Но алгоритм медленный, во всем мире принято считать хотябы по гауссу

vertyal17

чо за зубодробильный С++
k<i?k:k+1
i/2.0==i/2?1:-1

juliuzz

первое - вроде как обычная if конструкция
а вот второе - это хитрозадая проверка i на чётность

vertyal17

Вроде столько времени пргаю, а такой штукой никогда не пользовался (expr)?(expr):(expr)

lipa

дабы зубодробить по-отцовски, первое меняем на
k+(k>=i)
второе на
1-2*(i%2)
added: оператор ? : полезная вестчь

okunek

две минуты назад такую вставил

vook

Это самый рульный оператор в C. Полный аналог Лисповского (if a b c). Остальные операторы С гораздо менее мощны чем их Лисп-аналоги
PS. Рекурсивный алгоритм вычисления det - полное говно. Ботай метод Гаусса.

gopnik1994

я что-то пропустил?
метод Гусса отменили?
ну нахера искать определитель через миноры?
нет, ну нахрена это может пригодиться, я не понимаю......
позже: опередили

evgen5555

А какие операторы ты сравнивал?

vook

Ну например +. В С одним плюсом можно сложить только 2 числа, а в Лиспе - сколько угодно
Ср. a+b+c+d+e+f vs (+ a b c d e f).

Elina74

(+ a b c d e f)

а можно ли там сложить все элементы массива одной командой?

evgen5555

А это очень востребованно в задачах, с которыми программисты сталкиваются?

vook

>а можно ли там сложить все элементы массива одной командой?
Смотря что считать одной командой...
(loop for x across array summing x)

bleyman

Зато на лиспе нельзя напрямую в видеопамять писать.
unsigned char * ptr;
*int*)&ptr) = 0xB8000;
strcpy(ptr, "lliisspp ssoosseett");

okunek

ахуенный аргумент

maggi14

в паскале это делается еще изящнее. Там даже стркопи вызывать бы не пришлось, просто юзай absolute. Правда, у него нет оператора ?:

bleyman

Ну, в некоторых разновидностях сей было ключевое слово _at_, с точно таким же эффектом.

Landstreicher

Простите за оффтопик, но раз появились отцы Лиспа, то пользуясь случаем, спрошу:
Есть ли для Lisp какие-либо средства асинхронного сетевого программирования по типу
http://twistedmatrix.com/projects/core/documentation/howto/a... ?

zya369

(loop for x across array summing x)

sum = reduce(lambda x,y:x+y, list, 0)

это короче
ЗЫ а как в лиспе будет сложить сумму кубов:?

vook

А что это за язык такой интересный? list может быть и массивом и списком?

Чтобы посчитать сумму кубов надо вместо "summing x" написать "summing (expt x 3)" или "summing (* x x x)"

evgen5555

Я так понял, что лисп сливает по удобочитаемости даже ЦэПлюсПлюсу

zya369

это петон был

Olyalyau

а вот второе - это хитрозадая проверка i на чётность

Не столько хитрозадая, сколько очень неэффективная. Самым эффективным вариантом было бы завести отдельную переменную под флаг и в теле цикла делать ей ^=~1 (это на подходящей архитектуре).

Olyalyau

1-2*(i%2)

Это не по-отцовски, минимум 3 цикла.

Landstreicher

> это короче
можно так:
(reduce #'+ mylist) - это короче чем в питоне
> ЗЫ а как в лиспе будет сложить сумму кубов:?
я умею так:
(reduce #'+ (mapcar #'(lambda (x) (* x x x mylist

korsar0156

i % 2 == i & 1

Olyalyau

strcpy(ptr, "lliisspp ssoosseett");

Ты неправильно пишешь в видеопамять
Там толи чётные, толи нечётные байты содержат атрибуты символа -- цвет + цвет фона (+ мигание, если выставлен соответствующий атрибут контроллера)

vook

>(reduce #'+ (mapcar #'(lambda (x) (* x x x mylist
Бррр... Лучше уж (reduce #'+ mylist :key (lambda (x) (* x x x. mapcar работает только со списками, а не с массивами.

stm7583298

+1, i&1 - самая экономная проверка

bleyman

Именно поэтому каждая буковка повторяется два раза. Типа они разноцветные

Olyalyau

i % 2 == i & 1

Ты не поверишь, я знаю об этом.
Мой пост был про то, что использование этого

1-2*(i%2)

данной ситуации неэффективно, и требует как минимум три цикла (такта) процессора. В то время как введя переменную sign под знак можно обойтись одним тиком в теле for'а так:
sign^=~1; (До for'а, естественно надо объявить register sign = 1;)

Olyalyau

+1, i&1 - самая экономная проверка

Ёлы-палы, вы все прикалываетесь что ли?
1. самая эффективная проверка доступна только с ассемблером -- это тест флага чётности результата сразу после добавления 1 к i (цикл придётся слегка модифицировать)
2. ему не нужна проверка чётности, ему нужен знак минора, а вычислять знак минора через if -- очень неэкономно
3. вариант вычисления знака минора за один такт я уже привёл, быстрее работать никакой вариант не будет.

Olyalyau

Именно поэтому каждая буковка повторяется два раза. Типа они разноцветные

А, так это не бага -- это фича!
Я-то думал надо "l\x..i\x..s\x.. ..."

Dmitriy82

Нет флага четности результата (только не надо задвигать про parity flag) в архитектуре ..86.
А вообще говорить об эффективности реализации при таком неэффективном алгоритме - это
не просто прикалываться, скорее болезнь.

Ivan8209

Лучше тусуйся на FreeNode.
---
...Я работаю...