Перейти из форума на сайт.

НовостиФайловые архивы
ПоискАктивные темыТоп лист
ПравилаКто в on-line?
Вход Забыли пароль? Первый раз на этом сайте? Регистрация
Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Немного комбинаторики...

Модерирует : ShIvADeSt

 Версия для печати • ПодписатьсяДобавить в закладки
Страницы: 1 2 3

Открыть новую тему     Написать ответ в эту тему

Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
      Программированием (TP) занимаюсь не так давно, так что не смейтесь если это глупый вопрос  
       Хочу сделать пограмку которая генерировала бы варианты перестановок, скажем числа :9988887776. Но при этом не выдавала бы одинаковые перестановки т.е. те что были раньше.
 
Как это реализуется ???
 
 
P.S. Училка по математике сказала что вариантов будет (в данном случае)  
10!/2!*4!*3!*1! т.е. 12600
 

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 22:57 16-10-2002
Advanced_Guest



Silver Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Frez
Вариантов будет (при 10 значном числе, те цифры которые ты использовал.):
4*4*3*3*3*3*2*2*1=5184
 
Советую начинать с более простых чисел (2-3 значных.)
 
Например число 123
Варианты:
123
132
213
231
312
321
Всего 6
Вычесляеться по формуле 3*2*1.
 
На первое место может встать 3 варианта (1, 2 или 3), на второе - только 2 (1,2 или 3 кроме того что было в 1 варианте), на третье - то что осталось.
 
 
Если писать алгоритм, то наверное нужно будет использовать рекурсию.
То есть подпрограмма вызывает саму себя, потом опять саму себя и так далее, или же цикл в цикле, который опять в цикле и так далее .
 
Что-то типо:
 
Массив возможные_Символы()
Массив ответы()
 
for n=0 to Количество_Возможностей    
. . Первый_символ=возможные_Символы(n)
. . for i=0 to Количество_Возможностей    
. . . . Если i=n , тогда перейти к следующему i . . . .  .  .  '//Чтобы был один и тот же символ не повторялся 2 раза в одной строке.
. . . . Второй_символ=возможные_Символы(i)
. . . . for x=0 to Количество_Возможностей    
. . . . . . Если x=n или x=i, тогда перейти к следующему x
. . . . . . третьий_символ=возможные_Символы(x)
. . . . . . ответ(Номер_ответа) =Первый_символ & Второй_символ & третьий_символ
. . . . . . Номер_ответа=Номер_ответа+1
. . . . Следующий x
. . Следующий i
следующий n
 
 
Теперь только нужно переписать это всё из псевдо кода в программный код
 
PS: Этот вариант проходит только для 3-значных сочитаний.
Тебе же надо написать это в функцию, которая делает то-же.
PPS: Писал я это на пседо Visual Basic, как в других зыках не знаю
 


----------
The Abyss - UO, LA2, Ботва, BSFG

Всего записей: 2446 | Зарегистр. 14-04-2002 | Отправлено: 23:29 16-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Frez
 По теории, современные машины могут сделать это простым перебором. Т.е. задаешь массив из 12600 эл-тов и сравниваешь полученную комбинацию со всеми уже заданными значениями. Если не совпадает - дописываешь Но это ОЧЕНЬ долго.
 
 Как решить задачу правильно - не знаю...

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 00:12 17-10-2002
woffer

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Вариантов будет (при 10 значном числе, те цифры которые ты использовал.):  
4*4*3*3*3*3*2*2*1=5184

 
Неверно, формула для 3 значного : n! сам же написал 3*2*1,
Для 10 значного соответственно 10!, убираем повторения, имеем : 10!/2!*4!*3!*1!  
 

Всего записей: 935 | Зарегистр. 11-10-2002 | Отправлено: 02:32 17-10-2002 | Исправлено: woffer, 02:33 17-10-2002
Advanced_Guest



Silver Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
woffer
 
Ti prav
JA dumal vot tak:  
(no potom metodom podbora proveril sto ja ne pravilno dumal )
 
Если дано число "9988887776", то у нас:
Две 9
четыре 8
три 7
одна 6  

Всего 4 типа. (Для меня Все 9 на одно лицо )
 
