在pythonpypy中优化暴力过程以找到一个孩子的数字

概述蛮力方法并非旨在解决问题,而是有助于其研究.我正在研究一个 Project Euler问题,让我发现所有数字从X到小于Y,只有一个“子串”可以被一个数字中的位数整除. 这些被称为独子数字. 104是一个孩子的号码.在其子串中,[1,0,4,10,04,104]只有0可被3整除.该问题要求找出少于10 * 17的一子数的数量.蛮力方法不是正确的方法;但是,我有一个理论要求我知道在10 * 11之前发 蛮力方法并非旨在解决问题,而是有助于其研究.我正在研究一个 Project Euler问题,让我发现所有数字从X到小于Y,只有一个“子串”可以被一个数字中的位数整除.

这些被称为独子数字. 104是一个孩子的号码.在其子串中,[1,4,10,04,104]只有0可被3整除.该问题要求找出少于10 * 17的一子数的数量.蛮力方法不是正确的方法;但是,我有一个理论要求我知道在10 * 11之前发生的一个孩子数量.

我离开笔记本电脑半天后,我还没有成功找到这个数字.我试过Cython,我是一个对C一无所知的新手程序员.结果非常糟糕.我甚至尝试过云计算,但是我的ssh管道在进程完成之前总是会中断.

如果有人可以帮助我找出一些不同的方法或优化预先形成BRUTE FORCE
这个问题的方法高达10 ** 11,非常感谢.

请不要…

借给我关于数论的建议或你对这个问题的答案,因为我已经花了很长时间研究它,我真的希望自己得出结论.

## a one child number has only one "substring" divisable by the## number of digits in the number. Example: 104 is a one child number as 0## is the only substring which 3 may divIDe,of the set [1,104]## FYI one-child numbers are positive,so the number 0 is not one-childfrom multiprocessing import Poolimport os.pathdef OneChild(numRange): # hopefully(10*11,1)    OneChild = []    start = numRange[0]    number = numRange[1]    ## top loop handles one number at a time    ## loop ends when start become larger then end    while number >= start:        ## preparing to analayze one number        ## for exactly one divisableSubstrings        numberString = str(start)        numDigits = len(numberString)        divisableSubstrings = 0        ticker1,ticker2 = 0,numDigits        ## ticker1 starts at 0 and ends at number of digits - 1        ## ticker2 starts at number of digits and ends +1 from ticker1        ## an example for a three digit number: (0,3) (0,2) (0,1) (1,3) (1,2) (2,3)        while ticker1 <= numDigits+1:            while ticker2 > ticker1:                if int(numberString[ticker1:ticker2]) % numDigits == 0:                    divisableSubstrings += 1                    if divisableSubstrings == 2:                        ticker1 = numDigits+1                        ticker2 = ticker1                ##Counters                    ticker2 -= 1            ticker1 += 1            ticker2 = numDigits                     if divisableSubstrings == 1: ## One-Child Bouncer             OneChild.append(start) ## inefficIEnt but I want the specifics        start += 1     return (OneChild)## Speed seems improve with more pool arguments,labeled here as cores## Im guessing this is due to pypy preforming best when task is neither## to large nor smalldef MultiProcList(numRange,start = 1,cores = 100): # multiprocessing    print "Asked to use %i cores between %i numbers: From %s to %s" % (cores,numRange-start,start,numRange)    cores = adjustCores(numRange,cores)    print "Using %i cores" % (cores)    chunk = (numRange+1-start)/cores    end = chunk+start -1     total,argsList= 0,[]    for i in range(cores):        # print start,end-1        argsList.append((start,end-1))        start,end = end,end + chunk    pool = Pool(processes=cores)    data = pool.map(OneChild,argsList)    for d in data:        total += len(d)    print total##    f = open("Result.txt","w+")##    f.write(str(total))##    f.close()def adjustCores(numRange,cores):    if start == 1:        start = 0    else:        pass    while (numRange-start)%cores != 0:        cores -= 1    return cores#MultiProcList(10**7)from timeit import Timert = Timer(lambda: MultiProcList(10**6))print t.timeit(number=1)

解决方法 这是我最快的蛮力代码.它使用cython来加速计算.它不是检查所有数字,而是通过递归找到所有的One-Child数字.

%%cythoncdef int _one_child_number(int s,int child_count,int digits_count):    cdef int start,count,c,child_count2,s2,part,i    if s >= 10**(digits_count-1):        return child_count    else:        if s == 0:            start = 1        else:            start = 0        count = 0        for c in range(start,10):            s2 = s*10 + c            child_count2 = child_count            i = 10            while True:                part = s2 % i                if part % digits_count == 0:                    child_count2 += 1                    if child_count2 > 1:                        break                if part == s2:                    break                i *= 10            if child_count2 <= 1:                count += _one_child_number(s2,digits_count)        return count def one_child_number(int digits_count):    return _one_child_number(0,digits_count)

