Good day. Parse the puzzle.

#include<iostream> using namespace std; float fact(float q){ return !q ? 1: q*fact(q-1);} float funct(float n, float m){ return (fact(n)*fact(m))/fact(n+m); } int main ( ){ setlocale(LC_ALL,"Russian"); float n,m; cout<<"Введите n"<<endl; cin>>n; cout<<"Введите m"<<endl; cin>>m; cout<<"Результат"<<funct(n,m); system("pause"); return 0; }

Question about the program. The floating point function is called, the recursion goes on, but what is it for?

Next comes the description of the desired function. Here's how to int main is not quite clear what is happening Further it is clear: I enter n and m, I call the funct function, I transfer n and m to it.

  • 3
    Doesn't the word "factorial" mean anything? - Veikedo
  • Mathematically, I understand what factorial is .. but in this context it is not very clear - amora
  • one
    @amora, everyone knows that the factorial of the number n (n> 0) is n! = 1 * 2 * 3 * ... * n = n * (n-1)! Look at the function, draw conclusions - paulgri
  • one
    @amora, generally speaking, the implementation of factorial is very lame. What will happen with negative q values? Or not for the whole? For example, 0.000001 is almost zero, but the problem is obvious. - paulgri
  • 2
    Generally speaking, when speaking of factorial, factorial of a whole natural number is meant. At the same time (quite natural for English-language mathematics) 0! It is assumed to be 1. Therefore, the function func(float) from the question looks strange. - I rummaged a bit in Google and found that Factorial of a real number also exists, which is calculated by the formula: X! = N! * ((N + 1) ** d) N - the integer part of the number X d - the mantissa of the number X @amora, in principle, what is needed for your task? - avp

2 answers 2

@amora , I’ll try to describe the fact() function in more detail. By the way, since the task states that n and m are nonnegative integers , we will also make a function for them, not for float .

To start. Record:

  unsigned int fact (unsigned int q) { return !q ? 1 : q * fact(q - 1); }

it's just an abbreviated form like this:

  unsigned int fact (unsigned int q) { if (q == 0) // проверка, соответствующая !q return 1; // это часть перед ":" в тернарном операторе в return !q ? 1 : ... else return q * fact(q - 1); // естественно, правая, т.е. после ":" часть }

more familiar (yet for you) recording of the same algorithm.

I think that the algorithm itself after such a record n! :

  n! = n * (n - 1) * (n - 2) * ... * 2 * 1 * 1

(in fact, I just flipped the entry from the @paulgri comment) obvious.

Now let's look at a short example of what happens during recursion. Time flows from left to right, and the stack of function activations grows from top to bottom. Variables I replace them with values.

 main: func(3) оп-па результат 3! == 6 func: 3 * func(2) return 3 * 2 func: 2 * func(1) return 2 * 1 func: 1 * func(0) return 1 * 1 func: return 1

This is how the recursive version of the factorial function works.

It is clear that already with a small value of n overflow will arise in the course of the calculations. The result of the next multiplication will not fit into 32 bits of the unsigned int type. The delay to the unsigned long long type (64 bits) returned by the function will be somewhat delayed. Those. Here is her view:

 unsigned long long fact(unsigned int q) { return q ? q * fact( q - 1) : 1; }

somewhat more satisfy our curiosity.

(replacing! q? on q? doesn’t change anything by itself, it’s just that IMHO looks prettier).

  • @amora, no more questions about this? - avp
  • Thank you for the detailed explanation) So far the best I've seen) - amora

In addition to the @avp : answer, the method by which C_n^k calculated in your example is terribly inefficient, and most likely will lead to overflow even in cases where the result fits in an int .

Much better, faster, easier and more efficient to calculate using the recurrent formula:

 C_n^k = C_n^{nk} (*) C_n^0 = 1 (**) C_n^k/C_n^{k-1} = { n! / (k!(nk)!) } / { n! / ((k-1)!(n-k+1)!)} = = { (k-1)! / (k!) } * { (n-k+1)!/(nk)! } = = (n-k+1)/k (***)

That is, it turns out that:

 if (k > n/2) k = n - k; // воспользовались (*) Cni = 1; // инвариант цикла: Cni == C_n^i // воспользовались (**) for (int i = 1; i <= k; i++) Cni = Cni * (n - i + 1) / i; // воспользовались (***) return Cni;