论坛 › Python交流 › Python：每日一题 13

ooxx7788 发表于 2017-3-26 18:56:59

Python：每日一题 13

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

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

以上是我精炼以后的题目，为防止我理解的不准确，下图是原题

ooxx7788 发表于 2017-3-26 18:59:33

其实基本的算法我也弄出来了，但是不能满足2000万次的需求。
各位不妨试试看n=50,k=20000000，能不能算。

jerryxjr1220 发表于 2017-3-26 19:35:57

本帖最后由 jerryxjr1220 于 2017-4-2 06:27 编辑

ooxx7788 发表于 2017-3-26 18:59
其实基本的算法我也弄出来了，但是不能满足2000万次的需求。
各位不妨试试看n=50,k=20000000，能不能算。

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

    def magic(self, n, k):
      for i in range(k):
            first = self.rings
            for j in range(n - 1):
                self.rings += self.rings
                if self.rings >= 100:
                  self.rings %= 100
            self.rings += first
            if self.rings >= 100:
                self.rings %= 100
      return self.rings

print "Inputn and k:"
n, k = raw_input().split()
n, k = int(n), int(k)
print "Input the numbers of the rings:"
numbers = raw_input().split()

MagicRing = ring(numbers)
print MagicRing.magic(n, k)

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


***Repl Closed***

新手·ing 发表于 2017-3-26 19:39:32

大兄弟
添加到淘专辑...

ooxx7788 发表于 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个数为一个循环周期。
也正是想看看各位大佬是不是能找出其中规律。

ooxx7788 发表于 2017-3-26 20:24:19

新手·ing 发表于 2017-3-26 19:39
大兄弟
添加到淘专辑...

大哥，怎么弄啊？没找到标签在哪里啊

新手·ing 发表于 2017-3-26 20:25:08

ooxx7788 发表于 2017-3-26 20:24
大哥，怎么弄啊？没找到标签在哪里啊

我帮你加了...

jerryxjr1220 发表于 2017-3-26 20:36:17

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

没仔细看各个n和k之间的关系，如果确实是有循环关系的话，你可以建一个字典，把所有计算过的循环周期放到字典里，那么下次再碰到的话，就直接字典读取，速度可以快很多，我只是随便写写，没太多研究。{:5_97:}

gopythoner 发表于 2017-4-1 21:41:55

试着写了一个，还是用字典的方式，能行，测试了几个，完全正确
def newdic(dic):
    dic1 ={}
    for i in dic:
      dic1 = dic
    # print(dic1)
    for a in dic:
      if a == len(dic):
            dic = dic1 + dic1
      else:
            dic = dic +dic
    return dic

def test13(n,k):
    start_dic = {}
    for i in range(1,n+1):
      start_dic = i
    t = k-1
    while t:
      newdic(start_dic)
      t -= 1
    last_dic =newdic(start_dic)
    last_list = []
    for a in last_dic:
      last_list.append(str(last_dic))
    print(last_list)

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

>>> ['48', '64', '80', '89', '77', '51', '39']

gopythoner 发表于 2017-4-1 21:48:36

本帖最后由 gopythoner 于 2017-4-1 21:52 编辑

gopythoner 发表于 2017-4-1 21:41
试着写了一个，还是用字典的方式，能行，测试了几个，完全正确

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

加了两行判断，搞定
def newdic(dic):
    dic1 ={}
    for i in dic:
      dic1 = dic
    # print(dic1)
    for a in dic:
      if a == len(dic):
            dic = dic1 + dic1
            if dic >= 100:
                dic = dic-100
      else:
            dic = dic +dic
            if dic >= 100:
                dic = dic-100
    return dic

def test13(n,k):
    start_dic = {}
    for i in range(1,n+1):
      start_dic = i
    t = k-1
    while t:
      newdic(start_dic)
      t -= 1
    last_dic =newdic(start_dic)
    last_list = []
    for a in last_dic:
      last_list.append(str(last_dic))
    print(last_list)

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

>>> ['78', '30', '99', '14', '4', '94', '9']

ooxx7788 发表于 2017-4-1 21:55:30

gopythoner 发表于 2017-4-1 21:48
我忘了一个问题，超过100的要减去100，我居然没写，难怪我随想取个k=2000得到了一个4592522 ...

这个题目不在于怎么算出k=2000时候，这个数字是多少，而在于n=50 ,k =2000万的时候，计算的时间，在这个题目里面，更看重的是效率。

gopythoner 发表于 2017-4-1 22:14:21

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

试了一下，运行花了9分多钟
if __name__ == '__main__':
    start = datetime.datetime.now()
    test13(50,20000000)
    end = datetime.datetime.now()
    print(end-start)


看结果
['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']

0:09:24.525067

shigure_takimi 发表于 2017-4-5 15:14:28

import time


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


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

#    Test:

t1 = time.time()
numbers =
print(ring(numbers, k))
print(time.time() - t1)

##    >>>
##    input n and k: 5 20000000
##    起始5个数字，循环20000000次。
##    请输入5个数字：
##    1 2 3 4 5
##   
##    98.328125


两千万次，98秒。
2亿次估计980秒左右？15分钟？

