За последние 24 часа нас посетили 22709 программистов и 1046 роботов. Сейчас ищут 707 программистов ...

Алгоритм расстановки точек

Тема в разделе "Решения, алгоритмы", создана пользователем akeelow, 8 июн 2016.

  1. akeelow

    akeelow Активный пользователь

    С нами с:
    10 апр 2012
    Сообщения:
    58
    Симпатии:
    0
    Появилась возможность расставить точки в слове, после каждой буквы. Даже так, нагенерировать все возможные варианты, без повторений.

    Колдовал часик, получилось так:

    PHP:
    1. <?php
    2.  
    3.  
    4. $str = "ocicancel";
    5.  
    6. $lstr = strlen( $str );
    7.  
    8. for( $i = 0; $i < $lstr; $i++ )
    9. {
    10.     echo substr( $str , 0 , $lstr - $i ) . "." . substr( $str , $lstr-$i , $i ) . "<br>";
    11. }
    12. ?>
    Вывод:
    Код (Text):
    1. ocicancel.
    2. ocicance.l
    3. ocicanc.el
    4. ocican.cel
    5. ocica.ncel
    6. ocic.ancel
    7. oci.cancel
    8. oc.icancel
    9. o.cicancel
    Теперь нужно каждое слово надо обратно прогнать по циклу. Как их сохранять? в текстовом файле или массив создавать? Еще как-то проверить что бы точки подряд не ставились.
     
  2. anderstender

    anderstender Новичок

    С нами с:
    15 ноя 2016
    Сообщения:
    55
    Симпатии:
    25
    понимаю что автору это уже нафиг не уперлось, но мне стало интересно,
    в общем вот решение:

    PHP:
    1. /*
    2. суть алгоритма вот в чем, количество итераций у нас 2 ^ n , где n это количество символов
    3. номер итерации можно представить в двоичном виде
    4. двоичное представления номера итерации это по сути карта точек
    5. причем количество битов совпадает с количеством символов, 0 или 1 указывает на необходимость нарисовать точку
    6. ну далее для каждой итерации по её двоичному представлению преобразовываем слова
    7.  
    8. $nMaxIter - 2 так как реально количество итераций уменьшено
    9. на первой итерации мы сразу перескакиваем на единичку, так как 0 нет смысла обрабатывать
    10. и последняя итерация нам не нужна, так как там будет переход регистра, который также обнулит все биты
    11. */
    12.  
    13.  
    14.  
    15. $sBaseWord = "ocicancel";
    16.  
    17. //смысл этой штуки в подсчете количества итераций
    18. $nMaxIter = pow(2, mb_strlen($sBaseWord));
    19. $iter = 0;
    20.  
    21. while($iter <= ($nMaxIter - 2)){
    22.     echo getWord($sBaseWord, (++$iter)) . '<br/>';
    23. }
    24.  
    25. function getWord($sBaseWord, $nIter){
    26.     $sResWord = "";
    27.     $nMaxIndex = mb_strlen($sBaseWord) - 1;
    28.  
    29.     for($i = 0; $i <= $nMaxIndex; $i++){
    30.         $sResWord .= mb_substr($sBaseWord, $i, 1);
    31.         $sResWord .= (($nIter & (1 << $i)) ? '.' : '' );
    32.     }
    33.     return $sResWord;
    34. }
     
    igordata и denis01 нравится это.