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

Вход

Регистрация

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

 

= Мир MS Excel/Города - Мир MS Excel

Старая форма входа
  • Страница 1 из 1
  • 1
Модератор форума: китин  
Города
MCH Дата: Среда, 05.02.2014, 00:21 | Сообщение № 1
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

В игре "Города" последовательно называют города, при этом каждый следующий город должен начинаться на букву, которой заканчивается предыдущий город. Запрещено повторять название городов. Например, сначала была названа "Москва" - заканчивается на "а", следует назвать другой город, у которого в названии первая буква "а". Это может быть "Архангельск". Следующий город должен начинаться на "к" и т.д.
Дан список городов России:

КЕМЕРОВО
АРЗАМАС
САМАРА
КИРОВ
ОРСК
КАЛУГА
АРХАНГЕЛЬСК
КОВРОВ
ВЛАДИВОСТОК
ВОРОНЕЖ
АЛУШТА
КАЛИНИН
НОВГОРОД
САНКТ-ПЕТЕРБУРГ
НИЖНЕВАРТОВСК
ТАМБОВ
МОСКВА
МУРОМ
КУРСК
АБАКАН
НОРИЛЬСК
СМОЛЕНСК
ЖУКОВ
ГЛАЗОВ
ДЕРБЕНТ

Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов (может быть несколько вариантов решения)
 
Ответить
СообщениеВ игре "Города" последовательно называют города, при этом каждый следующий город должен начинаться на букву, которой заканчивается предыдущий город. Запрещено повторять название городов. Например, сначала была названа "Москва" - заканчивается на "а", следует назвать другой город, у которого в названии первая буква "а". Это может быть "Архангельск". Следующий город должен начинаться на "к" и т.д.
Дан список городов России:

КЕМЕРОВО
АРЗАМАС
САМАРА
КИРОВ
ОРСК
КАЛУГА
АРХАНГЕЛЬСК
КОВРОВ
ВЛАДИВОСТОК
ВОРОНЕЖ
АЛУШТА
КАЛИНИН
НОВГОРОД
САНКТ-ПЕТЕРБУРГ
НИЖНЕВАРТОВСК
ТАМБОВ
МОСКВА
МУРОМ
КУРСК
АБАКАН
НОРИЛЬСК
СМОЛЕНСК
ЖУКОВ
ГЛАЗОВ
ДЕРБЕНТ

Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов (может быть несколько вариантов решения)

Автор - MCH
Дата добавления - 05.02.2014 в 00:21
AndreTM Дата: Среда, 05.02.2014, 00:55 | Сообщение № 2
Группа: Друзья
Ранг: Старожил
Сообщений: 1762
Репутация: 501 ±
Замечаний: 0% ±

2003 & 2010
Формулами? А варианты - протяжкой этой формулы, например, вниз?

Или всё же макросом? :) (впрочем, решений кодом - и так достаточно известно)


Skype: andre.tm.007
Donate: Qiwi: 9517375010
 
Ответить
СообщениеФормулами? А варианты - протяжкой этой формулы, например, вниз?

Или всё же макросом? :) (впрочем, решений кодом - и так достаточно известно)

Автор - AndreTM
Дата добавления - 05.02.2014 в 00:55
MCH Дата: Среда, 05.02.2014, 07:50 | Сообщение № 3
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Формулами?... Или всё же макросом?

Все равно как, хоть в уме. "Мозговой штурм" это ведь не обязательно формульная оптимизация.
Как это реализовать формулами не знаю, но будет интересно посмотреть на чью нибудь реализацию
впрочем, решений кодом - и так достаточно известно

Если честно, то решение не гуглил, а сам изобретал велосипед.
 
Ответить
Сообщение
Формулами?... Или всё же макросом?

Все равно как, хоть в уме. "Мозговой штурм" это ведь не обязательно формульная оптимизация.
Как это реализовать формулами не знаю, но будет интересно посмотреть на чью нибудь реализацию
впрочем, решений кодом - и так достаточно известно

Если честно, то решение не гуглил, а сам изобретал велосипед.

Автор - MCH
Дата добавления - 05.02.2014 в 07:50
MCH Дата: Среда, 05.02.2014, 18:53 | Сообщение № 4
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Формулами? А варианты - протяжкой этой формулы, например, вниз?