余欲渔 发表于 2017-4-11 21:43:42

先贴上我的代码，因为答案还在跑。。。
输入50个数字太累了，我就随机生成了，验证过代码，大家帖出来的和我这个跑的结果是一样的，所以代码准确性没问题，就等50--2000万跑完看下时间吧
import random,time
time1=time.time()
n=50
k=20000000
c=[]
#c=
for i in range(n):
    c.append(random.randint(1,100))   
cs=
ta=[]
for j in range(n+1):
    for i in range(n-j):
      cs+=cs
    ta.append(cs[-1])
    del cs[-1]
ta+=ta[-1]
del ta[-1]   
k_n=k//n
kn=k%n
for i in range(k_n):
    cc=c.copy()
    for j in range(n):
      xx=0
      for k in range(n):
            xx=xx+(cc*ta)%100
      c=xx%100
      cc=cc+cc[:1]

for i in range(kn):
    c.append(c)
    for j in range(n):
      c=(c+c)%100
    del c[-1]
print(c,time.time()-time1)

5分钟了还没出来。。。。测试的时候有一次只有300秒多一点诶。。。
RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py
358.1024820804596
>>>
不知道是不是因为在操作电脑，比之前测试多跑了将近1分钟

willLin 发表于 2017-4-26 13:48:23

学习了

solomonxian 发表于 2017-4-29 21:52:12

没找着规律啊{:10_266:}
直接这么硬来的话，写了两个函数，50个数，2千万次循环耗时 358s和435s{:10_245:}
import numpy as np
def magic_count(a, k):
    """输入数组a ， 循环k次，返回结果数组"""
    for i in range(k):
      b = np.append(a, a) #将第一个元素放到最后，等于数组逆时针转一格
      a = (a + b) % 100          # 余100不影响小于100的值
    return a
有个for循环在，numpy估计不是这样用的，哪位兄台能指点一下···
def magic_count2(n, k):
    """试着不用 numpy ，传入列表n， 循环次数k"""
    a = n[:]
    loop_num = len(a)
    for j in range(k):
      b = a
      b.append(a)
      for i in range(loop_num):
            a = (a + b) %100
    return a

Bekkkkkahhh 发表于 2017-8-1 11:15:13

class Magical:
def __init__(self,number):
    self.numbers=[]
    for i in number:
      i=int(i)
      self.numbers.append(i)

def magic(self,n,k):
    for each1 in range(k):
      first=self.numbers
      for each2 in range(n-1):
      self.numbers+=self.numbers
      if self.numbers>100:
            self.numbers%=100
      each2 += 1
      self.numbers=self.numbers+first
      if self.numbers > 100:
          self.numbers%= 100
      each1+=1
    return self.numbers

n=int(input('请输入个数'))
k=int(input('请输入变化次数'))
number=input('请输入数字串').split(' ')
magicring=Magical(number)
magicring.magic(n,k)
print(magicring.numbers)

木一 发表于 2017-8-22 19:59:54

n = int(input('请输入手环上的数字个数：'))
k = int(input('请输入循环次数：'))
temp = str(input('请依次输入%d个数，以空格隔开：'%n)).split()
ring = []
for each in temp:
    ring.append(int(each))
while k > 0:
    first = ring
    for i in range(n - 1):
      ring += ring
      if ring > 100:
            ring = ring % 100
    ring[-1] += first
    if ring[-1] > 100:
      ring[-1] = ring[-1] % 100
    k -= 1
print(ring)
      {:10_243:}

morxrc 发表于 2017-8-24 21:21:43

print('___________magic wrist________')
n= int(input('请输入手环开启时的数字n_'))
k= int(input('请输入手环进行循环的次数k_'))
temp=str(input('请输入%d个数，以空格隔开:'%n)).split()
#只有str才能使用split进行切片，方法是str.split()或('',1)分割次数，
#''中填, ; * \n 4种分隔符
ring=[]
for i in temp:
    ring.append(int(i))

#输入项完成
#定义函数，使数字大于100时取模
import operator
def manage(n):
    if n>100:
      x=operator.mod(n,100)
      return x
    else:
      return n
number=1
while number<=k:
    the_last=ring[-1]
    for j in range(n-1,0,-1):
      ring=ring+ring#实现除首项外的手环要求
      ring=manage(ring)
    ring=the_last+ring#实现未处理前的项数要求
    ring=manage(ring)
    #处理生成的新数组
    number+=1
#   
print(ring)



学Python第三天。。注释后边的都算是我的笔记吧。。算n=8，k=2000000 用了14s左右吧。觉得还可以。希望可以多多交流

gausser 发表于 2017-9-14 22:33:42

def Take_Mold(n):
    if n >= 100:
      n = n % 100
    return n

def Magic_Ring(ring, loop):
    number = 1
    count = len(ring)
   
    while number <= loop:
      first = ring
      
      for i in range(count - 1):
            ring = Take_Mold(ring + ring)

      ring = Take_Mold(ring + first)
      number += 1
      
    return ring


ring =
print ring
print
print Magic_Ring(ring, 200000)

查看完整版本: Python：每日一题 13