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

Может так? :

максимальное кол-во разрядов чисел известно ?

Добавлено через 1 минуту и 58 секунд

думаю необходимо не  узнать кол-во перестановок, а определить все возможные:

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

а как с массивом, знаешь?    

а как все таки насчет ответа на этот вопрос :

?

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

Это сообщение отредактировал(а) Garcian - 1.3.2009, 15:17

переставлять надо числа или цифры каждого числа ?!


ну значит максимальное кол-во символов известно ?


во первых как это поможет решить именно саму задачу ?
во вторых как хранятся n натуральных чисел, если не в массиве ?

Это сообщение отредактировал(а) mes - 1.3.2009, 15:25

можно "запаковать" два числа типа int в одно число типа double 

Это сообщение отредактировал(а) zim22 - 1.3.2009, 15:49

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

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



Это сообщение отредактировал(а) Garcian - 1.3.2009, 15:57

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

Hапечатать все перестановки чисел 1..N

Предупреждаю, там на паскале.

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

Спасибо за предложение) Не совсем понимаю, как выделятся числа, но я попробую)

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

вот тут пример, тоже по перестановкам :
http://forum.vingrad.ru/index.php?showtopi...t&p=1723750
хоть и задание там несколько другое, но надеюсь получится переделать самому, так как ничего "необычного" в коде не использовано  

Это сообщение отредактировал(а) mes - 1.3.2009, 16:38

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

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

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

если я правильно понял, то






Это сообщение отредактировал(а) mes - 1.3.2009, 17:25

в голову ничего не пришло, что могло бы избавить от массива...
вот вариант в тупую, без массива, но с указателем...



Это сообщение отредактировал(а) Dmi3ev - 1.3.2009, 17:30

вряд ли так как 

представляю возмущение преподавателя: "А это что такое? Массив? Я же предупреждал тебя! Всё, ты отчислен!"  

и если пространоство std использовать нельзя, то что мешает его не использовать, а копировать из него необходимые функции?

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

Это сообщение отредактировал(а) zim22 - 1.3.2009, 18:21

Ну за 5 месяцев мможно было бы научиться работать с массивами и указателями.
Здесь требуется доступ ко всем предыдущим итерациям и без массива или списка не обойтить.
Массивы монжно скрыть в числах:
long (32 Битный) - 9 десятичных цифр, до n=9
int64 - 16 шестнадцатиричных цифр, до n=16
Если требуется рекурсивный алгоритм, данные лучше хранить в списке, в классическом языке использующем рекурсию ЛИСПе данные тоже хранятся в списках.

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

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

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

Добавлено через 1 минуту и 49 секунд
да и вобще как можно спрашивать решение, когда само задание (может и ошибаюсь) полностью не освещено ?!  

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

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

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

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

Сегодня еще раз спросил у препода насчет массивов - сказал нельзя! На вопрос " А как тогда?", он ехидно ответил "Не знаю".

зы: не я же задачи эти придумываю) Чтоб его понять я несколько дней потратил)
зыы: преподаватель даже не смотрит решение, если хоть что то не так)) Максимум укажет ошибку (что редко), а сам скажет - думайте дальше   



Это сообщение отредактировал(а) Garcian - 2.3.2009, 17:33

у тебя одного в группе такое задание? нельзя спросить у однокурсников как они решили?

ну тогда и ты прояви чудеса хитрости:
1) пять переменных объяви, по сути это не есть массив
2) пользуйся указателем, как в моем примере, тоже можно преподу втереть, что это не есть массив
3) объяви переменную типа long int и запихни туда свои цифры (пять цифр туда поместятся), а получай их, пользуясь остатком от деления:
long int x=12345;
//x%10
только сегодня выкладывал

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

Добавлено через 3 минуты и 43 секунды

посчитал нужным его убрать из вежливости... дабы не обидеть...   

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

я плакалъ! Ну нафлудили!

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

Лично мне вариант очень понравился.

а если на тип int посмотреть вот так

уж не массив ли это char-ов?   А если копнуть глубже, то всё состоит из битовых массивов. Так как решать задачу?   И чем, после этого, условию не удовлетворяет string?


Это сообщение отредактировал(а) Albor - 3.3.2009, 00:05

Про битовый массив я уже написал.  Можно еще опуститься до массива тактов задающего генератора системной шины.

Тем не менее, если не доводить до маразма, то вариант действительно отличный. Я думаю, препод именно это имел ввиду - дотумкает ли до использования чистой математики или пойдет по пути строки. Лично я бы по причине своей лени пошел бы наверное по пути строки. И скорее всего схлопотал бы пару.

Это сообщение отредактировал(а) Anikmar - 3.3.2009, 00:06

Если есть ограничение на число n (n<10 или n<16), то как я уже говорил, int32 можно использовать для хранения 9 десятичных цифр, а uint64 для хранения 16 шестнадцатиричных цифр:



Но с использованием структур ограничений на n нет (если обеспечить достаточный размер стека)

Добавлено через 6 минут и 45 секунд
Albor: string условию не удовлетворяет, нельзя использовать std::
Но обычные строки ("") по-видмому можно, иначе как печатать результат? (ostream тоже в std::, так что printf)

  

а если сказано в условии, что функции не использовать нельзя, то как писать программу ?!   ведь main() тоже функция.   

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

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

восьмиричных ?! a почему бы сразу не использовать тогда char для 5ти двоичных ?

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

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

Albor, string нельзя использовать точно) Зато его дали для следущей работы на подстроки   

log10(n) даст тотже самый результат. static_cast<int> - приведение типа, говорит компилятору (в данном контексте) :" не ругайся, я знаю что из double получаю int"

Это сообщение отредактировал(а) Albor - 5.3.2009, 13:37

Может прежде, чем задавать вопросы, стоит воспользоваться гуглом?

Про std::flush написано здесь: http://www.cplusplus.com/reference/iostream/manipulators/

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


***********


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

Это сообщение отредактировал(а) Garcian - 5.3.2009, 19:48

M bsa

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