Hello !

How i can find the smallest number, higher than average value. For example in deque I have these numbers: 46 84 25 93 91 25 37 32 64 49 17 81 59 38 79 22 57 17 61 11 (transferred from file Stack.txt to deque.txt). Тhe average of these numbers is 49.4, and the smallest number greater than this value should be 57. I should find it without using arrays.

Тhis is my code:

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <stdio.h>

using namespace std; 

int temp;
int br = 1;

struct delem
{

    int key;
    delem *next;

} *l = NULL, *r = NULL;

void push_l(int n) 
{

    delem *p;      
    p = l;           
    l = new delem;     
    l->key = n; 
    l->next = p;             
    if (r == NULL) 
    {

        r = l;
    }

}

void push_r(int n)             
{

    delem *p;           
    p = r;             
    r = new delem;    
    r->key = n;               
    r->next = NULL;   
    if (l == NULL)             
    {

        l = r; 

    }
    else                 
        p->next = r; 

}

int pop_l(int &n)             
{
    delem *p;                
    if (l)                     
    {
        n = l->key;        
        p = l;                  
        l = l->next;    
        if (l== NULL)             
            r = NULL;         
        delete p;             
        return 1;
    }
    else
        return 0;
}

int pop_r(int &n)
{
    delem *p;                 
    if (r)                     
    {

        n = r->key;                
        if (l == r)           
        {
            delete r;          
            l = r = NULL;  
        }
        else
        {
            p = l;                     
            while (p->next != r)
                p = p->next;                   
                //p++;
                n = r->key;                        
                p->next = NULL;         
                delete r;                  
                       r = p;                    
                       return 1;
        }

   }
   else
       return 0;

}

void get(int n)
{

    int i, t;
    for (i = 1; i < br; i++) 
    {

        pop_l(t); 
        if (i == n)
        {

            temp = t;

        }

        push_r(t); 

    }

}

void print_deque()
{

    for (int i = 1; i<br; i++) 
    {

        get(i);
        cout << temp << " ";

    }

}

void input_deque() 
{
    int a;
    ifstream i_file;
    i_file.open("Stack.txt", ios::in);
    if (i_file)
    {

        while (i_file >> a)
        {

            push_l(a);

        }

        ofstream f_file;
        f_file.open("deque.txt", ios::out);
        while (pop_l(a))
        {

            f_file << a << " ";
            cout << a << " ";

        }
        f_file.close();

        i_file.close();

    }
    else
        cout << "Error while opening input file!" << endl;

}

void find_number()
{

    int n, m;
    int total = 0;
    double min = 1;
    double count = 0;
    double average = 0;
    ifstream deque_file;
    deque_file.open("deque.txt", ios::in);

    if (deque_file)
    {

        while (deque_file >> n)
        {

            push_l(n);

            while(pop_l(n))
            {

                //min = (n<min)?n:min;
                total+=n;
                count++;

            }

        }

        average = total/count;

        cout<<"\nSum: " << total << " Count: " << count << " Average: " << average << endl;

    }
    else
        cout << "Error while opening input file!" << endl;

    deque_file.close();

    ifstream deque_file2;
    deque_file2.open("deque.txt", ios::in);
    if(deque_file2)
    {

        while(deque_file2 >> m)
        {

            push_l(m);

            while(pop_l(m))
            {

                //min = (m>average)?m:average;
                if(m > average)
                {

                    min = m;

                }


            }

        }

        cout << "\nMin: " << min << endl;

    }
    else
        cout << "Error while opening input file!" << endl;

    deque_file2.close();

}

void dclean()
{

    ifstream deque_file;
    deque_file.open("deque.txt", ios::trunc);
    deque_file.close();

}

int main()
{

    input_deque();

    print_deque();

    cout << endl;

    find_number();
    dclean();
    cout << endl;

    system("pause");
    return 0;

}

So you have several problems ...

/*
1) using the C++ library deque (FIFO) container to the hold the int's input from file
2) using pop / push onto a 2nd deque ...  get sum/size to get average
3) start with setting the 1st int in the new deque as the x value.
   if the next val is greater than the average and less than that previous x value, update x
    when you have emptied the deque you will have the desired x value;
4) when you get all the above debugged and working ok, code you own class Deque 
    (if you must) 
    and use that in the place of the C++ library deque you developed with above.
    */

Edited 11 Months Ago by David W

3) start with setting the 1st int in the new deque as the x value. If the next val is greater than the average and less than that previous x value, update x ... when you have emptied the deque you will have the desired x value;

The above idea was missing some things here ...

You need to firstly go though the container and select, as a comparator, the first element that was greater than the average ... then the above idea is valid.

