Ключевое слово
13 | 02 | 2026
Новости Библиотеки
Шахматы Онлайн
Welcome, Guest
Username: Password: Remember me

TOPIC: алгоритмические задачки

алгоритмические задачки 17 Апр 2020 11:59 #241

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Помните, упоминалась выигрышная стратегия в игре "Морской бой": большие корабли размещаем компактно, максимизируя неопределенность в размещении катеров. Я решил проверить эту стратегию если не прямо, то косвенно.

Сначала я размещаю в змейке линкор и два крейсера, оставляя позади них минимальное место для эсминцев и катеров. Затем независимо я размещаю эсминцы, оставляя минимальное место спереди и сзади для линкора с крейсерами и катеров. Потом независимо я размещаю катера, оставляя минимальное место спереди для всех больших кораблей. После этого линкор и крейсера я соединяю с эсминцами, одно множество кораблей с другим. И наконец, к большим кораблям я присоединяю катера, к одному множеству другое. В итоге получается множество флотилий, помещающихся в данную змейку (число их обозначено m). Среди этого множества надо найти флотилию, после удаления клеток которой из змейки в ней, в остаточной змейке, помещается максимально возможное число (sub m) флотилий. Непосредственно найти ее (и sub m) я не могу, а нахожу определенное рекордное решение, одну или несколько рекордных флотилий (и sub m).

Так вот, в духе выигрышной стратегии будем искать рекордсменов не на всем множестве флотилий, а только среди флотилий, оставляющих наибольший простор для катеров. Так сказать, немного поможем рекордсменам, сориентируем их. Результат для наших 10 змеек длиной 50 клеток следующий - не хуже, чем в самый первый раз, а в двух случаях лучше; для удобства сравнения я привожу тот первый результат справа.

detrikletka_50_reduced.png
m-tabl-50_2020-04-17.png



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

detrisudno_50_reduced.png


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

Конечно, по большому счету логичнее всего иметь дело с рекордсменами наиболее емкой змейки, здесь последней из 10.
Сам себе доктор наук
Last Edit: 17 Апр 2020 12:54 by Sam Sebe.

алгоритмические задачки 17 Апр 2020 14:35 #242

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Несколько иначе сориентировал поиск в духе стратегии, более правильно (заодно исправил несерьезную ошибочку, вылезшую в конце третьей и пятой строчек). Результаты заметно изменились, и поклеточно и покорабельно.

detrikletka_50_reduced_rep.png


detrisudno_50_reduced_rep.png


Стратегия если и подтверждается, то не для самых емких змеек. Но стратегию это не опровергает, потому что оптимизация непрямая.
Сам себе доктор наук
Last Edit: 19 Апр 2020 12:06 by Sam Sebe.

алгоритмические задачки 22 Апр 2020 18:59 #243

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Перепробовал кучу идей, но ничего особо интересного не обнаружил. Вот, пожалуй, единственное исключение.

Если ограничиться стратегией предыдущего поста, то число соответствующих ей флотилий, помещающихся в 10 наших змеек длиной 50 клеток, относительно невелико и остаточное число флотилий для каждой удаляемой флотилии можно посчитать непосредственно (примерно за полчаса в целом), не вычисляя никаких детриментов, и тем самым оценить точность метода последних.

opt_50.png


Видно, если сравнивать sub m из предыдущего поста с этими sub m (всегда не меньшими тех), что метод детриментов работает в общем неплохо.

Например, в 4-й строчке число sub m равно 0. В данном случае существует 3784 флотилии, удовлетворяющие стратегии (из 106 066 возможных упорядоченных флотилий, которые все оказались rev, а dir отсутствуют), но после удаления любой из них, в змейке не хватает места ни для одной упорядоченной флотилии (из 106 066). Напротив, в случае 10-й строки существует одна (единственная) стратегическая флотилия, после удаления которой в змейку все еще помещается 86 650 упорядоченных флотилий - максимум локальный и - для всех 10 змеек - глобальный.
Сам себе доктор наук
Last Edit: 22 Апр 2020 19:49 by Sam Sebe.

