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

Форум программистов > C/C++: Для новичков > Рекурсия

Автор: Garcian 1.3.2009, 12:58

Здравствуйте уважаемые программисты! С первым днем весны вас   . Ломаю голову над одной задачей на рекурсию, а именно "Напечатать все перестановки заданных n различных натуральных чисел", т.е. если даны числа "123", то кол-во возможных перестановок будет 3!=6. Вся проблема в том, что массив использовать запретили, а как сделать без него я не совсем представляю (зеленый еще). Помогите, пожалуйста.

Автор: ex386 1.3.2009, 13:58

Может так? : Код #include <iostream> long long fact(int k) {     if (k < 0) return 0;     if (k == 0) return 1;     return k * fact(k - 1); } int main() {     int a, b = 0;     while ( (a = std::cin.get()) != '\n')         if (a >= 48 && a <= 57)             ++b;                            //количество цифр     std::cout << fact(b); }

Автор: mes 1.3.2009, 14:04

максимальное кол-во разрядов чисел известно ? Добавлено через 1 минуту и 58 секунд Цитата(ex386 @  1.3.2009,  12:58 ) Может так? : думаю необходимо не  узнать кол-во перестановок, а определить все возможные: Цитата(Garcian @  1.3.2009,  11:58 ) "Напечатать все перестановки заданных n различных натуральных чисел",

Автор: Garcian 1.3.2009, 14:12

mes, ты прав. Для того же случая с "123" в выходном файле должно быть "123 132 213 231 312 321"

Автор: Dmi3ev 1.3.2009, 14:39

Цитата Вся проблема в том, что массив использовать запретили, а как сделать без него я не совсем представляю (зеленый еще) а как с массивом, знаешь?

Автор: mes 1.3.2009, 14:47

а как все таки насчет ответа на этот вопрос : Цитата(mes @  1.3.2009,  13:04 ) максимальное кол-во разрядов чисел известно ? ?

Автор: Garcian 1.3.2009, 15:16

у массива элементы свою область памяти хоть имеют, к ним обращаться проще. Не совсем  понял про разряды, здесь цифры как символы. На самом деле более четко задача звучит так "Напечатать все перестановки заданных n различных натуральных чисел (или символов)"

Автор: mes 1.3.2009, 15:23

Цитата(Garcian @  1.3.2009,  14:16 ) n различных натуральных чисел (или символов) переставлять надо числа или цифры каждого числа ?! Цитата(Garcian @  1.3.2009,  14:16 ) . Не совсем  понял про разряды, здесь цифры как символы. ну значит максимальное кол-во символов известно ? Цитата(Garcian @  1.3.2009,  14:16 ) у массива элементы свою область памяти хоть имеют, к ним обращаться проще. во первых как это поможет решить именно саму задачу ? во вторых как хранятся n натуральных чисел, если не в массиве ?

Автор: math64 1.3.2009, 15:40

Код struct  used_numbers {   int number;   used_umber* prev_numbers; }; void perestanovki(int n, used_numbers* used = NULL) {   used_number num;   int found_number = -1;   num.prev_numbers = used;   // поиск неиспользованного числа   ...   if (found_number == -1) {     // распечатка найденной перестановки     while (used != NULL) {        printf (" %d", used->number);        used = used->prev_numbers;     }     printf("\n");   } else {     num.number = found_number;     presestanovki(n, &num);   } }

Автор: zim22 1.3.2009, 15:49

Цитата(mes @  1.3.2009,  15:23 ) во вторых как хранятся n натуральных чисел, если не в массиве ? можно "запаковать" два числа типа int в одно число типа double

Автор: Dmi3ev 1.3.2009, 15:53

Да это чистый развод, называется "Реши за меня"...    Давай свой вариант с массивами, если выдашь вариант с массивами, я обещаю, что в лепешку расшибусь, но сделаю без них...

Автор: Garcian 1.3.2009, 15:55

Аааа, да в этом весь прикол! Кол-во символов не больше 5, поскольку 5 - это уже 120 вариаций. 6 -720 и т.д.) Пространство std:: использовать тоже нельзя) Мы не доросли до такого) Во всяком случае надо использовать минимум 2 функции имхо. А массивов нет)  зы: я не прошу в лепешку расшибаться кого-либо, мне нужен лишь дельный совет) Может даже с примером

