Python：每日一题 13

ooxx7788

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

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

ooxx7788

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

jerryxjr1220

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[0]
            for j in range(n - 1):
                self.rings[j] += self.rings[j + 1]
                if self.rings[j] >= 100:
                    self.rings[j] %= 100
            self.rings[n - 1] += first
            if self.rings[n - 1] >= 100:
                self.rings[n - 1] %= 100
        return self.rings

print "Input  n 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时：
Input  n and k:
5 100
Input the numbers of the rings:
1 2 3 4 5
[1, 77, 28, 79, 55]

***Repl Closed***

新手·ing

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

ooxx7788

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

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

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

新手·ing

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

我帮你加了...

jerryxjr1220

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

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

gopythoner

试着写了一个，还是用字典的方式，能行，测试了几个，完全正确

def newdic(dic):
    dic1 ={}
    for i in dic:
        dic1[i] = dic[i]
    # print(dic1)
    for a in dic:
        if a == len(dic):
            dic[a] = dic1[a] + dic1[1]
        else:
            dic[a] = dic[a] +dic[a+1]
    return dic

def test13(n,k):
    start_dic = {}
    for i in range(1,n+1):
        start_dic[i] = 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[a]))
    print(last_list)

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

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

gopythoner

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

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

加了两行判断，搞定

def newdic(dic):
    dic1 ={}
    for i in dic:
        dic1[i] = dic[i]
    # print(dic1)
    for a in dic:
        if a == len(dic):
            dic[a] = dic1[a] + dic1[1]
            if dic[a] >= 100:
                dic[a] = dic[a]-100
        else:
            dic[a] = dic[a] +dic[a+1]
            if dic[a] >= 100:
                dic[a] = dic[a]-100
    return dic

def test13(n,k):
    start_dic = {}
    for i in range(1,n+1):
        start_dic[i] = 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[a]))
    print(last_list)

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

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

ooxx7788

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

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

gopythoner

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

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 = [int(i) for i in input('请输入%d个数字：\n' % n).split()]
print(ring(numbers, k))
print(time.time() - t1)

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

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

余欲渔

先贴上我的代码，因为答案还在跑。。。
输入50个数字太累了，我就随机生成了，验证过代码，大家帖出来的和我这个跑的结果是一样的，所以代码准确性没问题，就等50--2000万跑完看下时间吧

import random,time
time1=time.time()
n=50
k=20000000
c=[]
#c=[1,2,3,4,5]
for i in range(n):
    c.append(random.randint(1,100))    
cs=[1 if i==0 else 0 for i in range(n+1)]
ta=[]
for j in range(n+1):
    for i in range(n-j):
        cs[i+1]+=cs[i]
    ta.append(cs[-1])
    del cs[-1]
ta[0]+=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[k]*ta[k])%100
        c[j]=xx%100
        cc=cc[1:]+cc[:1]

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

5分钟了还没出来。。。。测试的时候有一次只有300秒多一点诶。。。

 RESTART: C:\Users\Administrator\AppData\Local\Programs\Python\Python35-32\test.py 
[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
>>>

不知道是不是因为在操作电脑，比之前测试多跑了将近1分钟

willLin

学习了

solomonxian

没找着规律啊
直接这么硬来的话，写了两个函数，50个数，2千万次循环耗时 358s和435s

import numpy as np
def magic_count(a, k):
    """输入数组a ， 循环k次，返回结果数组"""
    for i in range(k):
        b = np.append(a[1:], a[0]) #将第一个元素放到最后，等于数组逆时针转一格
        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[1:]
        b.append(a[0])
        for i in range(loop_num):
            a[i] = (a[i] + b[i]) %100
    return a

Bekkkkkahhh

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[0]
      for each2 in range(n-1):
        self.numbers[each2]+=self.numbers[each2+1]
        if self.numbers[each2]>100:
            self.numbers[each2]%=100
        each2 += 1
      self.numbers[n-1]=self.numbers[n-1]+first
      if self.numbers[n-1] > 100:
          self.numbers[n-1]%= 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)

木一

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[0]
    for i in range(n - 1):
        ring[i] += ring[i + 1]
        if ring[i] > 100:
            ring[i] = ring[i] % 100
    ring[-1] += first
    if ring[-1] > 100:
        ring[-1] = ring[-1] % 100
    k -= 1
print(ring)
        

morxrc

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[j]=ring[j]+ring[j-1]#实现除首项外的手环要求
        ring[j]=manage(ring[j])
    ring[0]=the_last+ring[0]#实现未处理前的项数要求
    ring[0]=manage(ring[0])
    #处理生成的新数组
    number+=1
#    
print(ring)

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

gausser

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[0]
        
        for i in range(count - 1):
            ring[i] = Take_Mold(ring[i] + ring[i + 1])

        ring[count - 1] = Take_Mold(ring[count - 1] + first)
        number += 1
        
    return ring


ring = [1, 2, 3, 4, 5, 65]
print ring
print
print Magic_Ring(ring, 200000)