Помните, упоминалась выигрышная стратегия в игре "Морской бой": большие корабли размещаем компактно, максимизируя неопределенность в размещении катеров. Я решил проверить эту стратегию если не прямо, то косвенно.
Сначала я размещаю в змейке линкор и два крейсера, оставляя позади них минимальное место для эсминцев и катеров. Затем независимо я размещаю эсминцы, оставляя минимальное место спереди и сзади для линкора с крейсерами и катеров. Потом независимо я размещаю катера, оставляя минимальное место спереди для всех больших кораблей. После этого линкор и крейсера я соединяю с эсминцами, одно множество кораблей с другим. И наконец, к большим кораблям я присоединяю катера, к одному множеству другое. В итоге получается множество флотилий, помещающихся в данную змейку (число их обозначено m). Среди этого множества надо найти флотилию, после удаления клеток которой из змейки в ней, в остаточной змейке, помещается максимально возможное число (sub m) флотилий. Непосредственно найти ее (и sub m) я не могу, а нахожу определенное рекордное решение, одну или несколько рекордных флотилий (и sub m).
Так вот, в духе выигрышной стратегии будем искать рекордсменов не на всем множестве флотилий, а только среди флотилий, оставляющих наибольший простор для катеров. Так сказать, немного поможем рекордсменам, сориентируем их. Результат для наших 10 змеек длиной 50 клеток следующий - не хуже, чем в самый первый раз, а в двух случаях лучше; для удобства сравнения я привожу тот первый результат справа.
Это если определять детрименты поклеточно, как в самый первый раз. А если определять их покорабельно, то результат, как и раньше, получается так себе.
Таким образом, косвенно подтверждается, что катера должны иметь наибольший простор для размещения.
Конечно, по большому счету логичнее всего иметь дело с рекордсменами наиболее емкой змейки, здесь последней из 10.
Несколько иначе сориентировал поиск в духе стратегии, более правильно (заодно исправил несерьезную ошибочку, вылезшую в конце третьей и пятой строчек). Результаты заметно изменились, и поклеточно и покорабельно.
Стратегия если и подтверждается, то не для самых емких змеек. Но стратегию это не опровергает, потому что оптимизация непрямая.
Перепробовал кучу идей, но ничего особо интересного не обнаружил. Вот, пожалуй, единственное исключение.
Если ограничиться стратегией предыдущего поста, то число соответствующих ей флотилий, помещающихся в 10 наших змеек длиной 50 клеток, относительно невелико и остаточное число флотилий для каждой удаляемой флотилии можно посчитать непосредственно (примерно за полчаса в целом), не вычисляя никаких детриментов, и тем самым оценить точность метода последних.
Видно, если сравнивать sub m из предыдущего поста с этими sub m (всегда не меньшими тех), что метод детриментов работает в общем неплохо.
Например, в 4-й строчке число sub m равно 0. В данном случае существует 3784 флотилии, удовлетворяющие стратегии (из 106 066 возможных упорядоченных флотилий, которые все оказались rev, а dir отсутствуют), но после удаления любой из них, в змейке не хватает места ни для одной упорядоченной флотилии (из 106 066). Напротив, в случае 10-й строки существует одна (единственная) стратегическая флотилия, после удаления которой в змейку все еще помещается 86 650 упорядоченных флотилий - максимум локальный и - для всех 10 змеек - глобальный.
Напрашивается следующая идея, идея седловой точки. С одной стороны, за большими кораблями флотилии (упорядоченной) идут ее катера и каждой расстановке больших кораблей соответствует множество возможных расстановок катеров. С другой стороны, катерам предшествуют большие корабли и каждой расстановке катеров отвечает множество возможных расстановок больших кораблей. И одно множество и другое можно как минимизировать, так и максимизировать, чтобы для седловой клетки или флотилии иметь minmax = maxmin. Но сколько я ни старался, ничего путного из этой идеи у меня не получилось. ((
Зато удалось определить длину "тела" и "хвоста" змейки. Рассмотрим клетку, принадлежащую змейке и лежащую между большими кораблями флотилии, размещенной в змейке, и ее катерами. Этих клеток может быть много, тем более что они зависят и от флотилии и от змейки. Поэтому рассмотрим такую клетку, которая является промежуточной для наибольшего числа флотилий данной змейки. Эта клетка (изредка неединственная) и будет - по определению - разделять "тело" и "хвост" змейки. Для эксперимента я взял по 10 змеек длиной 50, 55, 60, 61, 62, 63 и 64 клетки. В итоге, в среднем, указанная клетка оказалась промежуточной примерно для 40% флотилий, а длина "хвоста" составила менее 30% длины всей змейки, причем я считал и измерял в обоих направлениях (dir и rev).
Погуглил для сравнения: у собственно змей средняя длина хвоста составляет до 20% их длины, вроде как. ))
Вот, изобразил для примера змейку максимальной длины, 64 клетки. Тело цвета охры имеет длину 45 клеток, хвост коричневый из 18 клеток, красная, 46-я клетка - "точка перегиба" - лежит между ними у 828 854 упорядоченных флотилий, которых в прямом направлении змейки насчитывается 2 153 018 штук, т.е. в 38.5% случаев.
Заметил такую вещь, что в прямом направлении - от начала к концу змейки по построению - хвост в среднем (у змеек всех длин) немного длиннее, чем в обратном направлении. В данном примере длина тела в обратном направлении была бы 47 клеток, а хвост был бы из 16 клеток, красная клетка была бы 48-й и промежуточной в 88494/237418 = 37.3% случаев.
Не знаю, как эту красную клетку назвать биологически по-научному.
Еще одна идея, которая напрашивается, - это определить размерность змейки. Вроде бы одномерная, одновременно она существенно покрывает всю доску и как бы двумерная, что намекает на ее промежуточную, фрактальную размерность. С одной стороны, у змейки есть емкость. С другой стороны, у нее есть длина. И нужно их как-то связать степенной зависимостью, но так, чтобы показатель степени был бы между 1 и 2. И сделать это естественным образом, не вводя никаких "эффективных" величин, так любимых физиками. )) Тем более что у змейки, если понадобится, есть тело, хвост (до головы я не додумался) и клетки, которые можно удалять.
Тоже вот бросается в глаза: если удалить из змейки любую размещенную в ней флотилию, то змейка станет сильно дырявой и похожей на Канторово множество, знаменито фрактальное.
Найти шесть пятибуквенных существительных русского языка с неповторяющимися буквами.
Есть ли решение - неизвестно
Надо это вопрос отдать компу - пусть думает он
Но ему нужно помочь
Вот база из 2943 пятибуквенных слова (с неповторяющимися буквами)
Deleted. Too big. Slows down(V)
Конечно здесь не только существительные (надо бы отсеять не существительные)
√ Отсеивать придётся "вручную". Разве что CHATGPT в помощь.
√ Значит, будет шесть вложенных циклов, а это скармливание займёт времени "до утра".
√ Очевидно, что слова с одной гласной будут в приоритете.
Прикинем насчёт шести пятибуквенных существительных.
Чистая арифметика: 33-5*6=3. Что крайне маловероятно.
То есть, если комбинация такая и будет найдена, то в зазоре останутся три буквы.
Например, малоупотребительные Ъ Й Щ.
На написание алгоритма 6*5 ушло 15 минут. Но ждать окончания перебора надоело.
В кэш надо что нито записать изначально
Для каждого слова создать списки только совместимых слов
Это О2, это недолго и должно сократить потом проход
Потом для каждого слова уже искать не из 2943, а только в этом списке для этого слова
// пример для двух слов
Stroka = "" ; Bukva = ""; FlagPovtor=false ;
// сумматор для символа флаг повторов
for (x1=1; x1<=kovlo_records("Table"); x1++)
{ for (x2=(x1+1); x2<=kovlo_records("Table"); x2++)
{
GoToRecord x1 ;
Stroka = [ Spisok ]; // запоминаем первое словов из колонки таблицы
GotoRecord x2 ;
FlagPovtor=false;
for (z=1; z<=5; z++) // крощим на буквы второе слово
{
Bukva= SubString([ Spisok ], z, 1);
if (SearchString(Stroka,Bukva)) >0
// ищем совпадения каждой из букв второго слова в пером слове
{ // если буквы повторяются, то выполняется следующая итерация x2
Flagpovtor=true; Break; // выходим из цикла
}
} // for z
if (FlagPovtor==false) // здесь два слова без повторов букв
Stroka += [ Spisok ]; // Складываем в строку и переходим к третьему слову
// и т.д. по аналогии до шестого слова
} // for x2
} // for x1
//для записи инфы в файл - test.txt
procedure WriteToFile(s:string;flag:Integer);
var
F: TextFile;
begin
try
AssignFile(F, ExtractFilePath(Application.ExeName)+'test.txt');{Ассоциируем переменную с файлом}
case flag of
0:Rewrite(F); {файла нет или он должен быть перезаписан, открытие для записи}
1:Append(F);
end;
Write(F,s);
finally
CloseFile(F);
end;
end;
//перекодируем слова в числовой код
procedure TWordle_6.FormCreate(Sender: TObject);
var
str_wordle,str:string;
i,j,z:integer;
U32:cardinal;
begin
//файла test.txt нет или он должен быть перезаписан
WriteToFile('',0);
//имя файла со словарем
str_wordle:='2941_Words.txt';
try
//текущая директория приложения
FName:=ExtractFilePath(Application.ExeName);
//если словарь существует
if FileExists(FName+str_wordle) then begin
//загружаем словарь из файла в ListBox1
ListBox1.Items.LoadFromFile(FName+str_wordle);
//копируем словарь в ListBox2
ListBox2.Items:=ListBox1.Items;
//перебераем слова в словаре - ListBox1.Items[i]
for i := 0 to ListBox1.Count - 1 do begin
//переменная для числового кода слова
U32:=0;
//парсим слово по буквам
for j := 0 to 4 do begin
//следующая буква слова
str:=copy(ListBox1.Items[i],j+1,1);
//позиция буквы в слове равна позиции бита в коде слова
for z := 1 to 32 do begin
if (str=AlfaBet[z]) then begin
//получаем код слова
U32:=U32 or (1 shl (z-1));
end;
end;
end;
//заменяем слово в ListBox2 на его код
ListBox2.Items[i]:=Format('%u', [U32]);
//если в коде слова 5 бит то пишем в файл
//делаем один раз, затем закомментируем эту строку
if UsePopcnt(StrToInt64(ListBox2.Items[i]))=5 then WriteToFile(ListBox2.Items[i]+#13#10,1);
end;
//начальные позиции словаря и его кода в ListBox
ListBox1.ItemIndex:=0;
ListBox2.ItemIndex:=0;
end else begin
//словарь не найден
ShowMessage('файл '+str_wordle+' не найден');
end;
finally
end;
end;
//функция подсчета бит
function UsePopcnt(value: Cardinal): Cardinal;
asm
DB $F3, $0F, $B8, $C0 // popcnt eax, eax
end;
AlfaBet: array [1..34] of string =('Й','Ц','У','К','Е','Н','Г','Ш','Щ','З','Х','Ъ',
'Ф','Ы','В','А','П','Р','О','Л','Д','Ж','Э',
'Я','Ч','С','М','И','Т','Ь','Б','Ю',
'33','34');
Буквы расположены, как на клавиатуре.
Порядок бит Й - первый бит, Ю - последний.
Это не принципиально
Перекодируемый словарь (в каждом числе установлено ровно 5 бит) Deleted. Too big. Slows down(V)
Вопрос чисто математический (или логический). Отобрать из списка чисел (в каждом числе из списка включено ровно 5 бит) шесть чисел с несовпадающими позициями включенных бит.
Т.е. A or B or C or D or E or F = G (в G будут включены 30 бит)
Warning: Spoiler![ Click to expand ][ Click to hide ]
До меня дошло
Нужно применить к шести числам логическую операцию "или".
Если в результате получиться число с 30 включенными битами, то этот набор из 6 чисел - решение.
Если меньше 30 бит, то в наборе есть повторы, и не важно конкретные числа. Меняем полностью все шесть чисел на новые.
Поправьте, если Я не прав.
Ну что ж
Решения из 6 слов найти не удалось.
Но четкого математического ответа, что это не возможно, то-же нет.
Набросал прогу по алгоритму указанному выше.
Недостаток основной - это случайные выбор слов
Поэтому исправлю на сочетания
Вот немного об этом - алгоритм
Попалась на глаза задача -
В выражении 1+2*3+4*5+6*7+8*9+10 расставить две пары скобок так, чтобы значение выражения стало равным 537
Задача для программистов, т.к. ни какого логического решения нет.
Мне пришел в голову алгоритм решения и я его реализовал и провел полный анализ выражения 1+2*3+4*5+6*7+8*9+10
Хотелось услышать у кого какие идеи по поводу алгоритма решения
Нечто похожее печатали давным давно в журнале "Наука и Жизнь". Там в задачках было расставить знаки +/-Х между цифрами.
На первый взгляд, если есть две пары скобок, то они могут быть как вложенные так и последовательные. А дальше комбинаторика с полным перебором всевозможных расстановок скобок в позициях.
А дальше комбинаторика с полным перебором всевозможных расстановок скобок в позициях
Пошел другим путем, реализовал другой алгоритм.
В двух словах алгоритм такой.
1. Поставить одну пару скобок
первый цикл
- парсим строку задачи слева на право
- вставляем ( в первую позицию строки задачи
- или если попали на символ + или *, то вставляем ( на позицию за этим символом
- после каждой итерации или перед ней восстанавливаем строку до состояния входа в цикл
второй цикл
- парсим строку задачи справа на лево
- вставляем ) в крайнюю позицию строки задачи
- или если попали на символ + или *, то вставляем ) в позицию этого символом после каждой итерации второго цикла должна получиться одна пара скобок
- находим и вычисляем значение в скобках , чтобы в дальнейшем заменить выражение в скобках этим значением
- после каждой итерации или перед ней восстанавливаем строку до состояния входа в цикл
После получения всех вариантов расстановки одной пары скобок повторяем для каждого варианта алгоритм расстановки одной пары скобок для каждой модифицированной строки с внесенными изменениями (выражение в скобках заменяется на его значение).
Табл. после получения всех вариантов расстановки одной пары скобок для исходной строки задачи 1+2*3+4*5+6*7+8*9+10
Warning: Spoiler![ Click to expand ][ Click to hide ]
P.S. Для подсчёта выражения проще использовать функцию JS.eval()
В делфи тоже есть аналогичная возможность
//uses ComObj
function Eval_test(Str_eval:string):string;
var
sc: Variant;
begin
result:='';
SC:=CreateOLEObject('ScriptControl');
try
SC.Language:='VBScript';
SC.Timeout:=-1;
SC.AllowUI:=True;
result:=VarToStr(SC.Eval(Str_eval));
except
on E : Exception do
ShowMessage(E.ClassName+' поднята ошибка, с сообщением : '+E.Message);
end;
SC:=Unassigned;
end;