Составление Простого Числа |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Составление Простого Числа |
Hindelberg |
Сообщение
#1
|
Группа: Пользователи Сообщений: 9 Пол: Мужской Репутация: 0 |
Никак не могу сообразить эту задачу.
Прошу наводку или подсказку. Пользователь вводит k(<=1000) чисел в файл. Вывести все k-значные простые числа(если возможно), которые можно составить из введенных пользователем чисел. Как составить из неизвестного кол-ва цифр число? Например: 1 2 4 5 9 k=5 это надо определить сколько чисел, и потом 1*10^(k-1)+ 2*10^(k-2) и Т.д.? И как быть с 1000? Возможно по какой-то закономерности возможно меньшее кол-во чисел? |
Altair |
Сообщение
#2
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Цитата которые можно составить из введенных пользователем чисел. это как ? именно из числел или из всех цифр которые ввеенны ? то есть если Цитата Например: 1 2 4 5 9 k=5 7 можно указать или нет ? а 3 ? -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
Сообщение
#3
|
Гость |
Hindelberg,
попробуй почитать про перестановки (по-моему в FAQ-е было), это поможет тебе из K цифр создать все возможные числа... Если нужны такие большие K, то смотри и "Длинную арифметику" |
Altair |
Сообщение
#4
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Цитата из K цифр создать тогда гораздо проще исользовать множество... заполнить его цифрами встречающимися в числах и протсо перебрать for i:=1 to <верхний предел> do .. если протсое и составляется из цифр множества то .... Hindelberg, для примера своего: Цитата Например: 1 2 4 5 9 k=5 напиши несколько допустимых чисел -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
volvo |
Сообщение
#5
|
Гость |
Altair
Пример в студию... Кстати, Hindelberg, вопрос: Цитата Пользователь вводит k(<=1000) чисел в файл Чисел, или все-таки цифр? |
Altair |
Сообщение
#6
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
To: volvo, только после того как автор ответит, пока задание не точно..
Цитата Hindelberg, для примера своего: QUOTE Например: 1 2 4 5 9 k=5 напиши несколько допустимых чисел -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Hindelberg |
Сообщение
#7
|
Группа: Пользователи Сообщений: 9 Пол: Мужской Репутация: 0 |
я не совсем точно описал условие.
Имеется файл. В него вводятся куча(<=1000) цифр. И нужно проверить сколько из этих цифр можно составить простых чисел, причем должны использоваться все цифры из файла. Цифры любые, т.е. 0 1 2 3 4 5 6 7 8 9 Сообщение отредактировано: Hindelberg - |
volvo |
Сообщение
#8
|
Гость |
Hindelberg, скорее всего тут надо брать бубен и плясать в сторону признаков делимости на определенные числа, потому что все 1000 цифр перебирать, да еще и проверять на простоту числа - ресурсов не хватит никаких...
|
Altair |
Сообщение
#9
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
мне кажется он задание все же не так как то произносит...
уж слишком это задача туманная и сложная... если там 1000 цифр будет и Цитата причем должны использоваться все цифры из файла. то это простите 1000 значное число .... -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
Hindelberg |
Сообщение
#10
|
Группа: Пользователи Сообщений: 9 Пол: Мужской Репутация: 0 |
Цитата(Altair @ 20.11.2005 11:32) мне кажется он задание все же не так как то произносит... уж слишком это задача туманная и сложная... Правильно я произношу. Сказано- Некоторое кол-во цифр k(k<=1000). Цитата(volvo @ 20.11.2005 11:27) плясать в сторону признаков делимости на определенные числа Это я понимаю, но как это сделать я не могу сообразить. |
volvo |
Сообщение
#11
|
Гость |
Ну, например, так:
1. Проверяешь, сколько всего цифр. С учетом этого вычисляешь, сколько чисел может быть составлено из этого количества цифр (для простоты будем считать, что допустимы числа типа "00093", "00903", ...) 2. Есть ли 2-ки? Есть... Сколько чисел можно составить, что в конце будет 2-ка? Отнимаешь это количество от общего количества возможных вариантов... 3. Есть ли 3-ки (и делится ли сумма всех цифр на 3), ... и т.д. Чистая комбинаторика... В этом направлении я бы двигался... |
Hindelberg |
Сообщение
#12
|
Группа: Пользователи Сообщений: 9 Пол: Мужской Репутация: 0 |
Таким образом можно найти кол-во простых чисел. А ведь надо еще их вывести всех.
|
volvo |
Сообщение
#13
|
Гость |
Значит тебе прямая дорога в FAQ: Длинная арифметика, и запасайся терпением, 1000 цифр будут обрабатываться достаточно долго... Хотя перебор можно тоже значительно сократить (пользуясь теми же принципами, о которых я говорил выше)...
|
Hindelberg |
Сообщение
#14
|
|||
Группа: Пользователи Сообщений: 9 Пол: Мужской Репутация: 0 |
Это задача из олимпиадных. Так что врядли там приемлима Длинная Арифметика и долгая обработка...
|
|||
volvo |
Сообщение
#15
|
Гость |
To: Hindelberg
Олимпиадная? Это хакерская задача, ты мне-то сказки не рассказывай. Подбор ключей RSA делается по той же схеме: простые числа из 200+ цифр и их обработка... |
Hindelberg |
Сообщение
#16
|
Группа: Пользователи Сообщений: 9 Пол: Мужской Репутация: 0 |
Это задача с заочной олимпиады для старшеклассников за 2005-2006 год. Недавно была и я не решил эту задачу. Вот и стало интересно.
Листок сохранился, если ты так не веришь могу сфотать и прислать. |
virt |
Сообщение
#17
|
Знаток Группа: Пользователи Сообщений: 419 Пол: Мужской Репутация: 6 |
volvo
я на республиканских сборах по информатике в этом году хочу дать задачу подбора ключа к RSA 32 или 64 битного. -------------------- |
Altair |
Сообщение
#18
|
Ищущий истину Группа: Пользователи Сообщений: 4 825 Пол: Мужской Реальное имя: Олег Репутация: 45 |
Цитата я на республиканских сборах по информатике в этом году хочу дать задачу подбора ключа к RSA 32 или 64 битного. Это как? -------------------- Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С) |
FreeMan |
Сообщение
#19
|
- Группа: Пользователи Сообщений: 480 Пол: Мужской Репутация: 4 |
Почитай про алгоритм Рабина-Миллера. Значительно уменьшает время поиска. Но всё-равно без длинной арифметики никуда
-------------------- бб
|
Текстовая версия | 5.05.2024 10:44 |