MACHINE PROBLEMS for IT14

February 21, 2012

TO ALL 2^nd YEAR BSIT STUDENTS                                                                  

IT 14 - Programming Exercises in Recursion

1.      Write a recursive method that takes as a parameter a nonnegative integer and generates the following pattern of stars. If the nonnegative integer is 4, then the pattern generated is:

****

***

**

*

*

**

***

****

            Also, write a program that prompts the user to enter the number of lines in the pattern and uses          the recursive method to generate the pattern. For example, specifying 4         as the number of lines            generates the above pattern.

2.      Write a recursive method that finds and returns the sum of the elements of an int array. Also, write a program to test your method.

3.      A palindrome is a string that reads the same both forwards and backwards. For example the string “madam” is a palindrome. Write a program that uses a recursive method to check whether a string is a palindrome. Your program must contain a value-returning recursive method that returns true if the string is a palindrome, and false otherwise. Use the appropriate parameters.

4.      Write a program that uses a recursive method to print a string backwards. Your program must contain a recursive method that prints the string backwards. Use the appropriate parameters.

5.      Write a recursive method, reverseDigits, which takes an integer as a parameter and returns the number with the digits reversed. Also, write a program to test your method.

6.      Write a recursive method, power, which takes as parameters two integers x and y such that x is nonzero and returns x^y. You can use the following recursive definition to calculate x^y. If y≥ 0,

                                    1                                  if y=0

power(x,y) =                         x                                  if y=1

                                    x*power(x,y-1)            if y>1

If y<0,

Also, write a program to test your method.

7.      (Greatest Common Divisor) Given two integers x and y, the following recursive definition determines the greatest common divisor of x and y, written gcd(x,y):

 

                                    x                      if y = 0

            gcd(x, y) =      

                                    gcd(y,x%y)       if y≠ 0

            Note: In this definition, % is the mod operator.

            Write a recursive method, gcd, which takes as parameters two integers and returns the greatest common divisor of the numbers. Also, write a program to test your method.

8.      (Converting a Number from Binary to Decimal) The language of a computer, called machine language, is a sequence of 0s and 1s. When you press the key A on the keyboard, 01000001 is stored in the computer. Also, the collating sequence of A in the Unicode character set is 65. In fact, the binary representation of A is 01000001 and the decimal representation of A is 65.

The numbering system we use is called the decimal system, or base 10 system. The numbering system that the computer uses is called the binary system, or base 2 system. The purpose of this is to write a program to convert a number from base 2 to base 10.

To convert a number from base 2 to base 10, we first find the weight of each bit in the binary number. The weight of each bit in the binary number is assigned from right to left. The weight of the rightmost bit is 0. The weight of the bit immediately to the left of the rightmost bit is 1; the weight of the bit immediately to the left of it is 2, and so on. Consider the binary number 1001101. The weight of each bit is as follows:

weight             6          5          4          3          2          1          0

                        1          0          0          1          1          0          1

We use the weight of each bit to find the equivalent decimal number. For each bit, we multiply the bit by 2 to the power of its weight, and then we add all of the numbers. For the above binary number, the equivalent decimal number is

1 * 2⁶ + 0 * 2⁵ + 0 * 2⁴  + 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰

= 64 + 0 + 0 + 8 + 4 + 0 + 1

= 77

To write a program that converts a binary number into its equivalent decimal number, we note two things: (1) the weight of each bit in the binary number must be known, and (2) the weight is assigned from right to left. Because we do not know in advance how many bits are in the binary number, we must process the bits from right to left. After processing a bit, we can add 1 to its weight, giving the weight of the bit immediately to the left to it. Also, each bit must be extracted from the binary number and multiplied by 2 to the power of its weight. To extract a bit, you can use the mod operator. Write a method that converts a binary number into an equivalent decimal number.

Moreover, write a program and test your method for the following values: 11000101, 10101010, 11111111, 10000000, and 1111100000.

