Tutorial Exercises: Set 6

---

Click on the links above

Exercise 1

Write a C program that reads n floating-point numbers from the user, stores them in an array, and finally computes the standard deviation of the input values.

Solution 1

   #include <stdio.h>
   #include <stdlib.h>
   #include <math.h>

   #define MAXSIZE 1024

   int main ()
   {
      unsigned int i, n;
      double A[MAXSIZE], s1, s2;

      /* Read from the user */
      printf("n = ");
      scanf("%u", &n);
      for (i=0; i<n; ++i) {
         printf("A[%u] = ", i);
         scanf("%lf", &A[i]);
      }

      /* Compute the standard deviation */
      s1 = s2 = 0;
      for (i=0; i<n; ++i) {
         s1 += A[i];
         s2 += A[i] * A[i];
      }
      printf("Standard deviation = %lf\n", sqrt((s2/n)-(s1/n)*(s1/n)));

      exit(0);
   }

Exercise 2

Write a C function that takes an array A of n integers and returns the number of inversions in A. An inversion in A is a pair of indices i and j such that i < j but A[i] > A[j]. You may assume that the elements of A are distinct.

Solution 2

   unsigned int countInversions ( int A[] , unsigned int n )
   {
      unsigned int cnt, i, j;

      cnt = 0;
      for (i=0; i<n; ++i)
         for (j = i+1; j < n; ++j)
            if (A[i] > A[j]) ++cnt;
      return cnt;
   }

Exercise 3

Write a function that accepts a character string as input and converts the string to upper case. For example, the upper case of the string "I.I.T. Kharagpur" is "I.I.T. KHARAGPUR". Do not use any string library functions.

Solution 3

   void makeuc ( char A[] )
   {
      int l, i;

      l = strlen(A);
      for (i=0; i<l; ++i)
         if ((A[i] >= 'a') && (A[i] <= 'z')) A[i] += 'A' - 'a';
   }

Exercise 4

Recall that Catalan numbers C_n are defined recursively as follows:

   C₀ = 1
   C_n = C₀C_n-1 + C₁C_n-2 + C₂C_n-3 + ... + C_n-1C₀ for n >= 1.

Write a non-recursive function that, upon input n, returns C_n.

Solution 4

   unsigned long int Catalan ( unsigned long int n )
   {
      unsigned long int i, j, C[MAXSIZE];

      C[0] = 1;
      for (i=1; i<n; ++i) {
         C[i] = 0;
         for (j=0; j<i; ++j) C[i] += C[j] * C[i-j-1];
      }
      return C[n];
   }

Exercise 5

You are sitting at the origin (0,0) of a two-dimensional plane. Your task is to reach the point (m,n) in the plane, where m and n are positive integers. At each step, you are allowed to move by one unit of length either to the right or to the top. Write a recursive function to print all the ways in which you can reach (m,n). Also write a main() function which reads m and n from the user and invokes the recursive function.

Solution 5

We use an auxiliary array path[] to store the current path discovered by the recursive algorithm. We pass this array to the recursive function, and print the array as soon as the path reaches the destination (m,n). We use a character array for path, where '-' indicates a rightward movement and '|' indicates an upward movement.

Suppose that you are sitting at the position (i,j). Consider all the possibilities one by one.

If i > m or j > n, then you can never reach the destination by rightward and upward movements only, so terminate recursion without printing anything.

If i = m and j = n, then you have reached the destination. Print the currently discovered path, and terminate recursion.

If i <= m and j <= n (with at most one equality), then you have to make further moves to reach the destination. The first i + j locations of the array path[] stores the movement steps made so far. Now, you have two choices: '-' and '|'. First, choose '-' (right movement), store this choice in the (i + j + 1)-st location (that is, (i + j)-th index) of path[], and make a recursive call. After the recursive call returns, set path[i + j] to '|' (upward movement) , and make a second recursive call. After this second call returns, there is nothing else to do. So, return from the function.

The following code snippet implements these ideas.

   void prnpaths ( int i , int j , int m , int n , char path[] )
   {
      if ((i > m) || (j > n)) return;
      if ((i == m) && (j == n)) {
         printf("%s\n", path);
         return;
      }
      path[i+j] = '-'; prnpaths(i+1,j,m,n,path);
      path[i+j] = '|'; prnpaths(i,j+1,m,n,path);
   }

   int main ()
   {
      int m, n;
      char path[MAXLEN];

      printf("Enter m: "); scanf("%d", &m);
      printf("Enter n: "); scanf("%d", &n);
      path[m+n] = '\0';
      prnpaths(0,0,m,n,path);
      exit(0);
   }

Here is a program that makes a two-dimensional printing of all the paths. This program uses a two-dimensional array.

Brain-teaser

Consider the following function.

   void f ( unsigned int m , unsigned int n , unsigned int A[] , unsigned int k )
   {
      unsigned int i;

      if (m > n) { f(n,m,A,k); return; }
      printf("{"); for (i=0; i<k; ++i) printf("%s%u", (i)?",":"", A[i]); printf("}\n");
      while (++m <= n) { A[k] = m; f(m,n,A,k+1); }
   }

What does the call f(0,n,A,0) print?

What does the call f(m,n,A,0) print?

---

Back  |  Home