python - 优化 python/pypy 中的蛮力过程以查找独生子女号码-6ren

python - 优化 python/pypy 中的蛮力过程以查找独生子女号码

转载作者：太空宇宙更新时间：2023-11-03 11:54:34

蛮力方法并非旨在解决问题，而是有助于其研究。我正在研究 Project Euler这个问题让我找到从 X 到比 Y 小一的所有数字，这些数字恰好有一个“子串”可以被数字中的位数整除。

这些被称为独生子女号码。 104是独生子女号码。在它的子串中，[1, 0, 4, 10, 04, 104] 只有 0 能被 3 整除。该题要求找出小于 10*17 的独生子数的数量。蛮力方法不是正确的方法；然而，我有一个理论，要求我知道在 10*11 之前出现的一个 child 数字的数量。

即使将我的笔记本电脑打开半天，我也没有成功找到这个数字。我试过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,0,4,10,04,104]

## FYI one-child numbers are positive, so the number 0 is not one-child


from multiprocessing import Pool
import os.path

def 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 small
def 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,start,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,start,cores):
    if start == 1:
        start = 0
    else:
        pass
    while (numRange-start)%cores != 0:
        cores -= 1
    return cores

#MultiProcList(10**7)
from timeit import Timer
t = Timer(lambda: MultiProcList(10**6))
print t.timeit(number=1)

最佳答案

这是我最快的暴力破解代码。它使用cython来加速计算。它不是检查所有数字，而是通过递归找到所有独生子数字。

%%cython
cdef 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, child_count2, digits_count)
        return count 

def one_child_number(int digits_count):
    return _one_child_number(0, 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中的 child 数，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, child_count2, digits_count)
        return count

这是_one_child_number(0, 0, 3)的输出，3位独生子女数的计数是第一列为3的第二列之和位数。

关于python - 优化 python/pypy 中的蛮力过程以查找独生子女号码，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15378514/

文章推荐： python - 是否可以通过 wine 从 Windows 应用程序获取输出？

文章推荐： java - 在 map 上放置多个标记时获取 Latlng 值的无效双 "n\a"

css - 独生子女，当不止一位 parent 拥有独生子女时
第一次发帖，当前学生正在学习 CSS 伪选择器。问:如果一个元素是两个或多个不同父项的独生子，如何对其中一个父项使用独生子？上下文:我在 CSS Diner 上独生子女类(class)。布局如下:

太空宇宙

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

python - 优化 python/pypy 中的蛮力过程以查找独生子女号码