Thread: Assignment HELP!!

  1. #1
    Registered User
    Join Date
    Nov 2008
    Posts
    31

    Assignment HELP!!

    I need help with this assignment, any takers? I need to fill in the functions and make it work

    Computer Science

    The Problem
    The unsigned int type in C requires 4 bytes of memory storage. With 4 bytes we can store integers as large as 232-1; but what if we need bigger integers, for example ones having hundreds of digits? If we want to do arithmetic with such very large numbers we cannot simply use the unsigned data type. One way of dealing with this is to use a different storage structure for integers, such as an array of digits. If we represent an integer as an array of digits, where each digit is stored in a different array index. Since the integers are allowed to be as large as we like, a dynamically-sized array will prevent the possibility of overflows in representation. However we need new functions to add, subtract, compare, read and write these very large integers.

    175—way to store in array index 0=5 1=7 2=1
    Doing this all major operations goes from least sig digit to most significant digit.S
    Write several functioms

    Write a program that will manipulate such arbitrarily large integers. Each integer should be represented as an array of digits, where the least significant digit is stored in index 0. Your program should be able to read in a string of digits and create a struct that stores the big integer.

    Your program should store each decimal digit (0-9) in a separate array element. In order to perform addition and subtraction more easily, it is better to store the digits in the array in the reverse order. For instance, the value 1234567890 would be stored as:

    index 0 1 2 3 4 5 6 7 8 9
    array 0 9 8 7 6 5 4 3 2 1

    Note: Although this seems counter-intuitive, it makes the code slightly easier, because in all standard mathematical operations, we start with the least significant digits. It also makes sense that the digit at the place 10i is stored in index i.

    Your program should include the following functions:

    • a function that will read in an integer from the keyboard-read into string and convert digit by digit
    • a function that will print an integer.
    • a function that will add two integers and return the result.
    • a function that compares two integers and returns -1 if the first is less than the second, 0 if they are equal, and 1 if the first is greater than the second.
    • a function that will subtract one integer from the other and return the result. Since you’ll be dealing with positive integers only, the result should be a positive number. To ensure that the result is integer you should subtract the smaller number from the larger one. If they are equal, 0 should be returned.this will always return a non negative result. Return pos6 not neg 6 . there are prototypes.
    Input/Output Specification
    Your program should allow the user to do two things:

    1) Add two big integers
    2) Subtract to big integers

    Instead of getting input from the user, you read in input from a file, "bigint.txt". (This will expedite the grading process.)

    The input file format is as follows:

    The first line will contain a single positive integer, n, representing the number of operations to carry out. The next n lines will contain one problem each. Each line will have three integers separated by white space. The first integer on each of these lines is guaranteed to either be 1 or 2, indicating addition and subtraction, respectively. The next two integers on the line will be the two operands for the problem. You may assume that these two integers are non-negative, are written with no leading zeros (unless the number itself is 0) and that the number of digits in either of the numbers will never exceed 200.

    You should generate your output to the screen. In particular, you should generate one line of output per each input case. Your output should fit one of the two following formats:

    X + Y = Z
    X – Y = Z

    corresponding to which option was chosen. For the first option, always print the first operand first. For the second option, always print the larger of the two operands first. If the two operands are equal, the same number is printed both times.

    Implementation Restrictions
    You must use the following struct:

    Code:
    struct integer {
    	int* digits;
    	int size;
    }
    Whenever you store or return a big integer, always make sure not to return it with any leading zeros. Namely, make sure that the value stored in index size-1 is NOT zero. The only exception to this rule is if 0 is being stored. 0 should be stored in an array of size 1.


    Here are the prototypes of the functions for you to write:

    //Preconditions: the first parameter is string that stores
    // only contains digits, doesn't start with
    // 0, and is 200 or fewer characters long.
    //Postconditions: The function will read the digits of the
    // large integer character by character,
    // convert them into integers and return a
    // pointer to the appropriate struct integer.
    struct integer* read_integer(char* stringInt);

    //Preconditions: p is a pointer to a big integer.
    //Postconditions: The big integer pointed to by p is
    // printed out.
    void print(struct integer *p);

    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that
    // stores the sum of the integers pointed to
    // by p and q and a pointer to it is
    // returned.
    struct integer* add(struct integer *p, struct integer *q);

    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that
    // stores the absolute value of the
    // difference between the two and a pointer
    // to this is returned.
    struct integer* subtract(struct integer *p, struct integer *q);

    //Preconditions: Both parameters of the function are
    // pointers to struct integer.
    //Postconditions: The function compares the digits of two
    // numbers and returns:
    // -1 if the first number is smaller than the second,
    // 0 if the first number is equal to the second number,
    // 1 if the first number is greater than the second.
    int compare(struct integer *p, struct integer *q);

    Sample Input File
    3
    1 8888888888 2222222222 take8888.. plus 222..
    2 9999999999 10000000000
    2 10000000000 9999999999

    Corresponding Output
    8888888888 + 2222222222 = 11111111110
    10000000000 – 9999999999 = 1 have to flip around
    10000000000 – 9999999999 = 1
    Last edited by Salem; 01-21-2009 at 12:01 AM. Reason: tag only the bits that matter, more than you deserve for just dumping your homework, this is for all the other board members

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    [Here we have some stuff without code tags since I too would rather not scroll endlessly right or bother to break lines if I am going to use code tags, since the point of code tags is to escape formatting such as enforced line length! Since we are are computer programming, let's not ignore TOO MUCH the actual computer and all.]


    I need help with this assignment, any takers? I need to fill in the functions and make it work

    Computer Science

    The Problem
    The unsigned int type in C requires 4 bytes of memory storage. With 4 bytes we can store integers as large as 232-1; but what if we need bigger integers, for example ones having hundreds of digits? If we want to do arithmetic with such very large numbers we cannot simply use the unsigned data type. One way of dealing with this is to use a different storage structure for integers, such as an array of digits. If we represent an integer as an array of digits, where each digit is stored in a different array index. Since the integers are allowed to be as large as we like, a dynamically-sized array will prevent the possibility of overflows in representation. However we need new functions to add, subtract, compare, read and write these very large integers.

    175—way to store in array index 0=5 1=7 2=1
    Doing this all major operations goes from least sig digit to most significant digit.S
    Write several functioms

    Write a program that will manipulate such arbitrarily large integers. Each integer should be represented as an array of digits, where the least significant digit is stored in index 0. Your program should be able to read in a string of digits and create a struct that stores the big integer.

    Your program should store each decimal digit (0-9) in a separate array element. In order to perform addition and subtraction more easily, it is better to store the digits in the array in the reverse order. For instance, the value 1234567890 would be stored as:

    index 0 1 2 3 4 5 6 7 8 9
    array 0 9 8 7 6 5 4 3 2 1

    Note: Although this seems counter-intuitive, it makes the code slightly easier, because in all standard mathematical operations, we start with the least significant digits. It also makes sense that the digit at the place 10i is stored in index i.

    Your program should include the following functions:

    • a function that will read in an integer from the keyboard-read into string and convert digit by digit
    • a function that will print an integer.
    • a function that will add two integers and return the result.
    • a function that compares two integers and returns -1 if the first is less than the second, 0 if they are equal, and 1 if the first is greater than the second.
    • a function that will subtract one integer from the other and return the result. Since you’ll be dealing with positive integers only, the result should be a positive number. To ensure that the result is integer you should subtract the smaller number from the larger one. If they are equal, 0 should be returned.this will always return a non negative result. Return pos6 not neg 6 . there are prototypes.
    Input/Output Specification
    Your program should allow the user to do two things:

    1) Add two big integers
    2) Subtract to big integers

    Instead of getting input from the user, you read in input from a file, "bigint.txt". (This will expedite the grading process.)

    The input file format is as follows:

    The first line will contain a single positive integer, n, representing the number of operations to carry out. The next n lines will contain one problem each. Each line will have three integers separated by white space. The first integer on each of these lines is guaranteed to either be 1 or 2, indicating addition and subtraction, respectively. The next two integers on the line will be the two operands for the problem. You may assume that these two integers are non-negative, are written with no leading zeros (unless the number itself is 0) and that the number of digits in either of the numbers will never exceed 200.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    This is an interesting assignment because of the tip about storing the numbers backwards because of the "least significant digit" being the most processed in arithmetic. I think the prof is being a bit picky with the struct tho, because really you could use array[0] for the size and skip a struct completely which also makes the coding easier. Loops, loop, loops.

    I'm not going to do it anyway, tho. I would say from the list beginning with "Your program should include the following functions" the first two are obviously the easiest so begin there, probably with the first one (input), but keeping in mind you must deal with the second one (output).
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    POeT GuY Matus's Avatar
    Join Date
    Feb 2008
    Location
    Bz
    Posts
    235
    Quote Originally Posted by MK27 View Post
    .
    Wow MK u sure did have time to reply to this post, sure was a lot!
    PoEms R InsPiRatiOns of LIfE ExpErienCes!!


  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    Omaha, Nebraska
    Posts
    116
    Wire $1,000,000 non-sequential US dollars to an off shore account of my choosing.
    PM me when you have the money ready and I will give you further instructions from there.

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Read our forum's homework policy, please! We don't *do* your homework for you. We will try to help you, if you will post your code /pseudo code, and explain your problem accurately and concisely.

    I'm not even going to take the time to read some long-winded assignment paper. That's your job.

    If you aren't willing to work on your assignment, I'm certainly not going to.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The assignment is well specified, and it sounds easy enough. So my questions to you:
    Are there any bits you don't understand that we can clarify for you?
    Where is your code? We can't help until you've made a start on it and have gotten stuck.
    Even if you have no clue how to implement the algorithms asked of you, you can make a compile-able program by starting with add and subtract functions that just return 0 initially.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User
    Join Date
    Nov 2008
    Posts
    31
    I'm having trouble where to start off.. i need to read in the strings into a character array and then convert it to integers with the strtok function. This is what i have..

    Code:
    struct integer* read_integer(char* stringInt)
    {
        char* stringInt;
        int size;
        char delims [] = " \n";
        int line[MAXLEN];
        int i;
        
        FILE *fin;
        fin = fopen("bigint.txt","r"); // Open the file for reading
        fscanf(fin, "%d", &size); //Read in how many lines there are
        
        //Allocate memory for the struct with malloc
        integer = (struct integer*)(malloc(size*sizeof(struct integer*)));
        
        //Check to see if malloc is Null, if so crash program.
        if(integer = (struct integer*)(malloc(size*sizeof(struct integer*)))== NULL);
        {
            printf("Malloc Failed\n");
            return 0;
        }
        
        fgets(line, MAXLEN, fin);
        
        for(i = 0; i < size; i++)
        {
            fgets(line, MAXLEN, fin);// read in second line of file?
            strtok(line, delims);// Set up string tokenizer to split the string up based on the limits
            stringInt = (char*)strtok(NULL, delims);
            integer[i].choice = atoi(stringInt);
            
            stringInt = (char*)strtok(NULL, delims);
            integer[i].digits = atoi(stringInt);
            
            stringInt = (char*)strtok(NULL, delims);
            integer[i].size; = atoi(stringInt);
        }
        
        
        // Clean up Function 
        free(integer);
        fclose(fin);
        return struct integer;
    }

  9. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Code:
    integer = (struct integer*)(malloc(size*sizeof(struct integer*)));
    1. do not cast malloc - read FAQ
    2. you allocating space for size pointers not size structs
    3.
    Code:
        if(integer = (struct integer*)(malloc(size*sizeof(struct integer*)))== NULL);
    result of the previous malloc is lost
    Should be
    Code:
     if(integer == NULL)
    Do not forget to check the return value of fgets

    Second line of the file is just ignored?

    Code:
    struct integer* read_integer(char* stringInt)
    {
        char* stringInt;
    Why do you need two of them?

    Code:
        free(integer);
        fclose(fin);
        return struct integer;
    you should return variable - not type
    you should not free memory, if you plan return pointer to this memory
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Since the specifications include this: "a function that will read in an integer from the keyboard-read into string and convert digit by digit" but of course you may also want to read from a file, I would write a "read_integer" function that could do both by accepting a FILE* as a parameter (keyboard input is FILE *stdin and it already exists). Look:
    Code:
    #include <stdio.h>
    
    int read_integer (FILE *in, char *stringint) {
    	int i=0, ch;
    	while ((ch=fgetc(in))>0) {
    		if (ch=='\n') break;
    		stringint[i]=ch;
    		i++;
    	}
    	stringint[i]='\0';
    	return i;
    }
    	
    
    int main () {
    	char buffer[200];
    	int len=read_integer(stdin, buffer);
    	printf("%s length=%d\n", buffer, len);
    }
    This does not reverse the numbers or put them into a struct, but it does return the number of digits in the string. Plus you can read numbers from a file:
    Code:
    FILE *fp=fopen("some.file", "r");
    len=read_integer(fp, buffer);
    Some output from the first example:
    [root~/C] ./a.out
    12347198234501238411324512345
    12347198234501238411324512345 length=29
    Last edited by MK27; 01-21-2009 at 11:38 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  11. #11
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Code:
    char ch;
    	while ((ch=fgetc(in))>0)
    fgetc returns int, so using char to store the result even before you are sure it could be stored there -just asking for troubles.
    On compiler where char is unsigned - you'll be unable to determine the EOF condition
    On compilers where char is signed - you'll be unable to read chars from the 128-255 range
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  12. #12
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by vart View Post
    fgetc returns int, so using char to store the result even before you are sure it could be stored there -just asking for troubles.
    On compiler where char is unsigned - you'll be unable to determine the EOF condition
    Yes, very true, I will change this in the previous post!
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  13. #13
    Registered User
    Join Date
    Nov 2008
    Posts
    31
    how do i read the string in using fscanf ?
    how do i pass my char array to the first function if i have it in main.

    Code:
    # include<stdio.h>
    
    int main(void)
    {
       # include<stdio.h>
    
    int main(void)
    {
        int numlines;
        char stringline[200];
        
        FILE *fin;
        fin = fopen("bigint.txt","r");
        fscanf(fin, "%d", &numlines); //Read in how many lines there are
        fscanf(fin, "%s", &stringline);
        printf("stringline = %d\n", stringline);
        printf("%d\n", numlines);
        
        fclose(fin);
        system("PAUSE");
        return 0;
    }
    
    }

  14. #14
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    fscanf(fin, "%s", &stringline);
    you do not need & here

    printf("stringline = %d\n", stringline);
    format is wrong
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  15. #15
    Registered User
    Join Date
    Nov 2008
    Posts
    31
    Cannot get the function to add my numbers..

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXLEN 200
        
    struct integer* read_integer(char* stringInt);
    void print(struct integer *p);
    struct integer* add(struct integer *p, struct integer *q);
    struct integer* subtract(struct integer *p, struct integer *q);
    int compare(struct integer *p, struct integer *q);
    
    struct integer{
        int *digits;
        int size;
    };
    
    int main(void){
        int numlines; //Number of lines stored in the file
        char string1[200];
        char string2[200];
        int i;// loop index
        int opr; //Operator 1 or 2 tells us if we add or subtract
        struct integer *p;
        struct integer *q;
    
        // Open the file and read from bigint.txt
        FILE *fin;
        fin = fopen("bigint.txt","r");
        fscanf(fin, "%d", &numlines); //Read in how many lines there are in the file
    
         // read a line (\n)
        // read the operator(1 or 2) - forget about this one. 3 fscanf
        //scanf first sting; call read int (1st) function
        //same with the second string
        //if 1 then call add, if 2 then call subtract
        // end of loop
        for(i = 0; i < numlines; i++)
        {
            fscanf(fin, "%d", &opr);  // find out whether its add or subtract
            fscanf(fin, "%s", string1); // scan in 2nd number on the first line of input file
                p = read_integer(string1); 
            fscanf(fin, "%s", string2);// scan in 3rd number on the first line of input file
                q = read_integer(string2);
        
            printf(string1);//call function to print out information
            printf("\n");
            printf(string2);
            printf("\n");
    
            if(opr == 1)
            {
              
             // add
            }
            else if(opr == 2)
            {
             // subtract func  
            }
        }
        
    
            
        fclose(fin);
        system("PAUSE");
        return 0;
    }
    
    //Preconditions: the first parameter is string that stores
    //               only contains digits, doesn't start with
    //               0, and is 200 or fewer characters long.
    //Postconditions: The function will read the digits of the
    //	large integer character by character, 
    //	convert them into integers and return a 
    //             pointer to the appropriate struct integer.
    struct integer* read_integer(char* stringInt)
    {
        int len;
        struct integer *myString;//create a new struct
        int i;//loop index
        //allocate memory for the struct
        myString = (struct integer*)(malloc(sizeof(struct integer)));
        
        len = strlen(stringInt); // length of the strinInt in digits
        
        myString->size = len; // length of string assigned to size in struct myString
        
        //allocate memory for digits
        myString->digits = (int*)(malloc(sizeof(int)* len));
        
        // assign number to digits, convert to integers
        for(i = 0; i < len; i++)
        {
            myString->digits[i] = stringInt [len-1-i] - '0';
        }
        return myString;
    }
    
    //Preconditions: p is a pointer to a big integer.
    //Postconditions: The big integer pointed to by p is 
    //                printed out.
    void print(struct integer *p)
    {
    //given pointer, want to print out digits in reverse order...
        int i;
        // no reversing in add or subtract, but want to reverse here
        for(i = p->size-1; i >= 0; i--)
        {
            printf("%d\n", p->digits[i]);
        }
        
    }
    //Preconditions: p and q are pointers to struct integers.
    //Postconditions: A new struct integer is created that 
    //                stores the sum of the integers pointed to 
    //                by p and q and a pointer to it is 
    //                returned.
    struct integer* add(struct integer *p, struct integer *q)
    {
        int i;
        struct integer *addAnsw; //create new struct for answer
        
        //Allocate memory for the new struct
        addAnsw = (struct integer*)(malloc(sizeof(struct integer)));
        
        if(p->size > q->size)
        {
            addAnsw = (int*)(malloc(sizeof(int)*(p->size)));
        }
        for(i ; i; i++)
        {
         addAnsw = p->digits[i] + q->digits[i];
        }
        
        return addAnsw;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Menu
    By Krush in forum C Programming
    Replies: 17
    Last Post: 09-01-2009, 02:34 AM
  2. Assignment Operator, Memory and Scope
    By SevenThunders in forum C++ Programming
    Replies: 47
    Last Post: 03-31-2008, 06:22 AM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  4. Help with a pretty big C++ assignment
    By wakestudent988 in forum C++ Programming
    Replies: 1
    Last Post: 10-30-2006, 09:46 PM
  5. Replies: 1
    Last Post: 10-27-2006, 01:21 PM