Всего возможно 495687 вариантов составления различных последовательностей, из которых 8064 имеют максимальную длину.

Реализовал перебор всех возможных вариантов формулами с использованием доп. ячеек
Не стал выводить все варианты на лист, т.к. файл получается очень тяжелым и долго пересчитывается. (файл пока не выкладываю)
 
Ответить
Сообщение
Формулами? А варианты - протяжкой этой формулы, например, вниз?

Всего возможно 495687 вариантов составления различных последовательностей, из которых 8064 имеют максимальную длину.

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

Автор - MCH
Дата добавления - 05.02.2014 в 18:53
Serge_007 Дата: Среда, 05.02.2014, 21:07 | Сообщение № 5
Группа: Админы
Ранг: Местный житель
Сообщений: 16475
Репутация: 2749 ±
Замечаний: ±

Excel 2016
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий". При выборе каждого последующего слова надо учитывать какая последующая цепочка будет максимальной, причем начинать это делать с первого же слова
Думаю что одной формулой сделать этого не получится, учитывая ограничения Excel, да и по идее формула должна быть итеративной
С доп столбцами делать не интересно, т. к. Михаил уже сделал и вряд ли сделал неправильно :)


ЮMoney:41001419691823 | WMR:126292472390
 
Ответить
СообщениеНасколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий". При выборе каждого последующего слова надо учитывать какая последующая цепочка будет максимальной, причем начинать это делать с первого же слова
Думаю что одной формулой сделать этого не получится, учитывая ограничения Excel, да и по идее формула должна быть итеративной
С доп столбцами делать не интересно, т. к. Михаил уже сделал и вряд ли сделал неправильно :)

Автор - Serge_007
Дата добавления - 05.02.2014 в 21:07
MCH Дата: Среда, 05.02.2014, 23:52 | Сообщение № 6
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

С доп столбцами делать не интересно

Вопрос в том, сколько дополнительных ячеек задействовано? чем меньше, тем лучше
 
Ответить
Сообщение
С доп столбцами делать не интересно

Вопрос в том, сколько дополнительных ячеек задействовано? чем меньше, тем лучше

Автор - MCH
Дата добавления - 05.02.2014 в 23:52
Serge_007 Дата: Четверг, 06.02.2014, 00:06 | Сообщение № 7
Группа: Админы
Ранг: Местный житель
Сообщений: 16475
Репутация: 2749 ±
Замечаний: ±

Excel 2016
Я пока думаю что шесть
У тебя сколько?

чем меньше, тем лучше
Кстати, не факт. Возможно большее количество доп ячеек даст большую скорость вычислений...


ЮMoney:41001419691823 | WMR:126292472390
 
Ответить
СообщениеЯ пока думаю что шесть
У тебя сколько?

чем меньше, тем лучше
Кстати, не факт. Возможно большее количество доп ячеек даст большую скорость вычислений...

Автор - Serge_007
Дата добавления - 06.02.2014 в 00:06
AndreTM Дата: Четверг, 06.02.2014, 02:29 | Сообщение № 8
Группа: Друзья
Ранг: Старожил
Сообщений: 1762
Репутация: 501 ±
Замечаний: 0% ±

2003 & 2010
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий"
На самом деле, всё проще - это задачка на нахождение, эм-м-м... "максимальной длины простого пути направленного графа" или "максимальной простой цепи простого орграфа", типа того... :)
А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3), и даже волновой метод - не панацея. Потому что граф у нас может содержать циклы, а также быть многокомпонентным (по связности). И это кодом (т.е. с предварительным составлением матрицы/списка смежности), плюс затраты памяти минимум на две матрицы n2. Так что про формулы я вообще молчу - либо вирт.массивы (или доп.ячейки) будут немерено кушать ресурсы, либо расчёты будут бешеными, особенно при использовании чисто матричного подхода (с МУМНОЖ() в степени, например)...


Skype: andre.tm.007
Donate: Qiwi: 9517375010


Сообщение отредактировал AndreTM - Четверг, 06.02.2014, 02:32
 
