/* [challenge] who has to pay? In a class there are 20 students. For a coffee they have to pay 1$ They lend this dollar sometimes to some other student but each student not more than one time. At the end of semester, the students want to clear their debts: If a lend to b and b lend to c and c lend to a, nobody has to pay. But if additionally d lend to c, c has to pay 1$ to d Challenge: create a random situation of who lend money to whom. Let change dollars as little as possible. Example a->b b->c c->a d->b only b has to pay to d. ---- a->b b->c c may pay to a --- a->b b->c d->c c has to pay to a and to d Hint: create a linked list and remove all circles. */ #include #include #include using namespace std; const string students[] = { "Axel","Brian","Cip","Dan","Ed", "Fred","Grace","Heidi","Kim","Isa", "Lee","Mary","Nik","Opra","Pam", "Qin","Rob","Shawn","Tim","Uma" }; class Transactions { public : Transactions() { initialize(); } ~Transactions() {} void lend( int, int ); void close(); private : bool hasLent[20]; int personalDebt[20]; void initialize() { for ( int i = 0 ; i < 20 ; i++ ) { hasLent[i] = false; personalDebt[i] = 0; } } }; void Transactions::lend( int lender , int receiver ) { if ( lender == receiver ) return ; if ( ! hasLent[ lender ] ){ hasLent[ lender ] = true; personalDebt[ receiver ] += 1; cout<< students[lender ] << " lends to " << students[ receiver ]< 0 ) { personalDebt[ iStudent ] -= 1; hasLent[ iStudent ] = false; } } for ( int iStudent = 0 ; iStudent < 20; /* if personalDebt == 0 */ ){ if ( personalDebt[ iStudent ] > 0 ) { for ( int j = 0 ; j < 20 ; j++ ) { if ( hasLent[ j ] ) { personalDebt[ iStudent ] -= 1; hasLent[ j ] = false; cout<< students[ iStudent ] << " give 1$ " << students[ j ]< ~Transactions() ; } int main() { srand(time(0)); Transactions balance; // generates transactions for ( int i = 0 ; i < rand()%40 + 5 ; i++ ) balance.lend( rand()%20, rand()%20 ) ; balance.close(); return 0; }