鱼C论坛

 找回密码
 立即注册
查看: 7332|回复: 56

[技术交流] Python:每日一题 13

[复制链接]
发表于 2017-3-26 18:56:59 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 新手·ing 于 2017-3-30 21:17 编辑

一个由n个数字构成的环,每次变化后,每个数字会变成自己和后面一个数的和,最后一个数的后面是第一个数。
当数字大于100时,取模。
给出这个手环开始的n个数字,循环次数k,循环后的数值。
要求 2<=n<=50, 1<=k<=20000000;
注意,一定使得运算可以满足以上n,k的要求(所以,不要认为一个小数字你可以算出来,大数字就一定能算的出来,尽量让计算在有限的时间内完成)。

以上是我精炼以后的题目,为防止我理解的不准确,下图是原题
QQ图片20170326185636.jpg

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| 发表于 2017-3-26 18:59:33 | 显示全部楼层
其实基本的算法我也弄出来了,但是不能满足2000万次的需求。
各位不妨试试看n=50,k=20000000,能不能算。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-26 19:35:57 | 显示全部楼层
本帖最后由 jerryxjr1220 于 2017-4-2 06:27 编辑
ooxx7788 发表于 2017-3-26 18:59
其实基本的算法我也弄出来了,但是不能满足2000万次的需求。
各位不妨试试看n=50,k=20000000,能不能算。

  1. # coding:utf-8
  2. class ring(object):
  3.     def __init__(self, numbers):
  4.         self.rings = []
  5.         for num in numbers:
  6.             self.rings.append(int(num))

  7.     def magic(self, n, k):
  8.         for i in range(k):
  9.             first = self.rings[0]
  10.             for j in range(n - 1):
  11.                 self.rings[j] += self.rings[j + 1]
  12.                 if self.rings[j] >= 100:
  13.                     self.rings[j] %= 100
  14.             self.rings[n - 1] += first
  15.             if self.rings[n - 1] >= 100:
  16.                 self.rings[n - 1] %= 100
  17.         return self.rings

  18. print "Input  n and k:"
  19. n, k = raw_input().split()
  20. n, k = int(n), int(k)
  21. print "Input the numbers of the rings:"
  22. numbers = raw_input().split()

  23. MagicRing = ring(numbers)
  24. print MagicRing.magic(n, k)
复制代码


题目本身没难度,只是当n=50, k=20000000的时候,运算慢了一些,不过也还行,就几分钟
举例,当n=5,k=100时:
Input  n and k:
5 100
Input the numbers of the rings:
1 2 3 4 5
[1, 77, 28, 79, 55]

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

使用道具 举报

发表于 2017-3-26 19:39:32 | 显示全部楼层
大兄弟
添加到淘专辑...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-26 20:22:55 | 显示全部楼层
本帖最后由 ooxx7788 于 2017-3-26 20:23 编辑
jerryxjr1220 发表于 2017-3-26 19:35
题目本身没难度,只是当n=50, k=20000000的时候,运算慢了一些,不过也还行,就几秒钟
举例,当n=5 ...


大佬,我用的你程序,改成3.0的语法,设定n=50,k=2000万,跑了大概6-7分钟跑出来结果来。
不过确实比我写的要快很多,我自己写的在n=50的情况下,差不多要15-20分钟才能出结果。我仔细看了下,除了你是在类里面做运算外,虽然主要步骤相似,但确实自己也设置一些多余的步骤。
之所以,我会列这个题目出来,正是因为,我也认为在本身程序在计算上面好像没什么难度。所以速度就比较重要。
我研究以后发现,这个数列循环根据n的数值不同,会出现不同的循环,但是循环的起始数是不一定的。
比如n=6的时候,是120数是一个循环周期。
n=7是4340个数一个循环周期。
n=8是120个数一个循环周期。
n=9是39060个数为一个循环周期。
也正是想看看各位大佬是不是能找出其中规律。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-3-26 20:24:19 | 显示全部楼层
新手·ing 发表于 2017-3-26 19:39
大兄弟
添加到淘专辑...

大哥,怎么弄啊?没找到标签在哪里啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-3-26 20:25:08 | 显示全部楼层
ooxx7788 发表于 2017-3-26 20:24
大哥,怎么弄啊?没找到标签在哪里啊

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

使用道具 举报