Ответить
Сообщение
Насколько я себе представляю алгоритм решения задачи, то он сродни игре в шахматы, где на каждый ход надо просчитать все возможные варианты его "последствий"
На самом деле, всё проще - это задачка на нахождение, эм-м-м... "максимальной длины простого пути направленного графа" или "максимальной простой цепи простого орграфа", типа того... :)
А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3), и даже волновой метод - не панацея. Потому что граф у нас может содержать циклы, а также быть многокомпонентным (по связности). И это кодом (т.е. с предварительным составлением матрицы/списка смежности), плюс затраты памяти минимум на две матрицы n2. Так что про формулы я вообще молчу - либо вирт.массивы (или доп.ячейки) будут немерено кушать ресурсы, либо расчёты будут бешеными, особенно при использовании чисто матричного подхода (с МУМНОЖ() в степени, например)...

Автор - AndreTM
Дата добавления - 06.02.2014 в 02:29
PowerBoy Дата: Четверг, 06.02.2014, 10:16 | Сообщение № 9
Группа: Проверенные
Ранг: Участник
Сообщений: 100
Репутация: 31 ±
Замечаний: 0% ±

2003
Попробовал решить задачу в лоб, к сожалению SQL не дает больше 13 полей. Запрос выполнялся 8 мин. вместе с выводом данных.

[vba]
Код

SELECT  
г1.F1 AS F1,
г2.F1 AS F2,
г3.F1 AS F3,
г4.F1 AS F4,
г5.F1 AS F5,
г6.F1 AS F6,
г7.F1 AS F7,
г8.F1 AS F8,
г9.F1 AS F9,
г10.F1 AS F10,
г11.F1 AS F11,
г12.F1 AS F12,
г13.F1 AS F13
FROM
[Лист1$1:25] AS г1,
[Лист1$1:25] AS г2,
[Лист1$1:25] AS г3,
[Лист1$1:25] AS г4,
[Лист1$1:25] AS г5,
[Лист1$1:25] AS г6,
[Лист1$1:25] AS г7,
[Лист1$1:25] AS г8,
[Лист1$1:25] AS г9,
[Лист1$1:25] AS г10,
[Лист1$1:25] AS г11,
[Лист1$1:25] AS г12,
[Лист1$1:25] AS г13
WHERE
right(г1.F1,1) = left(г2.F1,1)  
AND
right(г2.F1,1) = left(г3.F1,1)  
AND
right(г3.F1,1) = left(г4.F1,1)  
AND
right(г4.F1,1) = left(г5.F1,1)  
AND
right(г5.F1,1) = left(г6.F1,1)  
AND
right(г6.F1,1) = left(г7.F1,1)  
AND
right(г7.F1,1) = left(г8.F1,1)  
AND
right(г8.F1,1) = left(г9.F1,1)  
AND
right(г9.F1,1) = left(г10.F1,1)  
AND
right(г10.F1,1) = left(г11.F1,1)
AND
right(г11.F1,1) = left(г12.F1,1)
AND
right(г12.F1,1) = left(г13.F1,1)
AND г1.F1 <> г2.F1 AND г1.F1 <> г2.F1 AND г1.F1 <> г3.F1 AND г1.F1 <> г4.F1 AND г1.F1 <> г5.F1 AND г1.F1 <> г6.F1 AND г1.F1 <> г7.F1 AND г1.F1 <> г8.F1 AND г1.F1 <> г9.F1 AND г1.F1 <> г10.F1 AND г1.F1 <> г11.F1 AND г1.F1 <> г12.F1 AND г1.F1 <> г13.F1               
AND г2.F1 <> г3.F1 AND г2.F1 <> г4.F1 AND г2.F1 <> г5.F1 AND г2.F1 <> г6.F1 AND г2.F1 <> г7.F1 AND г2.F1 <> г8.F1 AND г2.F1 <> г9.F1 AND г2.F1 <> г10.F1 AND г2.F1 <> г11.F1 AND г2.F1 <> г12.F1 AND г2.F1 <> г13.F1                 
AND г3.F1 <> г4.F1 AND г3.F1 <> г5.F1 AND г3.F1 <> г6.F1 AND г3.F1 <> г7.F1 AND г3.F1 <> г8.F1 AND г3.F1 <> г9.F1 AND г3.F1 <> г10.F1 AND г3.F1 <> г11.F1 AND г3.F1 <> г12.F1 AND г3.F1 <> г13.F1                    
AND г4.F1 <> г5.F1 AND г4.F1 <> г6.F1 AND г4.F1 <> г7.F1 AND г4.F1 <> г8.F1 AND г4.F1 <> г9.F1 AND г4.F1 <> г10.F1 AND г4.F1 <> г11.F1 AND г4.F1 <> г12.F1 AND г4.F1 <> г13.F1                       
AND г5.F1 <> г6.F1 AND г5.F1 <> г7.F1 AND г5.F1 <> г8.F1 AND г5.F1 <> г9.F1 AND г5.F1 <> г10.F1 AND г5.F1 <> г11.F1 AND г5.F1 <> г12.F1 AND г5.F1 <> г13.F1                            
AND г6.F1 <> г7.F1 AND г6.F1 <> г8.F1 AND г6.F1 <> г9.F1 AND г6.F1 <> г10.F1 AND г6.F1 <> г11.F1 AND г6.F1 <> г12.F1 AND г6.F1 <> г13.F1                           
AND г7.F1 <> г8.F1 AND г7.F1 <> г9.F1 AND г7.F1 <> г10.F1 AND г7.F1 <> г11.F1 AND г7.F1 <> г12.F1 AND г7.F1 <> г13.F1                           
AND г8.F1 <> г9.F1 AND г8.F1 <> г10.F1 AND г8.F1 <> г11.F1 AND г8.F1 <> г12.F1 AND г8.F1 <> г13.F1  
AND г9.F1 <> г10.F1 AND г9.F1 <> г11.F1 AND г9.F1 <> г12.F1 AND г9.F1 <> г13.F1  
AND г10.F1 <> г11.F1 AND г10.F1 <> г12.F1 AND г10.F1 <> г13.F1  
AND г11.F1 <> г12.F1 AND г11.F1 <> г13.F1   
AND г12.F1 <> г13.F1    
                    
