Как исправить ошибку арифметического переполнения в паскале?

[DarkDen]

Пока считает...

[DarkDen]

Сообщение от BDA

Добавил тестовый вывод (не комбинации, а номер рассматриваемой).
На Core i5 M450 займет теоретически 17 часов (1000000 комбинаций в секунду).

Чтото меня терзают смутные сомнения по поводу времени рачсетов. Неужели токая большая разница в производительности процессоров? У меня Атлон 4 ядра(2.7 на ядро), счиатает уже 33 часа???...
Спасибо

[BDA]

Ошибочка вышла
Ошибся на порядок - не 17 часов, а 176.

Продолжаю поиск формулы и ускорение последнего варианта перебора.
Пока есть ускорение на 2 секунды (обычный вариант - 127 секунд, ускоренный - 125) на небольшом тесте n = 29 m = 13 k = 4.

[DarkDen]

Значит и я ошибся.
Расчитал что будет считать около 4 суток.
Спасибо

[Poma][a]

Ошибся на порядок - не 17 часов, а 176.

Кхе-кхе
Это же неделя с хвостом! Да плюс это теоретически.. Вообщем жесть..

Как вариант : распределить работу (если есть ненужные компы).

А еще лучше вычислить математически...

Давай пойдем сначала..
У нас есть 52 шара. Кол-во перестановок - 52!
Найдем сколькими способами мы можем выбрать из 13 шаров 4 (возможно потом пригодится) - 13!/(4!*9!) = 5*11*13 = 715
Пляшем дальше..

1-ый красный шар может находиться в любой из 52 ячеек. Рассмотрим шары справа от 1-го шара : 2-ой - 51 3-ий - 50 4-ый - 49.
Всего 52*51*50*49 вариантов.

Так же для "лево"
Всего 2 * 52*51*50*49

А теперь умножим это на наши сочетания.
и того 715 * 2 * 52 * 51 * 50 * 49
Теперь поделим это на 52! и получим вероятность..

(Надо еще похимичить с шапами по в центре.. а так же учесть случай когда 2 первых и 2 последних шара образуют 4-ку)

ВНИМАНИЕ!! Я совсем не уверен!!

[BDA]

