1.研究一个银行家如何将总数一定的资金，安全地借给若干个顾客，使顾客既能满足对资金的需求，也使银行家可以收回自己的全部资金，不至于破产
一些限制条件：
- 每次顾客在借款前必须提前说明所需资金总额
- 每次借钱都是以一个单位进行
- 顾客在拿到一个单位的借款前可能需要等待
- 银行保证顾客的等待时间是有限的（借或不借）
2.Qt中的算法实现方案
- 使用多线程机制模拟客户和银行
- 银行优先分配资源给最小需求的客户
- 当客户的资源需求无法满足的时候
- 收回已分配的资源
- 强制结束线程
#include <QCoreApplication> #include <QThread> #include <QMutex> #include <QList> #include <QDebug> class Customer : public QThread { protected: int m_need; //所需金额总额 int m_current; //当前有的金额数 QMutex m_mutex; void run() { bool condition = false; qDebug() << objectName() << "begin to apply money"; do { m_mutex.lock(); condition = (m_current < m_need); m_mutex.unlock(); msleep(10); } while( condition ); qDebug() << objectName() << "end (get enough money)"; } public: Customer(int current, int need) { m_current = current; m_need = need; } void addMoney(int m) { m_mutex.lock(); m_current += m; m_mutex.unlock(); } int backMoney() //需要还的钱 { int ret = 0; m_mutex.lock(); ret = m_current; m_current = 0; m_mutex.unlock(); return ret; } int current() { int ret = 0; m_mutex.lock(); ret = m_current; m_mutex.unlock(); return ret; } int need() { return m_need; } }; class Bank : public QThread { protected: QList<Customer*> m_list; //需要借款的对象列表 int m_total; //总额 void run() { int index = -1; qDebug() << objectName() << "begin: " << m_total; do { index = -1; for(int i=0; i<m_list.count(); i++) { if( m_list[i]->current() == m_list[i]->need()) { qDebug() << objectName() << "take back money from" << m_list[i]->objectName() << " " << m_list[i]->need(); m_total += m_list[i]->backMoney(); } } qDebug() << objectName() << "current: " << m_total; int toGet = 0x00FFFFFF; //初始化一个很大的值 //找到需求量最小的消费者 for(int i=0; i<m_list.count(); i++) { if( m_list[i]->isRunning() ) { int tmp = m_list[i]->need() - m_list[i]->current(); if( toGet > tmp ) { index = i; toGet = tmp; } } } if( index >= 0 ) //找到了 { if( toGet <= m_total ) { qDebug() << objectName() << " give money to: " << m_list[index]->objectName(); m_total--; m_list[index]->addMoney(1); } else { qDebug() << objectName() << "terminate: " << m_list[index]->objectName(); m_total += m_list[index]->backMoney(); m_list[index]->terminate(); } } } while( index >= 0 ); } public: Bank(int total) { m_total = total; } void addCustomer(Customer* customer) { m_list.append(customer); } }; int main(int argc, char *argv[]) { QCoreApplication a(argc, argv); Customer p(4, 8); Customer q(2, 3); Customer r(2, 9); Bank bank(2); p.setObjectName("P"); q.setObjectName("Q"); r.setObjectName("R"); bank.setObjectName("Bank"); bank.addCustomer(&p); bank.addCustomer(&q); bank.addCustomer(&r); p.start(); q.start(); r.start(); bank.start(); return QCoreApplication::exec(); }
