小练习 ：20170731 有奖字符串

冬雪雪冬

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

                               
登录/注册后可看大图

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成，即8.7 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。题目不难，大家看看谁的效率高。

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


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





题目：

某个学校财大气粗，不迟到、不旷课的好学生会得到现金的奖励。但是，如果学生连续三天不上课或迟到不只一次的话，奖励就没了。（迟到比旷课的惩罚还狠……）

如果以 n 天为一个时间段，则可以为每个孩子构造一个字符串，字符串的每个结点可能是下面三种状态之一： L (迟到次数)，O (准时次数)，或者A (旷课次数)

如果把 4 天分成一个时间段，我们可以得到 81 种组合得到的串，其中，有 43 种情况是可以得到奖励的：

                               
登录/注册后可看大图

那么，如果每 30 天划分成一个时间段，那么，有多少种情况是可以得到奖励的呢？

jerryxjr1220

这题粗看上去还是比较复杂的，一开始我准备穷举所有情况，但是算了一下一共有3**30种可能，然后就放弃了。
换一种思路，可以利用动态规划的思想：
假设没有迟到的情况下，n天获得奖励的情况是F(n)，
那么当第1天为“O”时，f1=F(n-1)
当第1天为“A”,第2天为“O”时，f2=F(n-2)
当第1天为“A”,第2天为“A”，第3天为“O”时，f3=F(n-3)
F(n) = f1+f2+f3 = F(n-1)+F(n-2)+F(n-3), F(0) = 1, F(1) = 2, F(2) = 4
有1天迟到的情况下，把n天看成前i天不迟到+第i天迟到+后n-1-i天不迟到的情况。
F'(n) = sum((F(i)*F(n-1-i) for i in range(n)))
这样只要统计总天数就可以了。
S(n) = F(n) + F'(n)

1. import time
   
2. from functools import lru_cache
   
3. @lru_cache(maxsize=None)
   
4. def F(n):
   
5.         return 2**n if n<3 else F(n-1)+F(n-2)+F(n-3)
   
6. def S(n):
   
7.         return F(n) + sum((F(i)*F(n-1-i) for i in range(n)))
   
8. print(S(30))
   
9. print(time.process_time())

复制代码

1918080160
0.046875
吸取上次的教训，不准用numba，那么内置的functools可以用吧？不要又把我删除了，那用时又长了
不用functools的话，
1918080160
62.56459

suloman

n天分为一个时间段  就有 3**n种可能
然后 把所有的可能 变成3进制的表达方式
这样每个位数上 有 0 1 2分别表示 正常 迟到 旷课
再对这个数 进行判断 是否符合奖励条件
4天 应该 是47种 符合奖励吧
n=int(input("多少天为一个时间段"))
li=[]
total=0
        
for i in range(n):
    li.append(0)

for i in range(3**n):
    temp=i
    wei=n-1
    chi=0
    kuang=0
    dua=True
    while temp / 3 > 0:
        li[wei]=temp%3
        if temp%3==2:
            kuang+=1
            if kuang==3:
                dua=False
        else:
            kuang=0
        if temp%3==1:
            chi+=2
            if chi>=3:
                dua=False
        else:
            if chi!= 0:               
                chi-=1
        temp=temp//3
        wei-=1
    if dua==True:
        total+=1
        
    #print(li,"     ",i,"\n",dua,"   ",total)




print(total)
我想吐槽一下  我迟到一天 旷课两天 再迟到一天 旷课两天 如此循环下去  也能拿到奖励

小Q学Python

有点难啊
L只能出现一次，O随便出现多少次，A不能连续出现三次，根据题目要求我们可以得到以下结论：
1.需要找到A和O的所有排列组合（A不能连续3次）
2.对于上面找到的组合，有多少个O，就可以将其中一个O替换成L（譬如AAOO可以变成AAOL和AALO），有N个O，就对应的N个奖励情况
3.A和O的组合，只有2个元素，利用二进制办法，A代表1，O代表0，方便遍历
4.从0遍历到30个1（20亿次），时间太长了，当中想了个办法，当遍历到111时，直接进位，减少遍历次数（譬如：遇到1110000，直接加10000）
5.但就算这样，还是慢

