основной форум
Архив сообщений 2004-2006 года

Алгоритмы, методы, исходники


Олимпиады >> Задачи

Страницы: 1
StatujaLeha
новичок


Рег.: 07/08/05
Сообщений: 8
Из: Великий Новгород
Меня терзают смутные сомнения :)
      #11970 - 08/29/06 07:34 AM

Вот есть тут одна задачка http://www.ttb.by/trainingzone/tasks/PermutationCycles/statement.htm . Вот ее разбор http://www.ttb.by/trainingzone/tasks/PermutationCycles/solution.htm
Подумал я немного: вот сумма перестановок из n элементов, в которых 1 цикл, 2 цикла, ..., n циклов, т.е. countPermutations (n,1) + ... + countPermutations (n,n), должна быть n!. Написал маленький тестик для n <= 15. 15! влезает в long long. Для 14, 15 уже несоответствия. Я где-то ошибся?

Code:
#include <memory.h>

using namespace std;

#define MAXN 1000
#define int64 long long
#define MODULE 123456789

int F[MAXN+1][MAXN+1];

class PermutationCycles {
public:
long long countPermutations (int N, int K) {
memset(F, 0, sizeof(F));
F[0][0] = 1;
for (int i=1; i <= N; i++)
for (int j=1; j <= i; j++)
F[i][j] = ((int64)F[i-1][j-1] + (i-1) * (int64)F[i-1][j]);
return F[N][K];
}
};

long long factorial(int n)
{
if(n <= 1)
return 1;

return n*factorial(n - 1);
}

bool check(int K)
{
PermutationCycles count;
long long result = 0;
for (int i = 1;i <= K;++i)
{
result += count.countPermutations(K,i);
}

return result == factorial(K);
}

void main()
{

for (int i = 1;i <= 15;++i)
if(!check(i))
std::cout << i << std::endl;
}



Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
kia
новичок
*****

Рег.: 06/12/06
Сообщений: 21
Re: Меня терзают смутные сомнения :) [Re: StatujaLeha]
      #11972 - 08/29/06 08:52 AM

У тебя тип элементов массива F - int, а должно быть long long.

Операции над сообщением Печать сообщения   Добавить тему в напоминания!   Известить модератора  
Страницы: 1



Дополнительная информация
0 зарегистрированных и 401 анонимных пользователей просматривают этот форум.

Модератор:  Илья Кантор, Sergeyev, M_Gustokashin 

Распечатать тему

Права
      Вы не можете создавать новые темы
      Вы не можете отвечать на сообщения
      HTML выключен
      UBBCode включен

Рейтинг:
Просмотры темы: 8629

Rate this topic

Переход в