алгоритмические задачки 26 Апр 2020 09:52 #244

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Напрашивается следующая идея, идея седловой точки. С одной стороны, за большими кораблями флотилии (упорядоченной) идут ее катера и каждой расстановке больших кораблей соответствует множество возможных расстановок катеров. С другой стороны, катерам предшествуют большие корабли и каждой расстановке катеров отвечает множество возможных расстановок больших кораблей. И одно множество и другое можно как минимизировать, так и максимизировать, чтобы для седловой клетки или флотилии иметь minmax = maxmin. Но сколько я ни старался, ничего путного из этой идеи у меня не получилось. ((

Зато удалось определить длину "тела" и "хвоста" змейки. Рассмотрим клетку, принадлежащую змейке и лежащую между большими кораблями флотилии, размещенной в змейке, и ее катерами. Этих клеток может быть много, тем более что они зависят и от флотилии и от змейки. Поэтому рассмотрим такую клетку, которая является промежуточной для наибольшего числа флотилий данной змейки. Эта клетка (изредка неединственная) и будет - по определению - разделять "тело" и "хвост" змейки. Для эксперимента я взял по 10 змеек длиной 50, 55, 60, 61, 62, 63 и 64 клетки. В итоге, в среднем, указанная клетка оказалась промежуточной примерно для 40% флотилий, а длина "хвоста" составила менее 30% длины всей змейки, причем я считал и измерял в обоих направлениях (dir и rev).

Погуглил для сравнения: у собственно змей средняя длина хвоста составляет до 20% их длины, вроде как. ))
Сам себе доктор наук
Last Edit: 26 Апр 2020 10:12 by Sam Sebe.

алгоритмические задачки 26 Апр 2020 15:42 #245

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Вот, изобразил для примера змейку максимальной длины, 64 клетки. Тело цвета охры имеет длину 45 клеток, хвост коричневый из 18 клеток, красная, 46-я клетка - "точка перегиба" - лежит между ними у 828 854 упорядоченных флотилий, которых в прямом направлении змейки насчитывается 2 153 018 штук, т.е. в 38.5% случаев.

zmejka_45118.png


Заметил такую вещь, что в прямом направлении - от начала к концу змейки по построению - хвост в среднем (у змеек всех длин) немного длиннее, чем в обратном направлении. В данном примере длина тела в обратном направлении была бы 47 клеток, а хвост был бы из 16 клеток, красная клетка была бы 48-й и промежуточной в 88494/237418 = 37.3% случаев.

Не знаю, как эту красную клетку назвать биологически по-научному. :)
Сам себе доктор наук
Last Edit: 26 Апр 2020 18:54 by Sam Sebe.

алгоритмические задачки 28 Апр 2020 15:59 #246

  • Sam Sebe
  • Sam Sebe's Avatar
  • OFFLINE
  • Самоед
  • Posts: 1309
  • Thank you received: 28
  • Karma: 3
Еще одна идея, которая напрашивается, - это определить размерность змейки. Вроде бы одномерная, одновременно она существенно покрывает всю доску и как бы двумерная, что намекает на ее промежуточную, фрактальную размерность. С одной стороны, у змейки есть емкость. С другой стороны, у нее есть длина. И нужно их как-то связать степенной зависимостью, но так, чтобы показатель степени был бы между 1 и 2. И сделать это естественным образом, не вводя никаких "эффективных" величин, так любимых физиками. )) Тем более что у змейки, если понадобится, есть тело, хвост (до головы я не додумался) и клетки, которые можно удалять.

Тоже вот бросается в глаза: если удалить из змейки любую размещенную в ней флотилию, то змейка станет сильно дырявой и похожей на Канторово множество, знаменито фрактальное.
Сам себе доктор наук
Last Edit: 28 Апр 2020 16:00 by Sam Sebe.

Головоломка 28 Апр 2024 07:57 #247

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Найти шесть пятибуквенных существительных русского языка с неповторяющимися буквами.
"Е", "Ё" считается одной буквой.

