Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Связная область - Мир MS Excel

Регистрация · Логин: · Пароль: · · Забыли пароль?
Страница 1 из 11
Модератор форума: _Boroda_, Pelena 
Мир MS Excel » Работа и общение » Мозговой штурм » Связная область (Определение связности области "1" на поле 6Х6)
Связная область
Светлый Дата: Воскресенье, 24.04.2016, 10:18 | Сообщение № 1
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
Прошу прощения, не увидел что новый вопрос в МШ уже есть.
Предлагаю свой перенести на следующую неделю.

Имеется поле 6Х6. На нём половина клеток 1, половина 0.
Необходимо формулой определить все ли клетки 1 касаются друг друга боковыми сторонами. Т.е., если разрезать все грани между 1 и 0, будет ли это целый кусок.
У меня с использованием дополнительных ячеек получилась протягиваемая массивная формула 174 символа и окончательное решение в результирующей ячейке 18 символов. Значение в результирующей ячейке может быть истина/ложь или число<>0/0
Ну и дополнительно формулы поворотов на правом зелёном поле, если кто-то заинтересуется. Или это можно вынести в отдельную тему. Над ними я особо не заморачивался.
К сообщению приложен файл: DeskDiv.xlsx(27Kb)


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Воскресенье, 24.04.2016, 10:22
 
Ответить
СообщениеПрошу прощения, не увидел что новый вопрос в МШ уже есть.
Предлагаю свой перенести на следующую неделю.

Имеется поле 6Х6. На нём половина клеток 1, половина 0.
Необходимо формулой определить все ли клетки 1 касаются друг друга боковыми сторонами. Т.е., если разрезать все грани между 1 и 0, будет ли это целый кусок.
У меня с использованием дополнительных ячеек получилась протягиваемая массивная формула 174 символа и окончательное решение в результирующей ячейке 18 символов. Значение в результирующей ячейке может быть истина/ложь или число<>0/0
Ну и дополнительно формулы поворотов на правом зелёном поле, если кто-то заинтересуется. Или это можно вынести в отдельную тему. Над ними я особо не заморачивался.

Автор - Светлый
Дата добавления - 24.04.2016 в 10:18
MCH Дата: Воскресенье, 24.04.2016, 10:40 | Сообщение № 2
Группа: Админы
Ранг: Старожил
Сообщений: 1757
Репутация: 665 ±
Замечаний: ±

На нём половина клеток 1, половина 0

Вопросы:
1. Условие, что половина "1" (18 штук) и половина "0" (тоже 18) - обязательное, т.е. не может такого быть, что 17 единиц и 19 нулей?
2. Исходные данные находятся в ячейках G1:L6? ссылаться нужно только на эти ячейки?
3. Нарисовано две фигуры, нужно выводить ЛОЖЬ? (в примере указана ИСТИНА)
4. Что за числа в ячейках N1:W8? какое они имеют отношение к задаче? и что за числа в D1:D2?


3 и 4 вопрос снимаю, разобрался
 
Ответить
Сообщение
На нём половина клеток 1, половина 0

Вопросы:
1. Условие, что половина "1" (18 штук) и половина "0" (тоже 18) - обязательное, т.е. не может такого быть, что 17 единиц и 19 нулей?
2. Исходные данные находятся в ячейках G1:L6? ссылаться нужно только на эти ячейки?
3. Нарисовано две фигуры, нужно выводить ЛОЖЬ? (в примере указана ИСТИНА)
4. Что за числа в ячейках N1:W8? какое они имеют отношение к задаче? и что за числа в D1:D2?


3 и 4 вопрос снимаю, разобрался

Автор - MCH
Дата добавления - 24.04.2016 в 10:40
MCH Дата: Воскресенье, 24.04.2016, 11:27 | Сообщение № 3
Группа: Админы
Ранг: Старожил
Сообщений: 1757
Репутация: 665 ±
Замечаний: ±

Вне конкурса, решение через VBA (UDF), подсчет количества несвязанных фигур
Функция в A2
К сообщению приложен файл: DeskDiv.xlsm(35Kb)
 
Ответить
СообщениеВне конкурса, решение через VBA (UDF), подсчет количества несвязанных фигур
Функция в A2

