免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 6242 | 回复: 25

用python来做这个题目,还真好玩! [复制链接]

论坛徽章:
11
2015年迎新春徽章
日期:2015-03-04 09:55:282017金鸡报晓
日期:2017-02-08 10:39:4215-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:1715-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:2015-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:1215-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:182016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52每日论坛发贴之星
日期:2016-02-07 06:20:00程序设计版块每日发帖之星
日期:2016-02-07 06:20:0015-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37
发表于 2014-08-13 13:00 |显示全部楼层
"""
给定一个正整数x,我们定义函数w(x)表示x的各个数位之和,例如w(1)=1 w(11)=2 w(223)= 7。
我们定义一种顺序,对正整数x和y, 如果w(x)<w(y) 或者w(x) == w(y)并且x的字典序比y小(按字符串算),则认为x“小于”y。
例如 我们认为100 “小于” 2 因为w(100) = 1 w(2) = 2
我们认为 370 ”小于” 55  这是因为字符串w(370) = w(55) = 10 但是”370” < “55”
给定正整数n和k,1<=k<=n,我们把1-n之间全部的正整数按上述关系由“小”到“大”排好顺序,请问k在第几个位置?另外,第k个位置的数是几?
输入格式
多组数据,每组数据一行包含两个整数n和k,(1<=k<=n<=10^1
输出格式
每组数据一行,包含两个空格分隔的整数,第一个是k的位置,第二个是第k个整数。
"""

注意啊,千万别想用穷举的方法上面的题目,在n=100000时光测试就耗时不少
穷举法是用来做小范围测试的

论坛徽章:
33
荣誉会员
日期:2011-11-23 16:44:17天秤座
日期:2014-08-26 16:18:20天秤座
日期:2014-08-29 10:12:18丑牛
日期:2014-08-29 16:06:45丑牛
日期:2014-09-03 10:28:58射手座
日期:2014-09-03 16:01:17寅虎
日期:2014-09-11 14:24:21天蝎座
日期:2014-09-17 08:33:55IT运维版块每日发帖之星
日期:2016-04-17 06:23:27操作系统版块每日发帖之星
日期:2016-04-18 06:20:00IT运维版块每日发帖之星
日期:2016-04-24 06:20:0015-16赛季CBA联赛之天津
日期:2016-05-06 12:46:59
发表于 2014-08-13 14:26 |显示全部楼层
实在没看出来这个题有什么现实意义.

如果有现实的意义, 我倒觉得可能会有更优化的算法吧.

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2014-08-13 20:19 |显示全部楼层
回复 1# bskay


    穷举法有何不可?
  1. #/usr/bin/python
  2. from time import clock

  3. def csdn618(n, k):
  4.     lst = sorted((sum(map(int, str(i))), str(i)) for i in range(1, n + 1))

  5.     strk = str(k)
  6.     for i,e in enumerate(lst):
  7.         if strk == e[1]:
  8.             index = i + 1
  9.             break

  10.     return index, int(lst[k - 1][1])
  11. start = clock()
  12. print(csdn618(100000, 10000))
  13. end = clock()
  14. print(end - start)
复制代码
i5处理器,在n=100000时,不到半秒就出来了,这速度很难接受吗?如果需要经常要计算这个,还是可以优化的,事先算好保存起来,以后只管查询就可以了。

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
发表于 2014-08-13 22:03 |显示全部楼层
暂时还是看不懂

论坛徽章:
11
2015年迎新春徽章
日期:2015-03-04 09:55:282017金鸡报晓
日期:2017-02-08 10:39:4215-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:1715-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:2015-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:1215-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:182016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52每日论坛发贴之星
日期:2016-02-07 06:20:00程序设计版块每日发帖之星
日期:2016-02-07 06:20:0015-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37
发表于 2014-08-16 23:46 |显示全部楼层
本帖最后由 bskay 于 2014-08-16 23:52 编辑

回复 3# ssfjhh


    n=10000000(1千万时看看穷举的效率,哈哈)
输入格式
多组数据,每组数据一行包含两个整数n和k,( 1<=k<=n<=10^18 ) 。
输出格式
每组数据一行,包含两个空格分隔的整数,第一个是k的位置,第二个是第k个整数。

怎么转义变成笑脸了

论坛徽章:
11
2015年迎新春徽章
日期:2015-03-04 09:55:282017金鸡报晓
日期:2017-02-08 10:39:4215-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:1715-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:2015-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:1215-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:182016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52每日论坛发贴之星
日期:2016-02-07 06:20:00程序设计版块每日发帖之星
日期:2016-02-07 06:20:0015-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37
发表于 2014-08-16 23:56 |显示全部楼层
回复 2# q1208c


    这个题目我也没看出有什么现实意义,非要说有的话,那就是锻炼一下自己的逻辑分析能力,动手测试能力
很久没有锻炼了,汗,这个问题我差不多做了2周,现在才算彻底解决。。。。

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2014-08-17 02:30 |显示全部楼层
bskay 发表于 2014-08-16 23:46
回复 3# ssfjhh



你自己说的话:
注意啊,千万别想用穷举的方法上面的题目,在n=100000时光测试就耗时不少


我写出程序,发现不到半秒搞定。

结果你又提出要测试n=10000000,我测试出来了,31秒。

QQ图片20140817022832.png


很难接受吗?

论坛徽章:
11
2015年迎新春徽章
日期:2015-03-04 09:55:282017金鸡报晓
日期:2017-02-08 10:39:4215-16赛季CBA联赛之辽宁
日期:2016-12-15 10:24:1715-16赛季CBA联赛之佛山
日期:2016-11-30 09:04:2015-16赛季CBA联赛之江苏
日期:2016-04-29 15:56:1215-16赛季CBA联赛之同曦
日期:2016-04-12 13:21:182016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之山东
日期:2016-02-16 11:37:52每日论坛发贴之星
日期:2016-02-07 06:20:00程序设计版块每日发帖之星
日期:2016-02-07 06:20:0015-16赛季CBA联赛之新疆
日期:2018-01-09 16:25:37
发表于 2014-08-17 12:19 |显示全部楼层
本帖最后由 bskay 于 2014-08-17 12:25 编辑

回复 7# ssfjhh


    这个题目你可以找找原题目,输入数据的范围是1到10的18次方,
处理的数据也不是一个两个的

呵呵,多想想、并且,你只做了K在哪个位置,还有第k个位置是什么数呢。。。。。。。要多想想

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2014-08-17 18:01 |显示全部楼层
回复 8# bskay


    放你的方法吧。

论坛徽章:
4
金牛座
日期:2013-10-11 16:12:50卯兔
日期:2014-07-31 09:17:19辰龙
日期:2014-08-08 09:28:02狮子座
日期:2014-09-14 20:32:05
发表于 2014-08-18 09:12 |显示全部楼层
回复 8# bskay


    你没有看我的代码是有K的位置的。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP