ПОМОГИТЕ ДОПОЛНИТЬ АЛГОРИТМ, ДОПОЛНИТЬ АЛГОРИТМ ПОДСЧЁТА СОЧЕТАНИЙ Опции

[KOMBIDEN]

ПОМОГИТЕ КТО МОЖЕТ.
Я ФИЗИК В ПОСКАЛЕ СИКУ СЛОБО, НО НАШЁЛ НА ВАШЕМ САЙТЕ ПОЧТИ ТО ЧТО МНЕ НУЖНО.
ВОТ СХОЖАЯ С МОЕЙ ЗАДАЧА НА СОЧЕТАНИЯ КОТОРУЮ Я НАШЁЛ.
Сочетания
Задачи о сочетаниях решают вопрос о том, сколькими способами можно выбрать M элементов из заданного N элементного множества и генерации всех возможных выборок. Число выборок вычисляется следующей формулой С=n!/(m!(n - m)!).

Рассмотрим задачу о генерации сочетаний в лексикографическом порядке.
ПРИМЕР 1.
Для примера рассмотрим начальные данные N=6 и M=4. Тогда число сочетаний равно 15. Начальное сочетание образует последовательность 1, 2, .. m, а последнее n-m+1, … , n.

Цитата
1234 1256 2345
1235 1345 2346
1236 1346 2356
1245 1356 2456
1246 1456 3456

Переход к следующему сочетанию осуществляется по следующему правилу: требуется просмотреть текущее сочетание с конца и найти элемент, который можно увеличить. То есть такой элемент что a[i] <> n-k+i. Далее увеличиваем этот элемент на 1, а оставшуюся часть сочетания заполняем числами натурального ряда большими измененного элемента в порядке их следования.

program sochets; 
 var
    i, j, n, m: integer;
    a: array[0 .. 100] of integer;

    { процедура вывода текущего сочетания }
  procedure use;
  var i: integer;
  begin
    writeln;
    for i:=1 to m do write(a[i]:3)
  end;

    begin
    write('ввод N и M: '); read(n, m);
      { формирование первого сочетания }

    for i:=0 to m do a[i]:=i;
      repeat
      use;
      i:=m;
      while a[i]=n-m+i do dec(i); { поиск элемента для изменения }
      inc(a[i]);
      for j:=i+1 to m do a[j]:=a[j-1]+1; { изменение правой части сочетания }
    until i=0;
  end.

МОЯ ЗАДАЧА ОТЛИЧАЕТСЯ ОТ ПРЕДСТАВЛЕННОЙ ЗАДАЧИ(ПРИМЕР 1) ТЕМ ЧТО:

1) N=8 А НЕ 6 А СЛЕДОВАТЕЛЬНО И КОЛЛИЧЕСТВО СОЧЕТАНИЙ УВЕЛИЧИТСЯ С 15 ДО 70.
2) НЕОБХОДИМО ЧТОБЫ АЛГОРИТМ НЕ ТОЛЬКО ПОДСЧИТЫВАЛ И ВЫВОДИЛ НА ЭКРАН КОЛ-ВО СОЧЕТАНИЙ НО И ПОДСЧИТЫВАЛ И ВЫВОДИЛ КОЛ-ВО СОЧЕТАНИЙ В КОТОРЫХ ВСТРЕЧАЮТСЯ ОПРЕДЕЛЁННЫЕ ЦЫФРЫ, А КОНТРЕТНЕЕ НУЖНО ПОДСЧИТАТЬ И ВЫВЕСТИ ВСЕ СОЧЕТАНИЯ В КОТОРЫХ ВСТРЕЧАЮТСЯ СЛЕДУЮЩИЕ ЦЫФРЫ:

1 И 3 ЛИБО
2 И 4 ЛИБО
3 И 5 ЛИБО
4 И 6 ЛИБО
5 И 7 ЛИБО
6 И 8 ЛИБО
1 И 7 ЛИБО
2 И 8.

С ПОМОЩЬЮ ТЕОРИИ ВЕРОЯТНОСТИ Я ЭТУ ЗАДАЧУ РЕШИЛ НО МНЕ НУЖЕН ИМЕННО АЛГОРИТМ НА ПАСКАЛЕ.

