Софтуерно Инженерство
Loading...
James242 avatar James242 0 Точки

C# Book chapter 6 exercise 6 - Dividing by 2 factorials

Hello!  I do not speak Bulgarian, but I have finished reading the Fundamentals of Computer Programming with C# book, am going back over some of the exercises I did not initally complete, and am hoping this forum might be useful to me even though I don't speak Bulgarian. I know a lot of you must speak English since much of the course material is in English.  I just noticed the language toggle at the bottom of the website's page.

Chapter 6 exercise 6 asks us to "write a program that calculates N!/K! for given N and K (1<K<N).

I wrote a solution to this problem with a calculateFactorial function that is used to calculate N! and then K!, after which those values are divided.

    static void Main(string[] args)
        {
            Console.WriteLine("Enter the first digit to muliply");
            BigInteger n = BigInteger.Parse(Console.ReadLine());

            Console.WriteLine("Enter the second digit to muliply");
            BigInteger k = BigInteger.Parse(Console.ReadLine());
            if (1 > k || k > n)
            {
                Console.WriteLine("second number must be larger than 1 and smaller than first number.");
            }
            else
            {
                BigInteger nFactorial = calculateFactorial(n);
                BigInteger kFactorial = calculateFactorial(k);

                Console.WriteLine("n! = " + nFactorial);
                Console.WriteLine("k! = " + kFactorial);

                BigInteger output = nFactorial / kFactorial;

                Console.WriteLine("{0} / {1} = {2}", nFactorial, kFactorial, output);
            }

           

            Console.ReadLine();

        }

        static BigInteger calculateFactorial(BigInteger x)
        {

            BigInteger factorial = 1;
            do
            {
                factorial *= x;
                x--;

            }
            while (x > 0);
            return factorial;
        }
    }



However, I'm looking at the word .doc with the solutions and this provided solution is more elegant since it only caluclates k+1 * each n and removes the division step.

 for (int i = k+1; i <= n; i++)
                {
                    result *= i;
                }



I don't quite understand the mathematical logic on why doing the above caluclation is the same as N!/K!

Any insight on this topic would be very much appreciated!

James

Тагове:
Slavi007 avatar Slavi007 0 Точки

Hello, James.

I will try to show the mathematic logic on the problem you have.

If we examine your code which is absolutely correct we can see that if k is 2 and n is 4 the code methodically calculates n!/k! 

For example (using your code): we type n= 4 and k=2, then the code calculates n! = 24 and k! = 2 and then return n!/k! = 12 and that is correct.

The second solution is also correct and it is also quite faster to be compiled. 

For example (using the second solution) we type n=4 and k=2 then the for loop starts and here comes the magic. i starts from k+1 which is 3 in this example and i is added to result = result*i; Then i = 4 and it is again added to result which is now 3 and now becomes 3*4 =12; 

You can try with other numbers but the result will be always n!/k!

Hope to help you with this.

Regards, Slavi

 

0
James242 avatar James242 0 Точки

Love it!  Thanks so much for explaining this to me in English!  Nice people in this forum.

0