Программирование рекурсивных процедур для вычисления выражения

@jestero · Регистрация: 17.02.2014

Author24 — интернет-сервис помощи студентам

Вычислить значение:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?{c}_{n}^{m}=\frac{n!}{m!(n-m)!}$

Здесь как я понял нужна процедура с параметрами n и m. Но не знаю как саму рекурсию организовать. Помогите пожалуйста.

@Puporev · 09.02.2016, 16:27

Pascal

function C(n,m:integer):real;
begin
if (m=0)or(m=n) then C:=1
else C:=C(n-1,m-1)+C(n-1,m);
end;
var m,n:integer;
begin
repeat
writeln('Ведите n m,  n>=m ');
readln(n,m);
until n>=m;
write('Число сочетаний=',C(n,m):0:0);
end.

Большие числа не водите, зависнет.

@jestero · 10.02.2016, 06:15 **[ТС]**

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

C:=C(n-1,m-1)+C(n-1,m);

А как здесь всё вычисляется, что то не пойму? Хотя всё правильно работает. Тут же только из арифметических действий сложение, а например такое выражение не понятно как вычисляется в программе C(n-1,m-1)

@Puporev · 10.02.2016, 06:51

Здесь для написания рекурсивной функции определения числа сочетаний умные люди ( не я) не используют факториалы, а формулу
C_n^k = C_{n - 1}^{k - 1} + _{Cn - 1}^k (при 0 < k < n).
При этом пишут

Действительно, выбрать из n предметов k можно C_n^k способами. Пометим один из данных n предметов. Тогда все выборки можно разбить на две группы: в которые входит помеченный предмет (их будет C_{n - 1}^{k - 1}) и не содержащие помеченного предмета (таких выборок будет C_{n - 1}^k)).

Добавив к этой формуле краевые значения: C_nⁿ = C_n⁰ = 1 (выбрать все предметы или не выбрать ни одного предмета можно единственным способом), можно написать рекурсивную функцию вычисления числа сочетаний:

Можно конечно и написать рекурсивную функцию факториала и считать по приведенной формуле, но эта функция лучше (более эффективна).
Хотя еще лучше считать число сочетаний и без рекурсии и без факториалов.

@jestero · 10.02.2016, 06:54 **[ТС]**

То есть в данном случае мы сначала проходим вниз до того момента, когда начинает выполняться это условие: if (m=0)or(m=n) then C:=1. И потом поднимаемся вверх считая все значения на основании предыдущих. Правильно я понимаю?

@Puporev · 10.02.2016, 06:54

Да.

@jestero · 10.02.2016, 07:02 **[ТС]**

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

Можно конечно и написать рекурсивную функцию факториала

В этом случае будет такое условие?

Pascal

1	if (n=1) and (m=1) or (n=0) and (m=0) or (n=1) and (m=0) and (n=0) or (m=1) then C:=1

@Puporev · 10.02.2016, 07:15

Зачем? Пишется рекурсивная функция факториала

Pascal

function Fac(n:integer):longint;
begin
if n<2 then Fac:=1
else fac:=n*fac(n-1);
end;

и вычисляется выражение

Pascal

1	c:=Fac(n)/Fac(m)/Fac(n-m);

@jestero · 10.02.2016, 07:21 **[ТС]**

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

Зачем? Пишется рекурсивная функция факториала

Pascal

function Factrl (n: integer): integer; 
begin
 if n = 0 then
 Factrl:= 1;
 if n = 1 then
 Factrl:= 1;
 if n > 1 then
 Factrl:= n*Factrl(n-1);
end; 
var
C,n,m:integer;
begin
repeat
writeln('Ведите n m,  n>=m ');
readln(n,m);
until n>=m;
C:=(Factrl(n))/(Factrl(m)*Factrl(n-m));
write('Число сочетаний= ',C);
end.

Почему в этой строчке у меня ошибка?

Pascal

1	C:=(Factrl(n))/(Factrl(m)*Factrl(n-m));