[/vba]


Excel + SQL = ActiveTables (http://vk.com/ExcelSQL)
 
Ответить
СообщениеПопробовал решить задачу в лоб, к сожалению SQL не дает больше 13 полей. Запрос выполнялся 8 мин. вместе с выводом данных.

[vba]
Код

SELECT  
г1.F1 AS F1,
г2.F1 AS F2,
г3.F1 AS F3,
г4.F1 AS F4,
г5.F1 AS F5,
г6.F1 AS F6,
г7.F1 AS F7,
г8.F1 AS F8,
г9.F1 AS F9,
г10.F1 AS F10,
г11.F1 AS F11,
г12.F1 AS F12,
г13.F1 AS F13
FROM
[Лист1$1:25] AS г1,
[Лист1$1:25] AS г2,
[Лист1$1:25] AS г3,
[Лист1$1:25] AS г4,
[Лист1$1:25] AS г5,
[Лист1$1:25] AS г6,
[Лист1$1:25] AS г7,
[Лист1$1:25] AS г8,
[Лист1$1:25] AS г9,
[Лист1$1:25] AS г10,
[Лист1$1:25] AS г11,
[Лист1$1:25] AS г12,
[Лист1$1:25] AS г13
WHERE
right(г1.F1,1) = left(г2.F1,1)  
AND
right(г2.F1,1) = left(г3.F1,1)  
AND
right(г3.F1,1) = left(г4.F1,1)  
AND
right(г4.F1,1) = left(г5.F1,1)  
AND
right(г5.F1,1) = left(г6.F1,1)  
AND
right(г6.F1,1) = left(г7.F1,1)  
AND
right(г7.F1,1) = left(г8.F1,1)  
AND
right(г8.F1,1) = left(г9.F1,1)  
AND
right(г9.F1,1) = left(г10.F1,1)  
AND
right(г10.F1,1) = left(г11.F1,1)
AND
right(г11.F1,1) = left(г12.F1,1)
AND
right(г12.F1,1) = left(г13.F1,1)
AND г1.F1 <> г2.F1 AND г1.F1 <> г2.F1 AND г1.F1 <> г3.F1 AND г1.F1 <> г4.F1 AND г1.F1 <> г5.F1 AND г1.F1 <> г6.F1 AND г1.F1 <> г7.F1 AND г1.F1 <> г8.F1 AND г1.F1 <> г9.F1 AND г1.F1 <> г10.F1 AND г1.F1 <> г11.F1 AND г1.F1 <> г12.F1 AND г1.F1 <> г13.F1               
AND г2.F1 <> г3.F1 AND г2.F1 <> г4.F1 AND г2.F1 <> г5.F1 AND г2.F1 <> г6.F1 AND г2.F1 <> г7.F1 AND г2.F1 <> г8.F1 AND г2.F1 <> г9.F1 AND г2.F1 <> г10.F1 AND г2.F1 <> г11.F1 AND г2.F1 <> г12.F1 AND г2.F1 <> г13.F1                 
AND г3.F1 <> г4.F1 AND г3.F1 <> г5.F1 AND г3.F1 <> г6.F1 AND г3.F1 <> г7.F1 AND г3.F1 <> г8.F1 AND г3.F1 <> г9.F1 AND г3.F1 <> г10.F1 AND г3.F1 <> г11.F1 AND г3.F1 <> г12.F1 AND г3.F1 <> г13.F1                    
AND г4.F1 <> г5.F1 AND г4.F1 <> г6.F1 AND г4.F1 <> г7.F1 AND г4.F1 <> г8.F1 AND г4.F1 <> г9.F1 AND г4.F1 <> г10.F1 AND г4.F1 <> г11.F1 AND г4.F1 <> г12.F1 AND г4.F1 <> г13.F1                       
AND г5.F1 <> г6.F1 AND г5.F1 <> г7.F1 AND г5.F1 <> г8.F1 AND г5.F1 <> г9.F1 AND г5.F1 <> г10.F1 AND г5.F1 <> г11.F1 AND г5.F1 <> г12.F1 AND г5.F1 <> г13.F1                            
AND г6.F1 <> г7.F1 AND г6.F1 <> г8.F1 AND г6.F1 <> г9.F1 AND г6.F1 <> г10.F1 AND г6.F1 <> г11.F1 AND г6.F1 <> г12.F1 AND г6.F1 <> г13.F1                           
AND г7.F1 <> г8.F1 AND г7.F1 <> г9.F1 AND г7.F1 <> г10.F1 AND г7.F1 <> г11.F1 AND г7.F1 <> г12.F1 AND г7.F1 <> г13.F1                           
AND г8.F1 <> г9.F1 AND г8.F1 <> г10.F1 AND г8.F1 <> г11.F1 AND г8.F1 <> г12.F1 AND г8.F1 <> г13.F1  
AND г9.F1 <> г10.F1 AND г9.F1 <> г11.F1 AND г9.F1 <> г12.F1 AND г9.F1 <> г13.F1  
AND г10.F1 <> г11.F1 AND г10.F1 <> г12.F1 AND г10.F1 <> г13.F1  
AND г11.F1 <> г12.F1 AND г11.F1 <> г13.F1   
AND г12.F1 <> г13.F1    
                    
[/vba]

Автор - PowerBoy
Дата добавления - 06.02.2014 в 10:16
MCH Дата: Четверг, 06.02.2014, 22:12 | Сообщение № 10
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3)