Also ... you can traverse a deque with iterators.

See below ...
(an example of how this could be coded using the C++ library deque.)

// findNextNumAfterAvg.cpp //

/*
    How i can find the smallest number, higher than average value.

    For example in deque I have these numbers:
    46 84 25 93 91 25 37 32 64 49 17 81 59 38 79 22 57 17 61 11
    (transferred from file Stack.txt to deque.txt).

    The average of these numbers is 49.4,
    and the smallest number greater than this value should be 57.
    I should find it without using arrays.

*/


#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

const char* FNAME = "numbers.txt";
/*
46 84 25 93 91 25 37 32 64 49 17 81 59 38 79 22 57 17 61 11
*/


bool load_from_file( const char* fname, deque< int >& dq )
{
    ifstream fin( fname );
    if( fin )
    {
        int i;
        while( fin >> i ) dq.push_back(i);
        fin.close();
        return true;
    }
    // else if reach here ...
    cout << "There was a problem opening file: '" << fname
         << "'\n";
    return false;
}


int main()
{
    deque< int > dq;
    if( load_from_file( FNAME, dq ) )
    {
        deque< int >::const_iterator it;
        double sum = 0;
        for( it = dq.begin(); it != dq.end(); ++ it )
        {
            sum += *it;
        }
        double avg = sum / dq.size();
        cout << "Sum is: " << sum
             << " and average is: " << avg << endl;

        it = dq.begin();
        while( ++it != dq.end() )
        {
            if( *it > avg ) break;
        }

        int low = *it;

        while( ++it != dq.end() )
        {
            if( *it > avg && *it < low ) low = *it;
        }

        cout << "The next largest value after the average value of "
             << avg << " is: " << low << endl;
    }

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

But note that since your spec's were only that ...

I should find it without using arrays.

You could have use a list constainer ... which is what you seemed to have been coding in a ...'roll your own version' ... of the C++ library list container. Note also that you could replace everywhere above deque with list and the code will compile and run with correct output. (Try it and see?)

Edited 11 Months Ago by David W

David W, thank you for helping, but i need to do it without using STL. I found the higher value less than the average value, which is 49. Now i need to find smallest number, higher than average.

Here is the updated code:

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <stdio.h>

using namespace std; 

int temp;
int br = 0;

struct delem
{

    int key;
    delem *next;

} *l = NULL, *r = NULL;

void push_l(int n) 
{

    br++;
    delem *p;      
    p = l;           
    l = new delem;     
    l->key = n; 
    l->next = p;             
    if (r == NULL) 
    {

        r = l;
    }

}

void push_r(int n)             
{

    br++;
    delem *p;           
    p = r;             
    r = new delem;    
    r->key = n;               
    r->next = NULL;   
    if (l == NULL)             
    {

        l = r; 

    }
    else                 
        p->next = r; 

}

int pop_l(int &n)             
{
    delem *p;                
    if (l)                     
    {
        n = l->key;        
        p = l;                  
        l = l->next;    
        if (l== NULL)             
            r = NULL;         
        delete p;             
        return 1;
    }
    else
        return 0;
}

int pop_r(int &n)
{
    delem *p;                 
    if (r)                     
    {

        n = r->key;                
        if (l == r)           
        {
            delete r;          
            l = r = NULL;  
        }
        else
        {
            p = l;                     
            while (p->next != r)
                p = p->next;                   
                n = r->key;                        
                p->next = NULL;         
                delete r;                  
                       r = p;                    
                       return 1;
        }

   }
   else
       return 0;

}

void print_deq()
{

    delem *beg = l;

    while (l != r)
    {
        cout << l->key << " ";
        l = l->next;
    }

    cout << l->key;
    cout << endl;
    l = beg;

}

void sort_deq()
{

    delem *T;
    int n, flag;
    if (l == NULL) cout << "Empty deque!";
    else{
        do
        {
            flag = 0;
            T = l;
            while (T->next)
            {
                if (T->key > T->next->key)
                {
                    n = T->key;
                    T->key = T->next->key;
                    T->next->key = n;
                    flag = 1;
                }
                T = T->next;
            }
        } while (flag);
    }

}

void find_avg()
{

    sort_deq();
    double sum = 0;
    double avg;
    delem *beg = l;
    while (l->next)
    {
        sum+=l->key;
        l = l->next;
    }
    sum += l->key;
    avg = sum/br;
    l = beg;

    while (l->next->key < avg)
    {
        l = l->next;
    }
    cout << "br: " << br << endl;
    cout << "avg: " << avg << endl;
    cout << "min: " << l->key << endl;
    l = beg;

}

int main()
{

    int n;

    ifstream deq_file;
    deq_file.open("deque.txt", ios::in);

    if (deq_file)
    {

        while (deq_file >> n)
        {

            push_l(n);

        }

        print_deq();
        sort_deq();
        print_deq();
        find_avg();

    }
    else
        cout << "Error while opening input file!" << endl;

    deq_file.close();

    system("pause");
    return 0;

}

Oops, i have a mistake:

while (l->next->key < avg)
should be:
while (l->key < avg)

Edited 11 Months Ago by preslav_milev

Did you notice the steps I took to get a solution?

Firstly using the C++ library container to solve the problem at hand.

Then, if you need to code your own 'home-grown' List container ... (a single-link linked list is what you looked to be coding) ... that is a SEPARATE problem.

And when that List is working ok ... just plug-in that List.

See below:

#include <iostream>
#include <fstream>
#include <climits>

using namespace std; 

const char* FNAME = "numbers.txt";

struct Node
{
    int key;
    Node *next;

    // ctor...
    Node( int key=0, Node* next = 0 ) : key(key), next(next) {}
} ;

struct List
{
    Node* head;
    Node* tail;
    int len;

    // ctor...
    List( Node* head=0, Node* tail=0 ) :  head(head), tail(tail), len(0) {}
    // detor...
    ~List() { clear();   }

    void clear()
    {
        while( head != 0 )
        {
            Node* cur = head;
            head = head->next;
            delete cur;
        }
        tail = 0;
        len = 0;
    }

    int size() const { return len; }

    void push_front( int key )
    {
        head = new Node( key, head );
        if( !len ) tail = head;

        ++ len;
    }

    void push_back( int key )
    {
        Node* old_tail = tail;
        tail = new Node( key );
        if( len ) old_tail->next = tail;
        else head = tail;

        ++ len;
    }

    int pop_front()
    {
        if( len )
        {
            Node* cur = head;
            head = head->next;

            --len;
            if( !len ) tail = 0;
            int key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << INT_MIN << '\n';
        return INT_MIN;
    }

    int pop_back()
    {
        if( len )
        {
            Node* cur = head;
            if( len > 1 )
            {
                while( cur && cur->next )
                    cur = cur->next;
                tail = cur;
            }
            else // len == 1
                tail = 0;

            --len;

            if( !len ) head = 0;
            int key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << INT_MIN << '\n';
        return INT_MIN;
    }

    void print( ostream& os, const char end = ' ' ) const
    {
        for( Node* cur = head; cur != 0; cur = cur->next )
            os << cur->key << end;
    }

    void bubble_sort()
    {
        if( len > 1 )
        {
            bool swap;
            do
            {
                swap = false;
                Node* cur  = head;
                while( cur->next )
                {
                    if( cur->next->key < cur->key ) // swap //
                    {
                        int tmp = cur->key;
                        cur->key = cur->next->key;
                        cur->next->key = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
            }
            while( swap );
        }
        else
            cout << "Size was less than 2  ... so NO sort needed.\n";
    }

} ;


void process_display( List& lst )
{
    if( lst.size() )
    {

        // sort and show sorted list //
        lst.bubble_sort();
        lst.print( cout );
        cout << endl;

        // get sum and average //
        Node* cur  = lst.head;
        double avg, sum = 0;

        while( cur )
        {
            sum += cur->key;
            cur = cur->next;
        }

        avg = sum / lst.size();

        cur = lst.head;

        int low = cur->key;
        while( cur != 0 && cur->key <= avg )
            cur = cur->next;
        if( cur )
            low = cur->key;

        cout << "size            : " << lst.size() << endl;
        cout << "sum             : " << sum << endl;
        cout << "avg             : " << avg << endl;
        cout << "first after avg : " << low << endl;
    }
}


int main()
{
    ifstream fin( FNAME );

    if( fin )
    {
        int key;
        List lst; // get an enpty list //
        while( fin >> key )
        {
            lst.push_back( key );
        }
        fin.close();

        cout << "Showing list ...\n";
        lst.print( cout );
        cout << endl;

        cout << "Process and firstly show sorted ...\n";
        process_display( lst ) ;

    }
    else
        cout << "Error while opening input file!"
             << FNAME << '\n';

    cout << "Press 'Enter' to continue/exit ... " << flush;
    cin.get();
    return 0;
}

Edited 11 Months Ago by David W

And just to round out this demo ...
the edits needed to go to a template class
are fairly straight forward
once you have some code working ok for the class List (or struct List) with just an int data type;

Take a look:

// findNextGreatestAfterAvg2.cpp //


#include <iostream>
#include <fstream>

using namespace std; 

const char* FNAME = "numbers.txt";

template < typename T >
class List; // forward declaration //

template < typename T >
class Node
{
public:
    // ctor...
    Node( T key=0, Node* next = 0 ) : key(key), next(next) {}
    T get_key() const { return key; }
private:
    T key;
    Node* next;
    friend class List< T >;
} ;


template < typename T >
class List
{
private:
    Node< T >* head;
    Node< T >* tail;
    size_t len;
public:
    // ctor...
    List( Node< T >* head=0, Node< T >* tail=0 ) :  head(head), tail(tail), len(0) {}
    // detor...
    ~List() { clear();   }

    void clear()
    {
        while( head != 0 )
        {
            Node< T >* cur = head;
            head = head->next;
            delete cur;
        }
        tail = 0;
        len = 0;
    }

    size_t size() const { return len; }

    void push_front( const T& key )
    {
        head = new Node< T >( key, head );
        if( !len ) tail = head;

        ++ len;
    }

    void push_back( const T& key )
    {
        Node< T >* old_tail = tail;
        tail = new Node< T >( key );
        if( len ) old_tail->next = tail;
        else head = tail;

        ++ len;
    }

    T pop_front()
    {
        if( len )
        {
            Node< T >* cur = head;
            head = head->next;

            --len;
            if( !len ) tail = 0;
            T key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << T() << '\n';
        return T();
    }


    T pop_back()
    {
        if( len )
        {
            Node< T >* cur = head;
            if( len > 1 )
            {
                while( cur && cur->next )
                    cur = cur->next;
                tail = cur;
            }
            else // len == 1
                tail = 0;

            --len;

            if( !len ) head = 0;
            T key = cur->key;
            delete cur;
            return key;
        }

        cout << "List was empty so returning " << T() << '\n';
        return T();
    }

    void print( ostream& os, const char end = ' ' ) const
    {
        for( Node< T >* cur = head; cur != 0; cur = cur->next )
            os << cur->key << end;
    }

    void bubble_sort()
    {
        if( len > 1 )
        {
            bool swap;
            do
            {
                swap = false;
                Node< T >* cur  = head;
                while( cur->next )
                {
                    if( cur->next->key < cur->key ) // swap //
                    {
                        T tmp = cur->key;
                        cur->key = cur->next->key;
                        cur->next->key = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
            }
            while( swap );
        }
        else
            cout << "Size was less than 2  ... so NO sort needed.\n";
    }

    class Iterator
    {
    private:
        Node< T >* cur;
    public:
        Iterator( Node< T >* p = 0 ) : cur(p) {}

        Iterator operator ++ () { cur = cur->next; return *this; }
        Iterator operator ++ (int) { cur= cur->next; return *this; }

        bool operator == ( Iterator it ) const { return cur == it.cur; }
        bool operator != ( Iterator it ) const { return cur != it.cur; }

        T operator * () { return cur->key; }

    } ;

    Iterator begin() { Iterator it(head); return it; }
    Iterator end() { Iterator it; return it; }

} ;



void process_display( List< int >& lst )
{
    if( lst.size() )
    {

        // sort and show sorted list //
        lst.bubble_sort();
        lst.print( cout );
        cout << endl;

        // get sum and average //
        List< int >::Iterator it = lst.begin();
        double avg, sum = 0;

        while( it != lst.end() )
        {
            sum += *it;
            ++it;
        }

        avg = sum / lst.size();

        // Since the list is now in increasing sorted order ...
        // get 1st element value right after average ... if exists //

        it = lst.begin();

        int low = *it;
        while( it != lst.end() && *it <= avg )
            ++it;
        if( it != lst.end() )
            low = *it;

        cout << "size            : " << lst.size() << endl;
        cout << "sum             : " << sum << endl;
        cout << "avg             : " << avg << endl;
        cout << "first after avg : " << low << endl;
    }
}




int main()
{
    ifstream fin( FNAME );

    if( fin )
    {
        int key;
        List< int > lst; // get an enpty list //
        while( fin >> key )
        {
            lst.push_back( key );
        }
        fin.close();

        cout << "Showing list ...\n";
        lst.print( cout );
        cout << endl;

        cout << "Process but firstly show sorted ...\n";
        process_display( lst ) ;

    }
    else
        cout << "Error while opening input file!"
             << FNAME << '\n';

    cout << "Press 'Enter' to continue/exit ... " << flush;
    cin.get();
    return 0;
}

Edited 11 Months Ago by David W

This article has been dead for over six months. Start a new discussion instead.