1. def counts3(n):
   
2.     counts = 0  # 计数
   
3.     max = int('1'*n,2)  # 最大值（30个“1”二进制）
   
4.     i = 0
   
5.     while i <= max:
   
6.         str1 = str(bin(i))[2:]
   
7.         index = str1.find('111')  # 看找得到‘111’
   
8.         if index >= 0:
   
9.             i += 2**(len(str1)-3-index)   # 找到了，就进位，后头有n个0，就是2的n次方
   
10.         else:
    
11.             counts += 1+str1.count('0')+n-len(str1)  # n-len(str1)是补齐前面的0
    
12.             i+=1
    
13.     return counts

复制代码

%time counts3(30)
Wall time: 3min 50s
Out[2]: 1918080160

小剑剑

1. def func(n):
   
2.     lone=3
   
3.     ltwo=1
   
4.     lzero=8
   
5.     one=2
   
6.     two=1
   
7.     zero=4
   
8.     day=3
   
9.     while day<n:
   
10.         day+=1
    
11.         temp=lone,ltwo,lzero,one,two,zero
    
12.         lone=temp[2]#lzero
    
13.         ltwo=temp[0]#lone
    
14.         lzero=temp[5]+temp[3]+temp[4]+temp[1]+temp[0]+temp[2]#zero+ltwo+lone
    
15.         one=temp[5]#zero
    
16.         two=temp[3]#one
    
17.         zero=temp[3]+temp[4]+temp[5]#one+two
    
18.     return one+two+zero+lone+ltwo+lzero
    
19. print(func(30))
    

复制代码

1918080160

夜凉如水

12

达锅

简直不能相信我解出来了。
希望答案是
1918080160

首先，题目转化为：0准时，1旷课，因迟到最多为1次，所以分开讨论
第一种是没有迟到的情况：
则1旷课最多连续出现2次，所以写了如下代码看看有没有规律可循

1. #0代表准时，1代表旷课1天，2旷课两天
   
2. o=[0,1]#第一天有两种情况
   
3. for j in range(5):
   
4.     n=[]#新的一天
   
5.     for i in o:
   
6.         if i==0 or i==1:#当准时或者旷课1天时，第二天可以为0或者再旷课1天
   
7.             n.append(0)
   
8.             n.append(i+1)
   
9.         elif i==2:
   
10.             n.append(0)#当旷课2天时只能准时
    
11.     o=n#以新的一天为基础，再判断下一天
    
12.     print(len(o))
    

复制代码

然后就得到了以下数列：
2
4
7
13
24
44
81
149
274
504
927
1705
3136
5768
10609
19513
35890
66012
然后，我把数列放进了Excel……
因为数列增长接近2**n，所以我猜测后一项应该等于前一项的两倍减去某个数
然后我意外的发现，这个数列又出现了，

于是得出，An=A(n-1)*2-A(n-4)
这就是在没有迟到的情况下任意天数的可能数

第二种情况，有一天迟到
用以上的数列可以分析得出，
如果第一天迟到，则可取上述A【29】，
如果第二天迟到，则可取A[1]*A[28]，第一天两种可能数乘以后面28天可能数
如果第三天迟到，则可取A[2]*A[27]，前两天的可能数乘以后面27天的可能数
故最终代码如下：

1. #==============================================================================
   
2. # #0代表准时，1代表旷课1天，2旷课两天
   
3. # o=[0,1]#第一天有两种情况
   
4. # for j in range(20):
   
5. #     n=[]#新的一天
   
6. #     for i in o:
   
7. #         if i==0 or i==1:#当准时或者旷课1天时，第二天可以为0或者再旷课1天
   
8. #             n.append(0)
   
9. #             n.append(i+1)
   
10. #         elif i==2:
    
11. #             n.append(0)#当旷课2天时只能准时
    
12. #     o=n#以新的一天为基础，再判断下一天
    
13. #     print(len(o))#列表长度就是可能的情况数
    
14. #==============================================================================
    
15. 
    
16. xl=[1,2,4,7]#生成准时和旷课不超过2天的序列数
    
17. for i in range(3,30):
    
18.     xl.append(xl[i]*2-xl[i-3])
    