Андрей, не знаю как данную задачу решать за O(n3), матрицу смежности построить легко, а что дальше? какая здесь динамика?
Решал ее полным перебором, алгоритмом на подобии поиска в глубину на рекурсиях
 
Ответить
Сообщение
А задачка эта (в отличие от нахождения минимальных/кратчайших путей) - либо NP-полная, либо на ДП решаемая за O(n3)

Андрей, не знаю как данную задачу решать за O(n3), матрицу смежности построить легко, а что дальше? какая здесь динамика?
Решал ее полным перебором, алгоритмом на подобии поиска в глубину на рекурсиях

Автор - MCH
Дата добавления - 06.02.2014 в 22:12
MCH Дата: Среда, 12.02.2014, 01:02 | Сообщение № 11
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Прошла неделя, получил в личку только одно решение.

Хотя Андрей и писал
впрочем, решений кодом - и так достаточно известно

Но ответ так и не дал.

Задача не интересна? выкладывать собственный ответ?
 
Ответить
СообщениеПрошла неделя, получил в личку только одно решение.

Хотя Андрей и писал
впрочем, решений кодом - и так достаточно известно

Но ответ так и не дал.

Задача не интересна? выкладывать собственный ответ?

Автор - MCH
Дата добавления - 12.02.2014 в 01:02
Serge_007 Дата: Среда, 12.02.2014, 01:13 | Сообщение № 12
Группа: Админы
Ранг: Местный житель
Сообщений: 16475
Репутация: 2749 ±
Замечаний: ±

