Frog (C#) : Algorithm

A frog only moves forward, but it can move in steps 1 inch long or in jumps 2 inches long. A frog can cover the same distance using different combinations of steps and jumps.

Write a function that calculates the number of different combinations a frog can use to cover a given distance.

For example, a distance of 3 inches can be covered in three ways: step-step-step, step-jump, and jump-step.

Code Snippet

1. using System;
2.  
3. public class Frog
4. {
5.     public static int NumberOfWays(int n)
6.     {
7.         throw new NotImplementedException("Waiting to be implemented.");
8.     }
9.  
10.     public static void Main(String[] args)
11.     {
12.         Console.WriteLine(NumberOfWays(3));
13.     }
14. }

 

Solved Code Snippet

1. using System;
2. using System.Collections.Generic;
3.  
4.  
5. public class Frog
6. {
7.  
8.     public static void Main(String[] args)
9.     {
10.         Console.WriteLine(NumberOfWays(3));
11.     }
12.  
13.     public static int NumberOfWays(int n)
14.     {
15.         return NoOfPermutaions(NoOfCombinations(n));
16.     }
17.  
18.     private static List<Tuple<int, int>> NoOfCombinations(int distance)
19.     {
20.         List<Tuple<int, int>> lst = new List<Tuple<int, int>>();
21.         for (int i = 0; i <= distance; i++)
22.             for (int j = 0; j <= distance; j++)
23.             {
24.                 if ((i * 1 + j * 2) == distance) lst.Add(new Tuple<int, int>(i, j));
25.             }
26.         return lst;
27.     }
28.  
29.     private static int NoOfPermutaions(List<Tuple<int, int>> lst)
30.     {
31.         int Sum = 0;
32.         foreach (Tuple<int, int> itm in lst)
33.         {
34.             Sum += Convert.ToInt32(Factorial(itm.Item1 + itm.Item2) / Factorial(itm.Item1) / Factorial(itm.Item2)); //Formula: C(n,r)=n!/r!;
35.         }
36.  
37.         return Sum;
38.     }
39.  
40.     private static double Factorial(double num)
41.     {
42.         if (num <= 1)
43.             return 1;
44.         return num * Factorial(num - 1);
45.     }
46. }