Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/19: Рейтинг темы: голосов - 19, средняя оценка - 4.63
Янчик
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 20
#1

Рекурсивная процедура печати всех перестановок из n символов

03.11.2009, 21:32. Просмотров 3471. Ответов 15
Метки нет (Все метки)

"Написать процедуру печати всех перестановок из n символов"
методом рекурсии

непривычно и трудно в C++
помогите пожалуйста!
=(((
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.11.2009, 21:32
Ответы с готовыми решениями:

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

Поиск всех перестановок символов из строки (0..9)..пожалуйста помогите!!!
ведь наверняка ктото уже писал такие алгоритмы будь то на олимпеаде или где...

Рекурсивная функция печати массива
Напишите рекурсивную функцию печати массива, которая принимает массив и размер...

Рекурсивная функция печати массива
Напишите рекурсивную функцию печати массива, которая принимает массив и размер...

Рекурсивная подпрограмма печати чисел из файла
Написать рекурсивную подпрограмму, вводящую из файла последовательность...

15
Андрейка
422 / 226 / 87
Регистрация: 25.03.2009
Сообщений: 744
03.11.2009, 21:47 #2
http://algolist.manual.ru/maths/combinat/permutations.php
правда тут на паскале )
2
Янчик
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 20
03.11.2009, 22:12  [ТС] #3
так на паскале это одно дело!
именно C++!
=)
1
rrrFer
Заблокирован
03.11.2009, 22:53 #4
если маленькое n то можно так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
void f(int n,int m){
    int k=n-1;
    if(!n) cout<<m<<endl;
    while(n){
        (m*=10)+=n;
        f(k,m);
        (m-=n)/=10;
        n--;
    }
}
int main(){
    int n;
    cin>>n;
    f(n,0);
    cin.get(),cin.get();
    return 0;
}
для большого n надо переменную m заменить на массив.
1
ООП
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 13
03.11.2009, 23:46 #5
Привет земеля!!!
Ты точно всем нос утрешь такой прогой: открываем Borland C++ Builder, кидаем на форму ListBox (у него ставим Sort в true) и Button и пишем следующие (соответственно создавая нужные события и функции в заголовчном)
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
void __fastcall TForm1::Button1Click(TObject *Sender)
{
        ListBox1->Clear();
        TStringList *l = new TStringList();
        l->Delimiter = ' ';
        l->Add("1"); l->Add("2"); l->Add("3");
        l->Add("4"); l->Add("5"); l->Add("6");
 
        // это можно убрать
        AnsiString text = l->DelimitedText;
        ListBox1->Items->Add(text);
 
        next(l, fac(l->Count,l->Count));
        Button1->Caption = (AnsiString)ListBox1->Items->Count;
}
//---------------------------------------------------------------------------
 
 
void __fastcall TForm1::next(TStringList * lst, int pos)
{
        randomize();
        bool n = false;
        while(!n){
        lst->Exchange(random(lst->Count), random(lst->Count));
        AnsiString text = lst->DelimitedText;
        if(ListBox1->Items->IndexOf(text) < 0)
                {ListBox1->Items->Add(text); n = true;}
        }
        if(pos > 2) next(lst, --pos);
        else return;
}
 
int __fastcall TForm1::fac(int f, int n)
{
        return --n ? fac(f * n, n) : f;
}
1
manfeese
131 / 130 / 29
Регистрация: 04.01.2009
Сообщений: 415
03.11.2009, 23:59 #6
Если я правильно понял, то тебе надо найти n-факториал методом рекурсии. Если да, то это так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream.h>
#include <conio.h>
 
double factorial(int N)
{
return ( (N<0) ? 0 : ((N<=1) ? 1 : N*factorial(N-1)) );
}
 
int main()
{
    int n;
    cin>>n;
    cout<<factorial(n);
             getch();
 
    return 0;
}
0
Янчик
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 20
04.11.2009, 00:12  [ТС] #7
нет, мне не факториал надо найти, а просто перебор :
например: 123, 132, 213,231,312,321, и вывести на экран

Добавлено через 2 минуты
а что значит " ? " в 6-ой строчке?
я просто в языке С++ вообще полный ноль((((
0
sheka
Босс
161 / 127 / 9
Регистрация: 03.06.2009
Сообщений: 750
04.11.2009, 00:15 #8
это выбор из двух условий, если не ошибаюсь.
условие1 ? условие2 : условие3
если условие1 справедливо, выполняется условие2, иначе условие3
0
manfeese
131 / 130 / 29
Регистрация: 04.01.2009
Сообщений: 415
04.11.2009, 00:29 #9
sheka прав. Это сокращенная запись условного оператора.

Добавлено через 5 минут
Вот вариант, но без рекурсии Перебор возможных комбинаций символов
1
ООП
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 13
04.11.2009, 01:00 #10
Факториал все равно может понадобиться: n! - это число всех возможных вариантов. функция fac у меня как раз его и возвращает.

Янчик, у меня несколько шуточный пример (зато он работает и над ним не надо думать долго) для 6 чисел - хорошо, для 7 - уже плохо. Можно более оптимизированно сделать, чем просто ставить туда рандомные значения.

То, что я пометил в комментарии, что можно удалить, лучьше не удалять , но если все же удалишь, то нужно исправить строку в функции next с if(pos > 2) next(lst, --pos); на if(pos > 1) next(lst, --pos); а то один какой-то вариант не досчитает.

Добавлено через 2 минуты
а если не удалять, то, наверное, будет работать чуть быстрее
0
valeriikozlov
Эксперт С++
4683 / 2509 / 751
Регистрация: 18.08.2009
Сообщений: 4,550
04.11.2009, 09:39 #11
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
#include <iostream.h>
void f(int n, int temp[]){
    int i, j;
    bool fl=false;
    for(i=0; i<n-1; i++)
        for(j=i+1; j<n; j++)
            if(temp[i]==temp[j])
                fl=true;
    if(!fl)
    {
        for(i=0; i<n; i++)
            cout<<temp[i];
        cout<<endl;
    }
    temp[0]++;
    for(i=0; i<n; i++)
        if(temp[i]>n)
        {
            temp[i]=1;
            temp[i+1]++;
        }
    if(temp[n-1]==n && temp[n-2]==n)
        return;
    f(n, temp);
    return;
}
 
int main(){
        int n, i, *temp;
        cout<<"Vvedite n: ";
        cin>>n;
        temp=new int[n];
        for(i=0; i<n; i++)
            temp[i]=n-i;
        f(n, temp);
        cin.get(),cin.get();
        return 0;
}
1
rrrFer
Заблокирован
04.11.2009, 11:37 #12
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
void f(int n,int m){
    if(!n) 
        cout<<m<<endl;
    for(int k=n-1;n;n--)
        f(k,m*10+n);
}
int main(){
        int n;
        cin>>n;
        f(n,0);
        cin.get(),cin.get();
        return 0;
}
0
Chea
6 / 6 / 0
Регистрация: 29.09.2009
Сообщений: 41
04.11.2009, 15:04 #13
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
#include <stdio.h>
#include <conio.h>
 
int k=1;
 
int func (char * mas, int n,int h)
{
   char ch;
   int i;
   if (n==h)
      {
         printf ("%4d %s\n",k,mas);
         k++;
         return 1;
      }
   for (i=h;i<n;i++)
      {
         ch=mas[h];
         mas[h]=mas[i];
         mas[i]=ch;
         func (mas,n,h+1);
         mas[i]=mas[h];
         mas[h]=ch;
      }
}
 
int main ()
{
   char m[]="12345";
 
   func (m,5,0);
   getch();
}
1
Янчик
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 20
09.11.2009, 23:29  [ТС] #14
что значит "неразрешённый внешний символ"?
0
Chea
6 / 6 / 0
Регистрация: 29.09.2009
Сообщений: 41
11.11.2009, 20:38 #15
Можно про ошибку подробнее.
Кстати сейчас увидил - ошибочка в формировании массива.
Выводится как строка, а формируется как массив символов.
Необходимо что бы в конце массива был 0.
возможно и ошибка из-за этого

C
1
2
3
4
5
6
7
8
9
10
#include <string.h>
int main ()
{
   char m[20];
 
   strcpy (m,"12345");
 
   func (m,strlen(m),0);
   getch();
}
0
Янчик
2 / 2 / 0
Регистрация: 03.11.2009
Сообщений: 20
07.12.2009, 18:12  [ТС] #16
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
#include <vcl.h>
#include "iostream.h"
 
int* ar;
int n;
 
void func(int m)
{
for(int i=1;i<=n;i++)
{
int k=0;
for(int j=0;j<n;j++)
{
if(ar[j]==i)
{
k = 1;
break;
}
}
 
if(k==0)
{
ar[n-m] = i;
if(m==1)
{
for(int i=0;i<n;i++)
cout<<ar[i];
cout<<endl;
ar[n-m]=0;
return;
}
else
func(m-1);
}
 
}
ar[n-m]=0;
return;
}
 
int main(int argc, char* argv[])
{
cout<<"Input n:"<<endl;
cin>>n;
 
ar = new int[n];
for(int i=0;i<n;i++)
ar[i]=0;
cout<<endl;
func(n);
 
cout<<endl;
system("pause");
return 0;
}
Добавлено через 12 секунд
ура! всё сделала!!!
0
07.12.2009, 18:12
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.12.2009, 18:12

Рекурсивная процедура умножения матриц
Вот мне задали написать рекурсивную процедуру для умножения матриц. Я понимаю,...

Рекурсивная процедура вычисления факториала
Обязательно все через рекурсии надо сделать!! Помогите студенту сдать зачет

Рекурсивная процедура вычисления n-го числа Фибоначчи
Добрый день. Подскажите, пожалуйста, алгоритм рекурсивной процедуры вычисления...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru