Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Алгоритмы и теория программирования

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 295 RSS
←   Октябрь 2015   →
 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


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rfpro.ru/
Открыта: 11-11-2009

Автор
Калашников О.А.

Статистика

295 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Алгоритмы и теория программирования


РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Роман Селиверстов
Статус: Советник
Рейтинг: 4201
∙ повысить рейтинг » 		CradleA
Статус: Специалист
Рейтинг: 2606
∙ повысить рейтинг » 		Megaloman
Статус: Академик
Рейтинг: 1788
∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования

Номер выпуска:187
Дата выхода:18.10.2015, 15:59
Администратор рассылки:Лысков Игорь Витальевич (Старший модератор)
Подписчиков / экспертов:13 / 7
Вопросов / ответов:3 / 3

Консультация # 55432: Доброго времени суток! Задача следующая: игра Судоку (квадрат 9х9, числа от 1 до 9 не должны повторятся ни в строке ни в столбце ни в малых квадратах). Уже есть какой-то набор цифр в квадрате (не все). Необходмимо проверить количество вариантов решения этого кроссворда. Помогите с алгоритмом...

Консультация # 186069: Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Есть алгоримы Грэхема, Джарвиса и другие для построения выпуклой оболочки для множества точек. Нужна помощь в том, как разделить множество точек на выпуклые четырехугольники, сединенные между собой одной или двумя общими точками. ...
Консультация # 110858: Здравствуйте, дорогие друзья! Помогите, пожалуйста, решить задачу. Текст задачи: У нас три пробирки, каждая объёмом 100, две из них с ризками, которые задаются в ручную(пример: 12 34 56 98) число ризок не больше 10 и на этих двух ризки одинаковые. Нужно найти и вывести последовательность переливаний, чтобы в 3-й пробирке получился объём 1 или сказа...

Консультация # 55432:

Доброго времени суток!
Задача следующая: игра Судоку (квадрат 9х9, числа от 1 до 9 не должны повторятся ни в строке ни в столбце ни в малых квадратах).
Уже есть какой-то набор цифр в квадрате (не все). Необходмимо проверить количество вариантов решения этого кроссворда.
Помогите с алгоритмом

Дата отправки: 14.09.2006, 13:55
Вопрос задал: Dush
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Physicist:

Здравствуйте, Dush!

Если числа не повторяются, то решение представляет собой таблицу умножения для группы порядка 9. Таких групп всего две - C9 (циклическая) и C3xC3. Но в каждой из групп строки и столбцы могут быть переставлены в произвольном порядке, плюс, элементы группы могут обозначаться разными цифрами. Так что всего решений (в общем случае):
2*9!*9!*9!=95 569 451 679 744 000
Ваша задача - найти, сколько из этих решений совпадают с Вашим набором цифр. Ясно, что перебором здесь и не пахнет. Нужно исходить именно из теоретико-групповых методов. Как - пока незнаю (можно попытаться что-нибудь получить из предположения, что i-ый столбец и j-ая строка соответствуют единичному элементу...), если что придёт ещё в голову - напишу в минифорум.

Консультировал: Physicist
Дата отправки: 14.09.2006, 14:28
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультация # 186069:

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:


Есть алгоримы Грэхема, Джарвиса и другие для построения выпуклой оболочки для множества точек.

Нужна помощь в том, как разделить множество точек на выпуклые четырехугольники, сединенные между собой одной или двумя общими точками.

Дата отправки: 17.05.2012, 15:52
Вопрос задал: Дмитрий
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Лысков Игорь Витальевич (Старший модератор):

Здравствуйте, Дмитрий!
Увы, Вы не интересуетесь задачей, поэтому уточнить некоторые детали не представляется возможным.
Поэтому предлагаю следующий вариант:
В начале, предположим допустимость отсутствия точек из данного множества во всех вершинах четырехугольников,
обязательным является только то, что все точки будут внутри или в большинстве вершин. Это послабление условия необходимо только
для числа точек меньшего 4-х, ровно 5 и когда все точки внутри треугольника. В последнем случае задача разделения точек продолжает оставаться не намного проще исходной.
Итак, алгоритм следующий:
1) Если точек меньше 3, дополняем до 4
2) Находим при помощи алгоритма Грэхема точки, являющимися последовательными вершинами многоугольника, являющего оболочкой для всех точек.
3) Если вершин четное число:
а) берем 4 первых точки
б) оставляем первую и последнюю, добавляем две
в) и так, пока не дойдем до последней
4) Если вершин нечетное число и больше трех:
а) Если есть хоть одна дополнительная вершина внутри многоугольника,
то добавляем еще одну любую точку так, что внутри треугольника, состоящего из двух вершин многоугольника и этой точки нет других точек
Т.о. получили четное число вершин. Разбиваем на четырехугольники, начиная с этой добавленной, как в пункте 3)
б) Если внутри нет точек и вершин больше 5, то разбиваем аналогично 3), только для последнего четырехугольника оставляем от предпоследнего только одну точку, а не две последний будет иметь только одну общую точку)
в) Если у нас ровно 5 точек в вершинах пятиугольника, то добавляем любую точку, получаем шестиугольник, применяем 3)
5) Если три вершины, то добавляем одну дополнительную точку так, чтобы получился четырехугольник