Автор - MCH
Дата добавления - 24.04.2016 в 11:27
Светлый Дата: Воскресенье, 24.04.2016, 14:58 | Сообщение № 4
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
MCH, отвечаю:
1. По условию головоломки, из которой я взял эту задачу, разрезание должно быть на две равные симметричные части. Но в принципе, формула должна работать для любого количества единиц.
2. Если по формуле потребуется использовать окружающие ячейки, то вполне допустимо, они нигде не используются.
3. Случайно сохранил не с тем числом и не проверил. В задании сказано, что и при каких условиях там должно быть.
4. В ячейках N1:W6 примеры правильных комбинаций с их зеркальными отражениями и поворотами, а в N7:N8 примеры, не удовлетворяющие условию. В D1:D2 индексы, чтобы из таблицы взять числа для заполнения образца. В образце стоят формулы, которые заполняют поле из выбранного числа в ячейке C1.


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Воскресенье, 24.04.2016, 19:56
 
Ответить
СообщениеMCH, отвечаю:
1. По условию головоломки, из которой я взял эту задачу, разрезание должно быть на две равные симметричные части. Но в принципе, формула должна работать для любого количества единиц.
2. Если по формуле потребуется использовать окружающие ячейки, то вполне допустимо, они нигде не используются.
3. Случайно сохранил не с тем числом и не проверил. В задании сказано, что и при каких условиях там должно быть.
4. В ячейках N1:W6 примеры правильных комбинаций с их зеркальными отражениями и поворотами, а в N7:N8 примеры, не удовлетворяющие условию. В D1:D2 индексы, чтобы из таблицы взять числа для заполнения образца. В образце стоят формулы, которые заполняют поле из выбранного числа в ячейке C1.

Автор - Светлый
Дата добавления - 24.04.2016 в 14:58
MCH Дата: Понедельник, 25.04.2016, 18:42 | Сообщение № 5
Группа: Админы
Ранг: Старожил
Сообщений: 1757
Репутация: 665 ±
Замечаний: ±

По своей сути задачу нужно решать с помощью VBA, либо "поиском в глубину" с помощью рекурсий (код я уже выкладывал), либо "поиском в ширину".
На мой взгляд одной формулой задачу не решить, т.к. нужно использовать динамическое программирование.

Сделал решение с помощью формул, получилась не одна, а несколько разных формул, но все они достаточно компактные.

Способ решения (фактически волновой алгоритм или поиск в ширину):
Находим первую клетку с единицей, от нее запускаем волну, пытаясь "закрасить" соседние заполненные клетки
Если по истечению 35 итераций (достаточное количество для поля 6х6) количество "закрашенных" клеток равно общему кол-ву единиц, то на поле одна единственная фигура, если меньше, то фигур несколько

Решение выкладываю, кто хочет решить самостоятельно - не подглядывайте
К сообщению приложен файл: -DeskDiv.xlsx(45Kb)
 
Ответить
СообщениеПо своей сути задачу нужно решать с помощью VBA, либо "поиском в глубину" с помощью рекурсий (код я уже выкладывал), либо "поиском в ширину".
На мой взгляд одной формулой задачу не решить, т.к. нужно использовать динамическое программирование.

Сделал решение с помощью формул, получилась не одна, а несколько разных формул, но все они достаточно компактные.

Способ решения (фактически волновой алгоритм или поиск в ширину):
Находим первую клетку с единицей, от нее запускаем волну, пытаясь "закрасить" соседние заполненные клетки
Если по истечению 35 итераций (достаточное количество для поля 6х6) количество "закрашенных" клеток равно общему кол-ву единиц, то на поле одна единственная фигура, если меньше, то фигур несколько

Решение выкладываю, кто хочет решить самостоятельно - не подглядывайте

Автор - MCH
Дата добавления - 25.04.2016 в 18:42
Светлый Дата: Понедельник, 25.04.2016, 19:32 | Сообщение № 6
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
Если по истечению 35 итераций

С итерациями меня категорически не устроило, они нужны были для других целей. Пришлось решать формулами. Основная, протянутая на 18 ячеек 174 167 символа и значение последней ячейки не равное 0, как условие связности.
Может быть гуру форума имеют в заначке какие-нибудь функции или приёмы, способные решить эту задачу? Я долго ломал голову, но по другому не смог решить.

Кстати, в загруженном файле есть ошибки. Выдаёт ЛОЖЬ для правильных вариантов. (4096 и 4160)


Программировать проще, чем писать стихи.

Сообщение отредактировал Светлый - Понедельник, 25.04.2016, 20:27
 
Ответить
Сообщение
Если по истечению 35 итераций

