Форум программистов, компьютерный форум CyberForum.ru

Программа на рекурсию - Перестановка ! - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 27, средняя оценка - 4.78
Пират-Ромка
Сообщений: n/a
03.07.2011, 02:26     Программа на рекурсию - Перестановка ! #1
Доброго времени суток, уважаемые знатоки.
Возникла проблема с решением данной программы. Надеюсь услышать не глупые советы в стиле - решается простой рекурсией, или что тут всё просто как два пальца
Суть : Дана строка, состоящая из M попарно различных символов. Вывести все перестановки символов данной строки.
Ввод
В первой строке файла находится исходная строка.
Вывод
Вывести в каждой строке файла по одной перестановке. Перестановки можно выводить в любом порядке. Повторений и строк, не являющихся перестановками исходной, быть не должно.
Ограничения
2 ≤ M ≤ 8; символы - буквы латинского алфавита и цифры.

Ввод
IOX
Вывод
XOI
OIX
IXO
XIO
OXI
IOX

Как не тяжело догадаться количество комбинация = !n где n количество символов в строке. Хотел бы увидеть полное решение на СИ (не СИ++, и не на паскале и не дельфи и не что другое))) Спасибо заранее
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.07.2011, 02:26     Программа на рекурсию - Перестановка !
Посмотрите здесь:

C++ Программа на рекурсию
C++ В файл рекурсию
Вставить рекурсию C++
Задача на рекурсию C++
C++ Задача на рекурсию
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NightmareZ
 Аватар для NightmareZ
1336 / 559 / 37
Регистрация: 31.03.2009
Сообщений: 1,907
03.07.2011, 04:01     Программа на рекурсию - Перестановка ! #2
Первый аргумент программы - исходный файл, второй - куда писать результат.

И, да, тут всё просто, как два пальца.

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <stdlib.h>
 
#define MAX_SIZE 8
 
int isMaxCounters(int* counters, int size, int max)
{
    int i;
 
    for (i = 0; i < size; ++i)
        if (counters[i] < max - 1)
            return 0;
 
    return 1;
}
 
int isUniqCounters(int* counters, int size)
{
    int i, j;
 
    for (i = 0; i < size; ++i)
        for (j = i + 1; j < size; ++j)
            if (counters[i] == counters[j])
                return 0;
 
    return 1;
}
 
int main(int argc, char* argv[])
{
    FILE *inputFile, *outputFile;
    int finded, i, j, k, size;
    char source[MAX_SIZE], uniq[MAX_SIZE];
    int counters[MAX_SIZE] = {0};
 
    if (argc != 3)
        return EXIT_FAILURE;
 
    inputFile = fopen(argv[1], "r");
    if (inputFile == NULL)
        return EXIT_FAILURE;
    fgets(source, MAX_SIZE, inputFile);
    fclose(inputFile);
 
    for (i = 0, j = 0; i < MAX_SIZE; ++i)
    {
        if (source[i] == '\0')
            break;
 
        finded = 0;
        for (k = 0; k < j; ++k)
            if (uniq[k] == '\0' || uniq[k] == source[i])
            {
                finded = 1;
                break;
            }
 
        if (finded)
            continue;
 
        uniq[j++] = source[i];
    }
 
    uniq[j] = '\0';
    size = j;
 
    outputFile = fopen(argv[2], "w");
    if (outputFile == NULL)
        return EXIT_FAILURE;
 
    do
    {
        if (isUniqCounters(counters, size))
        {
            for (i = 0; i < size; ++i)
                fprintf(outputFile, "%c", uniq[counters[i]]);
 
            fprintf(outputFile, "%c", '\n');
        }
 
        ++counters[0];
 
        for (i = 0; i < size - 1; ++i)
            if (counters[i] >= size)
            {
                counters[i] = 0;
                ++counters[i + 1];
            }
    } while(!isMaxCounters(counters, size, size));
 
    fclose(outputFile);
    return EXIT_SUCCESS;
}
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
03.07.2011, 05:07     Программа на рекурсию - Перестановка ! #3
NightmareZ, вывод только немного странный
Код
andrew@andrew-home ~/cpp/other
$ gcc -o nightmarez_permutations nightmarez_permutations.c

