Неподвижные точки

JustYouSmile147 · 08.01.2013, 07:14

Задача №31 с сайта acmp

Неподвижные точки
(Время: 1 сек. Память: 16 Мб Сложность: 57%)
Перестановкой P[1..n] размера n называется набор чисел от 1 до n, расположенных в определенном порядке. При этом в нем должно присутствовать ровно один раз каждое из этих чисел. Примером перестановок являются 1,3,4,5,2 (для n=5) и 3,2,1 (для n=3), а, например, 1,2,3,4,5,1 перестановкой не является, так как число 1 встречается два раза.

Число i называется неподвижной точкой для перестановки P, если P[i] = i. Например, в перестановке 1,3,4,2,5 ровно две неподвижных точки: 1 и 5, а перестановка 4,3,2,1 не имеет неподвижных точек.

Даны два числа: n и k. Найдите количество перестановок размера n с ровно k неподвижными точками.

Входные данные

Входной файл INPUT.TXT содержит два целых числа n (1 ≤ n ≤ 9) и k (0 ≤ k ≤ n).

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

INPUT.TXT OUTPUT.TXT
5 2 20
9 6 168
2 1 0
9 0 133496

Код:

program abc;
const e=2.718281828;
var
  n,k,a:byte
  n1:integer;
Function fact(a:integer):longint;
begin
  if A=0 then fact:=1
   else fact:=a*fact(a-1);
end;
begin
  Assign(input, 'input.txt');
  Reset(input);
  Assign(output, 'output.txt');
  Rewrite(output);
  Read(n,k);
  n1:=round(fact(n-k)/e);
  write(n1);
end.

Почитал комментарии к задаче, узнал о субфакториале...Вообще я очень слаб в комбинаторике, поэтому, пожалуйста, напишите полное решение задачи и желательно с подробным объяснением

08.01.2013, 07:14	#1 (permalink)
JustYouSmile147 Новичок Регистрация: 07.01.2013 Сообщений: 2 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 10	Неподвижные точки Задача №31 с сайта acmp Неподвижные точки (Время: 1 сек. Память: 16 Мб Сложность: 57%) Перестановкой P[1..n] размера n называется набор чисел от 1 до n, расположенных в определенном порядке. При этом в нем должно присутствовать ровно один раз каждое из этих чисел. Примером перестановок являются 1,3,4,5,2 (для n=5) и 3,2,1 (для n=3), а, например, 1,2,3,4,5,1 перестановкой не является, так как число 1 встречается два раза. Число i называется неподвижной точкой для перестановки P, если P[i] = i. Например, в перестановке 1,3,4,2,5 ровно две неподвижных точки: 1 и 5, а перестановка 4,3,2,1 не имеет неподвижных точек. Даны два числа: n и k. Найдите количество перестановок размера n с ровно k неподвижными точками. Входные данные Входной файл INPUT.TXT содержит два целых числа n (1 ≤ n ≤ 9) и k (0 ≤ k ≤ n). Выходные данные В выходной файл OUTPUT.TXT выведите ответ на задачу. Примеры INPUT.TXT OUTPUT.TXT 5 2 20 9 6 168 2 1 0 9 0 133496 Код: program abc; const e=2.718281828; var n,k,a:byte n1:integer; Function fact(a:integer):longint; begin if A=0 then fact:=1 else fact:=a*fact(a-1); end; begin Assign(input, 'input.txt'); Reset(input); Assign(output, 'output.txt'); Rewrite(output); Read(n,k); n1:=round(fact(n-k)/e); write(n1); end. Почитал комментарии к задаче, узнал о субфакториале...Вообще я очень слаб в комбинаторике, поэтому, пожалуйста, напишите полное решение задачи и желательно с подробным объяснением

Опции темы
Версия для печати Отправить по электронной почте
Опции просмотра
Линейный вид Комбинированный вид Древовидный вид

08.01.2013, 07:14
Helpmaster Member Регистрация: 08.03.2016 Сообщений: 0	Несколько похожих на вашу тем уже создавались Не могу подключиться к беспроводной точки Wi-Fi Белые точки на экране

Ads
Яндекс Member Регистрация: 31.10.2006 Сообщений: 40200 Записей в дневнике: 0 Сказал(а) спасибо: 0 Поблагодарили 0 раз(а) в 0 сообщениях Репутация: 55070