В школе я ещ╦ учусь, и может не обладаю нужными знаниями, но в общем была на олимпиаде такая задачка:
Сколькими способами можно разбить N разных предметов на K групп?
N и K вводятся в процессе выполнения...
Например 4 предмета на 2 группы:
123 4 - 124 3 - 134 2 - 12 34 - 13 24 - 14 23 - 1 234
Воть так.... Как это на си написать (Сам алгоритм)
И ещ╦ одна была: Перевод из Дестичной системы в римскую.... Не такой простой она оказалась тоже алгоритмик бы
Просто поучиться немного.. си то я знаю, а книжек по алгоритмам неть
По поводу распределения $n$ человек по $k$ сообществам план такой.
I способ (типа поучительный):
0. Сначала посмотрим сколькими способами можно отправить $n$ дам в $k$
гаремов каких-то пронумерованных султанов, потом отрубим султанам головы,
освободим женщин, и забыв их прежних мужей но оставив общность по ним
получим распределение по сообществам.
1. Каждую женщину можно отправить в один из $k$ гаремов, всего барышень $n$,
значит общее количество вариантов распределения это $k^n$.
2. После революции нам не важно чьи были гаремы, поэтому надо поделить
получившийся ответ на $k!$ (кол-во перестановок этих гаремов).
3. Легко догадаться, что $k^n$ на $k!$ нифига не делится. Где же грабли?
Естественно, в том что мы могли использовать не все $k$ гаремов, а меньше.
Согласитесь, гарем без единой наложницы этой какой-то неправильный гарем.
Поэтому нам надо придумать как бы найти сколько способов отправить
$n$ девушек ровно в $k$ гаремов. Обозначим это искомое число через $s_{kn}$
4. Посмотрим на это с такой стороны: чтобы распределить $n$ красавиц по не более
чем $k$ гаремам, нужно выбрать $l$ гаремов из этих $k$, и распределить их ровно
по этим гаремам. То есть:
$$ k^n = \sum_{l \leq k} C_k^l s_{ln} $$, (1)
где $C_k^l = \frac{k!}{l! (k-l)!}$ - число способов выбрать $l$ гаремов из $k$.
5. Конечно, это равенство может показаться совершенно бесполезным -- ведь мы
выразили то, что и так знали через то, что хотим узнать. Но, его прелесть в том
что матрица преобразования универхнетреугольная, а поэтому ее легко обратить.
$(1+N)^{-1} = 1 - N + N^2 - N^3 + ...$
В принципе, для написания хоть какой-то программы этого уже было бы достаточно:
перенесем s_{kn} в левую часть, а k^n в правую, получим выражение s_{kn} через
s_{ln}, где l<k. Эту рекурсию уже легко написать. Но поучительнее доделать
до конца и получить точный ответ. Выражение s_{kn} через k^n выглядит
почти так же как и наоборот, только там каждый второй знак минус
(те, что на нечетных диагоналях).
II способ (не очень то поучительный):
Рассмотрим самую красивую девицу. Есть две альтернативы -
либо она окажется в в каком-то гареме единственной, либо с ней будет кто-то еще.
В последнем случае, если мы ее похитим, то оставшиеся $(n-1)$ девица будут
нормально распределены ровно по $k$ гаремам. В первом же случае, если мы
ее похитим, то нам придется убить ее мужа (что он за султан такой с гаремом без жен),
тогда оставшиеся наложницы в количестве (n-1) штук будут честно распределены
по (k-1) гарему. В общем получается такое соотношение:
$$ s_{kn} = k s_{k,n-1} + s_{k-1,n-1} $$ (2)
Слабый духом на этом месте остановится и начнет делать рекурсию.
Но нормальные герои всегда идут в обход - гораздо поучительнее рассмотреть
производящую функцию $ S(x,y) = \sum_{k,n} s_{kn} x^k y^n $
В таком случае, наше выражение (2) превратится в дифференциальное уравнение
$$ S = xy (dS/dx + S) + {какие-то поправочные члены при малыхх степенях k,n<2}$$
Этот дифур бодро решаем (граничные условия берем опять же из значений при x=0)
и в разложении ответа по степеням x,y получаем нужные нам числа.
III способ.
Пусть мы хотим чтобы в каждой группе было фиксированное количество особей:
l_1,l_2,...,l_k. Тогда количество таких расстановок это n!/(l_1! l_2! ... l_k!).
Соответственно, количество всех расстановок это \sum_{l_1,...,l_k} n!/(l_1! l_2! ... l_k!),
где сумма берется по таким наборам {l_i > 0}, что l_1 + ... + l_k = n. n! вынесем за
скобку, а то что останется очень похоже на коэффициент при x^n у функции
S_k(x) = (e^x-1)^k.
Разложив ее по биному Ньютона получим S_k(x) = \sum C_k^l (-1)^l e^{(k-l)x},
а коэффициент при x^n, соответственно \sum C_k^l (-1)^l (k-l)^n 1/n!
(что, кстати, я и обещал в первом способе).
Оригинальное пояснение к числу Стирлинга 2го рода :new_megalol: Сам придумал, или это из книжки (я про наложниц)? Если сам - то мегареспект! А ежли из книжки, то выходные данные в студию (если вся ДМ там в таком духе, очень забавно будет почитать)
2.6.14-gentoo-r5 kde-3.5.0 | openbox-3.2 Deep Purple | Rob Zombie | Led Zeppelin | ДДТ
Сам, конечно. Сведение любой задачи к бабам достаточно распространенный прием.
Можно было б про сети или про дистрибутивы линукса оформить. Про баб есть задачи
с гораздо более интересными философскими выводами. Например, можно строго обосновать
"если б я был султан то имел трех жен":
Пусть все женщины линейно упорядочены по каким-то трем параметрам,
и одна женщина считается лучше другой, если она превосходит ее по двум или трем,
тогда найдутся такие три женщины, что любую другую одна из них превосходит.
Насчет групп я не очень понял. А вот с переводом десятичных в другие легко!
Есть допустим у тебя переменная inti. Если тебе например надо из десятичной системы в восьмеричную то используй следующую строку:
printf ("%o", i);
%о - это значит восьмеричная система
Fixord добавил в 03.04.2005 13:52
Если тебе нужна книжка по алгоритмам зайди на www.books.ru и поищи да купи. Если лень покупать то зайди на www.helloworld.ru, там тебе и книжка по С или С++ и алгоритмы.
Нет такого слова в этой букве В смысле, не существует в природе такого названия.
(Fixord @ Воскресенье, 03 Апреля 2005, 12:52) писал(а):А вот с переводом десятичных в другие легко!
Есть допустим у тебя переменная inti. Если тебе например надо из десятичной системы в восьмеричную то используй следующую строку:
тоже алгоритмик бы 
В смысле, не существует в природе такого названия.