发表于 2017-3-26 20:36:17 | 显示全部楼层
ooxx7788 发表于 2017-3-26 20:22
大佬,我用的你程序,改成3.0的语法,设定n=50,k=2000万,跑了大概6-7分钟跑出来结果来。
不过确实比 ...

没仔细看各个n和k之间的关系,如果确实是有循环关系的话,你可以建一个字典,把所有计算过的循环周期放到字典里,那么下次再碰到的话,就直接字典读取,速度可以快很多,我只是随便写写,没太多研究。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-1 21:41:55 | 显示全部楼层
试着写了一个,还是用字典的方式,能行,测试了几个,完全正确
  1. def newdic(dic):
  2.     dic1 ={}
  3.     for i in dic:
  4.         dic1[i] = dic[i]
  5.     # print(dic1)
  6.     for a in dic:
  7.         if a == len(dic):
  8.             dic[a] = dic1[a] + dic1[1]
  9.         else:
  10.             dic[a] = dic[a] +dic[a+1]
  11.     return dic

  12. def test13(n,k):
  13.     start_dic = {}
  14.     for i in range(1,n+1):
  15.         start_dic[i] = i
  16.     t = k-1
  17.     while t:
  18.         newdic(start_dic)
  19.         t -= 1
  20.     last_dic =  newdic(start_dic)
  21.     last_list = []
  22.     for a in last_dic:
  23.         last_list.append(str(last_dic[a]))
  24.     print(last_list)

  25. if __name__ == '__main__':
  26.     test13(7,4)

  27. >>> ['48', '64', '80', '89', '77', '51', '39']
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-1 21:48:36 | 显示全部楼层
本帖最后由 gopythoner 于 2017-4-1 21:52 编辑
gopythoner 发表于 2017-4-1 21:41
试着写了一个,还是用字典的方式,能行,测试了几个,完全正确



我忘了一个问题,超过100的要减去100,我居然没写,难怪我随想取个k=2000得到了一个459252278109701809693133280471072793608927080835478080191057094730306504556948125542663794556771483508876273597605041775537225886800409875196612911040385751230521520209363724686486585553001191634596380472819043816462438769254127526429934038036458065818107828927538409140622037880952576198671631977475250259488913806994444843864495059465641426110816316710194014889691663729746622248069879584042761197029440659371728990372191243792583206203371501836803779297114806979115806580847837986241896690126318256913159523700508055766702598211413659561286862157558968946406194562319480896817608776630667090291253178
这么长的数,我还觉得奇怪,这个手表怎么这么傻

加了两行判断,搞定
  1. def newdic(dic):
  2.     dic1 ={}
  3.     for i in dic:
  4.         dic1[i] = dic[i]
  5.     # print(dic1)
  6.     for a in dic:
  7.         if a == len(dic):
  8.             dic[a] = dic1[a] + dic1[1]
  9.             if dic[a] >= 100:
  10.                 dic[a] = dic[a]-100
  11.         else:
  12.             dic[a] = dic[a] +dic[a+1]
  13.             if dic[a] >= 100:
  14.                 dic[a] = dic[a]-100
  15.     return dic

  16. def test13(n,k):
  17.     start_dic = {}
  18.     for i in range(1,n+1):
  19.         start_dic[i] = i
  20.     t = k-1
  21.     while t:
  22.         newdic(start_dic)
  23.         t -= 1
  24.     last_dic =  newdic(start_dic)
  25.     last_list = []
  26.     for a in last_dic:
  27.         last_list.append(str(last_dic[a]))
  28.     print(last_list)

  29. if __name__ == '__main__':
  30.     test13(7,2000)

  31. >>> ['78', '30', '99', '14', '4', '94', '9']
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2017-4-1 21:55:30 | 显示全部楼层
gopythoner 发表于 2017-4-1 21:48
我忘了一个问题,超过100的要减去100,我居然没写,难怪我随想取个k=2000得到了一个4592522 ...

这个题目不在于怎么算出k=2000时候,这个数字是多少,而在于n=50 ,k =2000万的时候,计算的时间,在这个题目里面,更看重的是效率。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-1 22:14:21 | 显示全部楼层
ooxx7788 发表于 2017-4-1 21:55
这个题目不在于怎么算出k=2000时候,这个数字是多少,而在于n=50 ,k =2000万的时候,计算的时间,在这个 ...

试了一下,运行花了9分多钟
  1. if __name__ == '__main__':
  2.     start = datetime.datetime.now()
  3.     test13(50,20000000)
  4.     end = datetime.datetime.now()
  5.     print(end-start)