Автор: zim22 1.3.2009, 16:03

вот пример совета без примера: Т.к. кол-во символов не больше пяти, создай пять переменных. Далее с помощью операции деления и остатка от деления выдели каждую цифру из числа. Занеси цифры в переменные. Тем самым ты обошёлся без массивов! Осталось только алгоритм перебора придумать.

Автор: Soah 1.3.2009, 16:07

Цитата(Dmi3ev @  1.3.2009,  14:39 ) а как с массивом, знаешь? http://algolist.manual.ru/maths/combinat/permutations.php Предупреждаю, там на паскале.

Автор: math64 1.3.2009, 16:08

А структуры использовать можно? Если да - доработай мой код. Поиск неиспользованного числа нужно выставить в цикл, возможно для этого понадобится ещё одна рекурсивная функция, печатать можно тоже рекурсивной функцией. Если символов не больше 64, можно использовать int64 как массив из 64 бит для запоминания использованных чисел.

Автор: Garcian 1.3.2009, 16:10

Спасибо за предложение) Не совсем понимаю, как выделятся числа, но я попробую) Добавлено через 4 минуты и 38 секунд math64, не не не, всего то 5й месяц обучения

Автор: mes 1.3.2009, 16:32

Цитата(Garcian @  1.3.2009,  14:55 ) Кол-во символов не больше 5, вот тут пример, тоже по перестановкам : http://forum.vingrad.ru/index.php?showtopic=234074&view=findpost&p=1723750 хоть и задание там несколько другое, но надеюсь получится переделать самому, так как ничего "необычного" в коде не использовано

Автор: Albor 1.3.2009, 17:12

Особо не ломаем голову, а подключаем #include<algorithm> и юзаем функцию next_permutation, принимающую указатель на начало и конец диапазона. Функция делает перестановку в лексикографическом порядке (то есть каждая следующая перестановка больше предыдущей) и возвращает логическое значение (true, если перестановка не последняя. Значит можно запустить в цикле). Конечно, исходный диапазон перед перестановками сортируем по возрастанию. Нельзя использовать массив - читаем входные данные в string (внутри это конечно массив, но извне - объект строка). Кстати, количество перестановок не обязательно равно n!. например число 112 - три возможных значения.

Автор: Dmi3ev 1.3.2009, 17:17

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

Автор: Albor 1.3.2009, 17:23

Вероятно можно и без массива. например, из данного числа, путём математических действий, получить большее, но состоящее из тех же цифр, затем ещё и ещё, пока не получен максимум. Нужно только вывести формулу, но это к математикам.

Автор: mes 1.3.2009, 17:24

если я правильно понял, то Цитата(Albor @  1.3.2009,  16:12 ) Особо не ломаем голову, а подключаем #include<algorithm>  Цитата(Garcian @  1.3.2009,  14:55 ) Пространство std:: использовать тоже нельзя)  Цитата(Albor @  1.3.2009,  16:12 ) Kоличество перестановок не обязательно равно n!. например число 112 - три возможных значения.  Цитата(Garcian @  1.3.2009,  14:16 ) Напечатать все перестановки заданных n различных натуральных чисел (или символов)"

Автор: Dmi3ev 1.3.2009, 17:27