Excel 2016
Давай подождем Андрея

И мог бы на мой вопрос ответить:
сколько дополнительных ячеек задействовано? чем меньше, тем лучше
У тебя сколько?


[p.s.]Я в гугле решения не нашел[/p.s.]


ЮMoney:41001419691823 | WMR:126292472390
 
Ответить
СообщениеДавай подождем Андрея

И мог бы на мой вопрос ответить:
сколько дополнительных ячеек задействовано? чем меньше, тем лучше
У тебя сколько?


[p.s.]Я в гугле решения не нашел[/p.s.]

Автор - Serge_007
Дата добавления - 12.02.2014 в 01:13
MCH Дата: Среда, 12.02.2014, 01:52 | Сообщение № 13
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

И мог бы на мой вопрос ответить:

Четыре доп.столбца по 25 ячеек, и один столбец для ответа
 
Ответить
Сообщение
И мог бы на мой вопрос ответить:

Четыре доп.столбца по 25 ячеек, и один столбец для ответа

Автор - MCH
Дата добавления - 12.02.2014 в 01:52
AndreTM Дата: Понедельник, 17.02.2014, 17:48 | Сообщение № 14
Группа: Друзья
Ранг: Старожил
Сообщений: 1762
Репутация: 501 ±
Замечаний: 0% ±

2003 & 2010
Четыре доп.столбца по 25 ячеек, и один столбец для ответа
А формулы в доп.столбцах - не массивные, случаем? :D

Я формулами не стал решать. Ну просто потому, что задачки такого плана решать формулами не то, чтобы бессмысленно - но как-то некомильфовно :)
А полные переборы (если кто не в курсе - NP) и рекурсии - они, как бы, чисто программистские и алгоритмические, а посему решаемы средствами любого ЯП. А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время"), и к Excel'ю это перестаёт иметь даже отдаленное отношение :)

И да (Михаилу) - нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину", с предварительным переходом к псевдо-двойственному графу (т.е. замене рёбер на вершины, что дало возможность оперировать над конечным множеством символов алфавита в качестве вершин), но тогда всё упёрлось в вычисление всех циклов... И на объемах набора "городов" ниже пятого прорядка - проигрывая обычной тупой рекурсии...


Skype: andre.tm.007
Donate: Qiwi: 9517375010
 
Ответить
Сообщение
Четыре доп.столбца по 25 ячеек, и один столбец для ответа
А формулы в доп.столбцах - не массивные, случаем? :D

Я формулами не стал решать. Ну просто потому, что задачки такого плана решать формулами не то, чтобы бессмысленно - но как-то некомильфовно :)
А полные переборы (если кто не в курсе - NP) и рекурсии - они, как бы, чисто программистские и алгоритмические, а посему решаемы средствами любого ЯП. А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время"), и к Excel'ю это перестаёт иметь даже отдаленное отношение :)

И да (Михаилу) - нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину", с предварительным переходом к псевдо-двойственному графу (т.е. замене рёбер на вершины, что дало возможность оперировать над конечным множеством символов алфавита в качестве вершин), но тогда всё упёрлось в вычисление всех циклов... И на объемах набора "городов" ниже пятого прорядка - проигрывая обычной тупой рекурсии...

Автор - AndreTM
Дата добавления - 17.02.2014 в 17:48
MCH Дата: Понедельник, 17.02.2014, 23:53 | Сообщение № 15
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

А формулы в доп.столбцах - не массивные, случаем?

Даже если массивные, то какая разница?

Ну просто потому, что задачки такого плана решать формулами не то, чтобы бессмысленно - но как-то некомильфовно

Ну так на это есть VBA

А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время")

При данном перечне городов, полный перебор всех (495687) вариантов занимает менее минуты (на моем ноуте - 22 секунды), так что задача вполне решаема перебором и не особо требовательна к ресурсам.

нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину"...

Ответ на поставленный вопрос:
"Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов"
есть?

ИМХО, "Мозговой штурм" это не обязательно формулы, это может быть и решение на VBA или "поиском решения" или даже карандашом на листке бумаги (хотя данная задача не для формул, а для VBA)
 
Ответить
Сообщение
А формулы в доп.столбцах - не массивные, случаем?

Даже если массивные, то какая разница?