wordly_test.jpg


Для разминки начнити с пяти слов.

Головоломка 28 Апр 2024 17:08 #248

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Мой вариант из 5 слов :)

wordly_test3.jpg
The following user(s) said Thank You: Vladimirovich

Головоломка 30 Апр 2024 05:02 #249

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
alexlaw wrote:
Найти шесть пятибуквенных существительных русского языка с неповторяющимися буквами.
Есть ли решение - неизвестно :?
Надо это вопрос отдать компу - пусть думает он %-)
Но ему нужно помочь :writing:
Вот база из 2943 пятибуквенных слова :glasses: (с неповторяющимися буквами)

Deleted. Too big. Slows down(V)

Конечно здесь не только существительные (надо бы отсеять не существительные)

Остается скормить это все компу :beer: и пусть подумает
Last Edit: 13 Нояб 2025 09:04 by Vladimirovich.

Головоломка 30 Апр 2024 06:10 #250

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Боярин
  • Если кажется, что читерят, - то это не кажется!
  • Posts: 3596
  • Thank you received: 98
  • Karma: 23
Найти шесть пятибуквенных существительных

√ Отсеивать придётся "вручную". Разве что CHATGPT в помощь.
√ Значит, будет шесть вложенных циклов, а это скармливание займёт времени "до утра".
√ Очевидно, что слова с одной гласной будут в приоритете.
:glasses:
...не мы первые, не мы последние...

Головоломка 30 Апр 2024 10:12 #251

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Боярин
  • Если кажется, что читерят, - то это не кажется!
  • Posts: 3596
  • Thank you received: 98
  • Karma: 23
Прикинем насчёт шести пятибуквенных существительных.
Чистая арифметика: 33-5*6=3. Что крайне маловероятно. :popcorn:
То есть, если комбинация такая и будет найдена, то в зазоре останутся три буквы.
Например, малоупотребительные Ъ Й Щ.

На написание алгоритма 6*5 ушло 15 минут. Но ждать окончания перебора надоело.

А пока несколько примеров пятибуквенных пятёрок.

АБРЕК ВОЗНЯ ЖМУДЬ ХЛЮСТ ЩИПЦЫ
АБРЕК ВЫЖИГ ДОНЬЯ ЗУМПФ ХЛЮСТ
АБРИС ВЗДОХ МУЛЯЖ ФЕТЮК ШПЫНЬ
АБРИС ВЗЛОМ ТЮФЯК УДЭГЕ ШПЫНЬ
АБРИС ВЪЕЗД ГЛУШЬ МОХНЫ ТЮФЯК
АБРИС ВЪЕЗД ГЛУШЬ ТЮФЯК ЭПОНЖ
АБРИС ВЪЕЗД МУЛЯЖ ТЮЧОК ШПЫНЬ
АБРИС ВЪЕЗД ТЮФЯК ХОЛУЙ ШПЫНЬ
АБРИС ВЫЕЗД ГЛУШЬ ТЮФЯК ЭПОНЖ
АБРИС ТЮФЯК УЗДЦЫ ХМЕЛЬ ЭПОНЖ
АБРИС ТЮФЯК УЗДЦЫ ШМЕЛЬ ЭПОНЖ
АБЦУГ ВЕДРО КНЯЗЬ ФИЖМЫ ХЛЮСТ
АБЦКГ ВЕДРО МЯЧИК ХЛЮСТ ШПЫНЬ
АБЦУГ ВЕДРО ХЛЮСТ ШПЫНЬ ЯМЩИК

(пока хватит)
...не мы первые, не мы последние...

Головоломка 01 Май 2024 15:36 #252

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Простым "сочетанием" 6 из 2943 эту задачу не решить.

Screenshot_20240501-182755.png


Комп будет считать целую вечность :unsure:
Нужен какой-то алгоритм.
Какой - не знаю :?

Головоломка 01 Май 2024 16:28 #253

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 115084
  • Thank you received: 2532
  • Karma: 119