в голову ничего не пришло, что могло бы избавить от массива... вот вариант в тупую, без массива, но с указателем... Код #include "stdafx.h" #include <iostream> using namespace std; int fact (int n) {     if(n==0)         return 1;     else         return (n*fact(n-1)); } int _tmain() {     int *c, n;     cout<<"How many numbers?\n n=";     cin>>n;     if (n>5 || n<1)     {         cout<<"Error: n>5 or n<1"<<endl;         system("pause");         return 0;     }     c=new int[n];     for (int i=0; i<n; i++)     {         cout<<"Enter number "<<i+1<<": ";         cin>>*(c+i);     }     cout<<endl<<"Results: "<<endl;     cout<<"Factorrial: "<<fact(n)<<endl;     switch (n)     {     case 5:     for (int i=0; i<n; i++)         for(int i1=0; i1<n; i1++)           if (i1!=i)             for(int i2=0; i2<n; i2++)               if (i2!=i && i2!=i1)                   for (int i3=0; i3<n; i3++)                       if(i3!=i2 && i3!=i1 && i3!=i)                           for (int i4=0; i4<n; i4++)                               if (i4!=i2 && i4!=i1 && i4!=i && i4!=i3)                                   cout<<endl<<c[i]<<"; "<<c[i1]<<"; "<<c[i2]<<"; "<<c[i3]<<"; "<<c[i4]<<"; ";     break;     case 4:         for (int i=0; i<n; i++)             for(int i1=0; i1<n; i1++)                 if (i1!=i)                     for(int i2=0; i2<n; i2++)                         if (i2!=i && i2!=i1)                             for (int i3=0; i3<n; i3++)                                 if(i3!=i2 && i3!=i1 && i3!=i)                                     cout<<endl<<c[i]<<"; "<<c[i1]<<"; "<<c[i2]<<"; "<<c[i3]<<"; ";         break;     case 3:         for (int i=0; i<n; i++)             for(int i1=0; i1<n; i1++)                 if (i1!=i)                     for(int i2=0; i2<n; i2++)                         if (i2!=i && i2!=i1)                             cout<<endl<<c[i]<<"; "<<c[i1]<<"; "<<c[i2]<<"; ";         break;     case 2:         for (int i=0; i<n; i++)             for(int i1=0; i1<n; i1++)                 if (i1!=i)                     cout<<endl<<c[i]<<"; "<<c[i1]<<"; ";         break;     case 1:         cout<<endl<<c[0]<<"; ";         break;     }             cout<<endl;     system("pause");     return 0; }

Автор: mes 1.3.2009, 17:27

Цитата(Albor @  1.3.2009,  16:23 ) Нужно только вывести формулу, но это к математикам.  вряд ли так как  Цитата(Garcian @  1.3.2009,  15:10 ) всего то 5й месяц обучения  smile

Автор: zim22 1.3.2009, 18:07

Цитата(Dmi3ev @  1.3.2009,  17:27 ) c=new int[n]; представляю возмущение преподавателя: "А это что такое? Массив? Я же предупреждал тебя! Всё, ты отчислен!"   и если пространоство std использовать нельзя, то что мешает его не использовать, а копировать из него необходимые функции? ещё можно функцию swap применить для двух случайных цифр из числа.  полученное новое число сохраним в списке.  снова применим функцию swap. пройдёмся по списку.  если числа нет такого - добавим его в список.  я думаю за миллион итераций все перестановки как раз и нагенерируются.

Автор: math64 1.3.2009, 21:04

Ну за 5 месяцев мможно было бы научиться работать с массивами и указателями. Здесь требуется доступ ко всем предыдущим итерациям и без массива или списка не обойтить. Массивы монжно скрыть в числах: long (32 Битный) - 9 десятичных цифр, до n=9 int64 - 16 шестнадцатиричных цифр, до n=16 Если требуется рекурсивный алгоритм, данные лучше хранить в списке, в классическом языке использующем рекурсию ЛИСПе данные тоже хранятся в списках. Код struct list {   int number;   struct list* prev; }; void print_list(struct list* l) {    if (l == NULL)      return;    print_list(l->prev);    printf(" %d", l->number); } bool is_in_list(int n, struct list* l) {   if (l == NULL)     return false;   is_in_list(l->prev, n);  } void perestanovki (int n, struct list* l) {   int i;   struct list data;   data.prev = l;   data.number = -1;   for(i = 1; i <= n; i++) {     if (!is_in_list(n, l)) {       data.number = i;       perestanovki(n, &data);     }   }   if (data.number == -1)     print_list(l); } Можно обойтись и без структур, используя функции с переменным числом агрументов (...)