andrew@andrew-home ~/cpp/other
$ cat before.txt
123

andrew@andrew-home ~/cpp/other
$ ./nightmarez_permutations before.txt after.txt

andrew@andrew-home ~/cpp/other
$ cat after.txt

321
3
21

231
2
31
32
1
23
1

312
3
12

132
1
32
31
2
13
2

213
2
13

123
1
23
21
3
12
3
321

231

312

132

213

123


andrew@andrew-home ~/cpp/other
$
это задумано так? Программа ваша, ни буквы не изменил.
Nameless One
Эксперт С++
 Аватар для Nameless One
5754 / 3403 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
03.07.2011, 05:44     Программа на рекурсию - Перестановка ! #4

Не по теме:

Цитата Сообщение от Пират-Ромка Посмотреть сообщение
Надеюсь услышать не глупые советы в стиле - решается простой рекурсией, или что тут всё просто как два пальца
Цитата Сообщение от Пират-Ромка Посмотреть сообщение
Хотел бы увидеть полное решение на СИ
Вы все такие непосредственные...


Вот решение с рекурсией (ввод-вывод из файла сделаешь сам):
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void permutation(char*, size_t, size_t);
 
int chars_unique(const char*);
 
int main(int argc, char* argv[])
{
    size_t i, len;
        
    if(argc == 1)
    fprintf(stderr, "Usage: %s STRING ...\n", *argv), exit(1);
 
    for(i = 1; i < argc; ++i)
    {
    printf("String `%s' permutations:\n", argv[i]);
    
    if(!chars_unique(argv[i]))
        fprintf(stderr, "String `%s' contains duplicating characters\n", argv[i]);
    else
    {
        len = strlen(argv[i]);
        permutation(argv[i], len, len);
    }
    putchar('\n');
    }
 
    exit(0);
}
 
int chars_unique(const char* str)
{
    const char *i, *j;
    
    for(i = str; *i; ++i)
    for(j = i + 1; *j; ++j)
        if(*i == *j)
        return 0;
    return 1;
}
 
void swap(char* s, size_t i, size_t j)
{
    char t = s[i];
    s[i] = s[j];
    s[j] = t;
}
 
void permutation(char* str, size_t n, size_t length)
{
    size_t i;
    
    if(n)
    {
    permutation(str, n - 1, length);
    for(i = n - 1; i >= 1; --i)
    {
        swap(str, n - 1, i - 1);
        permutation(str, n - 1, length);
        swap(str, n - 1, i - 1);
    }
    } else {
    puts(str);
    }
}
Пример:
Код
[nameless@desktop c]$ ./sample IOX 123
String `IOX' permutations:
IOX
OIX
IXO
XIO
XOI
OXI

String `123' permutations:
123
213
132
312
321
231

[nameless@desktop c]$
xAtom
 Аватар для xAtom
910 / 735 / 60
Регистрация: 09.12.2010
Сообщений: 1,346
Записей в блоге: 1
03.07.2011, 06:26     Программа на рекурсию - Перестановка ! #5
Мой вариант.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h>
#include <string.h>
 
void _strrev(char*  src, int len) {
    char*  dst = src + len - 1;
    char   ch;
    while( dst != src ) {
          ch   = *dst;
         *dst = *src;
         *src = ch;
        ++src;
        --dst;
    }
}
 
int  generator(char* src, int len, int cnt) {
     int  k, i;
     char ch;
     if(cnt <= 1 || len < 2)
         return 0;
     if(cnt == len)
         printf("%s\n", src);
     for(k = 0; k < len-1; k++, cnt--) {
          for(i = 0; i < cnt; i++) {
              ch        = *((src)+i);
              *((src)+i) = *((src)+k);
              *((src)+k) = ch;
              if(*((src)+i) == *((src)+k))
                  _strrev(src, len);
              printf("%s\n", src);
         }
      }
      return generator(src, len, cnt);
}
 
 
 