По этому и получилось такое странное число  
(4*4*3*3*3*3*2*2*1=5184)
 
Если же брать вариант что везде абсолютно разные цифры (1234567890), Будет 10*9*8*7*6*5*4*3*2*1

----------
The Abyss - UO, LA2, Ботва, BSFG

Всего записей: 2446 | Зарегистр. 14-04-2002 | Отправлено: 08:21 17-10-2002 | Исправлено: Advanced_Guest, 13:29 17-10-2002
woffer

Advanced Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору

Цитата:
Advanced_Guest,

Я тут еще подумал, и решил что в данно случае, я не прав, просто ты в качестве примера привел трехзначное число
 
Я в задаче фигурирует 9988887776  
 
Frez,
Вообще не понятно, входит ли в искомый набор, Скажем число 1122223334 ? (Если нет, то наверное вполне нормально подойдет простой перебор значений Вчего 4 разных цифры
 

Всего записей: 935 | Зарегистр. 11-10-2002 | Отправлено: 15:59 17-10-2002 | Исправлено: woffer, 16:01 17-10-2002
Advanced_Guest



Silver Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
woffer

Цитата:
Я тут еще подумал, и решил что в данно случае, я не прав, просто ты в качестве примера привел трехзначное число  

 
Даже с 3 значным числом получаеться проблеммы.
 
(Кстати, если вопрос только в перестановке, то лучше использовать термин "строка", или "порядок знаков" а не число..)
например дана строка:
"112"
 
Варианты:
112
121
211
то есть 3*2*1/2*1 =3
 
Вариант 5-значной стороки:
11223
 
Варианты:
11223
11232
11322
 
12123
12132
12213
 
12231
12312
12321
 
13122
13212
13221
-------
21123
21132
21213
 
21231
21312
21321
 
22113
22131
22311
 
23112
23121
23211
-------
31122
31212
31221
 
32112
32121
32211
 
Всё. Больше вариантов нету. Проверенно VBA + MS Excel  
 
Всего - 30
 
только мой вышепреведённый алгоритм не совсем работает
 
После него надо всё равно делать чистку (А точнее делить результат на 4 )
 
Сейчас ещё подумаю....

----------
The Abyss - UO, LA2, Ботва, BSFG

Всего записей: 2446 | Зарегистр. 14-04-2002 | Отправлено: 17:33 17-10-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
                               
Advanced_Guest
 Спосибо, подробно, но немного не то что мне надо...
qwd
 Перебор долго !
woffer

Цитата:
Вообще не понятно, входит ли в искомый набор, Скажем число 1122223334 ? (Если нет, то наверное вполне нормально подойдет простой перебор значений  Вчего 4 разных цифры  
 

Попробую подробнее...
Давайте для удовства заменим исходное число 9988887776 на aabbbbcccd - просто набор букв(слово)
Так вот надо получить все возможные ПЕРЕСТАНОВКИ букв данного слова. Причем если мы поменяем местами первые две буквы "аа" то это не будет считаться так как получившееся новое слово будет такимже как и исходное. Участвуют только буквы abcd.  
 
                                             
 
Добавлено
Advanced_Guest
Ты прав именно это мне и надо!
 
 
Добавлено
Advanced_Guest
Ты прав именно это мне и надо!

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 18:00 17-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Frez
 Условие задачи понятно, но вот как это осуществить...
 Думаю, что перебор имеет право на жизнь, так как 12 тысяч циклов с 10 вложенными. Ну может несколлько минут помудрит...
 на досуге помудрю...
 
Добавлено

Цитата:
Проверенно VBA + MS Excel  

 Лучше сказать - проверенно математикой. 5!/(2!*2!) Как раз 30.

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 22:35 17-10-2002
Advanced_Guest



Silver Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
qwd

Цитата:
Думаю, что перебор имеет право на жизнь, так как 12 тысяч циклов с 10 вложенными. Ну может несколлько минут помудрит...

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

Цитата:
Лучше сказать - проверенно математикой. 5!/(2!*2!) Как раз 30.

 
Факториалы это конечно хорошо, но я их не помню
 
Я же проверил именно в Excel +Vba
 
1. Скрипт генерит все варианты сочитанию чисел 1, 2 и 3
(всего получилось 3125 варианта.)
Начало ряда:
11111
11112
.....
2. отбор и удаление тех, в которых не встречаеться ровно 2 знака "1", 2 знака "2" и 1 знак "3" (VBA)
(вариант для строки 11223)  
(осталось 480 значений)
3. Сортировка стандартными средствами Excel.
4. Удаление дублей с помощью VBA
осталось ровно 30 :=)
 
PS: С помощью excel Решить проблемму с 9988887776 по моему алгоритму(не совсем "чистому") не возможно. Слишком много вариантов получаеться...
 
 


----------
The Abyss - UO, LA2, Ботва, BSFG

Всего записей: 2446 | Зарегистр. 14-04-2002 | Отправлено: 23:05 17-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Advanced_Guest
 Ну так я же не для себя писать буду - так что, смотри...

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 23:51 17-10-2002
Memo



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Учиться, учиться и учиться!..
 
Очень хорошо бы автору темы почитать классику, например
Д.Кнут, "Искусство программирования для ЭВМ", т. 1-й,
"Основные алгоритмы". Там есть прекрасная глава, посвященная
именно алгоритмам перестановок! Однако ж лень, наверное?
Проще кинуть вопрос в конфу и получить ответ на блюдечке, не
так ли?

Всего записей: 114 | Зарегистр. 27-08-2002 | Отправлено: 01:40 18-10-2002
igcomp



Громозека с баяном
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Memo
Отлично сказал Сейчас поищу на одной из полок и отсканю одну станицу.

----------
Век живи, век учись...
Всегда сперва думай, а потом действуй. И никогда не действуй прежде, чем подумаешь.

Всего записей: 7904 | Зарегистр. 07-12-2001 | Отправлено: 19:05 18-10-2002
SergejKa

Full Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
igcomp мне тогда на мыло скинь. Ладно? У меня сканер загнулся

Всего записей: 469 | Зарегистр. 04-03-2002 | Отправлено: 03:10 19-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
igcomp
 Выкладывай, интересно почитать будет..

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 08:30 19-10-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
igcomp
Жду с нетерпением !  

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 14:31 19-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Выход найден, и если процесс не будет выполнятся на машине более-менее современной (выше 286) то всё будет ОК.
 Пробавлением к числу 6777888899 единицы до тех пор, пока оно не станет больше максимального числа 9988887776.
 И, соответственно, анализировать на к-во девяток, восьмерок, семерок и шестёрок. Причем при невыполнении любого условия моментальный выход.

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 19:52 19-10-2002 | Исправлено: qwd, 19:53 19-10-2002
Romero



BANNED
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
=)

