Алгоритм Маркова

java
  1. import java.util.ArrayList;
  2.  
  3. public class AlgorithmMarkov {
  4.  
  5.     public static void main(String[] args) {
  6.         /* Исходные данные */
  7.         // Слово
  8.         String P = "213022";
  9.         // Правила подстановки
  10.         ArrayList<Replacement> rules = new ArrayList<>();
  11.         rules.add(new Replacement("~0", "00~"));
  12.         rules.add(new Replacement("~1", "01~"));
  13.         rules.add(new Replacement("~2", "10~"));
  14.         rules.add(new Replacement("~3", "11~"));
  15.         rules.add(new Replacement("~", "", true)); // заключительная подстановка
  16.         rules.add(new Replacement("", "~"));
  17.  
  18.         /* Реализация */
  19.         int step = 0;
  20.         boolean iterate = true;
  21.         // Ограничение на 1000 итераций
  22.         while(iterate && (step < 1000)) {
  23.             String pref = P;
  24.             for (int i = 0; i < rules.size(); i++) {
  25.                 Replacement current = rules.get(i);
  26.                 String replaceString = replaceFirst(P, current);
  27.                 // Если что-то изменилось в слове, то начинаем цикл заново с полученным словом
  28.                 if (!replaceString.equals(P)) {
  29.                     P = replaceString;
  30.                     step++;
  31.                     // Если произошла заключительная подстановка - выходим
  32.                     if (current.endless) iterate = false;
  33.                     break;
  34.                 }
  35.             }
  36.             if (pref.equals(P)) break; // Если ни одно правило не изменило слово - выходим
  37.             System.out.println(step+" P=\""+P+"\"");
  38.         }
  39.     }
  40.  
  41.     private static String replaceFirst(String str, Replacement replace) {
  42.         // Если заменяем пустой символ на что-то, то склеиваем что-то со словом.
  43.         if (replace.from.length() == 0) return replace.to+str;// _ -> *
  44.         // Заменяем первое вхождение
  45.         return str.replaceFirst(replace.from, replace.to);
  46.     }
  47.  
  48.     private static class Replacement {
  49.  
  50.         /* Что на что заменять */
  51.         private String from, to;
  52.         /* Заключительная подстановка */
  53.         private boolean endless;
  54.  
  55.         private Replacement(String from, String to) {
  56.             this(from, to, false);
  57.         }
  58.  
  59.         private Replacement(String from, String to, boolean endless) {
  60.             this.from = from;
  61.             this.to = to;
  62.             this.endless = endless;
  63.         }
  64.  
  65.     }
  66. }
Пример перевода числа из четверичной системы счисления в двоичную с использованием нормального алгоритма Маркова.
Можно добавлять свои правила и менять исходные данные. Только в правилах подстановки не следует юзать регулярные символы, такие как *
Назад

Реклама

Мы в соцсетях

tw tg yt gt