复制代码


看结果
  1. ['26', '2', '28', '4', '30', '6', '82', '58', '34', '10', '86', '62', '38', '14', '40', '16', '42', '18', '44', '20', '96', '72', '48', '24', '0', '76', '52', '28', '4', '80', '56', '32', '58', '34', '60', '36', '62', '38', '14', '90', '66', '42', '18', '94', '70', '46', '72', '48', '74', '50']

  2. 0:09:24.525067
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-5 15:14:28 | 显示全部楼层

  1. import time


  2. n, k = input('input n and k: ').split()
  3. n = int(n)
  4. k = int(k)
  5. print('起始%s个数字,循环%s次。'%(n, k))


  6. def ring(lst, n):
  7.     for i in range(n):
  8.         lst1 = lst[:]
  9.         lst2 = lst[:]
  10.         lst2.insert(0, lst2.pop())
  11.         lst = list(map(lambda x, y: (x + y)%100, lst1, lst2))
  12.     return lst

  13. #    Test:

  14. t1 = time.time()
  15. numbers = [int(i) for i in input('请输入%d个数字:\n' % n).split()]
  16. print(ring(numbers, k))
  17. print(time.time() - t1)

  18. ##    >>>
  19. ##    input n and k: 5 20000000
  20. ##    起始5个数字,循环20000000次。
  21. ##    请输入5个数字:
  22. ##    1 2 3 4 5
  23. ##    [1, 52, 28, 4, 55]
  24. ##    98.328125
复制代码


两千万次,98秒。
2亿次估计980秒左右?15分钟?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-11 21:43:42 | 显示全部楼层
先贴上我的代码,因为答案还在跑。。。
输入50个数字太累了,我就随机生成了,验证过代码,大家帖出来的和我这个跑的结果是一样的,所以代码准确性没问题,就等50--2000万跑完看下时间吧
  1. import random,time
  2. time1=time.time()
  3. n=50
  4. k=20000000
  5. c=[]
  6. #c=[1,2,3,4,5]
  7. for i in range(n):
  8.     c.append(random.randint(1,100))   
  9. cs=[1 if i==0 else 0 for i in range(n+1)]
  10. ta=[]
  11. for j in range(n+1):
  12.     for i in range(n-j):
  13.         cs[i+1]+=cs[i]
  14.     ta.append(cs[-1])
  15.     del cs[-1]
  16. ta[0]+=ta[-1]
  17. del ta[-1]   
  18. k_n=k//n
  19. kn=k%n
  20. for i in range(k_n):
  21.     cc=c.copy()
  22.     for j in range(n):
  23.         xx=0
  24.         for k in range(n):
  25.             xx=xx+(cc[k]*ta[k])%100
  26.         c[j]=xx%100
  27.         cc=cc[1:]+cc[:1]

  28. for i in range(kn):
  29.     c.append(c[0])
  30.     for j in range(n):
  31.         c[j]=(c[j]+c[j+1])%100
  32.     del c[-1]
  33. print(c,time.time()-time1)
复制代码


5分钟了还没出来。。。。测试的时候有一次只有300秒多一点诶。。。
  1. RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py
  2. [32, 0, 46, 26, 39, 61, 56, 9, 2, 51, 8, 61, 14, 49, 22, 18, 14, 67, 0, 74, 91, 49, 57, 79, 57, 57, 0, 71, 76, 39, 36, 31, 9, 2, 1, 8, 11, 14, 24, 22, 43, 39, 92, 0, 99, 41, 74, 57, 29, 7] 358.1024820804596
  3. >>>
复制代码

不知道是不是因为在操作电脑,比之前测试多跑了将近1分钟
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-26 13:48:23 | 显示全部楼层
学习了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-4-29 21:52:12 | 显示全部楼层
没找着规律啊
直接这么硬来的话,写了两个函数,50个数,2千万次循环耗时 358s和435s
  1. import numpy as np
  2. def magic_count(a, k):
  3.     """输入数组a , 循环k次,返回结果数组"""
  4.     for i in range(k):
  5.         b = np.append(a[1:], a[0]) #将第一个元素放到最后,等于数组逆时针转一格
  6.         a = (a + b) % 100          # 余100不影响小于100的值
  7.     return a
复制代码

