roboforum.ru

Технический форум по робототехнике.
Текущее время: 10 апр 2025, 16:33

Сообщения без ответов | Активные темы


Список форумов » Общие вопросы » Свободное общение

Часовой пояс: UTC + 4 часа




Начать новую тему Ответить на тему  Страница 1 из 7
  [ Сообщений: 91 ]  На страницу 1, 2, 3, 4, 5 ... 7  След.
  Версия для печати Пред. тема | След. тема 
Автор Сообщение
blindman
 Заголовок сообщения: Задачка
СообщениеДобавлено: 24 дек 2009, 20:17 
Не в сети
Аватара пользователя

Зарегистрирован: 29 апр 2008, 21:15
Сообщения: 4130
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич
Дана квадратная матрица 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!
Вернуться к началу
 Профиль  
 
Duhas
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:24 
Не в сети
Аватара пользователя

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

_________________
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Вернуться к началу
 Профиль  
 
blindman
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:25 
Не в сети
Аватара пользователя

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

_________________
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru
Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!
Вернуться к началу
 Профиль  
 
Duhas
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:27 
Не в сети
Аватара пользователя

Зарегистрирован: 15 сен 2007, 13:03
Сообщения: 6338
Откуда: Красноярск
прог. языки: ASM(МК), C(PC)
ФИО: Гагарский Андрей Александрович
ГА?

_________________
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Вернуться к началу
 Профиль  
 
Michael_K
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:31 
Не в сети
Аватара пользователя

Зарегистрирован: 07 окт 2009, 00:29
Сообщения: 6028
Откуда: СПб
вам сюда это надо задать
http://www.sciteclibrary.ru/cgi-bin/yabb2/YaBB.pl?board=golovolomki
Вернуться к началу
 Профиль  
 
Duhas
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:32 
Не в сети
Аватара пользователя

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

с ГА думаю я бредил )))

_________________
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Вернуться к началу
 Профиль  
 
blindman
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:35 
Не в сети
Аватара пользователя

Зарегистрирован: 29 апр 2008, 21:15
Сообщения: 4130
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич
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!
Вернуться к началу
 Профиль  
 
Duhas
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:38 
Не в сети
Аватара пользователя

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

_________________
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Вернуться к началу
 Профиль  
 
blindman
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:42 
Не в сети
Аватара пользователя

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

_________________
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru
Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!
Вернуться к началу
 Профиль  
 
Duhas
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:46 
Не в сети
Аватара пользователя

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

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

в В все или 0 или 1.. то по идее такой суммы = равен сумме n меньших элементов А...

_________________
«Как сердцу выразить себя? … Мысль изреченная есть ложь!»
В этом мире меня подводит доброта и порядочность...
"двое смотрят в лужу, один видит лужу, другой отраженные в ней звезды"
Вернуться к началу
 Профиль  
 
blindman
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 20:53 
Не в сети
Аватара пользователя

Зарегистрирован: 29 апр 2008, 21:15
Сообщения: 4130
Откуда: Хабаровск
прог. языки: C,C++,Assembler,PHP,Javascript,Ruby, SPIN,Java(?)
ФИО: Андрей Юрьевич
Цитата:
ищем 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!
Вернуться к началу
 Профиль  
 
avr123.nm.ru
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 21:11 
Не в сети
отсылающий читать курс
Аватара пользователя

Зарегистрирован: 06 ноя 2005, 04:18
Сообщения: 14195
Откуда: Москва
blindman писал(а):
Дана квадратная матрица


Для чего это применяется.
Вернуться к началу
 Профиль  
 
blindman
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 21:13 
Не в сети
Аватара пользователя

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

_________________
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru
Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!
Вернуться к началу
 Профиль  
 
avr123.nm.ru
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 21:21 
Не в сети
отсылающий читать курс
Аватара пользователя

Зарегистрирован: 06 ноя 2005, 04:18
Сообщения: 14195
Откуда: Москва
Это просто вопрос вызваный любопытством.
Вернуться к началу
 Профиль  
 
blindman
 Заголовок сообщения: Re: Задачка
СообщениеДобавлено: 24 дек 2009, 21:28 
Не в сети
Аватара пользователя

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

_________________
Проект [[Open Robotics]] - универсальные модули для построения роботов
Модули Open Robotics можно приобрести в магазине shop.roboforum.ru
Day OFF? You must be pulling my leg! Stop making humor before someone sees you, fool!
Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  Страница 1 из 7
  [ Сообщений: 91 ]  На страницу 1, 2, 3, 4, 5 ... 7  След.

Список форумов » Общие вопросы » Свободное общение

Часовой пояс: UTC + 4 часа


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

Сейчас этот форум просматривают: Google [Bot] и гости: 4

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Русская поддержка phpBB
phpBB SEO