IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

2 страниц V  1 2 >  
 Ответить  Открыть новую тему 
> ПОМОГИТЕ ДОПОЛНИТЬ АЛГОРИТМ, ДОПОЛНИТЬ АЛГОРИТМ ПОДСЧЁТА СОЧЕТАНИЙ
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


ПОМОГИТЕ КТО МОЖЕТ.
Я ФИЗИК В ПОСКАЛЕ СИКУ СЛОБО, НО НАШЁЛ НА ВАШЕМ САЙТЕ ПОЧТИ ТО ЧТО МНЕ НУЖНО.
ВОТ СХОЖАЯ С МОЕЙ ЗАДАЧА НА СОЧЕТАНИЯ КОТОРУЮ Я НАШЁЛ.
Сочетания
Задачи о сочетаниях решают вопрос о том, сколькими способами можно выбрать 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

ОГРОМНОЕ СПОСИБО ПРОГРАМИСТАМ ОТ ФИЗИКОВ.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

Сколько времени будет выполняться - прикинь сам. Ты можешь оценить количество строк и можешь оценить время на вывод одной строки. Это скорее область физики smile.gif.
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.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Большое спосибо Lapp
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(KOMBIDEN @ 10.02.2010 22:35) *
Большое спосибо Lapp
Нет проблем, заходи еще. Можно и про физику поговорить... smile.gif


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

Цитата(KOMBIDEN @ 27.02.2010 22:02) *
в реальном времени на экране было выдно как изменяется, точнее увеличивается колличество токих комбинаций и в конце алгоритм выводил на экран не только количество таких сочетаний(в которых есть определенное кобинация цифр), но и полное колличество всех возможных сочетаний

Так?
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.

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Спосибо за токую оперативную помощ.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


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


Я.
****

Группа: Пользователи
Сообщений: 809
Пол: Мужской
Реальное имя: Саша

Репутация: -  11  +


Цитата(KOMBIDEN @ 20.03.2010 22:10) *

Здравсвуйте. В чём ошибка!? Формула подсчёта всех возможных коминаций - С=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 влазит.. wacko.gif

Добавлено через 11 мин.
Аа.. Вроде понял smile.gif
Наверное ты использовал LongInt, как в вышенаведеном примере. Попробуй Real.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(KOMBIDEN @ 20.03.2010 23:10) *
при значениях n = 50 и m = 10 алгоритм выдал что (С) = 1682343578 но из формулы следует что (С) = 10272278170
Sheka совершенно прав. Тип LongInt занимает 4 байта и может представлять числа в диапазоне от -2,147,483,648 до 2,147,483,647. Твой ожидаемый результат находится за его пределами.

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Цитата
В TurboPascal тип LongInt является максимальным целым типом.
Вот только про Comp не надо забывать... Хоть формально он и относится к вещественным, но справка Турбо-Паскаля это недоразумение тут же рассеивает:
Цитата
Note: The comp type is a 64-bit integer. It holds only integral values within the range (-263 + 1) to (263 - 1).
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


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

Сообщение отредактировано: KOMBIDEN -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(KOMBIDEN @ 21.03.2010 10:52) *
Подскажите, пожалуйсто, по подробнее как менять тип данных longint на comp ? При замене longint на comp в алгоритме выдает ошибку 104 в 29 строке.
Наверное, твой нынешний код не совпадает с тем, который опубликован здесь, и номера строк не те. Ты уж приводи саму строку, клгда спрашиваешь, а не только ее номер..

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(KOMBIDEN @ 23.03.2010 0:59) *
ответ выдает в десятичном числе с плавоющей точкой.
Выводи по формату типа ": 1 : 0" (пробелы внутри не нужны, я вствил их, чтобы форумский софт не интерпретировал это как смайл). Вот так:
  WriteLn('Total combinations: ',k1:1:0);


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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Понял, спосибо, пользуюсь пока Турбо, а какие приимущества у FPC перед Турбо в моём случае?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(KOMBIDEN @ 23.03.2010 9:01) *
какие приимущества у FPC перед Турбо в моём случае?
Преимущества те, что FPC использует вычислительные возможности более эффективно. Турбо - очень старый компилятор, он ничего не знает о процессорах, вышедших после 286-го. Это же каменный век... Конечно, на простых вычислениях с использованием копроцессора это не очень сильно сказывается, но все же это неправильно.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(KOMBIDEN @ 26.03.2010 10:32) *
Скачаю 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. Разницы никакой, компилятор все равно соптимизирует, думаю.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


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

2 страниц V  1 2 >
 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 18:09
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name