19. #print(xl)
    
20. 
    
21. n=30
    
22. total=0
    
23. for i in range(1,n+1):#计算当迟到在第n天的可能情况数
    
24.     total+=xl[i-1]*xl[n-i]
    
25. print(total+xl[n])
    

复制代码

夏天和大熊

      大概的想法是，每一天获奖的情况和之前的情况是有关系的，这是一个能通过迭代解决的问题，可以通过对每一天所发生情况的统计，给出后一天所能发生的情况，将所有可能的情况分为三类，没有犯错的，有嫌疑的，没有获奖可能的。对于没有获奖可能的情况，是不能弥补的，所以无论天数如何增加，都没有转正的可能。这里主要讨论有嫌疑的情况，如果之前迟到过那再次迟到就没奖，如果之前连续2天迟到，那当天再迟到也会失去奖金。对于迟到而言，嫌疑效果将伴随之后每一天，而对于缺勤而言，如果当天没有缺勤，则缺勤所带来的嫌疑就会被刷新。因此在进行统计是对有迟到嫌疑的情况进行标记，并按照目前为止连续缺勤的天数的情况，将有获奖可能的情况划分为六类。
      对于当天这一天而言，没有错的情况要求前一天也没有犯错，或者之前有缺勤记录但是当天到了，都认为是没有任何犯错记录。迟到一天的情况意味着前一天没有迟到，迟到两天的情况意味着前一天有连续一天迟到的记录。没有过迟到标记的当天迟到则被划分到有迟到类。对违规行为不做统计。

     当天数等于30时，有获奖可能的种类有1918080160。

1. def num_reward(num_day):
   
2.     #按有无迟到将可能的情况分为两类，并按照到当前天数为止连续旷课的天数进行划分，假设第0天有1个人没有犯任何错
   
3.     mark_n_n = 1
   
4.     mark_n_a_1 = 0
   
5.     mark_n_a_2 = 0
   
6.    
   
7.     mark_l_n = 0
   
8.     mark_l_a_1 = 0
   
9.     mark_l_a_2 = 0
   
10. 
    
11.     #每次循环作为增加一天，对可能发生的情况种类进行重新统计
    
12.     for i in range(num_day):
    
13.         mark_n_n, mark_n_a_1, mark_n_a_2, mark_l_n, mark_l_a_1, mark_l_a_2 = \
    
14.                   mark_n_n + mark_n_a_1 + mark_n_a_2, \
    
15.                   mark_n_n, \
    
16.                   mark_n_a_1, \
    
17.                   mark_n_n + mark_n_a_1 + mark_n_a_2 + mark_l_n + mark_l_a_1 + mark_l_a_2, \
    
18.                   mark_l_n, \
    
19.                   mark_l_a_1
    
20.         
    
21.     #返回经过num_day后所有有嫌疑和没犯错的情况的总数
    
22.     mark = mark_n_n + mark_n_a_1 + mark_n_a_2 + mark_l_n + mark_l_a_1 + mark_l_a_2
    
23.     return mark

复制代码

chunchun2017

