理发师问题？ 理发师问题 pv操作
理发师的问题
你这只是“悖论”，且很凑巧的刚好是最著名的逻辑悖论：伯特纳德·罗素提出的理发师悖论：
一个理发师的招牌上写着：
告示：城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。
谁给这位理发师刮脸呢？
如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此其他任何人也不能给他刮脸。看来，没有任何人能给这位理发师刮脸了！
伯特纳德·罗素提出这个悖论，为的是把他发现的关于集合的一个著名悖论用故事通俗地表述出来。某些集合看起来是它自己的元素。例如，所有不是苹果的东西的集合、它本身就不是苹果，所以它必然是此集合自身的元素。现在来考虑一个由一切不是它本身的元案的集合组成的集合。这个集合是它本身的元素吗？无论你作何回答，你都自相矛盾。
悖论 （paradox，也称逆论，反论），是指一种导致矛盾的命题。
悖论的定义可以这样表述：由一个被承认是真的命题为前提，设为B，进行正确的逻辑推理后，得出一个与前提互为矛盾命题的结论非B；反之，以非B为前提，亦可推得B。那么命题B就是一个悖论。当然非B也是一个悖论。
悖论有点像魔术中的变戏法，它使人们在看完之后，几乎没有—个不惊讶得马上就想知道：“这套戏法是怎么搞成的？”当把技巧告诉他时，他就会不知不觉地被引进深奥而有趣的数学世界之中。正因为如此，悖论就成了一种十分有价值的教学手段。
悖论(paradox)来自希腊语“para+dokein”，意思是“多想一想”。这个词的意义比较丰富，它包括一切与人的直觉和日常经验相矛盾的数学结论，那些结论会使我们惊异无比。悖论是自相矛盾的命题。即如果承认这个命题成立，就可推出它的否定命题成立；反之，如果承认这个命题的否定命题成立，又可推出这个命题成立如果承认它是真的，经过一系列正确的推理，却又得出它是假的；如果承认它是假的，经过一系列正确的推理，却又得出它是真的。古今中外有不少著名的悖论，它们震撼了逻辑和数学的基础，激发了人们求知和精密的思考，吸引了古往今来许多思想家和爱好者的注意力。解决悖论难题需要创造性的思考，悖论的解决又往往可以给人带来全新的观念。
最早的悖论被认为是古希腊的"说谎者悖论".
数学中的“理发师”问题到底是怎么回事？
理发师悖论（罗素悖论）：某村只有一人理发，且该村的人都需要理发，理发师规定，给且只给村中不自己理发的人理发。试问：理发师给不给自己理发？
如果理发师给自己理发，则违背了自己的约定；如果理发师不给自己理发，那么按照他的规定，又应该给自己理发。这样，理发师陷入了两难的境地。
一个很古老的理发师的问题
你好，很高兴你也对悖论的有关问题感兴趣，我也很喜欢悖论的一些知识，下面是我在大一时自学的一些悖论的知识。
好了，现在来说说你提出的著名的理发师悖论，先前在大二我也问过我一个很厉害的哲学老师，他给我了几页资料即是关于如何正确对待这个问题：
这个命题的实质可以这么理解：这是一个关于当事人之间权利安排的合约规则，有鉴于此合约并未经过所有当事人的谈判，而是其中某一个特别的当事人给出的强制性规定，它突出地反映了参与到此项合约里的当事人之间权力的分殊。具体地说，理发师的（话语）权力来自于专业分工赋予他的在理发技艺上的相对精良与比较优势，在这个问题上任何期待拥有一个完美发型的潜在理发对象都不可能对理发师的权威做出挑战。这个说明非常关键，它是理发师的规则得以成立的必不可少又常被无条件忽略的前提。
理发师做出如上声明的必要性，从经济学的观点来看也相当地明了：提高他人为节省理发费用而自行开工的成本费用。村里总有一些人对理发师制定的垄断价格感到不满，一个迫不得已的选择是自己为自己剪头发，但这可能冒着降低自己外观被可接受程度的巨大风险。如果由此造成的不幸后果得不到专业人士的修正，此以实际行动损坏理发师利益的行为将变得极其可怕：我觉得用偷鸡不成亏把米的俗语来形容收益对成本的巨大亏空比较贴切。在理发师做出一个预防性质的声明后，加入的新变量推动风险投资的衡量标准向不利于意图对理发师的专业权威挑战的方向上倾斜，从而保证了理发师的最大利益。整体来看，如果村里每一个要求专业分工的领域都配备类似的游戏规则，则可以想象此村集体拥有比较清晰的知识产权保护意识与相关激励制度，拥有一个比较美好的未来。
但村里总会有一些人对此强势规则感到郁闷，他们会拿出罗素先生的问题让理发师下不了台：请问，按照你的规则，你是否应当给自己剪头发呢？如果我是那个理发师，对此挑衅我有如下的对应：没错，先生们，表面上看我陷入了两难的窘境，如果我给自己剪过头发，结论自然是相当清晰的，但倘若我先前从未给自己剪头发而是一直照顾我的师兄的生意呢，我是否拥有为自己剪头发的权力？是否我刚刚开始的工作可以被等同于各位强调的“剪”，并立即停止我的活计，让剪永远永远到不了它的终点，而我始终在剪与非剪之间困惑徘徊？在此我要提醒诸位，如何是“剪“？ 我觉得在这个问题上我们已经达成了共识。在我的那个声明里有对这个动词的清楚的界定，即任何完成了对头发的演变到某种不可接受程度的混乱外观效果的修整操作，而这还只是一个底线，使得你们对我的专业能力表示认同与尊重，自觉地遵从我的合理限制的，是你们对更高层次的追求：对美的向往。我有理由认为，我剪下一根头发不算是“剪”，即使我已经消灭掉过长的乱发而使头顶表现出一种粗糙的整洁效果，那也还未穷尽我们都已默认的概念的内涵。在我完成能够使我本人感到满意并同时认定我的工作已经充分体现了我的水平与技巧的最后一项细心的操作以前，我不相信你们可以将我已经为自己剪头发的罪名强加与我，从而推证说这个过程根本不应当发生。并且，在我完成所有操作的那一瞬间，我已经归属于这样一个团体，他们都是为自己剪过头发的理发师。先生们，你们的诘问将不再适用于我。
我相信，在场没人能够对理发师的上述高论提出有力反驳。他抓住了这样一个要害：罗素悖论的表达方式与悖论中的概念得以产生的前提在根本上是悖谬的，这是悖论能够在字面上成立的根本原因。但这个悖论是通过对一个具体情景的不恰当的抽象建立起来的，体现其悖论色彩的问题本身便是一个虚假的问题，纯粹无中生有，自然悖得无路可解了。如果有人非得要你来解决一个并不存在的问题，岂非滑稽？
罗素悖论的真正意义似乎是，在有了作为限制条件的第一次后，是否允许第二次以至更多？
二：从资源配置的角度理解理发师给自己剪发的合理性
上面已对规则对资源配置的影响作了粗浅的描述，这里可以略加发挥充实这一方向上的论述。我以为理发师为自己剪发符合规则所欲的经济效果。虽然不太看得出在给自己剪发的过程中发生的比较明确的利益转移，但仔细分析理发师所扮演的双重角色还是不难得到相同的在与规则对外部发生作用之时比较显明地表现出的效果。在理发师——平民模式中平民以报酬形式流失的损失是理发师收益的来源；在理发师自己面对自己的时候资源转移的来源与趋向何在呢？不难想象，理发师扮演了两个不同的角色，分别填补前一模式中对立双方充当的角色。他本人在理发师角色上的收益体现在：避免了在其他理发师处接受服务而不得不付出的损失；但在平民角色上他也蒙受了对等的损失，体现在其付出劳动但无法向这个特殊的顾客索要当然的报酬。最后的结果是正负抵消，于资源配置无影响，规则的制度安排依然有效。存心挑刺的人们在此无理由指摘理发师的规则不能够向所有的人开放，而且这一方面的认识再一次证明理发师给自己剪发榄括在规则建立的意图内，在事实层面上也完全合理。
当然，另一个安排是在理发师内部的互助，但可能的交易成本使得这不是一个最优的选择。
再次谢谢你的提问！
理发师问题算法如何实现
2.理发师问题：一个理发店有一个入口和一个出口。理发店内有一个可站5 位顾客的站席
区、4 个单人沙发、3 个理发师及其专用理发工具、一个收银台。新来的顾客坐在沙发上等
待；没有空沙发时，可在站席区等待；站席区满时，只能在入口外等待。理发师可从事理
发、收银和休息三种活动。理发店的活动满足下列条件：
1）休息的理发师是坐地自己专用的理发椅上，不会占用顾客的沙发；
2）处理休息状态的理发师可为在沙发上等待时间最长的顾客理发；
3）理发时间长短由理发师决定；
4）在站席区等待时间最长的顾客可坐到空闲的理发上；
5）任何时刻最多只能有一个理发师在收银。
试用信号量机制或管程机制实现理发师进程和顾客进程。
原理：
(1)customer 进程：
首先检查站席区是否已满（stand_capacity）,若满选择离开，否则进入站席区，即进入
理发店。在站席区等待沙发的空位（信号量sofa），如果沙发已满，则进入阻塞等待队列，
直到出现空位，在站席区中等待时间最长的顾客离开站席区（stand_capacity）。坐到沙
发上，等待理发椅(barber_chair)，如果理发椅已满，则进入阻塞等待队列，直到出现
空位，在沙发上等待时间最长的顾客离开沙发（释放信号量sofa）。坐到理发椅上，释放
准备好的信号（customer_ready），获得该理发师的编号（0~1 的数字）。等待理发师理
发结束（finished[barber_number]）。在离开理发椅之前付款（payment），等待收据
(receipt)，离开理发椅（leave_barberchair）。最后离开理发店。
这里需要注意几点：
a) 首先是几个需要进行互斥处理的地方，主要包括:进入站席区、进入沙发、进入理发椅
和付款几个地方。
b) 通过barber_chair 保证一个理发椅上最多只有一名顾客。但这也不够，因为单凭
baber_chair 无法保证一名顾客离开理发椅之前，另一位顾客不会坐到该理发椅上，
因此增加信号量leave_barberchair，让顾客离开理发椅后，释放该信号，而理发
师接收到该信号后才释放barber_chair 等待下一位顾客。
c) 在理发的过程中，需要保证是自己理发完毕，才能够进行下面的付款、离开理发椅的活
动。这个机制是通过customer 进程获得给他理发的理发师编号来实现的，这样，当
该编号的理发师释放对应的finished[i]信号的时候，该顾客才理发完毕。
d) 理发师是通过mutex 信号量保证他们每个人同时只进行一项操作（理发或者收款）。
e) 为了保证该顾客理发完毕后马上可以付款离开，就应该保证给该顾客理发的理发师在理
发完毕后马上到收银台进入收款操作而不是给下一位顾客服务。在伪码中由以下机制实
现：即顾客在释放离开理发椅的信号前，发出付款的信号。这样该理发师得不到顾客的
离开理发椅的信号，不能进入下一个循环为下一名顾客服务，而只能进入收款台的收款
操作。直到顾客接到收据后，才释放离开理发椅的信号，离开理发椅，让理发师释放该
理发椅的信号，让下一位等待的顾客坐到理发椅上。
(2)barber 进程
首先将该理发师的编号压入队列，供顾客提取。等待顾客坐到理发椅坐好(信号量
customer_ready)，开始理发，理发结束后释放结束信号（finished[i]）。等待顾客
离开理发椅（leave_barberchair）（期间去收银台进行收款活动），释放理发椅空闲信
号(barber_chair)，等待下一位顾客坐上来。
(3)cash（收银台）进程
等待顾客付款(payment),执行收款操作，收款操作结束，给付收据（receipt）。
信号量总表：
信号量 wait signal
stand_capacity 顾客等待进入理发店 顾客离开站席区
sofa 顾客等待坐到沙发 顾客离开沙发
barber_chair 顾客等待空理发椅 理发师释放空理发椅
customer_ready 理发师等待，直到一个顾客坐
到理发椅
顾客坐到理发椅上，给理发师
发出信号
mutex 等待理发师空闲，执行理发或
收款操作
理发师执行理发或收款结束，
进入空闲状态
mutex1 执行入队或出队等待 入队或出队结束，释放信号
finished[i] 顾客等待对应编号理发师理
发结束
理发师理发结束，释放信号
leave_barberchair 理发师等待顾客离开理发椅 顾客付款完毕得到收据，离开
理发椅释放信号
payment 收银员等待顾客付款 顾客付款，发出信号
receipt 顾客等待收银员收、开具收据收银员收款结束、开具收据，
释放信号
伪码：
semaphore stand_capacity=5;
semaphore sofa=4;
semaphore barber_chair=3;
semaphore customer_ready=0;
semaphore mutex=3;
semaphore mutex1=1;
semaphore finished[3]={0,0,0};
semaphore leave_barberchair=0;
semaphore payment=0;
semaphore receipt=0;
void customer()
{
int barber_number;
wait(stand_capacity); //等待进入理发店
enter_room(); //进入理发店
wait(sofa); //等待沙发
leave_stand_section(); //离开站席区
signal(stand_capacity);
sit_on_sofa(); //坐在沙发上
wait(barber_chair); //等待理发椅
get_up_sofa(); //离开沙发
signal(sofa);
wait(mutex1);
sit_on_barberchair(); //坐到理发椅上
signal(customer_ready);
barber_number=dequeue(); //得到理发师编号
signal(mutex1);
wait(finished[barber_number]); //等待理发结束
pay(); //付款
signal(payment); //付款
wait(receipt); //等待收据
get_up_barberchair(); //离开理发椅
signal(leave_barberchair); //发出离开理发椅信号
exit_shop(); //了离开理发店
}
void barber(int i)
{
while(true)
{
wait(mutex1);
enqueue(i); //将该理发师的编号加入队列
signal(mutex1);
wait(customer_ready); //等待顾客准备好
wait(mutex);
cut_hair(); //理发
signal(mutex);
signal(finished[i]); //理发结束
wait(leave_barberchair); //等待顾客离开理发椅信号
signal(barber_chair); //释放barber_chair 信号
}
}
void cash() //收银
{
while(true)
{
wait(payment); //等待顾客付款
wait(mutex); //原子操作
get_pay(); //接受付款
give_receipt(); //给顾客收据
signal(mutex);
signal(receipt); //收银完毕，释放信号
}
}
分析：
在分析该问题过程中，出现若干问题，是参阅相关资料后才认识到这些问题的隐蔽性和严重
性的,主要包括：
（1）在顾客进程，如果是在释放leave_barberchair 信号之后进行付款动作的话，很
容易造成没有收银员为其收款的情形， 原因是： 为该顾客理发的理发师收到
leave_barberchair 信号后，释放barber_chair 信号，另外一名顾客坐到理发椅上，
该理发师有可能为这另外一名顾客理发，而没有为刚理完发的顾客收款。为解决这个问题，
就是采取在释放leave_barberchair 信号之前，完成付款操作。这样该理发师无法进入
下一轮循环为另外顾客服务，只能到收银台收款。
（2）本算法是通过给理发师编号的方式，当顾客坐到某理发椅上也同时获得理发师的编号，
如此，当该理发师理发结束，释放信号，顾客只有接收到为其理发的理发师的理发结束信号
才会进行付款等操作。这样实现，是为避免这样的错误，即：如果仅用一个finished 信
号量的话，很容易出现别的理发师理发完毕释放了finished 信号，把正在理发的这位顾
客赶去付款,而已经理完发的顾客却被阻塞在理发椅上的情形。当然也可以为顾客进行编
号，让理发师获取他理发的顾客的编号，但这样就会限制顾客的数量，因为finished[]
数组不能是无限的。而为理发师编号，则只需要三个元素即可。