| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
vilza
Зарегистрирован: 30.11.2006
Сообщения: 5
|
 Добавлено: Чт Ноя 30 2006 09:03 Заголовок сообщения: Помогите реализовать алгоритм |
 |
|
Задача на языке РЕФАЛ
Задача: Бусы
Сколько разных бус можно собрать из заданного набора разноцветныз бусинок? Бусы - это цепочка бусинок, надетых на нитку, которая связана в кольцо, поэтому у них нет начала и конца. Понятно, что как бусы ни поворачивай - это одни и те же бусы. Если поменять местами бусинки одного цвета, бусы от этого не изменятся.
Техническое требование
Задана строка латинских букв, больших и маленьких. Каждая буква обозначает цвет. Причем маленькая означает темный вариант цвета, большая светлый(r - красный, R - светло-красный). Бусинок одного цвета столько, сколько раз встречается эта буква в строке. Длина строки не более 50 символов.
Пример
Бусинки: tSst
Разных бус: 2
Алгоритм
1. Пусть n - количество бус.
2. Найдем k1,k2... - количество бусинок каждого цвета.
Найдем k - общее количество повторяющихся.
Найдем l - количество элементов имеющих повторы.
3. Тогда найдем количество возможных наборов (n-k+l)!
4. Сравним наборы:
(1),(2) - наборы, тогда:
а) 1-ый элемент (1) соотносим с 1-ым элементом (2)
б) n-ый элемент (1) соотносим с 1-ым элементом (2)
Подскажите пожайлуста.Возможно дело в алгоритме, но это лучшее что пришло в голову.
Заранее спасибо всем.
_________________
Just be smart... |
|
| Вернуться к началу |
|
 |
next
Зарегистрирован: 20.11.2006
Сообщения: 28
|
| Добавлено: Чт Ноя 30 2006 19:16 Заголовок сообщения: |
|
|
если элементы (ака бусины) не зацикленны, то их пермутации находятся с помощью рекурсии, наверное вот-так:
| Цитата: | /* factorial function */
int f(int n) {
if(n > 1) return n*f(n-1);
return n;
}
char s[] = "tSst";
/* number of values element in 's' can take */
#define MAX 26
int main() {
int n, i, t, k[MAX];
/* init element counters to 0 */
for(i = 0; i < MAX; ++i) k[i] = 0;
/* count unique elements and get total
* number of available positions */
for(t = 0; s[t]; ++t) k[tolower(s[t])-'a']++;
/* get number of possible position-permutations */
n = f(t);
/* exclude repetative positions */
for(i = 0; i < MAX; ++i) if(k[i]) n/=f(k[i]);
printf("permutations: %d\n", n);
return 0;
}
|
а вот как тем-же методом убрать элементы повторяющиеся в результате скроллинга?
может заменить "n = f(t);" на "n = f(t)/(t-1);" ????? =/
вроде комбинаторика с этим разбирается, думаю ее и следует почитать. |
|
| Вернуться к началу |
|
|
vilza
Зарегистрирован: 30.11.2006
Сообщения: 5
|
| Добавлено: Пт Дек 01 2006 01:23 Заголовок сообщения: |
|
|
Спасибо за отклик.
Мой алгоритм, кажется, верен, но главная проблема, на данный момент, заключается в реализации идеи на РЕФАЛ'е... В Си пока не пробовал, т.к. задание было именно на рефале.
_________________
Just be smart... |
|
| Вернуться к началу |
|
|
next
Зарегистрирован: 20.11.2006
Сообщения: 28
|
| Добавлено: Пт Дек 01 2006 03:49 Заголовок сообщения: |
|
|
| vilza писал(а): | | главная проблема, на данный момент, заключается в реализации идеи на РЕФАЛ'е... В Си пока не пробовал, т.к. задание было именно на рефале. |
честно признаюсь, про РЕФАЛ впервые от вас услышал, но думаю там все так-же 
а замена 'n = f(t);" на "n = f(t)/(t-1);" похоже действительно выдает правильные результаты.
посему количество бус можно записать как: n = t! / (t+k-1)
где:
't' - полное число бусинок
'k' - произведение факториалов количеств бусинок каждого цвета |
|
| Вернуться к началу |
|
|
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