本人是新手，热爱编程，热爱Python，以下是解答过程，请高手指点：
如果仅仅是要计算出有多少种情况可以得到奖励，而不要求将所有的奖励字符串打印出来，那么下面的方法可以得到答案：
运算结果为：1918080160
基本思路：如果用set(m+n)表示所有的(m+n)位的奖励字符串，那么可以考虑set(m+n)是由setm和setn排列组合，然后排除一些不符合条件的字符串，就会得到set(m+n)，当然set(m+n）也可以通过其他的方式，比如set(2)与set(m+n-2)...等很多方式排列组合得到
==============================================================================
'''
本函数通过setm和setn构造出set(m+n)
将setm细分为6个子集：以OA或LA结尾且含有L的元素组成setm_1，以OA或LA结尾且不含L的元素组成setm_2，以AA结尾且不含L的元素组成setm_3,以AA结尾且含有L的元素组成setm_4,
以AO,LO,OO,LA,LO结尾且不包含L的元素组成setm_6,剩下的元素组成setm_6;同理，将setn分成类似的6个子集（setn_1...setn_6)
setm与setn排列组合，实际上是setm_1...setm_6与setn_1...setn_6排列组成，
以下几种组合得到的元素显然不能放入set(m+n)中：
1.以A结尾的元素与AA开头的元素组合
2.以AA结尾的元素与A开头的元素组合
3.包含L的元素与包含L的元素组合
（1，2会生成AAA，3会生成多L)
剩下的各种情况排列组合得到的元素都应该放入set(m+n)中
'''
def combm_n(setm,setn):
        setm_1=set()
        setm_2=set()
        setm_3=set()
        setm_4=set()
        setm_5=set()
        setm_6=set()
        setm_n=set()
        for x  in setm:
                if((x.endswith('OA') or (x.endswith('LA'))) and (x.count('L')==1)):
                        setm_1.add(x)
                elif (x.endswith('OA') and x.find('L')==-1):
                        setm_2.add(x)
                elif (x.endswith('AA') and x.count('L')==1):
                        setm_3.add(x)
                elif (x.endswith('AA') and x.find('L')==-1):
                        setm_4.add(x)
                elif (x.endswith('AO') or x.endswith('OO')) and (x.find('L')==-1):
                        setm_6.add(x)
                else:
                        setm_5.add(x)
        setn_1=set()
        setn_2=set()
        setn_3=set()
        setn_4=set()
        setn_5=set()
        setn_6=set()
        for x in setn:
                if((x.startswith('AL') or (x.startswith('AO'))) and (x.count('L')==1)):
                        setn_1.add(x)
                elif (x.startswith('AO') and x.find('L')==-1):
                        setn_2.add(x)
                elif (x.startswith('AA') and x.find('L')==-1):
                        setn_3.add(x)
                elif (x.startswith('AA') and x.count('L')==1):
                        setn_4.add(x)
                elif ((x.startswith('OO') or (x.startswith('OA')))and x.find('L')==-1):
                        setn_5.add(x)
                else:
                        setn_6.add(x)

        for each1 in setm_1:
                for each2 in setn_2:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_1:
                for each2 in setn_5:
                        str0=each1+each2
                        setm_n.add(str0)

        for each1 in setm_2:
                for each2 in setn_1:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_2:
                for each2 in setn_2:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_2:
                for each2 in setn_5:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_2:
                for each2 in setn_6:
                        str0=each1+each2
                        setm_n.add(str0)

        for each1 in setm_3:
                for each2 in setn_5:
                        str0=each1+each2
                        setm_n.add(str0)

        for each1 in setm_4:
                for each2 in setn_5:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_4:
                for each2 in setn_6:
                        str0=each1+each2
                        setm_n.add(str0)

        for each1 in setm_5:
                for each2 in setn_2:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_5:
                for each2 in setn_3:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_5:
                for each2 in setn_5:
                        str0=each1+each2
                        setm_n.add(str0)

        for each1 in setm_6:
                for each2 in setn_1:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_6:
                for each2 in setn_2:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_6:
                for each2 in setn_3:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_6:
                for each2 in setn_4:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_6:
                for each2 in setn_5:
                        str0=each1+each2
                        setm_n.add(str0)
        for each1 in setm_6:
                for each2 in setn_6:
                        str0=each1+each2
                        setm_n.add(str0)

        return setm_n

def countm_n(setm,setn): #与combm_n(setm,setn)函数类似，只不过不需要生成set(m+n)的每个元素，只计算set(m+n)集合中元素的个数
        setm_1=set()
        setm_2=set()
        setm_3=set()
        setm_4=set()
        setm_5=set()
        setm_6=set()
        setm_n=set()
        sum=0
        for x  in setm:
                if((x.endswith('OA') or (x.endswith('LA'))) and (x.count('L')==1)):
                        setm_1.add(x)
                elif (x.endswith('OA') and x.find('L')==-1):
                        setm_2.add(x)
                elif (x.endswith('AA') and x.count('L')==1):
                        setm_3.add(x)
                elif (x.endswith('AA') and x.find('L')==-1):
                        setm_4.add(x)
                elif (x.endswith('AO') or x.endswith('OO')) and (x.find('L')==-1):
                        setm_6.add(x)
                else:
                        setm_5.add(x)
        setn_1=set()
        setn_2=set()
        setn_3=set()
        setn_4=set()
        setn_5=set()
        setn_6=set()
        for x in setn:
                if((x.startswith('AL') or (x.startswith('AO'))) and (x.count('L')==1)):
                        setn_1.add(x)
                elif (x.startswith('AO') and x.find('L')==-1):
                        setn_2.add(x)
                elif (x.startswith('AA') and x.find('L')==-1):
                        setn_3.add(x)
                elif (x.startswith('AA') and x.count('L')==1):
                        setn_4.add(x)
                elif ((x.startswith('OO') or (x.startswith('OA')))and x.find('L')==-1):
                        setn_5.add(x)
                else:
                        setn_6.add(x)

        sum=sum+len(setm_1)*len(setn_2)+len(setm_1)*len(setn_5)
        sum+=len(setm_2)*len(setn_1)+len(setm_2)*len(setn_2)+len(setm_2)*len(setn_5)+len(setm_2)*len(setn_6)
        sum+=len(setm_3)*len(setn_5)+len(setm_4)*len(setn_5)+len(setm_4)*len(setn_6)+len(setm_5)*len(setn_2)
        sum+=len(setm_5)*len(setn_3)+len(setm_5)*len(setn_5)
        sum+=len(setm_6)*len(setn)
        return sum

def combm_1(setm):#用于通过setm构造出set(m+1)
        setm_n = set()
        for x in setm:
                if(x.find('L')==-1):
                        x+='L'
                        setm_n.add(x)
        for x in setm:
                x+='O'
                setm_n.add(x)
        for x in setm:
                if (x.endswith('OO')or x.endswith('AO') or x.endswith('LA') or x.endswith('OA') or x.endswith('LL') or x.endswith('LO') or x.endswith('OL') or x.endswith('AL')):
                        x+='A'
                        setm_n.add(x)
        return setm_n

import time
tt=time.time()

set2 = {"AA","AL","AO","LA","LO","OA","OL","OO"}
set4 = {"OOOO","OOOA","OOOL","OOAO","OOAA","OOAL",
"OOLO","OOLA","OAOO","OAOA","OAOL","OAAO","OAAL",
"OALO","OALA","OLOO","OLOA","OLAO","OLAA","AOOO",
"AOOA","AOOL","AOAO","AOAA","AOAL","AOLO","AOLA",
"AAOO","AAOA","AAOL","AALO","AALA","ALOO",
"ALOA","ALAO","ALAA","LOOO","LOOA","LOAO",
"LOAA","LAOO","LAOA","LAAO"}
set3=combm_1(set2)
set7=combm_n(set4,set3)
set8=combm_1(set7)
set15=combm_n(set8,set7)
print(countm_n(set15,set15))
print('Time used: {} sec'.format(time.time()-tt))
如果要求不但要计算出所有可能的奖励字符串的数量，还要打印出所有的奖励字符串，那上面的程序只能计算到25位，耗时：78.96465563774109 sec（去掉countm_n(）函数），到计算26位奖励字符串时，内存不够用（电脑配置为16G内存），后面想尽了各种办法，也没办法计算出所有26位奖励字符串，当然更不用说30位了，很想知道能用什么高效的办法把所有的30位奖励字符串都打印出来。.

小Q学Python

小剑剑 发表于 2017-8-1 17:32
1918080160

。。。膜拜，算法能加点注释么。。。

chunchun2017

小剑剑 发表于 2017-8-1 17:32
1918080160

大神，能对代码作些说明吗？看不懂，感觉大神的代码好简洁，膜拜

小剑剑

小Q学Python 发表于 2017-8-7 11:35
。。。膜拜，算法能加点注释么。。。

8楼的鱼油的思路和我一样，我就懒得写了，
很简单30天的情况可以获奖学金，那么按29天算，钱29天也可以获得奖学金，因为标准是一样的

小剑剑

chunchun2017 发表于 2017-8-7 14:42
大神，能对代码作些说明吗？看不懂，感觉大神的代码好简洁，膜拜

8楼的鱼油的思路和我一样，我就懒得写了，
很简单30天的情况可以获奖学金，那么按29天算，钱29天也可以获得奖学金，因为标准是一样的