要找到F(10 ** 7)的数量,需要大约100ms才能得到结果277674.

print sum(one_child_number(i) for i in xrange(8))

您需要64位整数来计算大结果.

编辑：我添加了一些评论,但我的英语不好,所以我将代码转换为纯python代码,并添加一些打印,以帮助您弄清楚它是如何工作的.

_one_child_number递归地将数字从左添加到s,child_count是s中的子计数,digits_count是s的最终数字.

def _one_child_number(s,child_count,digits_count):    print s,child_count    if s >= 10**(digits_count-1): # if the length of s is digits_count        return child_count # child_count is 0 or 1 here,1 means we found one one-child-number.    else:        if s == 0:             start = 1 #if the length of s is 0,we choose from 123456789 for the most left digit.        else:            start = 0 #otherwise we choose from 0123456789         count = 0 # init the one-child-number count        for c in range(start,10): # loop for every digit            s2 = s*10 + c  # add digit c to the right of s            # following code calculates the child count of s2            child_count2 = child_count             i = 10            while True:                part = s2 % i                if part % digits_count == 0:                    child_count2 += 1                    if child_count2 > 1: # when child count > 1,it's not a one-child-number,break                        break                if part == s2:                    break                i *= 10            # if the child count by far is less than or equal 1,# call _one_child_number recursively to add next digit.            if child_count2 <= 1:                 count += _one_child_number(s2,digits_count)        return count

这里是输出_one_child_number(0,3),并且一个3位数的子数是第一列是3位数的第二列的总和.

0 01 010 1101 1104 1107 111 0110 1111 1112 1113 1114 1115 1116 1117 1118 1119 112 1122 1125 1128 113 1131 1134 1137 114 0140 1141 1142 1143 1144 1145 1146 1147 1148 1149 115 1152 1155 1158 116 1161 1164 1167 117 0170 1171 1172 1173 1174 1175 1176 1177 1178 1179 118 1182 1185 1188 119 1191 1194 1197 12 020 1202 1205 1208 121 1211 1214 1217 122 0220 1221 1222 1223 1224 1225 1226 1227 1228 1229 123 1232 1235 1238 124 1241 1244 1247 125 0250 1251 1252 1253 1254 1255 1256 1257 1258 1259 126 1262 1265 1268 127 1271 1274 1277 128 0280 1281 1282 1283 1284 1285 1286 1287 1288 1289 129 1292 1295 1298 13 131 1311 1314 1317 132 1322 1325 1328 134 1341 1344 1347 135 1352 1355 1358 137 1371 1374 1377 138 1382 1385 1388 14 040 1401 1404 1407 141 0410 1411 1412 1413 1414 1415 1416 1417 1418 1419 142 1422 1425 1428 143 1431 1434 1437 144 0440 1441 1442 1443 1444 1445 1446 1447 1448 1449 145 1452 1455 1458 146 1461 1464 1467 147 0470 1471 1472 1473 1474 1475 1476 1477 1478 1479 148 1482 1485 1488 149 1491 1494 1497 15 050 1502 1505 1508 151 1511 1514 1517 152 0520 1521 1522 1523 1524 1525 1526 1527 1528 1529 153 1532 1535 1538 154 1541 1544 1547 155 0550 1551 1552 1553 1554 1555 1556 1557 1558 1559 156 1562 1565 1568 157 1571 1574 1577 158 0580 1581 1582 1583 1584 1585 1586 1587 1588 1589 159 1592 1595 1598 16 161 1611 1614 1617 162 1622 1625 1628 164 1641 1644 1647 165 1652 1655 1658 167 1671 1674 1677 168 1682 1685 1688 17 070 1701 1704 1707 171 0710 1711 1712 1713 1714 1715 1716 1717 1718 1719 172 1722 1725 1728 173 1731 1734 1737 174 0740 1741 1742 1743 1744 1745 1746 1747 1748 1749 175 1752 1755 1758 176 1761 1764 1767 177 0770 1771 1772 1773 1774 1775 1776 1777 1778 1779 178 1782 1785 1788 179 1791 1794 1797 18 080 1802 1805 1808 181 1811 1814 1817 182 0820 1821 1822 1823 1824 1825 1826 1827 1828 1829 183 1832 1835 1838 184 1841 1844 1847 185 0850 1851 1852 1853 1854 1855 1856 1857 1858 1859 186 1862 1865 1868 187 1871 1874 1877 188 0880 1881 1882 1883 1884 1885 1886 1887 1888 1889 189 1892 1895 1898 19 191 1911 1914 1917 192 1922 1925 1928 194 1941 1944 1947 195 1952 1955 1958 197 1971 1974 1977 198 1982 1985 1988 1

总结

以上是内存溢出为你收集整理的在python / pypy中优化暴力过程以找到一个孩子的数字全部内容，希望文章能够帮你解决在python / pypy中优化暴力过程以找到一个孩子的数字所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。