С итерациями меня категорически не устроило, они нужны были для других целей. Пришлось решать формулами. Основная, протянутая на 18 ячеек 174 167 символа и значение последней ячейки не равное 0, как условие связности.
Может быть гуру форума имеют в заначке какие-нибудь функции или приёмы, способные решить эту задачу? Я долго ломал голову, но по другому не смог решить.

Кстати, в загруженном файле есть ошибки. Выдаёт ЛОЖЬ для правильных вариантов. (4096 и 4160)

Автор - Светлый
Дата добавления - 25.04.2016 в 19:32
MCH Дата: Понедельник, 25.04.2016, 20:35 | Сообщение № 7
Группа: Админы
Ранг: Старожил
Сообщений: 1757
Репутация: 665 ±
Замечаний: ±

Кстати, в загруженном файле есть ошибки. Выдаёт ЛОЖЬ для правильных вариантов. (4096 и 4160)

Исправил, файл перевложил
 
Ответить
Сообщение
Кстати, в загруженном файле есть ошибки. Выдаёт ЛОЖЬ для правильных вариантов. (4096 и 4160)

Исправил, файл перевложил

Автор - MCH
Дата добавления - 25.04.2016 в 20:35
MCH Дата: Среда, 27.04.2016, 07:24 | Сообщение № 8
Группа: Админы
Ранг: Старожил
Сообщений: 1757
Репутация: 665 ±
Замечаний: ±

Пока не могу придумать другой алгоритм.
Можно попробовать 36 значений 1/0 запихнуть в одну ячейку в виде числа (сумма степеней двойки).
Но кроме компактности решения ничего полезного не получится, а формулы могут увеличиться в разы

Нужно менять алгоритм, идей никаких нет.
 
Ответить
СообщениеПока не могу придумать другой алгоритм.
Можно попробовать 36 значений 1/0 запихнуть в одну ячейку в виде числа (сумма степеней двойки).
Но кроме компактности решения ничего полезного не получится, а формулы могут увеличиться в разы

Нужно менять алгоритм, идей никаких нет.

Автор - MCH
Дата добавления - 27.04.2016 в 07:24
Светлый Дата: Среда, 27.04.2016, 13:05 | Сообщение № 9
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
Думал я над подобными вариантами. У меня из числа так поле и заполняется. Правда для задачи было достаточно 2^18. Остальные заполняются поворотом этих 18. Но для МШ надо всё поле.
Моя формула будет работать и для поля 8Х8, только исправить диапазоны и константы. Тогда 2^64 уже будет проблемой. Excel позволит только 2^49 обрабатывать. Дальше уже округляет.
Лучше работать напрямую с полем. И выделение элементов проще, и поле можно заполнить любым способом.


Программировать проще, чем писать стихи.
 
Ответить
СообщениеДумал я над подобными вариантами. У меня из числа так поле и заполняется. Правда для задачи было достаточно 2^18. Остальные заполняются поворотом этих 18. Но для МШ надо всё поле.
Моя формула будет работать и для поля 8Х8, только исправить диапазоны и константы. Тогда 2^64 уже будет проблемой. Excel позволит только 2^49 обрабатывать. Дальше уже округляет.
Лучше работать напрямую с полем. И выделение элементов проще, и поле можно заполнить любым способом.

Автор - Светлый
Дата добавления - 27.04.2016 в 13:05
MCH Дата: Среда, 27.04.2016, 13:33 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 1757
Репутация: 665 ±
Замечаний: ±

Лучше работать напрямую с полем. И выделение элементов проще, и поле можно заполнить любым способом.

Ну так у меня оба решения (и UDF и формулы) работают изначально ссылаясь на исходное поле.
Размер самого поля может быть любым, нет ограничения на размер, фигуры также могут быть любыми (не обязательно симметричными)
Если посмотреть на формульное решение, то формулы достаточно простые, а решение макросом - в 2-3 десятка строчек кода.
 
Ответить
Сообщение
Лучше работать напрямую с полем. И выделение элементов проще, и поле можно заполнить любым способом.

Ну так у меня оба решения (и UDF и формулы) работают изначально ссылаясь на исходное поле.
Размер самого поля может быть любым, нет ограничения на размер, фигуры также могут быть любыми (не обязательно симметричными)
Если посмотреть на формульное решение, то формулы достаточно простые, а решение макросом - в 2-3 десятка строчек кода.

