Re: Алгоритм, Ansi C стандарт
[20.07.2004 1:12] Обнаружено письмо от Oleg V.Boguslavsky
[20.07.2004 1:12] Тема "Алгоритм, Ansi C стандарт"
OVB> Привет всем,
OVB> Вопросик первый: где можно найти стандарт Ansi C плюс его грамматику в
OVB> виде БНФ?
В БНФ нунжно, если ты свой компилятор пишешь :)
Может справочника хватит? В MSDN есть, может еще есть в сети. А вообще
хорошая книжка по С, это книжка "Язык Си", у которой авторы Керниган и Ритчи.
OVB> И еще такая проблема - может просто идею какую подкините, или
OVB> кого-то заинтересует, или кто-то уже делал... вообщем нужно сообразить
OVB> след. алгоритм:
OVB> Пусть есть последовательность чисел 1..2n на позициях 1..2n
OVB> e.g.
OVB> 1 2 3 4 5 6
OVB> Из нее нужно получить комбинации чисел следующим образом: каждая из них
OVB> получается путем n-обменов двух любых чисел между собой, например
OVB> 6 4 5 2 3 1, т.е. произошли обмены 6-1, 4-2 и 5-3. Причем если в
OVB> результате взять две любых комбинации, то в них не может быть больше
OVB> одного одинакового обмена (т.е. если n=4 и была получена комбинация
OVB> 8 7 6 5 4 3 2 1 (были обмены 1-8,2-7,3-6 и 4-5), то комбинация
OVB> 8 7 5 6 3 4 2 1 недопустима, т.к. обмены 1-8 и 2-7 для этих двух
OVB> комбинаций совпадают. Общее кол-во таких перестановок равна sum(i),
OVB> i=1..2n-1. Например для n=3:
OVB> 1 2 3 4 5 6
OVB> |
OVB> V
OVB> 1) 2 1 4 3 6 5
OVB> 2) 2 1 5 6 3 4
OVB> 3) 2 1 6 5 4 3
OVB> 4) 3 4 1 2 6 5
OVB> 5) 3 5 1 6 2 4
OVB> 6) 3 6 1 5 4 2
OVB> 7) 4 3 2 1 6 5
OVB> 8) 4 5 6 1 2 3
OVB> 9) 4 6 5 1 3 2
OVB> 10)5 3 2 6 1 4
OVB> 11)5 4 6 2 1 3
OVB> 12)5 6 4 3 1 2
OVB> 13)6 3 2 5 4 1
OVB> 14)6 4 5 2 3 1
OVB> 15)6 5 4 3 2 1
OVB> Как видно, еще одной особенностью является тот факт, что каждый обмен
OVB> встречается ровно в n комбинациях (e.g. обмен 2-1 встречается только в
OVB> 1,2 и 3-й комбинации). Более того - я точно знаю, что
OVB> далеко не для всех n такой набор комбинаций можно найти - можно лишь для
OVB> n=1,3 - а мне надо проверить для n=28 - для всех остальных значений n
OVB> видимо решения также нету.
Нужен список набора сортированных перестановок. Для поиска предыдущей
перестановки просматриваем предыдущие перестановки.
А можно сделать рекурсивно:
Есть множество чисел n, выбираем минимальное, например1, и делаем все
перестановки: 1:2, 1,3 ... 1,n
для каждоый перестановки вызываем перестановку оставшихся числел.
Таким образом считаем:
int recomb(bool *map, int begin_index, int end_index)
{
// условие завершения
if(begin_index == end_index)
return 0;
int sum = 0;
for(int i = begin_index + 1, i < end_index, i++)
{
// пропускаем выбранные номера
if(map[i] == false)
continue;
map[i] = false;
sum += recomb(map, begin_index + 1, end_index);
map[i] = true;
}
return sum;
}
Пример не компилил, так что за ошибки не пинать :)
С пожеланием доброго времени суток,
Олень Элмо
JabberID: da.el***@j*****.ru
gpg --keyserver pgp.mit.edu --search-keys da.el***@m*****.ru
Key fingerprint = 273C 4245 7209 240B E880 81E0 B22E 4291 77DB FB8C
Номер выпуска : 3427
Возраст листа : 301 (дней)
Количество подписчиков : 442
Адрес в архиве : http://subscribe.ru/archive/comp.soft.prog.prog/msg/194205
Получить правила : mailto:comp.soft.prog.prog-rules@subscribe.ru
Формат "дайджест" : mailto:comp.soft.prog.prog-digest@subscribe.ru
Формат "каждое письмо" : mailto:comp.soft.prog.prog-normal@subscribe.ru
Формат "читать с веба" : mailto:comp.soft.prog.prog-webonly@subscribe.ru
-*Информационный канал Subscribe.Ru
Адрес подписки:
Написать в лист: mailto:comp.soft.prog.prog-list@subscribe.ru
Отписать: mailto:comp.soft.prog.prog--unsub@subscribe.ru
http://subscribe.ru/ mailto:ask@subscribe.ru
