Рубрики

Генерация всех двоичных строк по заданному шаблону

Дана строка, содержащая «0», «1» и «?» подстановочные знаки, генерируют все двоичные строки, которые могут быть сформированы путем замены каждого подстановочного знака на «0» или «1».
Пример :

Input str = "1??0?101"
Output: 
        10000101
        10001101
        10100101
        10101101
        11000101
        11001101
        11100101
        11101101

Метод 1 (Использование рекурсии)
Мы передаем индекс следующего символа в рекурсивную функцию. Если текущий символ является символом подстановки «?», Мы заменяем его на «0» или «1» и повторяем для оставшихся символов. Мы печатаем строку, если достигнем ее конца.

Ниже приведена рекурсивная реализация.

C ++

// Рекурсивная программа на C ++ для генерации всех двоичных строк
// формируется путем замены каждого символа подстановки на 0 или 1
#include <iostream>

using namespace std;

  
// Рекурсивная функция для генерации всех двоичных строк
// формируется путем замены каждого символа подстановки на 0 или 1

void print(string str, int index)

{

    if (index == str.size())

    {

        cout << str << endl;

        return;

    }

  

    if (str[index] == '?')

    {

        // заменить '?' на 0 и рекурсировать

        str[index] = '0';

        print(str, index + 1);

  

        // заменить '?' на 1 и рекурсивно

        str[index] = '1';

        print(str, index + 1);

  

        // Нет необходимости возвращаться при передаче строки

        // по значению функции

    }

    else

        print(str, index + 1);

}

  
// Код драйвера для проверки вышеуказанной функции

int main()

{

    string str = "1??0?101";

  

    print(str, 0);

  

    return 0;

}

Джава

// Рекурсивная Java-программа для генерации всего
// двоичные строки, образованные заменой
// каждый символ подстановки 0 или 1

import java.util.*;

import java.lang.*;

import java.io.*;

  

class binStr

{   

    // Рекурсивная функция для генерации всего двоичного файла

    // строки, образованные заменой каждого шаблона

    // символ 0 или 1

    public static void print(char str[], int index)

    {

        if (index == str.length)

        {

            System.out.println(str);

            return;

        }

  

        if (str[index] == '?')

        {

            // заменить '?' на 0 и рекурсировать

            str[index] = '0';

            print(str, index + 1);

              

            // заменить '?' на 1 и рекурсивно

            str[index] = '1';

            print(str, index + 1);

              

            // ПРИМЕЧАНИЕ: нужно возвращать как строку

            // передается по ссылке на

            // функция

            str[index] = '?';

        }

        else

            print(str, index + 1);

    }

  

    // код драйвера

    public static void main (String[] args)

    {

        String input = "1??0?101";

        char[] str = input.toCharArray();

        print(str, 0);

    }

}

  
// Этот код предоставлен Чхави

python3

# Рекурсивная программа Python для генерации всех
# двоичные строки, образованные заменой
# каждый символ подстановки 0 или 1

  
# Рекурсивная функция для генерации всего двоичного файла
# строки, образованные заменой каждого шаблона
# символ 0 или 1

def _print(string, index):

    if index == len(string):

        print(''.join(string))

        return

  

    if string[index] == "?":

  

        # заменить '?' на 0 и рекурсировать

        string[index] = '0'

        _print(string, index + 1)

  

        # заменить '?' на 1 и рекурсивно

        string[index] = '1'

        _print(string, index + 1)

  

        # ПРИМЕЧАНИЕ: нужно возвращать как строку

        # передается по ссылке на

        # функция

        string[index] = '?'

    else:

        _print(string, index + 1)

  
# Код драйвера

if __name__ == "__main__":

  

    string = "1??0?101"

    string = list(string)

    _print(string, 0)

  

    # Этот код предоставлен

    # sanjeev2552

  
# Примечание: имя функции _print используется потому, что
# print - это уже предопределенная функция в Python

C #