В кэш надо что нито записать изначально
Для каждого слова создать списки только совместимых слов
Это О2, это недолго и должно сократить потом проход
Потом для каждого слова уже искать не из 2943, а только в этом списке для этого слова

Можно еще улучшить
Каждому - своё.

Головоломка 02 Май 2024 06:34 #254

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Боярин
  • Если кажется, что читерят, - то это не кажется!
  • Posts: 3596
  • Thank you received: 98
  • Karma: 23
  // пример для двух слов

  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
...не мы первые, не мы последние...

Головоломка 02 Май 2024 07:12 #255

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Я собираюсь тоже попробовать набросать код :writing:
У меня идея такая:
  • 32 буквы (Е Ё) одна буква - это 32 бита А первый включенный бит, Я последний (тридцать первй).
  • Значит решением будет число с 30 включенными битами.
  • Перекодируем словарь в числа.
  • Разделяем на списки (по начальной букве)
  • Берем случайным образом шесть (чисел) слов из разных списков
  • Делаем XOR c шестью числами
  • Считаем кол-во бит
  • Если 30 бит, то стоп.

Головоломка 03 Май 2024 04:14 #256

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
alexlaw wrote:
Делаем XOR c шестью числами
Эта мысль не верна.
  1. 1 xor 1 xor 1 xor 1 xor 1 xor 1 = 0
  2. 1 xor 1 xor 1 xor 1 xor 1 xor 0 = 1
  3. 1 xor 1 xor 1 xor 1 xor 0 xor 0 = 0
  4. 1 xor 1 xor 1 xor 0 xor 0 xor 0 = 1
  5. 1 xor 1 xor 0 xor 0 xor 0 xor 0 = 0
  6. 1 xor 0 xor 0 xor 0 xor 0 xor 0 = 1
Если более 1 единицы, то нам нужен 0

Ну да ладно, пока немного кода
//для записи инфы в файл -  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)
Last Edit: 13 Нояб 2025 09:06 by Vladimirovich.

Головоломка 04 Май 2024 07:49 #257

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Взял словарь - Более 67 тысяч русских существительных в именительном падеже
Чуть подправил свой код из предыдущего поста.
Получил словарь из 2923 слов с не повторяющимися буквами в слове

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 ]
Last Edit: 13 Нояб 2025 09:07 by Vladimirovich.

Головоломка 05 Май 2024 12:17 #258

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
До меня дошло :idea:
Нужно применить к шести числам логическую операцию "или".
Если в результате получиться число с 30 включенными битами, то этот набор из 6 чисел - решение.
Если меньше 30 бит, то в наборе есть повторы, и не важно конкретные числа. Меняем полностью все шесть чисел на новые.
Поправьте, :glasses: если Я не прав.

Головоломка 10 Май 2024 04:51 #259

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Ну что ж :)
Решения из 6 слов найти не удалось.
Но четкого математического ответа, что это не возможно, то-же нет.
Набросал прогу по алгоритму указанному выше.

wordly5x5.jpg


Недостаток основной - это случайные выбор слов :unsure:

Поэтому исправлю на сочетания
Вот немного об этом - алгоритм
Last Edit: 10 Май 2024 04:52 by alexlaw.
The following user(s) said Thank You: Andralex

Головоломка 19 Май 2024 06:18 #260

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Решения для 6 слов нет на 99%.
_2024_05_19_09_05_59_990.gif

Головоломка 19 Май 2024 06:49 #261

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 115084
  • Thank you received: 2532
  • Karma: 119
alexlaw wrote:
Решения для 6 слов нет на 99%.
Это уже не головоломка :)
Каждому - своё.

Головоломка 19 Май 2024 07:04 #262

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Vladimirovich wrote:
Это уже не головоломка :)
Хорошо, пусть будет просто задача века, типа квадратуры круга :glasses:

Головоломка 07 Июнь 2024 20:41 #263

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
alexlaw wrote:
Vladimirovich wrote:
Это уже не головоломка :)
Хорошо, пусть будет просто задача века, типа квадратуры круга :glasses:

:writing: Решил!!!
Есть решение и я его нашел :)

Головоломка 08 Июнь 2024 01:52 #264

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 115084
  • Thank you received: 2532
  • Karma: 119
:glasses:
Каждому - своё.

Интересная задача 21 Авг 2024 04:21 #265

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Попалась на глаза задача -
В выражении 1+2*3+4*5+6*7+8*9+10 расставить две пары скобок так, чтобы значение выражения стало равным 537
Задача для программистов, т.к. ни какого логического решения нет.
Мне пришел в голову алгоритм решения и я его реализовал и провел полный анализ выражения 1+2*3+4*5+6*7+8*9+10
Хотелось услышать у кого какие идеи по поводу алгоритма решения :)

Интересная задача 21 Авг 2024 06:00 #266

  • Andralex
  • Andralex's Avatar
  • OFFLINE
  • Боярин
  • Если кажется, что читерят, - то это не кажется!
  • Posts: 3596
  • Thank you received: 98
  • Karma: 23
1+2*3+4*5+6*7+8*9+10
Нечто похожее печатали давным давно в журнале "Наука и Жизнь". Там в задачках было расставить знаки +/-Х между цифрами.

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

(1 + 2) * (3 + 4) * 5 + 6 * 7 + 8 * 9 + 10
(1 + 2) * (3 + 4 * 5) + 6 * 7 + 8 * 9 + 10
(1 + 2) * (3 + 4 * 5 + 6) * 7 + 8 * 9 + 10
и т.д.

(1 + (2 * 3) + 4) * 5 + 6 * 7 + 8 * 9 + 10
(1 + (2 * 3) + 4 * 5) + 6 * 7 + 8 * 9 + 10
(1 + (2 * 3) + 4 * 5 + 6) * 7 + 8 * 9 + 10
и т.д.

P.S. Для подсчёта выражения проще использовать функцию JS.eval()
...не мы первые, не мы последние...

Интересная задача 21 Авг 2024 06:13 #267

  • Vladimirovich
  • Vladimirovich's Avatar
  • OFFLINE
  • Инквизитор
  • Posts: 115084
  • Thank you received: 2532
  • Karma: 119
На всякий случай добавлю ссылку на параллельную тему
алгоритмические задачки
Каждому - своё.

Интересная задача 21 Авг 2024 06:40 #268

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Andralex wrote:
А дальше комбинаторика с полным перебором всевозможных расстановок скобок в позициях
Пошел другим путем, реализовал другой алгоритм.
В двух словах алгоритм такой.
1. Поставить одну пару скобок
первый цикл
- парсим строку задачи слева на право
- вставляем ( в первую позицию строки задачи
- или если попали на символ + или *, то вставляем ( на позицию за этим символом
- после каждой итерации или перед ней восстанавливаем строку до состояния входа в цикл
второй цикл
- парсим строку задачи справа на лево
- вставляем ) в крайнюю позицию строки задачи
- или если попали на символ + или *, то вставляем ) в позицию этого символом
после каждой итерации второго цикла должна получиться одна пара скобок
- находим и вычисляем значение в скобках , чтобы в дальнейшем заменить выражение в скобках этим значением
- после каждой итерации или перед ней восстанавливаем строку до состояния входа в цикл

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

Табл. после получения всех вариантов расстановки одной пары скобок для исходной строки задачи 1+2*3+4*5+6*7+8*9+10

Warning: Spoiler! [ Click to expand ]

Интересная задача 21 Авг 2024 06:45 #269

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
После анализа получил все возможные варианты ответов для исходного условия
ответ кол-во
Warning: Spoiler! [ Click to expand ]

Интересная задача 21 Авг 2024 07:24 #270

  • alexlaw
  • alexlaw's Avatar
  • OFFLINE
  • Сокольничий
  • Posts: 331
  • Thank you received: 15
  • Karma: 3
Andralex wrote:
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;
Moderators: Grigoriy
Рейтинг@Mail.ru

Научно-шахматный клуб КвантоФорум