9.      Two more number systems, octal (base 8) and hexadecimal (base 16), are of interest to computer scientists. In fact, in Java, you can instruct the computer to store a number in octal or hexadecimal.

            The digits in the octal umber system are 0, 1, 2, 3, 4, 5, 6, and 7. The digits in the             hexadecimal number system are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, and F. So A in     hexadecimal is 10 in decimal, B in hexadecimal is 11 in decimal, and so on.

            The algorithm to convert a positive decimal number into an equivalent number in octal (or hexadecimal) is the same for binary numbers. Here we divide the decimal number by    8 (for octal) and by 16 (for hexadecimal). Suppose a_b represents the number a to the   base b. For example, 75₁₀ means 75 to the base 10 (that is, decimal), and 83₁₆ means 83      to the base 16 (that is, hexadecimal). Then

            753₁₀ = 1361₈

            753₁₀ = 2F1₁₆

            The method of converting a decimal number to base 2, or 8, or 16 can be extended to     any arbitrary base. Suppose you want to convert a decimal number n into an equivalent          number in base b, where b is between 2 and 36, you then divide the decimal number n         by b as in the algorithm for converting decimal to binary.

            Note that the digits in, say, base 20 are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F, G, H, I,    and J.

            Write a program that uses a recursive method to convert a number in decimal to a given           base b, where b is between 2 and 36. Your program should prompt the user to enter the number in decimal and in the desired base.

            Test your program on the following data:

            9098 and base 20

            692 and base 2

            753 and base 16

Note:  

·         This programming exercise must be done individually.

·         You are required to solve at least 5 problems among the given problems herein.The more problems correctly solved, the higher points you can acquire.

·         Write the problems, the corresponding recursive definitions (define the base case(s) and the recursive case of the algorithm) and the source code for each problem you have chosen on a long bond paper.

·         Secure a soft copy of your program for presentation purposes.

·         Chosen student must present his/her solutions during class lecture and/or laboratory time.

·         Students having the same solutions in a problem shall suffer a corresponding deduction.

Prepared by:

LEMUEL L. APA

Instructor

IT13: exer2(my answer) JAVA language

Name: Janer, Jesson L.

Section: Set A

Time: TF(1:00-2:30)  

Exercise: 1

Code:

public class exercise2{

      public static void main (String[] args) {

           

            String msg = "Hello World, This is a test ! :)";

            string_classes.display_msg (5,msg);

System.out.println ("\nThe reverse string is: " +string_classes.reverse_msg (msg));

System.out.println ("\nThe no of vowels in a string is: "  +string_classes.no_of_vowels (msg));

System.out.println ("\nThe no of consonants in a string is:" +string_classes.no_of_consonants(msg));

System.out.println ("\nThe no of special characters in a string is: "  +string_classes.no_of_special_chars (msg));

System.out.println ("\nThe no of characters occurences:  ");

string_classes.char_occurences (msg);

      }

}

public class string_classes {

            public static void display_msg(int x, String msg){

                  for(int i = 0; i < x ; i++){

                        System.out.println ("\n" +msg);

                        }

                  }

            public static String reverse_msg(String msg){

                  String str_reverse = " ";

                  //Enter your solution here.....

                 str_reverse = new StringBuffer(msg).reverse().toString();

                 return str_reverse;

                  }

            public static int no_of_vowels(String msg){

                  int nvowels = 0;

                  //Enter your solution here.....

                  String tester="aeiou";

             for(int a=0;a<msg.length();a++){

                   for(int b=0;b<tester.length();b++){

                     if((msg.toLowerCase()).charAt(a)==(tester.charAt(b)))nvowels++;

                              }

                }

                     return nvowels;

                  }

            public static int no_of_consonants(String msg){

                  int nconsonants = 0;

                  //Enter your solution here.....

              String tester="bcdfghjklmnpqrstvwxyz";

              for(int a=0;a<msg.length();a++){

                  for(int b=0;b<tester.length();b++){

                   if((msg.toLowerCase()).charAt(a)==(tester.charAt(b)))nconsonants++;

                    }

                }

                        return nconsonants;

                  }

