Thread: reviewing for final exam, need help with this question

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    41

    reviewing for final exam, need help with this question

    Final exams are a couple of weeks away and I'm studying early because I need to past my c++ final with an 85 or higher. We recently had a test and the following question is one that I got most of it wrong. Can someone help me with it? There may be somthing like this on the final.


    26) Consider the following header file (cross-section only -- more functions functions are possible):

    Code:
    //Filename: list.h -- Declaration of the class List
    
    class List
    {
    public:
    
    List(int x); // Initializes member data to represent empty list and 
                     //dynamically allocates array to starting size x
    
    int SumOdd();//returns the sum of all the odd numbers in the list
    
    int Greater(int val); //returns the number of the values in the list 
                                  //that are greater than val
    void PrintSquares(); //Prints the squares ofthe data elements in
                                    // the list, separated by commas. Ex. if the 
                                   //list stores (3, 5, -2), prints 9, 25,4
    
    private:
    
    int * data;// pointer to a dymanic array of integer value
    int current;//number of values currently stored in the list
    int max; //the allocated size of the array
    
    };
    Write the 4 member functons declared here, exactly as they would appear in the implementation file "list.cpp".

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    So paste what you did do then
    We're not here to write the whole thing for you, even if it does take 5 minutes to do.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    They all follow the same basic logic, traverse the entire data array and do something based on what the value is. Show us what your answers were and we will show you ours. This reeks of homework.
    My best code is written with the delete key.

  4. #4
    Registered User
    Join Date
    Oct 2002
    Posts
    41

    it's not homework

    This isn't homework thank you. It's a test question that I did horrible on and just want to know how to approach it if it's one like this on the final. thanks. I'll get help elsewhere.

  5. #5
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    Don't start another thread just to voice an assumed offense. Show us what your solution was and we will be happy to help you, but something that appears to be homework usually is so we tend to be careful not to give away answers. This is to everyones benefit. If you don't like it, then I'm sure you can find somewhere else to go.

    >I'll get help elsewhere.
    Okay. Threatening to leave means nothing to us unless you are already a well respected member.
    My best code is written with the delete key.

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Threads merged.

    OK, 3 of the functions contain this loop, and one other line of code
    Code:
    for ( int i = 0 ; i < current ; i++ )
    Is that enough nannying for you?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    Originally posted by Salem
    Threads merged.

    OK, 3 of the functions contain this loop, and one other line of code
    Code:
    for ( int i = 0 ; i < current ; i++ )
    Is that enough nannying for you?
    Or they could be done recursively.

    Salem or Prelude, what would be the advantage/disadvante of using recursion here versus a for/while loop approach?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Salem or Prelude, what would be the advantage/disadvante of using recursion here versus a for/while loop approach?
    Recursion would be rather stupid for this use. You are basically calling a function for each integer in the array, this is quite a bit more overhead for processing each element than a loop. That alone gives you performance problems and potential breakdown. Recursion doesn't buy you anything when it comes to clarity or code size either, so there's no advantage and severe disadvantage. No point in even considering a recursive solution.
    My best code is written with the delete key.

  9. #9
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    at what instances then would recursion be used within the list ADT...for one of my exams I had to write a recursive fuction which deletes all nodes of a list with a certain value, as well as a recursive fuction which takes two list pointers ad combines them into a single ordered list.

    Was this just an exercise in undestanding or were these the proper way of completing the task?

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  10. #10
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Here's what I would do...
    Code:
    #include <iostream>
    using namespace std;
    
    class List
    {
        int *data;
        int current;
        int max;
    
        int smd(int*p){return p<data?0:smd(p-1)+(*p&1?*p:0);}
        int grtr(int*p,int v,int c){return p<data?0:c+grtr(p-1,v,*p>v?c++:c);}
        wostream&prsq(int*p){return p<data?wcout:(prsq(p-1)<<*p**p).put(L',');}
    
    public:
        List(int x) : current(0),max(x),data(new int[x]) {}
        ~List() {delete[]data;}
    
        int SumOdd() {return smd(data+current-1);}
        int Greater(int val) {return grtr(data+current-1,val,0);}
        void PrintSquares() {prsq(data+current-1)<<L"\b "<<endl;}
    
        // added this for testing (doesn't "grow" data)
        void CopyList(int *p, int n) {memcpy(data,p,(current=n)<<2);}
    };//List
    
    int main()
    {
        int test[] = {1, 2, 3, 4 ,5, 6, 7, 8, 9 ,10};
    
        int len = sizeof(test)/sizeof(*test);
        List l(len);
        l.CopyList(test,len);
        
        cout << "l.SumOdd() = " << l.SumOdd() << endl
             << "l.Greater(3) = " << l.Greater(3) << endl
             << "l.PrintSquares() : ";
        l.PrintSquares();
    
        return 0;
    }//main
    As you can see, I chose a recursive strategy. Although rather stupid for this use, it is fun to look at.

    gg

  11. #11
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    Originally posted by axon
    Was this just an exercise in understanding or ...
    More like an exercise to determine your understanding - aka "exam".

    There are plenty of stock answers for adv/dis-adv of using recursion:
    Common advantages:
    - Ease of algorithm implementation. Some algorithms are simply recursive in nature and are much easier to implement, like quick sort, merge sort, or traversing a tree ADT.

    Common dis-advantages:
    - Code readability/maintainability. (See previous post for xtreme case).
    - Stack use. The number of times a function can recurse is limited by the size of the stack.
    - Speed. The overhead for making the recursive function call might be avoided by using a non-recursive implementation.

    It is up to you (or perhaps even the coding guidelines of the company you work for) to weigh the advantages vs. dis-advantages of the design you choose.

    gg

  12. #12
    Registered User axon's Avatar
    Join Date
    Feb 2003
    Posts
    2,572
    LMAO codeplug.

    man, pretty condensed if you ask me...if I would turn something like that in, it would surely get a low grade. I hope that the original poster gets your point

    some entropy with that sink? entropysink.com

    there are two cardinal sins from which all others spring: Impatience and Laziness. - franz kafka

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,897
    >Was this just an exercise in undestanding or were these the proper way of completing the task?
    You are confusing the class given with a linked list implementation. The OP posted a class implemented with a dynamic array, recursion is silly in most cases for arrays. For linked lists a recursive implementation isn't quite so unreasonable. However, recursion still doesn't buy you much.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. opengl DC question
    By SAMSAM in forum Game Programming
    Replies: 6
    Last Post: 02-26-2003, 09:22 PM
  2. sort problem for an exam
    By rjeff1804 in forum C Programming
    Replies: 10
    Last Post: 02-12-2003, 10:33 PM
  3. another exam question
    By rjeff1804 in forum C Programming
    Replies: 4
    Last Post: 02-12-2003, 10:29 PM
  4. The AP Exam.....
    By RoD in forum A Brief History of Cprogramming.com
    Replies: 32
    Last Post: 02-10-2003, 09:46 PM
  5. exam question
    By teja22 in forum C Programming
    Replies: 2
    Last Post: 10-08-2001, 08:03 PM