Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 577
  • Last Modified:

Compare function in recursive mode

I have wrote complete program. But, stuck in compare function in recursive mode.
Not getting how to maintain flags and return.

Need help.


Problem statement is as :
Write a program that finds the kth smallest Number from a list of any base-n numbers (for
any n up to a fixed maximum value, maxN). The definition of the ADT called Number is
the same as that defined in Lab-1. For ease of implementation, assume that each digit is
represented by a character. A separate lookup table needs to be created for storing the
symbols (character) corresponding to the various digit values.
The program must take two command-line parameters:
the first parameter is the name of a file containing the sequence of characters to
be used for the digit values from 0 to maxN-1, and
the second parameter is the name of a file containing N Numbers.
The sequence of characters corresponding to digit values 0 to maxN-1 is given in the first
line of the first input file, separated by spaces. Note that maxN to be used in the particular
instance of execution is calculated by the number of entries in the first line. Only
alphanumeric characters can be used for representing digits in the number system. (Note
that the total number of alphanumeric characters is limited to 62.)
Consider this sample file:
File1:
b i g s o u n d
By reading this you should infer that maxN is 8 and the value of symbol o is 4 and that of
symbol n is 6 and so on.
The second input file contains a list of N Numbers, with one Number in each line.
Consider the following sample (second) file: containing the numbers 59 in base-6, 36 in
base-8, 10 in base-2, 7 in base-3, 576 in base-4, 9 in base-2. Representation of the first
number in File2 is shown below.
F ile2:

6 isu
8 go
2 ibib
3 gi
4 gibbs
2 ibbi
Type definitions:
The definition for lookup table named Base, containing a list of symbols indexed by
digit values. Note that since the base is immutable (i.e. won’t change), the list can
be allocated at time of definition.
The type definition for a Number, containing the fields: the base of the number, a
linked list of digits each of which is a character, and other field that may be useful.
The type definition for an enumerated type called Order, that can have either
GREATER, LESSER or EQUAL.
Design of Base ADT with the following operations
(a) int initializeBase(FILE *basefile) : reads the file containing the
characters corresponding to each digit, populates the lookup table and returns the
maximum base supported in the current execution. Note that to use the number
system; this function has to be called first, before any other function.
(b) int lookup(char c) : looks-up the character in the Base lookup table and
returns the value associated with the character.
Design of Number ADT with the following operations:
(a) Number createNumber(char *number_format): takes the number
format as a string containing the base of the number, followed by a space, followed
by the number using the custom characters(Most Significant Digit first). This
function then creates a Number using the values corresponding to the digits and
returns it.
(b) void printNumber(Number n): prints the Number in the base stored in
the system.
(c) Number convert(Number n, int to_base): converts the number n to a
number of base to_base, and returns it.
(d) Order compare(Number n1, Number n2): This function is used to
compare two Numbers of any valid base. This function returns GREATER if n1 >
n2; LESSER if n1 < n2; or EQUAL if n1 = n2. This function must be written using
recursion.
(e) int partition(Number list[], int start, int end): This
function partitions the list[start...end] into 2 sublists, such that all
Numbers in left sublist is less than a chosen pivot and all the Numbers in the right
sublist are greater than the chosen pivot. Here, the pivot element is chosen as
median of the five elements list[start], list[(start+end)/4],
list[(start+end)/4*3], list[(start+end)/2], and list[end].
This function uses compare described above for comparison.
(f) Number quickSelect(Number list[], int size, int k): This
functions returns the kth smallest Number in the list, using an iterative version of
quickselect. This function uses partition described above for partitioning about
a pivot element,
0
prabhatia
Asked:
prabhatia
  • 2
1 Solution
 
TommySzalapskiCommented:
Well, since they are different bases you need to carry the difference so far around with you. Something like this (C-like syntax)

bool compare(Number n1, Number n2) //returns boolean
{
  return compareH(Number n1, Number n2, 0);
}

bool compareH(Number n1, Number n2, int leftGreater) //int for decimal integer
{
  int difference = valueOfFirstDigit(n1) - valueOfFirstDigit(n2);
  leftGreater = leftGreater + difference; //So you always maintain the total difference

  if (n1 and n2 are 0) //If they have both hit 0, then leftGreater now contains the difference
  {
    return leftGreater;
  }
  else
  {
    return compareH( stripFirstDigit(n1), stripFirstDigit(n2), leftGreater);
    //Note, if one has run out of digits, stripFirstDigit should leave it at 0.
  }
}

Open in new window


There are probably ways to improve this, but this gives a general idea.
0
 
TommySzalapskiCommented:
Giving a C grade without explaining why is generally considered impolite on Experts Exchange. Also, you never said what you didn't like about the solution or gave a chance for the experts to improve the answer to give you what you wanted. If the solution gave you what you needed, then give an A grade; if it didn't, comment and the experts will generally get you what you need.

Thanks.
Tommy
0

Featured Post

Keep up with what's happening at Experts Exchange!

Sign up to receive Decoded, a new monthly digest with product updates, feature release info, continuing education opportunities, and more.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now