            public static int no_of_special_chars(String msg){

                  int sp_chars = 0;

                  //Enter your solution here.....

                  String tester="~`!@#$%^&*()-_+={}[];:',.></?|";

                for(int a=0;a<msg.length();a++){

                   for(int b=0;b<tester.length();b++){

                     if((msg.toLowerCase()).charAt(a)==(tester.charAt(b)))sp_chars++;

                              }

                   }

                        return sp_chars;

                  }

            public static void char_occurences(String msg){

            //Enter your code here...

            /* Sample output: Hello World, This is a test ! :

             *H - 2, e - 2, l - 3, o - 2, W - 1, r - 1 d - 1,

             *T - 3, i - 2, s - 3, a - 1

             *

             */

    String tester="abcdefghijklmnopqrstuvwxyz";

    boolean t=true,th=true;

    int no=0;

    String char_passed=" ";

          

    System.out.println(msg);

          

    for(int a=0;a<msg.length();a++){

          

            for(int b=0;b<tester.length();b++){

           if(msg.toLowerCase().charAt(a)==tester.charAt(b)){

                 t=true;

                 b=27;

                }else{

                 t=false;

                }

           }

          

            if(t==true){

        for(int c=0;c<msg.length();c++){

           if(msg.toLowerCase().charAt(a)==msg.toLowerCase().charAt(c))no++;

             }

                    

        for(int d=0;d<char_passed.length();d++){

           if(msg.toLowerCase().charAt(a)==char_passed.charAt(d)){

                th=false;

                d=100;

                }

           }

                  

           if(th==true){

               System.out.println(msg.charAt(a)+ "-"+no);

               char_passed=char_passed+msg.toLowerCase().charAt(a);

                   }

          }

                    t=true;

                    th=true;

                    no=0;

     }

       }

}

IT13: exer1(my answer) JAVA language

Name: Janer, Jesson L.

Section: Set A

Time: TF(1:00-2:30)  

Exercise: 1

Code:

public class Exercise1{

public static void main (String[] args) {

       int x[] = {23, 6, 47, 35, 2, 14};

       num_classes.display_num (x);

       System.out.println ("\nSum of all integers: " +num_classes.sum_all(x));

       System.out.println ("\nAverage of a given integers: " +num_classes.get_ave (x));

       System.out.println ("\nLargest integer: " +num_classes.get_max (x));

       System.out.println ("\nSmallest integer: " +num_classes.get_min (x));

       System.out.println ("\nNumber of ODD integers: " +num_classes.get_no_of_odd (x));

       System.out.println ("\nNumber of EVEN integers: " +num_classes.get_no_of_even(x))

}

}

public class num_classes {

      public static void display_num(int x[]){

            for(int i=0; i < x.length; i++)

                  System.out.println (x[i]);

            }

      public static int sum_all(int x[]){

            int sum = 0;

            // type your solution here

            for(int i=0; i < x.length; i++){

            sum = sum + x[i];

                  }

            return sum;

            }

      public static int get_ave(int x[]){

            int ave = 0;

            // type your solution here

            int sum=0;

            for(int i=0; i < x.length; i++){

           sum=sum+x[i];

            }

           ave=sum/x.length;

           return ave;

            }

      public static int get_max(int x[]){

            int max = 0;

            // type your solution here

            for(int i=0; i < x.length; i++){

            if(x[i]>max)max=x[i];

                  }

                  return max;

            }

      public static int get_min(int x[]){

            int min = 0;

            // type your solution here

            for(int i=0; i < x.length; i++){

                  if(i==0)min=x[1];

                  if(x[i]<min)min=x[i];

                  }

                  return min;

            }

      public static int get_no_of_odd(int x[]){

            int n_odd = 0;

            // type your solution here

            for(int i=0; i < x.length; i++){

            if(x[i]%2!=0)n_odd++;

                  }

                  return n_odd;

            }

      public static int get_no_of_even(int x[]){

            int n_even = 0;

            // type your solution here

            for(int i=0; i < x.length; i++){

                if(x[i]%2==0)n_even++;

                  }

                  return n_even;

            }

}