ПОМОГИТЕ КТО МОЖЕТ.
Я ФИЗИК В ПОСКАЛЕ СИКУ СЛОБО, НО НАШЁЛ НА ВАШЕМ САЙТЕ ПОЧТИ ТО ЧТО МНЕ НУЖНО.
ВОТ СХОЖАЯ С МОЕЙ ЗАДАЧА НА СОЧЕТАНИЯ КОТОРУЮ Я НАШЁЛ.
Сочетания
Задачи о сочетаниях решают вопрос о том, сколькими способами можно выбрать 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.
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.
Большое спосибо Lapp
Добрый день LAPP. Извини что опять тебя беспокою. Ещё раз спосибо за алгоритм, работает .Если можешь помоги мне его ещё дополнить(усложнить). Мне это нужно для окончательной задчи с большими значениями N и M.Необходимо что бы алгоритм выводил на экран не сами сочетания в которых встречаются определённые комбинации цифр, а в реальном времени на экране было выдно как изменяется, точнее увеличивается колличество токих комбинаций и в конце алгоритм выводил на экран не только количество таких сочетаний(в которых есть определенное кобинация цифр), но и полное колличество всех возможных сочетаний( на языке комбинаторики: всех возможных выборок М элементов из задонного N элементного множества). Мне это нужно для вычесления вероятности генерации определённых комбинаций цифр. Спосибо!!!
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.
Спосибо за токую оперативную помощ.
Здравсвуйте. В чём ошибка!? Формула подсчёта всех возможных коминаций - С=n!/(m!(n - m)!). Алгоритм правильно считал (с) т. е все возможные сочетания чисел когда я задовал различные n и m. Например: n = 8, m = 4 или n = 20, m = 10, и другие значения n и m. Алгоритм выдавал токие же значения как и в формуле. Но при значениях n = 50 и m = 10 алгоритм выдал что (С) = 1682343578 но из формулы следует что (С) = 10272278170?! Спосибо.
Подскажите, пожалуйсто, по подробнее как менять тип данных longint на comp ? При замене longint на comp в алгоритме выдает ошибку 104 в 29 строке. Спосибо.
Спосибо. Работает, только ответ выдает в десятичном числе с плавоющей точкой.Скажите что означает примечание в одном учебнике"Эфективное использование типов single,doudle, extended, comp возможно только при включеной директиве {$N+}. По умолчанию она находится в выклыченом состоянии {$N-}".Спосибо.
WriteLn('Total combinations: ',k1:1:0);
Понял, спосибо, пользуюсь пока Турбо, а какие приимущества у FPC перед Турбо в моём случае?
Полял. Спосибо. Сейчас Скачаю FPC. Как я понимаю он полностью совместим с Турбо. Для првельной работы алгорима в FPC мне необходимо зделать те же изменения что и в Турбо, а конкретнее, поставить в первой строке дерективу {$R+}, второй строкой дерективу{$N+}, заменить longint на int64 и заменить все Inc(k1) и Inc(k2) на k1:=k1+1 и k2:=k2+1 ? Спосибо.
Огромое спосибо, что посоветовали FPC. На FPC алгоритм с дерективами на тестовых задачах (с не очень большими N и M) считает примерно в 2 раза быстрее.
Доброго времени суток всем. Помогите дополнить алгоритм ещё раз если это возможно т. к. я не могу вывести безошибочно математическую формулу. Чтобы было более понятно сначала представлю задачу в виде задачи по теории вероятности, а затем попытаюсь написать задачу языком приближенному к языку программирования. Предыдущий алгоритм вычислял следующее: было дано множество из N элементов предположим поле из N ячеек(у каждой ячейки свой порядковый номер). На это поле случайным образом выбрасоволось M белых шаров. Я в алгоритме задавал несколько комбинаций(сочетаний) выпадения белых шаров на поле с ячейками, указывая номер ячейки куда может выпасть шар . Алгоритм считал все возможные сочетания из заданного N элементного множества, другими словами подсчитывалось полное количество возможных сочетаний из M белых шаров на поле с количеством ячеек равное N(в алгоритме количество этих сочетаний обозначено как *total combinations*). Так же алгоритм отдельно считал и показывал количество всех заданных мной в алгоритме комбинаций выпадения белых шаров на поле с ячейками(данное количество заданных сочетаний обозночалось в алгоритме как *X combinations*.
В дополненном варианте на это же поле помимо M белых шаров выбрасывается R красных шаров. В алгоритме необходима возможность задавать нужные мне комбинации выпадения отдельно для красных и белых шаров т. е. задавать номера ячеек как я это делал в предыдущем алгоритме.
Нужно что бы алгоритм считал и показывал помимо всех возможных комбинаций выпадения белых и красных шаров на поле-*total combinations*, ещё считал и показывал количество всех сочетаний шаров где встречается хотя бы одна заданная в алгоритме комбинация или из белых шаров или из красных шаров(назовём эти сочетания *Y combinations*), а так же подсчитывал и показывал количество всех сочетаний где встречается хотя бы одна заданная комбинация из белых шаров И плюс хотя бы одна заданная комбинация из красных шаров(назовём эти сочетания *Z combinations*). В алгоритме нужно так же учесть что в одну ячейку может попасть только один шар.
Другими словами нужно ввести ещё одну переменную R элементы которой как и элементы M переменной принадлежат множеству N. Элементам переменной R как и элементам переменной M в алгоритме можно присваивать значения(натуральные числа). Из элементов переменной R как и из элементов переменной M формируются комбинации на множестве N. Помимо расчёта всех возможных сочетаний M и R элементов на N множестве необходимо чтобы алгоритм рассчитывал и показывал количество сочетаний в которых встречается хотя бы одна заданная в алгоритме комбинация из элементов переменной М или хотя бы одна заданная комбинация из элементов переменной R, а так же необходим расчет в алгоритме когда рассчитывается и выводится количество всех сочетаний в которых встречается хотя бы одна заданная в алгоритме комбинация из элементов переменной М и одновременно хотя бы одна заданная в алгоритме комбинация из элементов переменной R.
Я понимаю что всё это больше похоже на путаницу, но так как задача не совсем стандартная(по меркам теории вероятности и комбинаторики) я просто пытался представить её как можно более полно. Спасибо за любую помощь!