// Рекурсивная C # программа для генерации всего
// двоичные строки, образованные заменой
// каждый символ подстановки 0 или 1

using System; 

  

class GFG

    // Рекурсивная функция для генерации

    // все двоичные строки, образованные

    // заменяем каждый подстановочный знак

    // на 0 или 1

    public static void print(char []str, 

                             int index)

    {

        if (index == str.Length)

        {

            Console.WriteLine(str);

            return;

        }

  

        if (str[index] == '?')

        {

            // заменить '?' по

            // '0' и рекурсивный

            str[index] = '0';

            print(str, index + 1);

              

            // заменить '?' по

            // '1' и рекурсивный

            str[index] = '1';

            print(str, index + 1);

              

            // ПРИМЕЧАНИЕ: нужно вернуться

            // как строка передается

            // ссылка на функцию

            str[index] = '?';

        }

        else

            print(str, index + 1);

    }

  

    // Код драйвера

    public static void Main ()

    {

        string input = "1??0?101";

        char []str = input.ToCharArray();

        print(str, 0);

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// Рекурсивная PHP-программа для генерации всех двоичных строк
// формируется путем замены каждого символа подстановки на 0 или 1

  
// Рекурсивная функция для генерации всех двоичных строк
// формируется путем замены каждого символа подстановки на 0 или 1

function print1($str, $index)

{

    if ($index == strlen($str))

    {

        echo $str."\n";

        return;

    }

  

    if ($str[$index] == '?')

    {

        // заменить '?' на 0 и рекурсировать

        $str[$index] = '0';

        print1($str, $index + 1);

  

        // заменить '?' на 1 и рекурсивно

        $str[$index] = '1';

        print1($str, $index + 1);

  

        // Нет необходимости возвращаться при передаче строки

        // по значению функции

    }

    else

        print1($str, $index + 1);

}

  
// Код драйвера

  

    $str = "1??0?101";

  

    print1($str, 0);

  

      
// Этот код предоставлен chandan_jnu
?>


Выход :

10000101
10001101
10100101
10101101
11000101
11001101
11100101
11101101

Способ 2 (с использованием очереди)
Мы также можем достичь этого, используя итерацию. Идея состоит в том, чтобы использовать очередь. Мы находим позицию первого вхождения подстановочного знака во входной строке и заменяем ее на «0», затем «1» и помещаем обе строки в очередь. Затем мы выталкиваем следующую строку из очереди и повторяем процесс до тех пор, пока очередь не станет пустой. Если подстановочных знаков не осталось, мы просто печатаем строку.

Итеративная реализация C ++ с использованием очереди.

C ++

// Итеративная программа C ++ для генерации всего двоичного файла
// строки, образованные заменой каждого шаблона
// символ 0 или 1
#include <iostream>
#include <queue>

using namespace std;

  
// Итеративная функция для генерации всех двоичных строк
// формируется путем замены каждого символа подстановки на 0
// или 1

void print(string str)

{

    queue<string> q;

    q.push(str);

  

    while (!q.empty())

    {

        string str = q.front();

  

        // найти позицию первого появления подстановочного знака

        size_t index = str.find('?');

  

        // Если совпадений не найдено,

        // найти возвращает строку :: npos

        if(index != string::npos)

        {

            // заменить '?' на '0' и вставить строку в очередь

            str[index] = '0';

            q.push(str);

  

            // заменить '?' на '1' и вставить строку в очередь

            str[index] = '1';

            q.push(str);

        }

  

        else

            // Если не осталось подстановочных знаков,

            // напечатать строку

            cout << str << endl;

  

        q.pop();

    }

}

  
// Код драйвера для проверки вышеуказанной функции

int main()

{

    string str = "1??0?101";

  

    print(str);

  

    return 0;

}


Выход :

10000101
10001101
10100101
10101101
11000101
11001101
11100101
11101101

Эта статья предоставлена Aditya Goel . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Рекомендуемые посты:

Генерация всех двоичных строк по заданному шаблону

0.00 (0%) 0 votes