有个for循环在,numpy估计不是这样用的,哪位兄台能指点一下···
  1. def magic_count2(n, k):
  2.     """试着不用 numpy ,传入列表n, 循环次数k"""
  3.     a = n[:]
  4.     loop_num = len(a)
  5.     for j in range(k):
  6.         b = a[1:]
  7.         b.append(a[0])
  8.         for i in range(loop_num):
  9.             a[i] = (a[i] + b[i]) %100
  10.     return a
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-1 11:15:13 | 显示全部楼层
  1. class Magical:
  2.   def __init__(self,number):
  3.     self.numbers=[]
  4.     for i in number:
  5.       i=int(i)
  6.       self.numbers.append(i)

  7.   def magic(self,n,k):
  8.     for each1 in range(k):
  9.       first=self.numbers[0]
  10.       for each2 in range(n-1):
  11.         self.numbers[each2]+=self.numbers[each2+1]
  12.         if self.numbers[each2]>100:
  13.             self.numbers[each2]%=100
  14.         each2 += 1
  15.       self.numbers[n-1]=self.numbers[n-1]+first
  16.       if self.numbers[n-1] > 100:
  17.           self.numbers[n-1]%= 100
  18.       each1+=1
  19.     return self.numbers

  20. n=int(input('请输入个数'))
  21. k=int(input('请输入变化次数'))
  22. number=input('请输入数字串').split(' ')
  23. magicring=Magical(number)
  24. magicring.magic(n,k)
  25. print(magicring.numbers)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-22 19:59:54 | 显示全部楼层
  1. n = int(input('请输入手环上的数字个数:'))
  2. k = int(input('请输入循环次数:'))
  3. temp = str(input('请依次输入%d个数,以空格隔开:'%n)).split()
  4. ring = []
  5. for each in temp:
  6.     ring.append(int(each))
  7. while k > 0:
  8.     first = ring[0]
  9.     for i in range(n - 1):
  10.         ring[i] += ring[i + 1]
  11.         if ring[i] > 100:
  12.             ring[i] = ring[i] % 100
  13.     ring[-1] += first
  14.     if ring[-1] > 100:
  15.         ring[-1] = ring[-1] % 100
  16.     k -= 1
  17. print(ring)
  18.         
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-8-24 21:21:43 | 显示全部楼层
  1. print('___________magic wrist________')
  2. n= int(input('请输入手环开启时的数字n_'))
  3. k= int(input('请输入手环进行循环的次数k_'))
  4. temp=str(input('请输入%d个数,以空格隔开:'%n)).split()
  5. #只有str才能使用split进行切片,方法是str.split()或('',1)分割次数,
  6. #  ''中填, ; * \n 4种分隔符
  7. ring=[]
  8. for i in temp:
  9.     ring.append(int(i))

  10. #输入项完成
  11. #定义函数,使数字大于100时取模
  12. import operator
  13. def manage(n):
  14.     if n>100:
  15.         x=operator.mod(n,100)
  16.         return x
  17.     else:
  18.         return n
  19. number=1
  20. while number<=k:
  21.     the_last=ring[-1]
  22.     for j in range(n-1,0,-1):
  23.         ring[j]=ring[j]+ring[j-1]#实现除首项外的手环要求
  24.         ring[j]=manage(ring[j])
  25.     ring[0]=the_last+ring[0]#实现未处理前的项数要求
  26.     ring[0]=manage(ring[0])
  27.     #处理生成的新数组
  28.     number+=1
  29. #   
  30. print(ring)
复制代码



学Python第三天。。注释后边的都算是我的笔记吧。。算n=8,k=2000000 用了14s左右吧。觉得还可以。希望可以多多交流
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2017-9-14 22:33:42 | 显示全部楼层
  1. def Take_Mold(n):
  2.     if n >= 100:
  3.         n = n % 100
  4.     return n

  5. def Magic_Ring(ring, loop):
  6.     number = 1
  7.     count = len(ring)
  8.    
  9.     while number <= loop:
  10.         first = ring[0]
  11.         
  12.         for i in range(count - 1):
  13.             ring[i] = Take_Mold(ring[i] + ring[i + 1])

  14.         ring[count - 1] = Take_Mold(ring[count - 1] + first)
  15.         number += 1
  16.         
  17.     return ring


  18. ring = [1, 2, 3, 4, 5, 65]
  19. print ring
  20. print
  21. print Magic_Ring(ring, 200000)
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

本版积分规则

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

GMT+8, 2024-3-29 08:55

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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