鱼C论坛

 找回密码
 立即注册
查看: 2317|回复: 5

[技术交流] 小练习 20170522 一个googol(10^100)以下有多少数字不是跳跃数?

[复制链接]
发表于 2017-5-21 21:38:09 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-5-29 20:46 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。
什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives
这里已经有了500余题。


                               
登录/注册后可看大图


题目要求:
以python语言完成,如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成,即5.29 10:00之前,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。题目不难,大家看看谁的效率高。

----回帖需写明解题思路,鼓励在程序中加上注释


一些鱼油反映题目有些过难,为此略过一部分偏难的题目。



题目:

如果一个数的每一位都大于等于前一位,则称其为递增数,例如 134468。

类似的,如果一个数的每一位都小于等于前一位,则称其为递减数,例如 66420。

如果一个正整数既不是递增数也不是递减数,则称其为一个“跳跃数”,例如 155349。

随着 n 的增加,小于 n 的跳跃数的比例不断增加,以至于到了一百万以下的数中只有 12951 个不是跳跃数,

                               
登录/注册后可看大图
以下只有 277032 个数不是跳跃数。

一个googol

                               
登录/注册后可看大图
以下的数中有多少个不是跳跃数?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2017-5-21 22:20:12 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-5-21 22:21 编辑

这题计算其实不是很难,关键是解题思路:
先看升序,第一位最小必须是1,最大数只可能是9,所以100位数中,只有8次升序的机会。
那么所有排列组合就是Cn(i+8,i),i从1~100
同理降序,第一位最大是9,最小数可能是0,所以100位数中,可以有9次降序机会。
那么所有排列组合就是Cn(i+9,i),i从1~100
然后,再减去升序和降序都重复的数,i从1~100,每次都有10个数
所以:
  1. from math import factorial as f
  2. print(sum([f(i+8)//f(i)//f(8) for i in range(1, 101)]) + sum([f(i+9)//f(i)//f(9) for i in range(1, 101)]) - 10*100)
复制代码

输出:
51161058134250

评分

参与人数 1荣誉 +10 鱼币 +10 贡献 +10 收起 理由
冬雪雪冬 + 10 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-23 16:35:49 | 显示全部楼层
  1. # -*- coding=utf-8 -*-
  2. #!/usr/bin/python3.4

  3. def not_jump_num_advance(length):
  4.     """
  5.     统计10^length内有多少数不是跳跃数
  6.     """
  7.     if length == 1:
  8.         num_dic = {"equal": list(1 for _ in range(0,10)), "more":[], "less":[]} #一位数均为跳跃数
  9.         count = 9
  10.     elif length == 2:
  11.         num_dic = {"equal": list(0 for _ in range(0,10)), "more": list(0 for _ in range(0,10)), "less": list(0 for _ in range(0,10))} #两位数同理
  12.         
  13.         #num_dic字典有三个键equal, more, less,分别表示从个位向高位依次相等、递增、递减的情况
  14.         #以num_dic["more"]为例:num_dic["more"][3]表示以数字3开头且从个位向高位依次递增的数的个数,最高位为0的情况也统计,但是不计入总数目
  15.         
  16.         for i in range(0,100):
  17.             s = str(i)
  18.             if len(s) < 2:
  19.                 s = "0" + s
  20.             if int(s[1]) < int(s[0]):
  21.                 num_dic["more"][int(s[0])] += 1
  22.             elif int(s[1]) > int(s[0]):
  23.                 num_dic["less"][int(s[0])] += 1
  24.             else:
  25.                 num_dic["equal"][int(s[0])] += 1
  26.         count = 99
  27.     else:
  28.         pre_num_dic, pre_count = not_jump_num_advance(length - 1) #递归获取10^(length-1)之内的统计情况

  29.         equal_list = list(0 for _ in range(0,10)) #初始化各列表
  30.         more_list = list(0 for _ in range(0,10))
  31.         less_list = list(0 for _ in range(0,10))
  32.         
  33.         pre_equal_list = pre_num_dic["equal"]
  34.         pre_more_list = pre_num_dic["more"]
  35.         pre_less_list = pre_num_dic["less"]
  36.         
  37.         for i, c in enumerate(pre_equal_list):
  38.             for x in range(10): #x表示在length-1位的数字最前面添加x构造length位的数字
  39.                 if x > i:
  40.                     more_list[x] += c
  41.                 elif x < i:
  42.                     less_list[x] += c
  43.                 else:
  44.                     equal_list[x] += c
  45.             
  46.         for i, c in enumerate(pre_more_list):
  47.             for x in range(i, 10):
  48.                 more_list[x] += c
  49.                

  50.         for i, c in enumerate(pre_less_list):
  51.             for x in range(0, i+1):
  52.                 less_list[x] += c
  53.                         
  54.         num_dic = {"equal": equal_list, "more": more_list, "less": less_list}
  55.         count = pre_count + \
  56.                 sum(equal_list[1:]) + \
  57.                 sum(more_list[1:]) + \
  58.                 sum(less_list[1:]) #对于最高位为0的数字不计入总数
  59.     return num_dic, count

  60. if __name__ == "__main__":
  61.     length_1 = 6
  62.     length_2 = 10
  63.     length_3 = 100
  64.    
  65.     print("googol(10^6):", not_jump_num_advance(length_1)[1])
  66.     print("googol(10^10):", not_jump_num_advance(length_2)[1])
  67.     print("googol(10^100):", not_jump_num_advance(length_3)[1])
复制代码


答案:51161058134250

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-24 21:19:05 | 显示全部楼层
  1. rincrease=[0]*8
  2. rdecrease=[0]*9
  3. for i in range(10,100):
  4.     ii=i//10
  5.     ii=ii*10+ii
  6.     if i<ii:
  7.         rdecrease[i%10]+=1
  8.     elif i>ii:
  9.         rincrease[i%10-2]+=1

  10. increase=rincrease[:]
  11. decrease=rdecrease[:]
  12. sumnum=99

  13. def nextnum():
  14.     global increase ,decrease,rincrease,rdecrease,sumnum
  15.     temp=rincrease[:]
  16.     for i in range(8):
  17.         for j in range(i, 8):
  18.             temp[j]+=increase[i]

  19.     increase=temp[:]
  20.     temp=rdecrease[:]
  21.     for i in range(9):
  22.         for j in range(i+1):
  23.             temp[j]+=decrease[i]
  24.     decrease=temp[:]
  25.     sumnum+=9
  26.     sumnum+=sum(decrease)
  27.     sumnum+=sum(increase)

  28. for i in range(98):
  29.     nextnum()

  30. print(sumnum)
复制代码


答案  51161058134250

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-5-26 09:57:27 | 显示全部楼层
  1. def permutation(n, m):
  2.     a, b = 1, 1
  3.     for i in range(m):
  4.         a *= (n - i)
  5.         b *= (i + 1)
  6.     return int(a/b)

  7. n = 100
  8. increase = permutation(n + 9, 9) - 1

  9. decrease = 0
  10. for i in range(1, n + 1):
  11.     decrease += permutation(i + 9, 9) - 1

  12. nochange = n*9
  13.    
  14. num = decrease + increase - nochange
  15. print(num)
复制代码

答案是51161058134250,利用排列组合的方法,注意减去递增数和递减数中重复的数

评分

参与人数 1荣誉 +10 鱼币 +10 贡献 +10 收起 理由
冬雪雪冬 + 10 + 10 + 10

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-6-2 17:28:13 | 显示全部楼层
jerryxjr1220 发表于 2017-5-21 22:20
这题计算其实不是很难,关键是解题思路:
先看升序,第一位最小必须是1,最大数只可能是9,所以100位数中 ...

厉害
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 18:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表