小练习20170710 使用最多100万块瓷砖可以形成多少不同的中空的正方形？

冬雪雪冬

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

                               
登录/注册后可看大图

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

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


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





题目：

我们定义一个正方形薄板为一个中间为正方形空洞的正方形外框。这个形状在水平和竖直方向上都是对称的。比如，用 32 块方形砖，我们可以得到如下两个不同的薄板。

                               
登录/注册后可看大图

如果有 100 块砖，而且不需要一次全部使用的话，我们可以形成 25 种不同的正方形薄板。

那么请问，如果使用不超过 100 万块瓷砖的话，可以形成多少种不同的薄板呢？

china25qd

一个疑问：
正方型的边必须是实心的吗？

jerryxjr1220

这题貌似很简单啊，解法也就是暴力解法。
假设大正方形的边长是a，层数为b，那么这个中空正方形的总砖块数4*b*（a-b）。
然后就是累加统计了。用jit加快运算。

1. from numba import jit
   
2. import time
   
3. @jit
   
4. def solve():
   
5.         c = 0
   
6.         for a in range(3, 250002):
   
7.                 for b in range(1, (a-1)//2+1):
   
8.                         if 4*b*(a-b) <= 1000000:
   
9.                                 c += 1
   
10.                         else:
    
11.                                 break
    
12.         return c
    
13. tt = time.time()
    
14. print(solve())
    
15. print(time.time()-tt)

复制代码

1572729
0.1520087718963623

另外，还可以利用简化公式，一行代码输出：

1. print(sum((1000000//4//s-s for s in range(1, int((1000000//4)**0.5)))))

复制代码

WelanceLee

1. n = 10**6
   
2. a = int((n+4)/4)
   
3. num = 0
   
4. for i in range(a, 0, -1):
   
5.     for j in range(i-2, 0, -2):
   
6.         if i*i - j*j <=n :
   
7.             num += 1
   
8. ##            print(i, j, i*i-j*j)
   
9.         else:
   
10.             break
    
11. print(num)

复制代码

结果是1572729，然而我对100计算得到的结果是41，先占个位置吧~

小锟

1. import math
   
2. s = 0
   
3. ns= range(4,10**6+1,4)
   
4. for n in ns:
   
5.     k_max = int(math.sqrt(n / 4))
   
6.     for k in range(1,k_max + 1):
   
7.         b = n / (4 * k) -  k
   
8.         if int(b) == b and b > 0:
   
9.             s += 1
   
10. print(s)

复制代码

100的话是41种，题目错啦

suloman

不太明白  最后的条件  什么是 100块砖 不需要全部使用 8块应该也算
结果我的100块砖 就跟题目的不一样 但还是写一下过程吧
以最小内圈的单边为2 (也就是总数为8,中间空一个)开始,每次加一圈,然后 总数不超过目标值 计数加1
再以最小内圈的单边为3,每次加一圈,
直到(总数/4)的单边框为结束
zhuan=1000000
fangfa=0


for danbian in range (2, int(zhuan/4)+1  ):
   
    dd=danbian
    zongshu=dd*4
    while zongshu <= zhuan :
        dd += 2
        zongshu = zongshu + dd * 4
        
        fangfa += 1
print (fangfa)

达锅

不理解题目
100百块砖，如果边只有一层，最大可以形成25边长的正方形，最小是2边长的正方形，都已经24种了不同的模板了，再加上不止一层的，应该是41种才对啊

看不懂题目，按自己的思路写了，先是数组的

1. import numpy as np
   
2. import time as t
   
3. tt=t.time()
   
4. n=10**6#输入9会造成内存不足，死机
   
5. bc=n//4#最长的边长
   
6. b=np.arange(bc-1)+2#生成最小边长2，最大边长bc的数组
   
7. y=n-b*4#总数减去最外围的边长的剩余
   
8. c=bc-1#c统计，第一次为单层的情况
   
9. while np.sum(b):
   
10.     bb=b-2
    
11.     yy=y-bb*4
    
12.     b=bb>=2
    
13.     y=yy>0
    
14.     s=b*y
    
15.     c+=np.sum(s)
    
16.     b=bb[s]
    
17.     y=yy[s]
    
18. print(c)
    
19. print(t.time()-tt)

复制代码

1. 1572713
   
2. 0.0655832290649414

复制代码

接着是生成器的，理论上占用内存低

1. def js(ww,all):
   
2.     c=0
   
3.     while ww>1 and all>0:
   
4.         ww-=2
   
5.         all-=ww*4
   
6.         c+=1
   
7.     return c
   
8.    
   
9.    
   
10. import time as t
    
11. tt=t.time()
    
12. n=10**6
    
13. bc=n//4
    
14. a=((i,n-i*4) for i in range(2,bc+1))
    
15. 
    
16. print(sum(js(i[0]-2,i[1]-(i[0]-2)*4) for i in a)+bc-1)
    
17. print(t.time()-tt)

复制代码

然后是列表的，理论上会内存不足

1. import time as tt
   
2. t=tt.time()
   
3. n=10**6
   
4. bc=n//4
   
5. c=bc-1
   
6. a=[(i,n-i*4) for i in range(2,bc+1)]
   
7. while a:
   
8.     a=[(i[0]-2,i[1]-(i[0]-2)*4) for i in a if i[0]-2>=2 and i[1]-(i[0]-2)*4>0]#a的长度
   
9.     c+=len(a)
   
10. print(c)
    
11. print(tt.time()-t)

复制代码

1. 1572713
   
2. 1.1018621921539307

复制代码

plus

好难，连题目给的已知我都没算出来=。=

如果有 100 块砖，而且不需要一次全部使用的话，我们可以形成 25 种不同的正方形薄板。

题目这步 100块砖，我算就是41种不同的摆法。。这还怎么往下算。。

最终按这个算法 使用1000000块砖能够摆出1572729种图样

输入1000000计算时要注销掉代码中的print，不然卡到死

1. t=int(input('请输入地砖数量：'))   #t是地砖数量
   
2. i=0
   
3. a=[]  #定义空列表a
   
4. x=[]  #单边地砖数为 奇数 的列表
   
5. y=[]  #单边地砖数为 偶数 的列表
   
6. while 4*i<=t:    #计算总地砖数量为t时候能摆多少个宽度为1的空心正方形
   
7.    a.insert(i,4*i)
   
8.    if i>1 and i%2!=0:
   
9.       y.insert(i,4*i)
   
10.       i+=1  #偶数的存储到y列表中
    
11.    else:
    
12.       if 4*i>4:
    
13.         x.insert(i,4*i)    #奇数的存储到x列表中
    
14.       else:
    
15.         1==1
    
16.       i+=1
    
17. print(x) #单边地砖数为 奇数 的列表
    
18. print(y) #单边地砖数为 偶数 的列表
    
19. 
    
20. 
    
21. count=len(y)+len(x)  #单层的正方形能摆count种
    
22. 
    
23. #奇数多层正方形计数
    
24. i=0
    
25. j=2
    
26. while sum(x[i:i+j])<=t and j<len(x)/2:
    
27.    while i<len(x) and sum(x[i:i+j])<=t:
    
28.       print(x[i:i+j],sum(x[i:i+j])) #打印出几层的，每层用多少砖，一共用多少砖
    
29.       i+=1
    
30.       count+=1
    
31.    i=0
    
32.    j+=1
    
33. 
    
34. 
    
35. #偶数多层正方形计数   
    
36. i=0
    
37. j=2
    
38. while sum(y[i:i+j])<=t and j<len(y)/2:
    
39.    while i<len(y) and sum(y[i:i+j])<=t:
    
40.       print(y[i:i+j],sum(y[i:i+j])) #打印出几层的，每层用多少砖，一共用多少砖
    
41.       i+=1
    
42.       count+=1
    
43.    i=0
    
44.    j+=1
    
45.    
    
46. print('使用'+str(t)+'块砖能够摆出'+str(count)+'种图样')   #打印出一共能多少种
    

复制代码