找一个特殊的9位数

jerryxjr1220

刚好在刷题时看到这题，比较简单，也比较有趣，可以拿来练手。

这个9位数由1~9的9个数字组成， 每个数字只能出现一次：其第一位能被1整除， 前两位能被2整除， 前三位能被3整除...依次类推，前9位能被9整除。所有的9位数中，只有一个数字满足这些条件，请你输出这个9位数。

调动积极性，回复代码给奖励哦！

天空圣域

第一位是从个位开始还是从最高位开始？

小锟

1. import itertools
   
2. s = ''
   
3. a = itertools.permutations(range(1,10),9)
   
4. for i in a :
   
5.     for j in range(9):
   
6.         s += str(i[j])
   
7.         if int(s) % (j+1) != 0 :
   
8.             s = ''
   
9.             break      
   
10.     if len(s) == 9 :
    
11.         print s
    
12.         break

复制代码

jerryxjr1220

天空圣域 发表于 2017-6-14 12:50
第一位是从个位开始还是从最高位开始？

第一位是指高位，第9位才是个位。

冬雪雪冬

根据给定条件，2、4、6、8位为偶数，则剩下的只能是奇数，同时第5位只能是5

1. import itertools, functools
   
2. for i in itertools.permutations([1,3,7,9],4):
   
3.     for j in itertools.permutations([2, 4, 6, 8], 4):
   
4.         num = functools.reduce(lambda x, y: 10 * x + y, [i[0], j[0], i[1], j[1], 5, j[2], i[2], j[3], i[3]])
   
5.         n = 9
   
6.         while n > 2:
   
7.             if num //(10 ** (9 - n)) % n:
   
8.                 break
   
9.             n -= 1
   
10.         else:
    
11.             print(num)

复制代码

ooxx7788

我来收录一下，嘿嘿。一觉醒来，3楼已经给了做法了。我再来说些可以减少计算量的东西。不过本身跑的已经够快了，改进不改进也就那么回事儿了，算是个马后炮。

我能想到的有以下两条：
1，数字为1-9，第五位可以给5除，那么必然是   nnnn5nnnn      n for num

1. 可以在第三行后面插入，我测试过，可以缩短到原来的1/4-1/5的时间
   
2. a = filter(lambda x: x[4] == 5, a)

复制代码

2，偶数位可以被偶数整除，那么必然是  oeoe5oeoe         o  for odd , e for even
然后我自己试了下，用filter筛除不符合的数字，时间反而会变长，所以这里就不放代码了。我想如果要缩短时间，应该直接在构造permutations时候，就做好才好。

冬雪雪冬

ooxx7788 发表于 2017-6-14 14:47
我来收录一下，嘿嘿。一觉醒来，3楼已经给了做法了。我再来说些可以减少计算量的东西。不过本身跑的已经够 ...

我们考虑的优化方法是一样的，不知有没有更好的。

ooxx7788

冬雪雪冬 发表于 2017-6-14 17:14
我们考虑的优化方法是一样的，不知有没有更好的。

其实还有一些，不过我觉得意义不是特别大，所以就没说。
比如说，3,4位组成的数字必须是4的倍数。
还有7的倍数也有数字特征。
如果不使用itertools库的情况下面，这些特征应该有意义，因为可以减少很多用于生成验证数字的迭代循环的次数。直接用库以后，价值感觉不高。

Teagle

我的是用的基础的内置的函数，第一位能被1整除，可能性是1-9，
然后判断一次判断前num位的对应条件，
利用not k%num来判断前num位数字可以被num整除，
利用len(set(str(k))) == num 来判断前num位置的数字没有重复，

1. a = [1,2,3,4,5,6,7,8,9]
   
2. 
   
3. for num in range(2,10):
   
4.     n = len(a)
   
5.     for i in range(n):
   
6.         for j in range(1,10):
   
7.             k = a[0]*10 +j               
   
8.             if not k % num and len(set(str(k))) == num:
   
9.                 a.append(k)            
   
10.         a.remove(a[0])
    
11.         
    
12. print(a)

复制代码

方法有点笨，但是知识点简单
撤~，观摩大佬们的代码去

jerryxjr1220

Teagle 发表于 2017-6-15 14:25
我的是用的基础的内置的函数，第一位能被1整除，可能性是1-9，
然后判断一次判断前num位的对应条件，
利 ...

可以的，不知道你是不是意识到其实你使用了广度优先搜索算法，如果改a[0]为a[-1]，就可以转换成深度优先搜索。

Teagle

jerryxjr1220 发表于 2017-6-15 14:55
可以的，不知道你是不是意识到其实你使用了广度优先搜索算法，如果改a[0]为a[-1]，就可以转换成深度优先 ...

经您这么一说，发现确实是广度优先，我再想想深度优先去，感谢大佬指点

jerryxjr1220

Teagle 发表于 2017-6-15 14:25
我的是用的基础的内置的函数，第一位能被1整除，可能性是1-9，
然后判断一次判断前num位的对应条件，
利 ...

仿造你的格式写的深度优先搜索算法

1. a = [9, 8, 7, 6, 5, 4, 3, 2, 1]
   
2. while a:
   
3.         p = a.pop()
   
4.         if len(str(p)) == 9:
   
5.                 print(p)
   
6.                 break
   
7.         for i in range(9,0,-1):
   
8.                 if str(i) not in str(p) and (p * 10 + i) % len(str(p * 10 + i)) == 0:
   
9.                         a.append(p * 10 + i)

复制代码

Teagle

jerryxjr1220 发表于 2017-6-15 15:09
仿造你的格式写的深度优先搜索算法

跪拜

SixPy

来个 新人看不懂系列

1. from itertools import (accumulate as acc,
   
2.                        chain,
   
3.                        permutations as perm,
   
4.                        product)
   
5. 
   
6. tuple(filter(lambda t:len(t)==9,[tuple(filter(lambda x:x[1]%x[0]==0,enumerate(acc(filter(None,chain(*zip(filter(None,chain(*zip(a,(0,5,0,0)))),list(b)+[0]))),lambda x,y:x*10+y),1)))for a,b in product(perm((1,3,7,9)),perm((2,4,6,8)))]))[0][8][1]
   

复制代码

1. 381654729

复制代码

新手·ing

SixPy 发表于 2017-6-15 20:09
来个 新人看不懂系列

膜拜大佬ing

jerryxjr1220

SixPy 发表于 2017-6-15 20:09
来个 新人看不懂系列

版主去挑战一下挑战赛的题吧
http://bbs.fishc.com/thread-88937-1-1.html

Teagle

小锟 发表于 2017-6-14 13:33

这样也不错哎

1. s = ''.join(map(str,a[i][:j+1])))

复制代码

gopythoner

SixPy 发表于 2017-6-15 20:09
来个 新人看不懂系列

跪了

badaoqingchen

SixPy 发表于 2017-6-15 20:09
来个 新人看不懂系列

厉害了

WelanceLee

1. import itertools as it
   
2. 
   
3. result = 0
   
4. p = it.permutations([str(i) for i in range(10)], 9)
   
5. 
   
6. for each in p:
   
7.     flag = True
   
8.     for i in range(1, 10):
   
9.         if int(''.join(each[:i])) % i != 0:
   
10.             flag = False
    
11.             break
    
12.     if flag and each[0] != '0':
    
13.         result = int(''.join(each[:i]))
    
14.         break
    
15. 
    
16. print(result)

复制代码