Нельзя преобразовать real к integer пишет. Можно конечно написать везде real и будет работать. Но всё же почему такая ошибка?

@Puporev · 10.02.2016, 07:34

Pascal

1
2
3

var C:real;
.....................
write('Число сочетаний= ',C:0:0);

и что за ерунда?

Pascal

if n = 0 then
 Factrl:= 1;
 if n = 1 then
 Factrl:= 1;

@jestero · 10.02.2016, 08:39 **[ТС]**

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

и что за ерунда?

Условия при которых факториал равен 1.

Добавлено через 4 минуты

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

var C:real;
.....................
write('Число сочетаний= ',C:0:0);

Даже если так пишу:

Pascal

function Fac(n:integer):longint;
begin
if n<2 then Fac:=1
else fac:=n*fac(n-1);
end;
var
C,n,m:integer;
begin
repeat
writeln('Ведите n m,  n>=m ');
readln(n,m);
until n>=m;
C:=fac(n)/fac(m)*fac(n-m);
write('Число сочетаний= ',C:0:0);
end.

Коприлятор выдаёт ошибку к той же строчке: "Нельзя преобразовать real к integer". Что же тут является типом real?

@Puporev · 10.02.2016, 08:59

Совсем плохой что ли? Я же написал

Pascal

1	var C:real;

ты один хрен

Pascal

1 2	var C,n,m:integer;

@jestero 11 / 11 / 2 Регистрация: 17.02.2014 Сообщений: 947
		1
	Программирование рекурсивных процедур для вычисления выражения 09.02.2016, 16:08. Показов 1781. Ответов 11 Метки нет (Все метки) Вычислить значение: $https://www.cyberforum.ru/cgi-bin/latex.cgi?{c}_{n}^{m}=\frac{n!}{m!(n-m)!}$ Здесь как я понял нужна процедура с параметрами n и m. Но не знаю как саму рекурсию организовать. Помогите пожалуйста. 0

@jestero 11 / 11 / 2 Регистрация: 17.02.2014 Сообщений: 947
	10.02.2016, 06:15 [ТС]	3
	Сообщение от Puporev C:=C(n-1,m-1)+C(n-1,m); А как здесь всё вычисляется, что то не пойму? Хотя всё правильно работает. Тут же только из арифметических действий сложение, а например такое выражение не понятно как вычисляется в программе C(n-1,m-1) 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	10.02.2016, 06:51	4
	Здесь для написания рекурсивной функции определения числа сочетаний умные люди ( не я) не используют факториалы, а формулу C_n^k = C_{n - 1}^{k - 1} + _{Cn - 1}^k (при 0 < k < n). При этом пишут Действительно, выбрать из n предметов k можно C_n^k способами. Пометим один из данных n предметов. Тогда все выборки можно разбить на две группы: в которые входит помеченный предмет (их будет C_{n - 1}^{k - 1}) и не содержащие помеченного предмета (таких выборок будет C_{n - 1}^k)). Добавив к этой формуле краевые значения: C_nⁿ = C_n⁰ = 1 (выбрать все предметы или не выбрать ни одного предмета можно единственным способом), можно написать рекурсивную функцию вычисления числа сочетаний: Можно конечно и написать рекурсивную функцию факториала и считать по приведенной формуле, но эта функция лучше (более эффективна). Хотя еще лучше считать число сочетаний и без рекурсии и без факториалов. 0

@jestero 11 / 11 / 2 Регистрация: 17.02.2014 Сообщений: 947
	10.02.2016, 06:54 [ТС]	5
	То есть в данном случае мы сначала проходим вниз до того момента, когда начинает выполняться это условие: if (m=0)or(m=n) then C:=1. И потом поднимаемся вверх считая все значения на основании предыдущих. Правильно я понимаю? 0

@Puporev Почетный модератор 64300 / 47595 / 32743 Регистрация: 18.05.2008 Сообщений: 115,181
	10.02.2016, 06:54	6
	Да. 0

Программирование рекурсивных процедур для вычисления выражения

Решение