Автор: Garcian 2.3.2009, 01:20

Dmi3ev, а где здесь рекурсия, помимо факториала (по ходу нет)? Albor, мда, в самом деле, зачем голову ломать, преподаватель дурачок ничего не понимает

Автор: mes 2.3.2009, 01:55

Цитата(Garcian @  2.3.2009,  00:20 ) а где здесь рекурсия  а где в задании говорится об решении через рекурсию ? кроме упоминания в названии темы (что говорит лишь о  Вашем предположении о способе решения), я иных указаний не нашел. Добавлено через 1 минуту и 49 секунд да и вобще как можно спрашивать решение, когда само задание (может и ошибаюсь) полностью не освещено ?!

Автор: Albor 2.3.2009, 07:13

Цитата(Garcian @ 2.3.2009,  00:20) Albor, мда, в самом деле, зачем голову ломать, преподаватель дурачок ничего не понимает   Кто сказал о дурачке? Тебе предложили варианты - выбирай. Когда-то и нам задавали такую задачу, но массивы не запрещались. Перерыв кучу информации по алгоритмам такого рода задача была решена, а, через какое-то время, заглянул в STL и та же задача решилась в несколько строк кода. Успехов. PS Если преподавателю представить хоть какое-то решение, думаю, что это уже +.

Автор: Dmi3ev 2.3.2009, 15:59

Цитата Dmi3ev, а где здесь рекурсия, помимо факториала (по ходу нет)? а где спасибо... в задании действительно нигде не сказано, где должна быть рекурсия, и должна ли она быть... так что будь недоволен только собой, не только не справился с задачей, но даже не смог ее нормально сформулировать... слушай, что mes говорит...  Цитата да и вобще как можно спрашивать решение, когда само задание (может и ошибаюсь) полностью не освещено ?!  это 99% успеха, а когда оно размыто, как в твоем случае, мы сами выпытываем у тебя что можно, что нужно... и советы: 1) ты должен быть доволен и такому коду... потому как своего никакого нет...  3) ты можешь потратить свое драгоценное время и увидеть некое сходство в последовательных шагах, и выделить их в рекурсивную функцию... или не можешь))) дело за тобой)))

Автор: Garcian 2.3.2009, 17:32

Dmi3ev,  спасибо, а где второй пункт  . По 3му пункту - не сомневайся, мой прозорливый ум уже это подметил    В задании не указано, но рекурсия обязательна (в следующий раз буду уточнять). Вообще это заданиие из таких типов, как "анализатор скобок" например.  Сегодня еще раз спросил у препода насчет массивов - сказал нельзя! На вопрос " А как тогда?", он ехидно ответил "Не знаю". зы: не я же задачи эти придумываю) Чтоб его понять я несколько дней потратил) зыы: преподаватель даже не смотрит решение, если хоть что то не так)) Максимум укажет ошибку (что редко), а сам скажет - думайте дальше

Автор: zim22 2.3.2009, 18:17

Цитата(Garcian @  2.3.2009,  17:32 ) Сегодня еще раз спросил у препода насчет массивов  у тебя одного в группе такое задание? нельзя спросить у однокурсников как они решили?

Автор: Dmi3ev 2.3.2009, 18:27

Цитата Сегодня еще раз спросил у препода насчет массивов - сказал нельзя! На вопрос " А как тогда?", он ехидно ответил "Не знаю". ну тогда и ты прояви чудеса хитрости: 1) пять переменных объяви, по сути это не есть массив 2) пользуйся указателем, как в моем примере, тоже можно преподу втереть, что это не есть массив 3) объяви переменную типа long int и запихни туда свои цифры (пять цифр туда поместятся), а получай их, пользуясь остатком от деления: long int x=12345; //x%10 только сегодня выкладывал Код #include "stdafx.h" #include <iostream> using namespace std; int mysum(long int n) {     if (n==0)         return 0;     else         return((n%10)+mysum(n/10)); } int _tmain() {     long int n=1234567;     cout<<mysum(n)<<endl;     system("pause");     return 0; } это для понимания... 4) из файла читай, тоже не массив будет 5) тебе говорили про строки string, тоже возьми на заметку вариантов куча, а потом просто объясни преподу, в чем разница между выбранным тобой вариантом и массивом (предварительно почитав), чтобы он точно не пенился))) Добавлено через 3 минуты и 43 секунды Цитата Dmi3ev,  спасибо, а где второй пункт посчитал нужным его убрать из вежливости... дабы не обидеть...

Автор: mes 2.3.2009, 18:55

Цитата(Dmi3ev @  2.3.2009,  17:27 ) 1) пять переменных объяви, по сути это не есть массив боюсь тс нужно всего лишь переставить цифры в числе, именно поэтому массив сущность излишняя, так как переменная уже хранит все данные.

Автор: bsa 2.3.2009, 19:01

я плакалъ! Ну нафлудили! Код #include <iostream> #include <cmath> int getDig(int n, int r) {         return (n/r) % 10; //текущая цифра } int setDig(int n, int r, int dig) {         return n + r * (dig - getDig(n, r) ); //текущая цифра } void outAll(int n, int r) {     if (r < 10)         std::cout << n << std::endl;     else {         const int d = getDig(n, r); //текущая цифра         for(int x = r; x > 0; x /= 10) {             int d2 = getDig(n, x);             int t = setDig( setDig(n, x, d), r, d2);             outAll(t, r/10);         }     } } int main() {     int n;     std::cout << "Input number: " << std::flush;     std::cin >> n;     int power = static_cast<int>(log(n)/log(10)); //целое количество десятичных разрядов в числе -1     outAll(n, static_cast<int>( pow(10, power) ) );     return 0; }

Автор: Anikmar 2.3.2009, 20:39

bsa, +1, действительно удовлетворяет всем условиям задачи. Массива нет никак (только если рассматривать целое число как массив бит   ). Лично мне вариант очень понравился.

Автор: Albor 2.3.2009, 23:50

а если на тип int посмотреть вот так Код int a(12345678);     char *p=(char*)&a;     for(int i=0;i<sizeof(int);i++)         printf("%X ",*(p+i)&0xFF); уж не массив ли это char-ов?   А если копнуть глубже, то всё состоит из битовых массивов. Так как решать задачу?   И чем, после этого, условию не удовлетворяет string?

Автор: Anikmar 3.3.2009, 00:05

Цитата(Albor @  2.3.2009,  23:50 ) уж не массив ли это char-ов?   А если копнуть глубже, то всё состоит из битовых массивов. Так как решать задачу?   И чем, после этого, условию не удовлетворяет string? Про битовый массив я уже написал.  Можно еще опуститься до массива тактов задающего генератора системной шины. Тем не менее, если не доводить до маразма, то вариант действительно отличный. Я думаю, препод именно это имел ввиду - дотумкает ли до использования чистой математики или пойдет по пути строки. Лично я бы по причине своей лени пошел бы наверное по пути строки. И скорее всего схлопотал бы пару.

Автор: math64 3.3.2009, 08:59

Если есть ограничение на число n (n<10 или n<16), то как я уже говорил, int32 можно использовать для хранения 9 десятичных цифр, а uint64 для хранения 16 шестнадцатиричных цифр: Код bool has_digit(int digit, int32 number) {   int32 mod;   if (number == 0) // 0 не используем     return false;   mod = number % 10;   if (mod == digit)     return true;   return has_digit(digit, number / 10); } // добавление к числу новой цифры number = number * 10 + new_digit; Код bool has_hexdigit(int xdigit, uint64 number, int count_digits) {   uint64 mod;   if (count_digits == 0)     return false;   mod = number % 16; // or number & 0xF;   if (mod == xdigit)     return true;   return has_hexdigit(xdigit, nuber / 16, count_digits - 1); // or number >> 4 } // добавление к числу новой цифры number = number * 16 + new_digit; // or number = (number << 4) + new_digit; count_digits++; Но с использованием структур ограничений на n нет (если обеспечить достаточный размер стека) Добавлено через 6 минут и 45 секунд Albor: string условию не удовлетворяет, нельзя использовать std:: Но обычные строки ("") по-видмому можно, иначе как печатать результат? (ostream тоже в std::, так что printf)

Автор: mes 3.3.2009, 10:36

Цитата(Albor @  2.3.2009,  22:50 ) уж не массив ли это char-ов? smile  А если копнуть глубже, то всё состоит из битовых массивов. Так как решать задачу? smile  И чем, после этого, условию не удовлетворяет string? а если сказано в условии, что функции не использовать нельзя, то как писать программу ?!   ведь main() тоже функция.

Автор: bsa 3.3.2009, 11:51

math64, читай условие внимательно - он сказал, что число разрядов не более пяти.

Автор: math64 3.3.2009, 12:55

Ну для 5 хватит 5 восьмиричных цифр в int16

Автор: mes 3.3.2009, 13:06

Цитата(math64 @  3.3.2009,  11:55 ) Ну для 5 хватит 5 восьмиричных цифр в int16  восьмиричных ?! a почему бы сразу не использовать тогда char для 5ти двоичных ?

Автор: math64 3.3.2009, 13:17

Нужно запоминать не только набранные числа, но и их порядок, поэтому хранение в битах не годится. у bsa действительно лучшее решение,  правда нет проверки того, что в введённом числе есть одинаковые цифры. И насколько я понимаю, ostream нужно переделать на printf(),  Его можно переделать и для шестнацатиричных чисел.

Автор: Garcian 5.3.2009, 00:42

bsa, спасибо большое! Что касается проверки на повторяющиеся символы, имхо, она не нужна. Идет проверка только на пустой файл и на его отсутствие. Еще вопрос: что значит static_cast<int> и flush? Albor, string нельзя использовать точно) Зато его дали для следущей работы на подстроки

Автор: Albor 5.3.2009, 13:29

Цитата(bsa @ 2.3.2009,  18:01) [code=cpp    int power = static_cast<int>(log(n)/log(10)); //целое количество десятичных разрядов в числе -1  [/code] log10(n) даст тотже самый результат. static_cast<int> - приведение типа, говорит компилятору (в данном контексте) :" не ругайся, я знаю что из double получаю int"

Автор: bsa 5.3.2009, 14:12

Цитата(Garcian @ 5.3.2009,  00:42) что значит static_cast<int> и flush? Может прежде, чем задавать вопросы, стоит воспользоваться http://www.google.com/search?q=static_cast? Про std::flush написано здесь: http://www.cplusplus.com/reference/iostream/manipulators/

Автор: Garcian 5.3.2009, 19:44

Albor, спасибо. В гугле можно, но со слов понятней намного) Вот: "не ругайся, я знаю что из double получаю int" - сразу понятно в чем "фишка"   *********** посмотрел ссылку-все понятно. В следущий раз буду к гуглу обращаться, потом к вам.

Автор: bsa 10.3.2009, 16:54

M bsa Garcian, если ответ на вопрос получен, то пометь тему решенной

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)