roboforum.ru

Технический форум по робототехнике.


Задачка

Все здесь

Задачка

Сообщение blindman » 24 дек 2009, 20:17

Дана квадратная матрица A размером n x n. Найти матрицу B размером n x n, такую, что:
1. Все элементы В - 0 или 1
2. В[i][i] = 0 для любого i
3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце
4. SUM(i=0,n-1;j=0,n-1)(A[i,j]*B[i,j]) - минимально
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение Duhas » 24 дек 2009, 20:24

какой вид решения приемлем ? )
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Задачка

Сообщение blindman » 24 дек 2009, 20:25

Решения, требующие порядка n! итераций (тупой перебор) неприемлемы
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение Duhas » 24 дек 2009, 20:27

ГА?
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Задачка

Сообщение Michael_K » 24 дек 2009, 20:31

Аватара пользователя
Michael_K
 
Сообщения: 6028
Зарегистрирован: 07 окт 2009, 00:29
Откуда: СПб

Re: Задачка

Сообщение Duhas » 24 дек 2009, 20:32

мммм, а если найти n наименьший элементов матрицы А, и по их номерам заполнить В...

с ГА думаю я бредил )))
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Задачка

Сообщение blindman » 24 дек 2009, 20:35

Duhas писал(а):ГА?
Гугу :D А как оценить время нахождения решения?
Michael_K писал(а):вам сюда это надо задать

Решение-то я найду в любом случае. Здесь как-то ... поуютнее, что ли...

Добавлено спустя 53 секунды:
Duhas писал(а):с ГА думаю я бредил )))

Может быть и нет
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение Duhas » 24 дек 2009, 20:38

дык ваиант с примерно n^3 обращений к матрице не катит?
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Задачка

Сообщение blindman » 24 дек 2009, 20:42

Вполне
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение Duhas » 24 дек 2009, 20:46

ну дык а в чем проблема то ?

ищем n наименьших чисел в матрице А... то займет если быть точнее (n^2 - n)*n обращений... и прям в функции поиска пишем 1-цы оп найденным номерам в B... как я понимаю условие - минимальность суммы поэлементных произведений?

в В все или 0 или 1.. то по идее такой суммы = равен сумме n меньших элементов А...
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Аватара пользователя
Duhas
 
Сообщения: 6338
Зарегистрирован: 15 сен 2007, 13:03
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович

Re: Задачка

Сообщение blindman » 24 дек 2009, 20:53

ищем n наименьших чисел в матрице А

Что, если они все оказываются в одном столбце(строке)?

Добавлено спустя 3 минуты 30 секунд:
Duhas писал(а):в В все или 0 или 1

Это не единственное условие!
3. В содержит ровно 1 единичный элемент в каждой строке и в каждом столбце
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение avr123.nm.ru » 24 дек 2009, 21:11

blindman писал(а):Дана квадратная матрица


Для чего это применяется.
Аватара пользователя
avr123.nm.ru
отсылающий читать курс
 
Сообщения: 14195
Зарегистрирован: 06 ноя 2005, 04:18
Откуда: Москва
Предупреждения: -8

Re: Задачка

Сообщение blindman » 24 дек 2009, 21:13

Какая разница? От этого зависит решение? Если условие неоднозначно/непонятно - пишите, уточню
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

Re: Задачка

Сообщение avr123.nm.ru » 24 дек 2009, 21:21

Это просто вопрос вызваный любопытством.
Аватара пользователя
avr123.nm.ru
отсылающий читать курс
 
Сообщения: 14195
Зарегистрирован: 06 ноя 2005, 04:18
Откуда: Москва
Предупреждения: -8

Re: Задачка

Сообщение blindman » 24 дек 2009, 21:28

Изначально это задача по программированию - ничего более.
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru

Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!

Аватара пользователя
blindman
 
Сообщения: 4130
Зарегистрирован: 29 апр 2008, 21:15
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич

След.

Вернуться в Свободное общение

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2

Mail.ru counter