×
通过社交网站直接登录
×
条@我的评论,查看@我
条新私信,查看私信
条新评论,查看评论
位新粉丝 查看粉丝
数学天地 趣味数学 开放题 计算 解决
感谢 匿名网友 于 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
收藏
数学天地 趣味数学 选择题 计算 原创
于 2019-12-18 11:30提供
(16)

小D每天上下班需要乘坐公交车和地铁,已知乘坐公交车的价格为1元/次,乘坐地铁价格为5元/次,小D每天上班先乘坐公交车到地铁站,再乘坐地铁到公司,下班是先乘坐地铁,再乘坐公交车,当你换乘时,可以享受换乘优惠1元,现在小D参加了“今日刷,明日返”的优惠活动,最高每天返3元,即当天交通卡刷卡消费超过3元,明天就返3元到你的交通卡里,活动持续10天,即最高返30元,又当你的交通卡在当月消费满70元,后面乘坐地铁的消费金额享受9折优惠,而小D周末不用公交卡,假如现在是2019年12月1日,小D不想在本月充值公交卡,那么他至少要在公交卡里预留多少钱?(精确到整数)

标签: 地铁 公交车
著作权归作者所有,转载请注明出处
答案:
解析:
17
收藏
数学天地 趣味数学 选择题 计算 原创
于 2019-11-15 12:16提供 来源:33IQ网
(21)

假如现在国家要进行一项工程,需要将图中9个城市用某种特殊缆线连接(只要任意两个城市之间都有至少一条通路即可,例如“北京”和“贵阳”,可以通过“北京”——“郑州”——“株洲”——“贵阳”连接起来)。

图中显示的是所有允许用缆线连接的城市以及连接的成本如图所示。
现在我们来讨论解决类似问题的方法
①首先连接整幅图中成本最小的连接线,也就是“郑州”——“徐州”。之后把“郑州”和“徐州”看为一个整体,寻找其他城市中与他们之一相连成本最小的城市,也就是“徐州”——“上海”。然后将三个连接过的城市看为一个整体,找出其他城市与这三个城市之一连接成本最小的城市,也就是“北京”——“郑州”。就像这样,直到所有城市都连为一体。

②从每个城市出发,都有若干个允许连接的城市。首先对所有城市,连接它们与从它们出发允许连接的城市中连接成本最小的。例如从“郑州”出发,要连接“郑州”——“徐州”;从“贵阳”出发,要连接“贵阳”——“柳州”;从“柳州”出发,也要连接“贵阳”,但是已经连接过,就不用再连接。从“昆明”出发,应该与“贵阳”相连,虽然“贵阳”已经与“柳州”相连,但是仍然需要“昆明”与贵阳相连。如此一来,图中出现了若干个连为一体的城市集(例如“上海”“徐州”“郑州”“北京”四个城市被连为一体),然后对于每一个城市集,找出它们与其他城市集之间连接的成本最小线路。例如“上海”“徐州”“郑州”“北京”四个城市形成的城市集,与图中剩余5个城市形成的城市集之间,存在“郑州”——“成都”,“郑州”——“株洲”,“上海”——“株洲”。而我们要选择的是成本最小的“郑州”——“株洲”。就这样,直到所有城市连为一体。

上面说的方法①和方法②,都成功找出了图中的最优解。可是,这两种方法是否具有普适性,解决任意类似问题呢?

(答案提示中,是一个结论,这个结论是本题的关键)

标签: 工程 最优解
著作权归作者所有,转载请联系作者获得授权
答案:
解析:
16
收藏
数学天地 趣味数学 选择题 计算 原创
于 2015-08-31 16:00提供
(101)

某网举办每日签到抽奖赢好礼活动,大奖是中奖几率仅1%、价值3319元的写真集(什么人的写真集值3319?漏了小数点吧?。。。呃,反正这不是重点)。用户每天签到后,在抽奖之前可以在下面两个选项里任选其一,提高中奖概率:

1、前一天的中奖率提高20%(如第一天是1%,第二天就是1.2%,第三天就是1.44%,以此类推)

2、前一天的中奖率加4%(如第一天是1%,第二天就是5%,第三天就是9%,以此类推)

当中奖几率超过100%后,就一定会中奖,请问运气最差的情况下,最少需要多少天才能抽中写真集?(第一天从中奖率1%开始算起)

该题最近被收录于题集 等待学识解锁解析
最后修改于 2022-11-24 16:35:29
著作权归作者所有,转载请联系作者获得授权
答案:
解析:
78
收藏
数学天地 趣味数学 开放题 计算 原创
感谢 匿名网友 于 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
收藏

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

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