Ну просто потому, что задачки такого плана решать формулами не то, чтобы бессмысленно - но как-то некомильфовно

Ну так на это есть VBA

А там уже вступает в силу принцип экономии ресурсов (стандартный треугольник "память-проц-время")

При данном перечне городов, полный перебор всех (495687) вариантов занимает менее минуты (на моем ноуте - 22 секунды), так что задача вполне решаема перебором и не особо требовательна к ресурсам.

нормальной динамики я так и не придумал, максимум - замена полной рекурсии на "двойную глубину"...

Ответ на поставленный вопрос:
"Необходимо определить максимально возможную последовательность, которую можно составить из данного перечня и перечислить названия городов"
есть?

ИМХО, "Мозговой штурм" это не обязательно формулы, это может быть и решение на VBA или "поиском решения" или даже карандашом на листке бумаги (хотя данная задача не для формул, а для VBA)

Автор - MCH
Дата добавления - 17.02.2014 в 23:53
Serge_007 Дата: Вторник, 18.02.2014, 22:48 | Сообщение № 16
Группа: Админы
Ранг: Местный житель
Сообщений: 16475
Репутация: 2749 ±
Замечаний: ±

Excel 2016
Миш, вылкадывай свои решения, лично мне интересно узнать как ты решил задачу

А Андрея, видимо, мы не дождемся...


ЮMoney:41001419691823 | WMR:126292472390
 
Ответить
СообщениеМиш, вылкадывай свои решения, лично мне интересно узнать как ты решил задачу

А Андрея, видимо, мы не дождемся...

Автор - Serge_007
Дата добавления - 18.02.2014 в 22:48
MCH Дата: Среда, 19.02.2014, 00:18 | Сообщение № 17
Группа: Админы
Ранг: Старожил
Сообщений: 2004
Репутация: 752 ±
Замечаний: ±

Максимальная последовательность состоит из 20 городов

В файле решение макросом и формулами.
Решение формулами реализовано перебором на итерациях с запоминанием максимальной (итерации должны быть включены).
Для быстрого поиска наибольшей последовательности изменил порядок городов (если не менять, то поиск идет значительно дольше, но все равно находится)
Для запуска необходимо ввести какое либо число в ячейку C2. Если раскрыть группировку в столбцах G:J, то будет видно как происходит перебор городов.
К сообщению приложен файл: 1601269.xls (51.0 Kb)


Сообщение отредактировал MCH - Среда, 19.02.2014, 00:18
 
Ответить
СообщениеМаксимальная последовательность состоит из 20 городов

В файле решение макросом и формулами.
Решение формулами реализовано перебором на итерациях с запоминанием максимальной (итерации должны быть включены).
Для быстрого поиска наибольшей последовательности изменил порядок городов (если не менять, то поиск идет значительно дольше, но все равно находится)
Для запуска необходимо ввести какое либо число в ячейку C2. Если раскрыть группировку в столбцах G:J, то будет видно как происходит перебор городов.

Автор - MCH
Дата добавления - 19.02.2014 в 00:18
ZORRO2005 Дата: Среда, 19.02.2014, 09:46 | Сообщение № 18
Группа: Друзья
Ранг: Обитатель
Сообщений: 382
Репутация: 148 ±
Замечаний: 0% ±

Excel2010
Выкладываю свое решение.
"Поиск решения" подобрал максимальную цепочку в 19 городов, но с помощью хитрости я выудил у Миши название первого города и все стало на свои места.)
К сообщению приложен файл: 3357851.xlsx (68.5 Kb)
 
Ответить
СообщениеВыкладываю свое решение.
"Поиск решения" подобрал максимальную цепочку в 19 городов, но с помощью хитрости я выудил у Миши название первого города и все стало на свои места.)

Автор - ZORRO2005
Дата добавления - 19.02.2014 в 09:46
Stormy Дата: Воскресенье, 23.02.2014, 19:14 | Сообщение № 19
Группа: Проверенные
Ранг: Обитатель
Сообщений: 366
Репутация: 12 ±
Замечаний: 0% ±

Excel 2010
Вариант решения *карандашом* :p



Место для рекламы.
 
Ответить
СообщениеВариант решения *карандашом* :p


Автор - Stormy
Дата добавления - 23.02.2014 в 19:14
  • Страница 1 из 1
  • 1
Поиск:

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