×
通过社交网站直接登录
×
条@我的评论,查看@我
条新私信,查看私信
条新评论,查看评论
位新粉丝 查看粉丝
数学天地 趣味数学 开放题 计算 解决
感谢 匿名网友 于 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-02-04 17:01:31 提供
(22)

2006青少年数学国际城市邀请赛

一座大楼有4部电梯,每部电梯可停靠三层(不一定是连续三层,也不一定停最底层)。对大楼中的任意的两层,至少有一部电梯可同时停靠。请问这座大楼最多有几层?


标签: 竞赛 系列
最后修改于 2022-12-13 17:00:25
答案:
解析:
19
收藏
数学天地 趣味数学 选择题 计算
感谢 匿名网友 于 2020-02-01 18:30:35 提供
(21)

水洼里有19条蓝色变形虫和95条红色变形虫。有时它们会发生互变:如果2条红色变形虫相遇,会变成1条蓝色变形虫;如果2条蓝色变形虫相遇,在变成1条变形虫之后又立即分裂为4条红色变形虫;而1条红色变形虫与1条蓝色变形虫相遇,则在变成1条变形虫之后又立即分裂为3条红色变形虫。到了晚上,水洼里一共有100条变形虫。试问:其中有多少条蓝色变形虫?

标签: 系列 竞赛
最后修改于 2022-12-13 17:19:06
答案:
解析:
16
收藏
数学天地 趣味数学 选择题 计算
感谢 匿名网友 于 2020-02-04 17:08:10 提供 来源:33IQ网
(42)

“我发现你有一只猫”,小明对小芳说,“我确实非常喜欢它可爱的白尾巴!你有几只猫啊”?“不是很多”,小芳说,“隔壁的叔叔有20只猫,比我的多多了”。“你还没有告诉我你有几只猫呢!”“嗯......这么说吧,如果你随机选择我的两只猫,那么它们都有白尾巴的概率恰好是百分之五十”。“可你还是没有告诉我你有几只猫”!“我已经告诉你了”。请问小芳有几只猫?其中几只有白尾巴?

标签: 尾巴 小芳 概率
该题最近被收录于题集 回答正确
最后修改于 2022-12-13 17:36:34
答案:
解析:
36
收藏
数学天地 趣味数学 选择题 计算
感谢 匿名网友 于 2020-02-14 18:49:17 提供
(26)

在小于1000000的正整数中,最后两位数字相同(不能是00)的平方数有多少个?

标签: 系列
该题最近被收录于题集 好方法
最后修改于 2022-12-13 17:48:01
答案:
解析:
24
收藏
数学天地 趣味数学 选择题 计算 原创
于 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
收藏
数学天地 趣味数学 开放题 计算 解决
于 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
收藏
数学天地 趣味数学 选择题 计算
感谢 匿名网友 于 2020-02-04 17:06:31 提供
(12)

第43届IMO预选题

设T是由有序三元数组(x,y,z)组成的集合,其中x、y、z是整数,且0≤x,y,z≤9。甲、乙两人玩下面的游戏:甲在T中选一个三元数组(x,y,z),乙不得不用几次“运动”来猜甲所选的三元数组。一次“运动”为:乙给甲一个T中的三元数组(a,b,c),甲回答乙的数是|x+y-a-b|+|y+z-b-c|+|z+x-c-a|。求“运动”次数的最小值,使得乙能知道甲所选的三元数组。

标签: 系列 竞赛
最后修改于 2022-12-13 13:31:17
答案:
解析:
10
收藏
数学天地 趣味数学 选择题 计算 原创
于 2019-11-15 12:16提供 来源:33IQ网
(21)

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

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

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

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

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

标签: 工程 最优解
著作权归作者所有,转载请联系作者获得授权
答案:
解析:
16
收藏
数学天地 趣味数学 选择题 计算
于 2018-07-12 14:24提供
(53)

如图是一个平衡体系,其中一个秤砣的质量已给出,你能知道问号处的秤砣质量是多少吗?(忽略杆和绳的质量)

标签: 秤砣 质量 问号
最后修改于 2022-09-06 09:47:59
答案:
解析:
47
收藏
数学天地 趣味数学 选择题 计算
于 2017-10-08 11:19提供
(35)

幻方问题系列——烦人的8

我们知道,把1-9这9个数字组成三阶幻方,就必须在一个角上填上8。

那么,如果要求你在图中的位置填上8,其余空位填入任意不重复的数,你能完成这个幻方吗?


标签: 位置 烦人 系列
该题最近被收录于题集 回答正确
最后修改于 2022-03-15 08:58:07
答案:
解析:
23
收藏
数学天地 趣味数学 选择题 计算
感谢 匿名网友 于 2014-01-25 20:25:53 提供
(138)

目前全国正确率仅为13.2%的题目:

下面等式转换成立的是:(     )。

① 当 a/b = c/b 时, a=c

② 当 b/a = b/c 时, a=c

③ 当 a=c,b≠0 时 , a/b = c/b

④ 当 a=c 时 , b/a = b/c

该题最近被收录于题集 说谎者精选题
最后修改于 2022-10-02 12:59:11
答案:
解析:
80
收藏
数学天地 趣味数学 选择题 计算 原创
于 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
收藏

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

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