Автор - MCH
Дата добавления - 27.04.2016 в 13:33
Светлый Дата: Понедельник, 02.05.2016, 09:30 | Сообщение № 11
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
Судя по соседней теме выделения 6 цифр, на данном временном промежутке желающих решить задачу не появится. Но предлагаю дать неделю на проработку. Возможно, в праздничные дни кто-то предпочтёт пиву мозговую деятельность. Или хотя бы совместит. Найдутся желающие?
Вскроюсь числа восьмого?

[offtop]С праздниками всех!


Программировать проще, чем писать стихи.
 
Ответить
СообщениеСудя по соседней теме выделения 6 цифр, на данном временном промежутке желающих решить задачу не появится. Но предлагаю дать неделю на проработку. Возможно, в праздничные дни кто-то предпочтёт пиву мозговую деятельность. Или хотя бы совместит. Найдутся желающие?
Вскроюсь числа восьмого?

[offtop]С праздниками всех!

Автор - Светлый
Дата добавления - 02.05.2016 в 09:30
Michael_S Дата: Понедельник, 02.05.2016, 12:05 | Сообщение № 12
Группа: Друзья
Ранг: Старожил
Сообщений: 1688
Репутация: 327 ±
Замечаний: 0% ±

Excel2016
Чет я не понял задачи.
На примере четырех квадратов справа - что надо получить?

[offtop]и, наверно, не Связная область, а Связаная область[/offtop]
К сообщению приложен файл: DeskDiv_1.xlsx(33Kb)


ЯД: 41001136675053
WM: R389613894253


Сообщение отредактировал Michael_S - Понедельник, 02.05.2016, 12:13
 
Ответить
СообщениеЧет я не понял задачи.
На примере четырех квадратов справа - что надо получить?

[offtop]и, наверно, не Связная область, а Связаная область[/offtop]

Автор - Michael_S
Дата добавления - 02.05.2016 в 12:05
Светлый Дата: Понедельник, 02.05.2016, 16:28 | Сообщение № 13
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
Все четыре примера дадут ЛОЖЬ, потому что на них по несколько связных областей, но между собой они разрозненные.
Самый простой пример это половина доски, все единицы касаются друг друга боковыми сторонами.
Есть СВЯ'ЗНЫЕ пространства и области, а есть СВЯЗАННЫЕ. В интернете можно найти определения.


Программировать проще, чем писать стихи.
 
Ответить
СообщениеВсе четыре примера дадут ЛОЖЬ, потому что на них по несколько связных областей, но между собой они разрозненные.
Самый простой пример это половина доски, все единицы касаются друг друга боковыми сторонами.
Есть СВЯ'ЗНЫЕ пространства и области, а есть СВЯЗАННЫЕ. В интернете можно найти определения.

Автор - Светлый
Дата добавления - 02.05.2016 в 16:28
Светлый Дата: Суббота, 07.05.2016, 22:16 | Сообщение № 14
Группа: Проверенные
Ранг: Форумчанин
Сообщений: 226
Репутация: 56 ±
Замечаний: 0% ±

Excel 2007
Желающих больше не оказалось. Вскрываю свой вариант:
Код
=МАКС(Ч(СМЕЩ(F$1;ОСТАТ(СТРОКА($7:$47);7);СТРОКА($7:$47)/7))*СТРОКА($9:$49)*ЕСЛИ(B6="";1;НЕ(СЧЁТЕСЛИ(B$6:B6;СТРОКА($9:$49)))*СЧЁТЕСЛИ(B$6:B6;СТРОКА($8:$48)+{-6;0;2;8})))
К сообщению приложен файл: -DeskDiv_1.xlsx(45Kb)


Программировать проще, чем писать стихи.
 
Ответить
СообщениеЖелающих больше не оказалось. Вскрываю свой вариант:
Код
=МАКС(Ч(СМЕЩ(F$1;ОСТАТ(СТРОКА($7:$47);7);СТРОКА($7:$47)/7))*СТРОКА($9:$49)*ЕСЛИ(B6="";1;НЕ(СЧЁТЕСЛИ(B$6:B6;СТРОКА($9:$49)))*СЧЁТЕСЛИ(B$6:B6;СТРОКА($8:$48)+{-6;0;2;8})))

Автор - Светлый
Дата добавления - 07.05.2016 в 22:16
Мир MS Excel » Работа и общение » Мозговой штурм » Связная область (Определение связности области "1" на поле 6Х6)
Страница 1 из 11
Поиск:

Яндекс цитирования
© 2010-2016 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!