Всего записей: 58 | Зарегистр. 20-10-2002 | Отправлено: 11:33 20-10-2002
qwd



Наш человек
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
Пока доделывается прога на 9 знаков в данном числе. Бывало, конечно, хуже, но и лучше тоже можно.
 Время выполнения циклов - порядка 10 минут

Всего записей: 7717 | Зарегистр. 16-02-2002 | Отправлено: 11:42 20-10-2002
Frez



Junior Member
Редактировать | Профиль | Сообщение | Цитировать | Сообщить модератору
qwd
Какой проц у тебя? И в чем ты делаешь ?
Я знаю только ТР
 
 
Добавлено
Memo

Цитата:
Очень хорошо бы автору темы почитать классику, например  
Д.Кнут, "Искусство программирования для ЭВМ", т. 1-й,  

Сложно, на мой взгляд, изложено. Но книга дельная !

Всего записей: 68 | Зарегистр. 16-10-2002 | Отправлено: 13:13 20-10-2002
Открыть новую тему     Написать ответ в эту тему

Страницы: 1 2 3

Компьютерный форум Ru.Board » Компьютеры » Прикладное программирование » Немного комбинаторики...


Реклама на форуме Ru.Board.

Powered by Ikonboard "v2.1.7b" © 2000 Ikonboard.com
Modified by Ru.B0ard
© Ru.B0ard 2000-2024

BitCoin: 1NGG1chHtUvrtEqjeerQCKDMUi6S6CG4iC

Рейтинг.ru