И ПОДСКАЖИТЕ ПАЖАЛУЙСТО СКОЛЬКО ПРИМЕРНО ВРЕМЕНИ АЛГОРИТМ БУДЕТ СЧИТАТЬ НА ПОСКАЛЕ ЭТУ ЗАДАЧУ ЕСЛИ ЗНАЧЕНИЯ "M" И "N" БУДУТ БОЛЬШИМИ, А КОНКРЕТНЕЕ M=50, N=10

ОГРОМНОЕ СПОСИБО ПРОГРАМИСТАМ ОТ ФИЗИКОВ.

[Lapp]

KOMBIDEN, пожалуйста, прочти Правила Форума. Особенно обрати внимание на п.6. Я понимаю, что ты не имел в виду крик, но читать правда неприятно. Мы что тут, в детском саду и понимаем только большие буквы?..

Второе: не копируй другие сообщения с форума, а просто приводи ссылку (скопируй в сообщение из адресной строки, название она определит автоматом).

Я немного изменил программу в приведенном мессадже (volvo, извиняй) под твои требования. Теперь выводится только то, что подходит под твое условие. Плюс перенес вывод из процедуры в основную прогу (для скорости). Применимость расширил до диапазона байта (на всяк случай)).

Сколько времени будет выполняться - прикинь сам. Ты можешь оценить количество строк и можешь оценить время на вывод одной строки. Это скорее область физики .

program sochets_m;
var
  i, j, n, m, l: integer;
  a: array[0 .. 255] of integer;
  s,t: string;
  d: set of byte;

begin
  write('ввод N и M: ');
  read(n, m);
  if n<10 then l:=2 else if n<100 then l:=3 else l:=4;
    { формирование первого сочетания }
  for i:=0 to m do a[i]:=i;
  repeat
    s:='';
    d:=[];
    for i:=1 to m do begin
      d:=d+[a[i]];
      Str(a[i]:l,t);
      s:=s+t
    end;
    if
      (1 in d) and (3 in d) or
      (2 in d) and (4 in d) or
      (3 in d) and (5 in d) or
      (4 in d) and (6 in d) or
      (5 in d) and (7 in d) or
      (6 in d) and (8 in d) or
      (1 in d) and (7 in d) or
      (2 in d) and (8 in d)
    then WriteLn(s);
    i:=m;
    while a[i]=n-m+i do dec(i); { поиск элемента для изменения }
    inc(a[i]);
    for j:=i+1 to m do a[j]:=a[j-1]+1; { изменение правой части сочетания }
  until i=0;
end.

[KOMBIDEN]

Большое спосибо Lapp

[Lapp]

Большое спосибо Lapp

Нет проблем, заходи еще. Можно и про физику поговорить...

[KOMBIDEN]

Добрый день LAPP. Извини что опять тебя беспокою. Ещё раз спосибо за алгоритм, работает .Если можешь помоги мне его ещё дополнить(усложнить). Мне это нужно для окончательной задчи с большими значениями N и M.Необходимо что бы алгоритм выводил на экран не сами сочетания в которых встречаются определённые комбинации цифр, а в реальном времени на экране было выдно как изменяется, точнее увеличивается колличество токих комбинаций и в конце алгоритм выводил на экран не только количество таких сочетаний(в которых есть определенное кобинация цифр), но и полное колличество всех возможных сочетаний( на языке комбинаторики: всех возможных выборок М элементов из задонного N элементного множества). Мне это нужно для вычесления вероятности генерации определённых комбинаций цифр. Спосибо!!!

[Lapp]