Консультировал: Лысков Игорь Витальевич (Старший модератор)
Дата отправки: 24.05.2012, 12:11
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультация # 110858:

Здравствуйте, дорогие друзья! Помогите, пожалуйста, решить задачу. Текст задачи: У нас три пробирки, каждая объёмом 100, две из них с ризками, которые задаются в ручную(пример: 12 34 56 98) число ризок не больше 10 и на этих двух ризки одинаковые. Нужно найти и вывести последовательность переливаний, чтобы в 3-й пробирке получился объём 1 или сказать, что этого сделать нельзя. Решить с помощью волнового алгоритма.
Заранее большое спасибо!!!

Дата отправки: 25.11.2007, 02:11
Вопрос задал: Полянский Дмитрий Александрович
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Воробьёв Алексей Викторович:

Здравствуйте, Полянский Дмитрий Александрович!

Здравствуйте, дорогие друзья! Помогите, пожалуйста, решить задачу.
Текст задачи: У нас три пробирки, каждая объёмом 100, две из них с ризками, которые задаются в ручную(пример: 12 34 56 98) число ризок не больше 10 и на этих двух ризки одинаковые. Нужно найти и вывести последовательность переливаний, чтобы в 3-й пробирке получился объём 1 или сказать, что этого сделать нельзя. Решить с помощью волнового алгоритма.
Заранее большое спасибо!!!

Вообще-то, эта задача решается чисто аналитически.
Если у всех Ваших рисок (включая 100) есть общий делитель, то решения нет.
Поскольку входит 100, то это означает, что решений нет только если все риски чётные или все риски делятся на 5.
Во всех остальных случаях решение есть.

Я пока приведу решение основанное не на волновом алгоритме.
Этот алгоритм находит не самое оптимальное решение, но он гораздо проще и, возможно, даже быстрее волнового алгоритма, так как он не рассматривает огромное количество вариантов.

Все случаи, когда решение есть, разбиваются на 2 класса.
Самый простой вариант, если Вы можете найти две риски (включая 100) взаимно простые:
1. Наливаем первую пробирку до меньшей риски
2. Переливаем из первой пробирки во 2 полностью или до достижения второй риски.
3. Если не достигли второй риски переходим к 1.
4. Опустошаем вторую пробирку.
5. Если в первой пробике осталось не 1, переходим к 2.

Более сложный вариант, когда вы не можете найти 2 взаимно простых риски.
Поскольку у нас нет общего делителя у всех рисок, то можно найти 3 риски, такие что каждая пара имеет общие делители, но при этом эти делители различны для разных пар.
Например, 4, 12, 15.
Выбираем пару рисок с наименьшим общим делителем (в нашем случае 15 и 12).
1. Наливаем первую пробирку до меньшей риски
2. Переливаем из первой пробирки во 2 полностью или до достижения второй риски.
3. Если не достигли второй риски переходим к 1.
4. Опустошаем вторую пробирку.
5. Если в первой пробике осталось не равное общему делителю, переходим к 2.
6. Переливаем из первой пробирки в 3 полностью или до достижения третьей риски.
7. Если не достигли третей риски переходим к 1.
8. Опустошаем третью пробирку.
9. Если в первой пробирке осталось не 1, переходим к 6.
10. Переливаем из первой пробирку в 3-ю пробирку и решение найдено.

Как видите, второй случай, это копия первого, но первые 5 шагов используются для создания фиктивной риски, равной общему делителю.
При желании можно объединить первый случай со вторым, используя в качестве общего делителя 1.

Само собой разумеется, что Вам надо записывать в какой-то лог все Ваши переливания, чтобы показать ответ.

Если Вам всё-таки надо написать волновой алгоритм, то я могу попытаться написать его на С++, если это Вас устроит.

Консультировал: Воробьёв Алексей Викторович
Дата отправки: 25.11.2007, 04:28
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!
В избранное