Poma][a, да, нужно еще подумать над формулой.
Ускоренный вариант:

var
  i, n, m, k: integer;
  OurComb, AllComb, tmp: Int64;
  t, s: string;
  fl: boolean;

const
  RedOne = '1';
  WhiteOne = '2';
  Empty = '0';

function C(n, m: byte): Int64;
var
  i, j: byte;
begin
  result := 1;
  if m <> 0 then
  begin
    j := 2;
    for i := m + 1 to n do
    begin
      result := result * i;
      while (j <= n - m) and (result mod j = 0) do
      begin
        result := result div j;
        inc(j);
      end;
    end;
  end;
end;

procedure Permute(p: integer); // использование глобальных переменных для ускорения
var
  i, j: byte;
  ch: char;
begin
  if p = n + 1 then
  begin
    inc(AllComb);
    fl := true;
    j := 0;
    while fl and (j < k) do
    begin
      i := 0;
      while fl and (i < k) do
      begin
        if t[(n - k + j + i) mod n + 1] <> RedOne then
          fl := false;
        inc(i);
      end;
      inc(OurComb, ord(fl));
      fl := not fl;
      inc(j);
    end;

    {if AllComb mod 1000000 = 0 then
      writeln(AllComb div 1000000);}
  end
  else
  begin
    fl := false;
    if p - 1 >= k then
    begin
      fl := true;
      i := p - k;
      while fl and (i < p) do
      begin
        if t[i] <> RedOne then
          fl := false;
        inc(i);
      end;
      if fl then
      begin
        j := 0;
        for i := 1 to n do
          inc(j, ord(s[i] = RedOne));
        tmp := C(n - p + 1, j);
        inc(AllComb, tmp);
        inc(OurComb, tmp);
      end;

      {if AllComb mod 1000000 = 0 then
        writeln(AllComb div 1000000);}
    end;
    if fl = false then
      for i := 1 to n do
      begin
        if s[i] = Empty then
          continue;
        ch := s[i];
        j := 1;
        while s[j] <> ch do
          inc(j);
        if j = i then
        begin
          t[p] := ch;
          s[i] := Empty;
          Permute(p + 1);
          s[i] := ch;
        end;
      end;
  end;
end;

begin
  { cгенерируем S, сначала пойдут красные }
  readln(n, m, k);
  s := '';
  for i := 1 to m do
    s := s + RedOne;
  for i := m + 1 to n do
    s := s + WhiteOne;
  t := s;
  { собственно и сами перестановки }
  OurComb := 0;
  AllComb := 0;
  Permute(1);
  writeln(AllComb, ' ', OurComb);
  readln;
end.

Работа:

Тест 29 13 4
последний вариант из этой темы - 127 секунд
этот код - 43 секунды

Сообщение от Poma][a

Как вариант : распределить работу (если есть ненужные компы).

Было бы неплохо. Хотел перенести расчеты на GPU, но не нашел быстрого способа переноса.

Сообщение от Poma][a

А еще лучше вычислить математически...

Это бы было просто замечательно.
Хотел подойти к преподавателю по теорверу, но как-то не срослось
Мне не хватает формулы, которая решает задачу:
Количество комбинаций распределения N' шаров по M' ящикам, причем в каждом ящике не менее 1 шара и не более K'.

[Poma][a]

да, нужно еще подумать над формулой.

Ага. Благо времени у нас много

43 секунды

Вау! Впечатляет

Хотел подойти к преподавателю по теорверу, но как-то не срослось

Боюсь мой учитель по математике не знает..

Количество комбинаций распределения N' шаров по M' ящикам, причем в каждом ящике не менее 1 шара и не более K'.

Эм.. А это не C из N по K? Возьмем прощитаем варианты для K=1. Потом равного 2. потом... Потом k-1 и k. Сложим.. И вуаля!

Кстати.. если по раскладывать то получим : n + (n-1)n/2! + (n-1)n(n-2)/3! ... + (n-k)*(n-k+1)*..*(n-2)*(n-1)*(n)/k!
Как-то так..

[DarkDen]

Математически пробовал. Пришёл к тому, что одной, двумя формулами и теоремами теории вероятности и камбинаторики тут не отделаешся. И самое главное достаточно большая вероятнось ошибки. Есть "частые случаи" которые необходимо учесть.

Хотя бы этот.

[QUOTE=DarkDen;1226552]Если в ячейках подряд расположены более чем 4 красных шара, то это считается событием? И если это рассматривать как событие, то сколько раз его считать?

Именно по этой причине я не мог составить математическую формулу, не знал какое колличество комбинаций необходимо исключить.
Если даже 2 или 3 раза за один расклад всех шаров, появляется комбинация из 4 красных шаров это считаеться одним событием, математическая формула которую я составил считала это разными событиями и в этом была ошибка.
Если не 4 а 5 красных шарв выполо подряд это считаеться не 2 а 1 событием.
Я думаю програмным методом эту задачу решить немного легче чем искать математическую формулу, но нужен безошибочный алгоритм.


Можно просто прозевать какой либо "частый случай" и не исключить нужное количество комбинаций или неправильно посчитать какое количество комбинаций нужно исключить т. к. идеальной формулы как я не сторался я не вывел, хотя мне помогал не один математик.
Спасибо

[Poma][a]

но нужен безошибочный алгоритм.

Дело в том что кол-во переборных вариантов огроменно.. Нужен не только безошибочный, но и эффективный алгоритм.

[DarkDen]

Количество комбинаций распределения N' шаров по M' ящикам, причем в каждом ящике не менее 1 шара и не более K'.

Но в каждом ящике всегда или один белый шар или один красный шар.
Спасибо