Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [C]Сочетания в строке

Автор: igrulya 11.7.2007, 20:22

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

Автор: igrulya 12.7.2007, 09:58

Желательно только C

Автор: JackYF 12.7.2007, 17:50

ты потом код объяснять кому-нибудь будешь или тебе сдавать готовую программу, и все?

Автор: Dov 12.7.2007, 20:00

Цитата(igrulya @ 11.7.2007, 20:22

)

различные комбинации символов из введенной строки.

Допустим, я ввёл строку:

Код

123456

И что должна сделать программа? Что она должна вывести?

Автор: igrulya 12.7.2007, 20:30

Объяснять мот и придется.(Разберусь)
Прога должна выводить сочетания символов. Допустим для твоей строки
12
13
123
456 и т.д.

Автор: Dov 12.7.2007, 20:46

Цитата(igrulya @ 12.7.2007, 20:30

)

Допустим для твоей строки...

igrulya, ты конкретно можешь сказать? Сколько таких сочетаний должна выводить программа?
5, 10, 1000, сколько? В каком порядке она их должна выводить? Вперемешку или отсортированными?
Если ты хочешь что бы тебе помогли, то конкретизируй своё задание. И не заставляй людей вытягивать из тебя каждое слово, а чётко и ясно объясни, что должна делать твоя программа.
Желательно, на конкретных примерах.

Автор: igrulya 12.7.2007, 21:15

Подходил к приподу. Он сказал выводить все возможные сочетания символов из строки.

Код


void main()
{
    char str[255];
    gets(str);
    for(int i=0;i<(strlen(str)-1);i++)
    {
            if(str[i]==' ')
            {
                i++;
            }

        for(int j=(i+1);j<(strlen(str));j++)
        {
            if(str[j]==' ')
            {
                j++;
            }
            printf("%c%c\n",str[i],str[j]);
        }
    }
        getch();
}

Вот эта прога выводить по два символа по порядку.
Можно ли добиться такого же результата как-то по другому??Как быть с сочетаниями из трех-четырех символов??Можно ли обойтись без множества Вложенных циклов??

Автор: JackYF 12.7.2007, 22:07

igrulya, к чему я это все ввел.

В STL, стандартной библиотеке шаблонов C++, есть алгоритм, называется std::next_permutation.

Так вот.
С ним программа на С++ выглядела бы где-то так:

Код


std::string s;
std::cin >> s;

std::sort(s.begin(), s.end());
while ( std::next_permutation(s.begin(), s.end()) )
{
  std::cout << s << '\n';
}

Я так когда-то схитрил на олимпиаде, там точно же такое задание было...

Но вот чтобы превратить это в С-код, придется потрудиться...
Приведу код next_permutation, авось тебе поможет smile

Код


template<typename _BidirectionalIterator>
    bool
    next_permutation(_BidirectionalIterator __first,
                     _BidirectionalIterator __last)
    {
      if (__first == __last)
        return false;
      _BidirectionalIterator __i = __first;
      ++__i;
      if (__i == __last)
        return false;
      __i = __last;
      --__i;

      for(;;)
        {
          _BidirectionalIterator __ii = __i;
          --__i;
          if (*__i < *__ii)
            {
              _BidirectionalIterator __j = __last;
              while (!(*__i < *--__j))
                {}
              std::iter_swap(__i, __j);
              std::reverse(__ii, __last);
              return true;
            }
          if (__i == __first)
            {
              std::reverse(__first, __last);
              return false;
            }
        }
    }

Автор: Dov 13.7.2007, 00:27

Мой вариант:

Код


int main()
{
    char str[80];
    int i, j, a, b, d, n;

    puts("Enter a string: ");
    gets(str);

    puts("\nResult: ");
    n = strlen(str);
    for(i = 1; i < n; i++)
    {
        for(b = 1, d = i; b < n - 1; d++, b++)
        {
            for(a = d; a < n; a++)
            {
                for(j = i - 1; j < d; j++)
                    putchar(str[j]);

                printf("%c\n",str[a]);
            }
        } 
    }

    return 0;
}

Автор: sentry 24.7.2007, 20:23

Можно и без вложенных циклов, но с рекурсией:

Код


int n, k;
char a[80], b[80];

int print(int k)
{
    for (int i = 0; i < k; i++)
        printf("%c", a[i]);
    printf("\n");

    return 0;
}


int gen(int m, int l)
{
    int i;
    if (m == 0)
        print(k);
    else
        for (i = l; i <=  n - m + 1; i++)
        {
            a[k-m] = b[i-1];
            gen(m-1, i+1);
        };

    return 0;
};

int Cnk()
{
    for (k = 1; k <= n; k++)
        gen(k, 1);

    return 0;
};

int main()
{
    puts("Enter a string: ");
    gets(b);

    n = strlen(b);
    Cnk();
    
    return 0;
}

Автор: Dov 25.7.2007, 21:23

Цитата(sentry @ 24.7.2007, 20:23

)

Можно и без вложенных циклов, но с рекурсией:

На мой взгляд, это самое верное решение. sentry, молодец. smile

з.ы. И всё-таки влияние какого-то 'паскалеидного языка' видно невооружённым глазом. smile

Сишник написал бы немного иначе. smile

Впрочем, могу ошибаться. smile

В любом случае по репе заслужил. smile