×
通过社交网站直接登录
×
条@我的评论,查看@我
条新私信,查看私信
条新评论,查看评论
位新粉丝 查看粉丝
数学天地 趣味数学 开放题 计算 解决
感谢 匿名网友 于 2020-03-20 14:50:20 提供 来源:33IQ网
(3)
现定义三类问题
P类问题:所有可以在多项式时间内求解的判定问题构成P类问题。判定问题:判断是否有一种能够解决某一类问题的能行算法的研究课题。
NP类问题:所有的非确定性多项式时间可解的判定问题构成NP类问题。非确定性算法:非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的,算法的验证阶段是确定性的,它验证猜测阶段给出解的正确性。设算法A是解一个判定问题Q的非确定性算法,如果A的验证阶段能在多项式时间内完成,则称A是一个多项式时间非确定性算法。有些计算问题是确定性的,例如加减乘除,只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式能推出下一个质数是多少呢?这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式(polynomial)时间内算出来,就叫做多项式非确定性问题。
NPC问题:NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。
试问:
那么P问题与NP问题能相互转换吗?

标签: 之和 数字 日期
著作权归作者所有,转载请联系作者获得授权
答案:
解析:
5
收藏
数学天地 趣味数学 开放题 计算 解决
于 2020-03-15 17:19提供
(1)

一张扑克(去掉大小王)翻出四张,如果四张牌数字一样,赢400元,否则输一元。请问长期玩这个游戏能赢钱吗

标签: 游戏 小王 扑克
答案:
解析:
1
收藏
数学天地 趣味数学 开放题 计算 解决
于 2020-03-15 21:51提供 来源:33IQ网
(1)
在三维坐标系中,有A,B,C三点,问是否存在一点P到A,B,C三个点的距离相等?
答案:
解析:
3
收藏
数学天地 趣味数学 开放题 计算 求助
于 2020-03-09 11:09提供 来源:33IQ网
(3)
一个在书《陶哲轩教你学数学》中看到的问题,

有个男孩站在一个圆形泳池(半径为r)中央,他的游泳速度为v,他的老师(不会游泳)站在泳池的边缘。那么老师要想抓住男孩,所需最小速度是多少?或者找到一个下界(为男孩设计一个逃脱策略),并计算出一个上界(为老师设计一套完美的移动策略)
标签: 男孩 老师 游泳
10
答案:
解析:
1
收藏
数学天地 趣味数学 开放题 计算 原创
感谢 匿名网友 于 2016-01-16 21:42:11 提供
(11)

   在一个阴暗的角落里,有几个人交流。已知其中有2个傻子,2个疯子,1个普通人,1个高智商的人,2个幸运儿(只有这几类人)。

   他们正在做一套题,这套题包含10个选择题,2分一个;10个判断题,2分一个;10个填空题,2分1个;10个简答题,4分一个,总分为100分。

   其中,我们知道,傻子选择题的正确可能性是20%,填空题不可能正确,判断题的正确可能性是50%,简答题不可能正确;疯子简答题不可能正确,其余所有题的正确可能性都是10%;普通人简答题的正确可能性是75%,其余题做对的可能性是50%;高智商简答题一定做对,其余所有题的正确可能性都是80%;幸运儿选择题和判断题一定能作对,其余题做对的可能性是%30。

   问,有几种情况?并列出及格率(精确至xx%) 的几种可能 。

标签: 正确 可能性
最后修改于 2021-11-10 09:34:10
著作权归作者所有,转载请联系作者获得授权
答案:
解析:
6
收藏

开放题趣味数学题库提供各类与趣味数学相关的数学题解答以及各类小学趣味数学、趣味数学故事等。

如果你有其他有关趣味数学的好题目,欢迎与我们分享 请发布趣味数学的智力题