小练习 20170529 考察方块的替换方法的数量

冬雪雪冬

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

                               
登录/注册后可看大图

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

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


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




题目：

五块黑方形（长为 1）排成一行，我们要从几种长方形中选取，来替换掉五块中的若干块，其中，红色的长为 2，绿色的长为 3，蓝的是 4

如果选取红色的长方形，则正好有七种替换的方式，如下

                               
登录/注册后可看大图

如果选取绿色的长方形，则有三种

                               
登录/注册后可看大图

               
蓝色的话，就只有两种方法了

                               
登录/注册后可看大图

               
        
如果颜色不混搭的话，有 7 + 3 + 2 = 12 种方法来替换五块一行的黑方块。

请问，如果是五十块一行，那么，总共有多少种方式来替换？条件：颜色不混搭，至少使用一种颜色

WelanceLee

1. def permutation(n, i):
   
2.     a = 1
   
3.     b = 1
   
4.     for j in range(i):
   
5.         a *= n - j
   
6.         b *= j + 1
   
7.     return int(a/b)
   
8. 
   
9. def f(num, block):
   
10.     n = num//block
    
11.     x = 0
    
12.     for i in range(1, n + 1):
    
13.         black = num - i * block
    
14.         x += permutation(black + i, i)
    
15.     return x
    
16. 
    
17. num = 50
    
18. print(f(num, 2) + f(num, 3) + f(num, 4))

复制代码

答案是20492570929

jerryxjr1220

思路:这题用排列组合的方法，然后累加，依次计算红绿蓝的组合

1. 
   
2. from math import factorial as f
   
3. def solve(n,r=2,g=3,b=4):
   
4.   total = 0
   
5.   for c in [r,g,b]:
   
6.     for i in range(1,n//c+1):
   
7.       total += f(n-i*c+i)//f(i)//f(n-i*c)
   
8.   return total
   
9. print solve(50)
   

复制代码

20492570929

jerryxjr1220

当然可以简化输出:

1. from math import factorial as f
   
2. def solve(n,r=2,g=3,b=4):
   
3.   return sum((f(n-i*c+i)//f(i)//f(n-i*c) for c in (r,g,b) for i in range(1,n//c+1)))
   
4. print solve(50)

复制代码

小剑剑

动态规划

1. def func(leng,block=50):
   
2.     quantitylist=[]
   
3.     i=0
   
4.     while i<51:
   
5.         if i<leng:
   
6.             quantitylist.append(0)
   
7.         elif i==leng:
   
8.             quantitylist.append(1)
   
9.         else:
   
10.             quantitylist.append(quantitylist[i-1]+1+quantitylist[i-leng])
    
11.         i+=1
    
12.     return quantitylist[50]
    
13. sum([func(i) for i in (2,3,4)])

复制代码

答案 20492570929