KOMBIDEN, извини, но опять тебя приходится учить элементарным правилам общения.. На форуме, пожалуйста, обращайся ко всем (по крайней мере, если это не ответ на вопрос конкретного человека. И еще: алгоритм этот - не мой, а volvo!

в реальном времени на экране было выдно как изменяется, точнее увеличивается колличество токих комбинаций и в конце алгоритм выводил на экран не только количество таких сочетаний(в которых есть определенное кобинация цифр), но и полное колличество всех возможных сочетаний

Так?

program sochets_m;
var
  i, j, n, m, l: integer;
  k1,k2: LongInt;
  a: array[0 .. 100] of integer;
  s,t: string;
  d: set of byte;

begin
  write('ввод N и M: ');
  read(n, m);
  if n<10 then l:=2 else if n<100 then l:=3 else l:=4;
	{ формирование первого сочетания }
  for i:=0 to m do a[i]:=i;
  k1:=0;
  k2:=0;
  repeat
	s:='';
	d:=[];
	for i:=1 to m do begin
	  d:=d+[a[i]];
	  Str(a[i]:l,t);
	  s:=s+t
	end;
	if
	  (1 in d) and (3 in d) or
	  (2 in d) and (4 in d) or
	  (3 in d) and (5 in d) or
	  (4 in d) and (6 in d) or
	  (5 in d) and (7 in d) or
	  (6 in d) and (8 in d) or
	  (1 in d) and (7 in d) or
	  (2 in d) and (8 in d)
	then begin
	  Inc(k2);
	  WriteLn(k2:10,'	',s)
	end;
	i:=m;
	while a[i]=n-m+i do dec(i); { поиск элемента для изменения }
	inc(a[i]);
	for j:=i+1 to m do a[j]:=a[j-1]+1; { изменение правой части сочетания }
	Inc(k1);
  until i=0;
  WriteLn('Total combinations: ',k1);
end.

Если хочешь, убери вывод самих сочетаний и оставь только вывод их числа.

[KOMBIDEN]

Спосибо за токую оперативную помощ.

[KOMBIDEN]

Здравсвуйте. В чём ошибка!? Формула подсчёта всех возможных коминаций - С=n!/(m!(n - m)!). Алгоритм правильно считал (с) т. е все возможные сочетания чисел когда я задовал различные n и m. Например: n = 8, m = 4 или n = 20, m = 10, и другие значения n и m. Алгоритм выдавал токие же значения как и в формуле. Но при значениях n = 50 и m = 10 алгоритм выдал что (С) = 1682343578 но из формулы следует что (С) = 10272278170?! Спосибо.

[sheka]

Здравсвуйте. В чём ошибка!? Формула подсчёта всех возможных коминаций - С=n!/(m!(n - m)!). Алгоритм правильно считал (с) т. е все возможные сочетания чисел когда я задовал различные n и m. Например: n = 8, m = 4 или n = 20, m = 10, и другие значения n и m. Алгоритм выдавал токие же значения как и в формуле. Но при значениях n = 50 и m = 10 алгоритм выдал что (С) = 1682343578 но из формулы следует что (С) = 10272278170?! Спосибо.

Обычно такое получается, когда число не влазит в тип. Попробуй Extended с включенной директивой {$N+}
хотя вроде 10272278170 в Real влазит..

Добавлено через 11 мин.
Аа.. Вроде понял
Наверное ты использовал LongInt, как в вышенаведеном примере. Попробуй Real.

[Lapp]

при значениях n = 50 и m = 10 алгоритм выдал что (С) = 1682343578 но из формулы следует что (С) = 10272278170

Sheka совершенно прав. Тип LongInt занимает 4 байта и может представлять числа в диапазоне от -2,147,483,648 до 2,147,483,647. Твой ожидаемый результат находится за его пределами.

Чтобы не попадать впросак имеет смысл держать включенной опцию Range Check - вставь самой первой строкой программы вот такое:
{$R+}
Это, правда, несколько замедлит расчеты (что, возможно, нежелательно в данной ситуации), но зато ты не будешь получать неверные результаты. Программа завершится аварийно (с сообщением Range Check Error) при выходе числа за диапазон, и это все же лучше, чем думать, что все в порядке, или гадать - а где ошибка?

В TurboPascal тип LongInt является максимальным целым типом. Во FreePascal (FPC) есть тип Int64, занимающий 8 байт (соответственно, простирающийся от -2⁶³ до 2⁶³-1. Также можно рекомендовать использовать тип Extended (он есть в Турбо), который хотя и не является буквально целым, но точность представления у него те же самые 20 десятичных цифр (как у Int64). Он занимает 10 байт, из которых 8 идет на мантиссу.

Тем не менее, рекомендую скачать FPC в любом случае. Он 32-разрядный, а твои задачи не очень хорошо укладываются в 16 бит Турбо Паскаля..

[volvo]

В TurboPascal тип LongInt является максимальным целым типом.

Вот только про Comp не надо забывать... Хоть формально он и относится к вещественным, но справка Турбо-Паскаля это недоразумение тут же рассеивает:

Note: The comp type is a 64-bit integer. It holds only integral values within the range (-2⁶³ + 1) to (2⁶³ - 1).

[KOMBIDEN]

Подскажите, пожалуйсто, по подробнее как менять тип данных longint на comp ? При замене longint на comp в алгоритме выдает ошибку 104 в 29 строке. Спосибо.

Сообщение отредактировано: KOMBIDEN - 21.03.2010 16:58

[Lapp]

Подскажите, пожалуйсто, по подробнее как менять тип данных longint на comp ? При замене longint на comp в алгоритме выдает ошибку 104 в 29 строке.

Наверное, твой нынешний код не совпадает с тем, который опубликован здесь, и номера строк не те. Ты уж приводи саму строку, клгда спрашиваешь, а не только ее номер..

Думаю, тебе надо поменять все Inc(x) на x:=x+1 . Под x я тут понимаю k1 и k2.

[KOMBIDEN]

Спосибо. Работает, только ответ выдает в десятичном числе с плавоющей точкой.Скажите что означает примечание в одном учебнике"Эфективное использование типов single,doudle, extended, comp возможно только при включеной директиве {$N+}. По умолчанию она находится в выклыченом состоянии {$N-}".Спосибо.

[Lapp]

ответ выдает в десятичном числе с плавоющей точкой.

Выводи по формату типа ": 1 : 0" (пробелы внутри не нужны, я вствил их, чтобы форумский софт не интерпретировал это как смайл). Вот так:

  WriteLn('Total combinations: ',k1:1:0);

что означает примечание в одном учебнике"Эфективное использование типов single,doudle, extended, comp возможно только при включеной директиве {$N+}. По умолчанию она находится в выклыченом состоянии {$N-}"

В фигурных скобках И начинающие с символа доллара - это директивы компилятора; с их помощью можно управлять процессом компиляции. Ты уже встречался с одной выше - {$R+} - включить отслеживание выхода за диапазон. Директива N включает/выключает (в зависимости, что за ней - плюс или минус) использование математического сопроцессора. Просто вставь ее в самом начале программы - и все. Поскольку мат.сопроцессор сейчас присутствует абсолютно ВСЕГДА, то лучше ее держать всегда включенной.

Многие директивы (и эти обе в частности) можно включать/выключать в меню Options->Compiler, но помещение их непосредственно в код во многих случаях предпочтительнее.

Ты скажи все-таки - ты чем пользуешься? Турбо? или все же скачал FPC, как я советовал?

[KOMBIDEN]

Понял, спосибо, пользуюсь пока Турбо, а какие приимущества у FPC перед Турбо в моём случае?

[Lapp]

какие приимущества у FPC перед Турбо в моём случае?

Преимущества те, что FPC использует вычислительные возможности более эффективно. Турбо - очень старый компилятор, он ничего не знает о процессорах, вышедших после 286-го. Это же каменный век... Конечно, на простых вычислениях с использованием копроцессора это не очень сильно сказывается, но все же это неправильно.

[KOMBIDEN]

Полял. Спосибо. Сейчас Скачаю FPC. Как я понимаю он полностью совместим с Турбо. Для првельной работы алгорима в FPC мне необходимо зделать те же изменения что и в Турбо, а конкретнее, поставить в первой строке дерективу {$R+}, второй строкой дерективу{$N+}, заменить longint на int64 и заменить все Inc(k1) и Inc(k2) на k1:=k1+1 и k2:=k2+1 ? Спосибо.

[Lapp]

Скачаю FPC. Как я понимаю он полностью совместим с Турбо. Для првельной работы алгорима в FPC мне необходимо зделать те же изменения что и в Турбо, а конкретнее, поставить в первой строке дерективу {$R+}, второй строкой дерективу{$N+}, заменить longint на int64 и заменить все Inc(k1) и Inc(k2) на k1:=k1+1 и k2:=k2+1 ? Спосибо.

Ну, почти полностью. Есть и кардинальные отличия. Например, работа с памятью - 32-разрядная модель принципиально несовместима с 16-разрядной. Но в этой задаче ничего такого нет. Кроме того, можно для большей совместимости выбрать диалект Турбо в меню Options -> Compiler (и есть соответствующая директива вида {$..}, но я не помню, какая).

Если использовать Int64, то можно оставить Inc() и Dec(). Хотя, можно и заменить на x:=x+1. Разницы никакой, компилятор все равно соптимизирует, думаю.

[KOMBIDEN]

Огромое спосибо, что посоветовали FPC. На FPC алгоритм с дерективами на тестовых задачах (с не очень большими N и M) считает примерно в 2 раза быстрее.