|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
26.11.2009, 15:20
|
#1
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,358
Написано 2,472 полезных сообщений (для 6,854 пользователей)
|
Варианты. (Чёто я туплю)
Значит так проблема вот какая.
Никак не могу понять закономерность. Устал наверное.
Допустим у на есть 2 числа и две ячейки
Под ячейкой я подозреваю месту куда можно вставить какое либо из этих чисел.
В данной ситуации мы имеем две комбинации: 12 и 21
Как посчитать кол-во комбинация допустим если чисел 45 а ячеек для их подстановки 15 и тд.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
26.11.2009, 15:54
|
#2
|
Бывалый
Регистрация: 03.11.2008
Адрес: Украина, Днепропетровск
Сообщений: 871
Написано 554 полезных сообщений (для 2,520 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
зайди в асю - есть пару теорий
|
(Offline)
|
|
26.11.2009, 16:20
|
#3
|
Дэвелопер
Регистрация: 17.01.2007
Сообщений: 1,552
Написано 351 полезных сообщений (для 774 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
узнать минимальное составимое число из этих цифр, узнать максимально составимое число из этих цифр. А затем пройтись циклом от минимального к максимальному, результат будет количеством комбинаций.
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
26.11.2009, 16:33
|
#4
|
Нуждающийся
Регистрация: 26.12.2008
Сообщений: 57
Написано 22 полезных сообщений (для 28 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Если у нас 45 чисел то это можно представить как 45 ричная система счисления. Если 2 ячейки то это будет 45 во 2 степени. Если 3 то 45 в 3.
Может я конечно не прав. Подумал что по анологии с 16 и 2 системой счисления очень похоже.
В 16 системе можем в 1 ячейку записать 16 чисел от 0 до 15. Если 2 ячейки будет 256 вариантов.
|
(Offline)
|
|
Эти 4 пользователя(ей) сказали Спасибо 12121 за это полезное сообщение:
|
|
26.11.2009, 16:37
|
#5
|
Дэвелопер
Регистрация: 17.01.2007
Сообщений: 1,552
Написано 351 полезных сообщений (для 774 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
очень похоже что ты прав
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
26.11.2009, 16:53
|
#6
|
Дэвелопер
Регистрация: 17.01.2007
Сообщений: 1,552
Написано 351 полезных сообщений (для 774 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
чета я заморочился по этой формуле, этот случай будет при уникальных цифрах в числе ( не повторяющихся), а для ваще нашел формулу вычисления, вот : http://topfortuna.com/tms.html
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо H@NON за это полезное сообщение:
|
|
26.11.2009, 16:56
|
#7
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
ТеорВер, кросавчеги (в данном случае - комбинаторика)
http://ru.wikipedia.org/wiki/Обобщён...ема_размещения
http://ru.wikipedia.org/wiki/Размещение
Автор не путай понятие цифра (символ, занимающий одну позицию, пусть даже у тя 45-ричная с\с) и число.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
|
|
26.11.2009, 17:07
|
#8
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Пример:
два разряда троичной системы - все комбинации если каждая цифра встречается в числе не более 1ого раза.
{1,2,3}:
12
13
21
23
31
32
итого - 6 комбинаций
или сразу: 3!/(2-1)!=3!/1!=6/1=6
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
|
|
26.11.2009, 17:08
|
#9
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,358
Написано 2,472 полезных сообщений (для 6,854 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Спасибо всем!
Буду читать.
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
26.11.2009, 18:19
|
#10
|
Нуждающийся
Регистрация: 26.12.2008
Сообщений: 57
Написано 22 полезных сообщений (для 28 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Если надо что бы числа не повторялись то можно посмотреть на сайтах расчета лотерей.
Например
http://www.lottoball.info/index.php?...=article&sid=4
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
27.11.2009, 00:23
|
#11
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Сообщение от 12121
Если у нас 45 чисел то это можно представить как 45 ричная система счисления. Если 2 ячейки то это будет 45 во 2 степени. Если 3 то 45 в 3.
Может я конечно не прав. Подумал что по анологии с 16 и 2 системой счисления очень похоже.
В 16 системе можем в 1 ячейку записать 16 чисел от 0 до 15. Если 2 ячейки будет 256 вариантов.
|
Из получившейся формулы (n^k) надо вычесть повторные комбинации (вида ХХ, где Х - цифра: 11,22..). все го их будет: n - для двух позиций, для трёх - три раза по n (сочетания типа XX* Х*Х *ХХ: 11*,1*1,*11) и ещё раз n (XXX:111), т.е. n*4, т.о.
для n=2: n^2-n
n=3: n^3-4*n
далее уже придёться учесть все возможные миграции повторяющихся групп цифр длиной 2,3,.. В общем жесть.
Исчерпание же цифр (размещение без повторений) объясняется (в зависимости от специфики класса - изучается\додумывается в ходе решения самостяельно) ещё в школе: допустим, есть W цифр - составить все возможные из них числа (каждая цифра используется только один раз). Процесс конструирования числа можно представить как последовательный выбор цифр из некоего запасника, т.о. первую цифру мы можем выбрать W способами (берём одну любую цифру из W), после этого вторую цифру можно выбрать уже ( W-1) способами, и т.д. - на W-ом шаге, останется одна (ещё не встречавшаяся цифра). Значит всего решений:
Q= W*( W-1)*( W-2)*( W-3)*..*1= W! для W позиций (алфавит в данном случае тоже из W символов).
Если у нас есть, к примеру, 2 ячейки, а цифр 10, то продолжая расширять указанное выше решение, прийдём к следующему: две цифры из 10 (в двух ячейках) можно разместить 10*9 (всего 100 вариаций минус 10 ХХ сочеатний:00,11,22..99) раз способами, т.е. решением будет N первых множителей выражения для Q, где N - число ячеек. "Выкинуть" из Q "хвост" можно единтсвенным образом (обратным его "наращиванию") - делением, т.е. Q необходимо поделить на ( W- N)*( W- N-1)*( W- N-2)*..*1 (для рассматриваемой задачи - (10-2)*(10-2-1)*(10-2-2)*..*1=8*7*6*..*1 - какраз-таки "хвост"). Очевидно делим мы на факториал ( W- N). Значит всего решений:
Z= W!/( W- N)!
Собственно, данная формула и указана в учебниках.
Наблюдательный читатель, обратит внимание, что формулу можно переписать с использованием биномиального коэффициента (который должен быть знаком ещё по "формулам сокращённого умножения", люди которые долго пытались [как я, перебиваясь с удовл на хор] зазубрить в школе эти безумные формулы, могли заметить, что коэффициенты в формуле по сути и задают все возможные перестановки для слагаемых [подобно тому, как это требуется в решаемой задаче] - это ощущение захлопывающейся полноты системы взглядов и интерепретаций сложно с чем-то спутать).
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Эти 2 пользователя(ей) сказали Спасибо impersonalis за это полезное сообщение:
|
|
28.11.2009, 01:36
|
#12
|
Дэвелопер
Регистрация: 17.01.2006
Сообщений: 1,512
Написано 78 полезных сообщений (для 110 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Сообщение от impersonalis
Наблюдательный читатель, обратит внимание, что формулу можно переписать с использованием биномиального коэффициента (который должен быть знаком ещё по "формулам сокращённого умножения", люди которые долго пытались [как я, перебиваясь с удовл на хор] зазубрить в школе эти безумные формулы, могли заметить, что коэффициенты в формуле по сути и задают все возможные перестановки для слагаемых [подобно тому, как это требуется в решаемой задаче] - это ощущение захлопывающейся полноты системы взглядов и интерепретаций сложно с чем-то спутать).
|
А зачем ф-лу биномиального коэффициента, если формула для размещения входит в его состав?
A из n по k = n! / (n - k)!
C из n по k = n! / ((n - k)! * k!) = A / k!
Тогда, выражая A через C, получим
A = C * k!
Зачем усложнять себе жизнь?
|
(Offline)
|
|
Эти 4 пользователя(ей) сказали Спасибо alcoSHoLiK за это полезное сообщение:
|
|
28.11.2009, 02:30
|
#13
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Я не сказал, что это вывод. Я сказал что это можно заметить.
Наверно, косноязычно выразил свою мысль. Тогда хорошо, что ты ещё раз подчеркунл.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
22.05.2010, 16:58
|
#14
|
Мастер
Регистрация: 03.05.2010
Адрес: Подмосковье
Сообщений: 1,218
Написано 438 полезных сообщений (для 790 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
На самом деле всё проще
у нас комбинация из k цифр в системе счисления из N цифр
Считаем количество комбинаций x
x:=n!
теперь учтем то, что знаки могут повторяться
допустим, у нас в комбинации 3 нуля
тогда
x:=x/(3!);
допустим, у нас в комбинации у единиц
x:=x/(y!);
и так перебираем все цифры от нуля до (n-1)
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
22.05.2010, 17:36
|
#15
|
Быдлокодер
Регистрация: 05.07.2009
Адрес: Проспит
Сообщений: 5,021
Написано 2,312 полезных сообщений (для 5,349 пользователей)
|
Ответ: Варианты. (Чёто я туплю)
Igor, ты решил откаметинтся на всём форуме? Только не лезь в темы старше 2009-го, а то тебя уже некромантом называют
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Похожие темы
|
Тема |
Автор |
Раздел |
Ответов |
Последнее сообщение |
туплю |
falcon |
BlitzMax |
17 |
19.01.2009 22:57 |
Часовой пояс GMT +4, время: 12:19.
|