int main(void)
{
        char str[] = "ABC", str1[] = "TIMER";
        int  len     = strlen(str);
        generator( str, len, len);
 
        puts("-");
 
        len    = strlen(str1);
        generator( str1, len, len);
 
        getchar();
        return 0;
}
Пират-Ромка
Сообщений: n/a
03.07.2011, 12:41     Программа на рекурсию - Перестановка ! #6
Спасибо ребятки, сейчас я все ваши варианта проработаю. Заранее скажу, что вариант с #define N 8 делал уже сам, он был компактнее, но это не подходит, так как в условии сказано что данные могут быть любые входные, то есть одна и та же программа должна обрабатывать и строку 123 и строку УПЯЧКА выводя в первом случае 6 перестановок, а во втором 720 )

Компилятор кстати GCC ну он разве что на длину long long влияет, но всё таки для информации
И , о да, никакие левые файлы для чтения - записи не должны существовать.
То есть сухой ввод с клавиатуры и сухой вывод перестановок - каждая с новой строки

Добавлено через 13 минут
xAtom
хороший вариант, но вместо инициализации символьного массива при объявлении хотел бы увидеть, что-то вроде
int i;
char str[8];
for (i=0;i<8;i++)
{
scanf("%c",str[i]);
if (str[i]=='\n') break;
}

Ввод через аргумент, это я как понимаю при запуске через консоль вводить ? Запуск с параметром для этой задачи нежелателен, правильнее было сделать чтобы массив записывался через scanf

Добавлено через 1 час 48 минут
Переработал все ваши варианты. Ну через аргументы - это не подходило. Взял короче ваши функции и переделал слегка main для ввода через scanf. Вот что получилось :

Код
#include <stdio.h>
#include <stdlib.h>

void swap(char * a, char * b)
{
    char t = *a;
    *a = *b;
    *b = t;
}

void reverse(char * first, char * last)
{
    for (; first != last && first != --last; ++first)
        swap(first, last);
}

int next_perm(char * first, char * last)
{
    char * p = first;
    if (p == last) return 0;

    ++p;
    if (p == last) return 0;

    p = last;
    --p;

    for (;;)
    {
        char * q = p;
        --p;

        if (*p < *q)
        {
            char * r = last;
            while(!(*p < *--r))
                ;

            swap(p, r);
            reverse(q, last);
            return 1;
        }

        if (p == first)
        {
            reverse(first, last);
            return 0;
        }
    }
}

int char_comp(void const * a, void const * b)
{
    return *((char const *) a) - *((char const *) b);
}

void print_perms(char * first, char * last)
{
    qsort(first, last - first, 1, char_comp);

    do
    {
        puts(first);
    } while (next_perm(first, last));
}

int main()
{
    char str[8] = "12345678";
    int i=0;
    while (1)
    {
        scanf("%c",&str[i]);
        if (str[i]=='\n')
        {
            str[i]='\0';
            break;
        }
        i++;
    }
    print_perms(str, str + i);
}
Тему можно закрывать !
NightmareZ
 Аватар для NightmareZ
1336 / 559 / 37
Регистрация: 31.03.2009
Сообщений: 1,907
03.07.2011, 14:19     Программа на рекурсию - Перестановка ! #7
Цитата Сообщение от easybudda Посмотреть сообщение
это задумано так? Программа ваша, ни буквы не изменил.
Кроме 123 во входном файле нет, например, переноса строки?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
03.07.2011, 14:36     Программа на рекурсию - Перестановка ! #8
Цитата Сообщение от NightmareZ Посмотреть сообщение
Кроме 123 во входном файле нет, например, переноса строки?
Ага, редактором добавился, так нормально всё.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2011, 20:22     Программа на рекурсию - Перестановка !
Еще ссылки по теме:

C++ задача на рекурсию в си++
Задача на рекурсию C++
Почему программа уходит в рекурсию при передачи в нее буквы C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Mastadont777
Сообщений: n/a
10.07.2011, 20:22     Программа на рекурсию - Перестановка ! #9
Пират-Ромка, вы не могли бы написать алгоритм к этой программе?
Я не понимаю, что происходит в третьем блоке кода
Yandex
Объявления
10.07.2011, 20:22     Программа на рекурсию - Перестановка !
Ответ Создать тему
Опции темы

Текущее время: 21:10. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru