Приветствую  !
Уточнения: 

• порядок цифр можно менять;
•  каждая цифра в полученном числе может встречаться не больше раз, чем в первоначальном.

Например, для числа 137 нужно рассматривать не только 1, 3, 7, 13, 17, 37, 137, но и 713, 731, 371, 317, 173, 73, 71, 31.

Использовать можно только циклы и условия    .

Организовать сам перебор для заранее известного кол-ва разрядов числа мне удалось (видимо, не самым оптимальным образом, но все же удалось):

1) Но на самом деле мы же не знаем, сколько разрядов будет!!! Кол-во разрядов сосчитать несложно, а вот как потом это число вклинить в циклы : . Рекурсию использовать не получится, т.к. функций "нет".
2) Если для числа из n разрядов ни одно полученное из n цифр число - не простое, то надо уменьшать кол-во участвующих цифр до (n-1) ; потом, если опять нет простого, уменьшать до n-2. Я не могу догадаться, как занулить коэффициент перед текущей лишней цифрой.

Жавайте подумаем вместе, пожалуйста  .

KasMP, задачка на самом деле интересная.

Выделить цифры числа не составляет проблем, это простенький цикл while, который не зависит от конкретного конечного значения переменной-счетчика, как тот же for. Параллельно с этим мы можем и посчитать количество цифр собственно в исходном числе. После этого требуется просчитать все возможные перестановки этих цифр, из каждой перестановки делать число и проверять его на простоту.

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

Непосредственно вычисление числа с текущей комбинацией цифр  у меня происходит так:
в верхней строчке - общая формула;
 ниже - степени 10, которые будут подставляться в формулу для получение числа с текущей комбинацией.

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

Выделить-то их можно, вот только положить их некуда: массивов "нет", списков "нет", сколько переменных под них надо - тоже неизвестно.
Я уже писала, что для заранее известного числа разрядов у меня получается (только занулять некоторые разряды я пока не умею), а для неизвестного - нет.

Добавлено через 4 минуты и 20 секунд
Я свои проблемы написала в пунктах 1) и 2)  .

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

Если же использование функций "запрещено" - организуй псевдорекурсию. Она как раз организуется условными циклами. Просто для хранения текущего состояния системы и всех предыдущих потребуется не двумерный, а трехмерный массив. Впрочем, сначала таки напиши рекурсивное решение - превратить его в псевдорекурсивное в разы проще, чем сразу делать псевдорекурсию.

И последнее - запрет на функции мне представляется идиотизмом. Неужели и проверку на простоту тоже придется втискивать в plain code?

Это сообщение отредактировал(а) Akina - 28.10.2008, 22:23

во-первых, без дополнительных ограничений здесь большие проблемы
насколько я понимаю, по умолчанию предполагается, что входное число помещается в unsigned int
однако даже в этом случае некоторые числа, полученные перестановкой цифр уже не будут помещаться
например, максимально допустимое число для unsigned int = 4294967296, стоит поменять первую 4-ку с 9-кой и число помещаться перестанет

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

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

тогда просто сортируем исходного числа так, чтобы максимальная была старшей (све сортировки - пузырьком - самый простой и без рекурсии), а потом начинаем отнимать по 1 от него и проверять две вещи:
1. что набор цифр совпадает с исходным - сортируем оба и сравниваем
2. что текущее число является простым
первое найденное число и есть ответ, т.к. мы шли с наибольшего постепенно уменьшая

конечно, возможна просто куча оптимизаций, но это вполне может быть начальным вариантом

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


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

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

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

Это сообщение отредактировал(а) maxim1000 - 29.10.2008, 00:17

В данном случае я бы тоже поспорил - между методом (подходом и пр.) и инструментом есть таки некоторая разница.


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

нет-нет
я не ту разницу имел в виду
итерация и у меня, и у тебя, действительно по числам с нужными цифрами
но представлена она может быть двумя способами:
1. можно выделить во внешнюю функциональность проверку числа на простоту и передавать её в виде функтора в рекурсивные функции
2. а можно выделить во внешнюю функциональность проход по всем числам с нужными цифрами

первый порыв, конечно, - решить задачу первым методом

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

а-а-а... 

Задача, конечно, интересная, но решаемая. Вкратце:
1) Получить подмножество цифр (1, 13, 17, 37, 137);
2) получить все перестановки из текущего подмножества и среди них найти самое большое простое число.
Пункт первый решается элементарно: пусть число состоит из n разрядов (десятичных). Тогда все подмножества можно получить простым циклом от 1 до 2^n. Поясню. Для 137 необходимо три разряда. Соответственно цикл от 1 до 7, запишу их в двоичном коде:
001   //множество [7]
010  //[3]
011  //[37]
100  //[1]
101  //[17]
110  //[13]
111  //[137]
Таким образом, у нас есть алгоритм для генерации всех подмножеств. Зачем он нам нужен? чтобы путем перестановки элементов этого множества получать различные комбинации. Данная подзадача возникает для каждого подмножества - нужно сгенерировать все перестановки для [3] (правда для этого множества она всего-лишь одна ), для [37] (37, 73), ..., [137] (137, 173, 317, 371, 713, 731). Оказывается, это тоже можно сделать только лишь циклом. Главное - отделить мух от котлет. Вот передо мной лежит учебник Окулова С.М. ("Программирование в алгоритмах", изд-во "БИНОМ. Лаборатория знаний", 2004г), открытый на странице 37, и мне влом вколачивать сюда приведенный там код.
Ну и в догонку - полученные числа можно проверить на простоту решетом Эратосфена, благо оно строится тоже только лишь циклом.
P.S. Если ничо непонятно - у вас всегда есть возможность написать мне письмо для более подробных разъяснений 

Silent, очень неожиданно  .

Все очень понятно  .
Только решето Эратосфена, по-моему, здесь не совсем к месту: решетом удобно пользоваться тогда, когда нужно получить список всех простых чисел до заданного; а когда нужно проверить на простоту конкретное число, то решето, конечно, можно приспособить... но уж слишком коряво получается. Ну да ладно, проблема не в проверке на простоту  .

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

P.S.. И все же слишком внезапно    ...

Добавлено через 5 минут и 53 секунды
Я была бы счастлива так сделать, но массивов тоже "нет"    !

Добавлено через 9 минут и 28 секунд
Да, у меня тоже были такие вопросы...
Ответ такой:

• изначально число типа integer;
• при генерации перестановок проверять, не получилось ли что-то типа "95431", "39423", т.п.; если получилось, то пропускать

Добавлено через 12 минут и 44 секунды
Самое первое, что пришло в голову - вычитать не 1, а 2  ... Зачем нам четные числа ? Ну да ладно, это слишком очевидная оптимизация .
Вообще, maxim1000, у тебя всегда возникают очень интересные варианты  .

Ну строковые-то переменные есть? а что есть строка как не массив символов?

В нашем случае строки "есть", но именно как массив символов - у нас C++    !

KasMP, очень рад что тебе пришлась по душе такая вещь, как генерация множеств.
Но, я так понимаю, тебе не нравится что в приведенном мной источнике по генерации всех перестановок из множества используется массив? на это замечание я потрясу все той же книжкой, попросив тебя перелистнуть страницу и прочитать со слов "четвертая задача" (жирным шрифтом выделено). Это - генерация перестановки по его номеру. А номер - от 1 до N!, где N - количество элементов в множестве. Таким образом, все опять сведется к массиву for (int i=1;i<N!;i++), где ты будешь получать по номеру очередную перестановку. Только придется шибко подумать над тем как извратиться - и вместо предлагаемого автором книги (и моим деканом по совместительству ;-)) множества использовать битовое поле. Я уже даже почти созрел до того, чтобы таки пересилить лень и написать тебе код 

Добавлено через 2 минуты и 5 секунд
*строку "все опять сведется к массиву for (int i=1;i<N!;i++)" читать как "все опять сведется к циклу for (int i=1;i<N!;i++)"

Все в мире фигня, кроме пчел. Но если подумать, то и пчелы - фигня. Винни Пух®
Я не стал сливать все в кучу для "только циклы и условия", оставлю как есть, с процедурами и функциями, для наглядности. Воспитание не позволяет.

P.S. а все-таки я крут (маньяк, дурак, нужное подчеркнуть  )