Geek Answers Handbook

Python recursive algorithm doesn't work for large values ​​- C program works

I wanted to write a feedback solution for this question , in which it is proposed to find the clearest odd numbers that sum up to the given one n.

I hacked this Python code:

import sys
sys.setrecursionlimit(10000) 


stop = False
def solve(n, used, current_sum):
    global stop
    if stop:
        return

    if current_sum == n:
        print(used)
        stop = True
        return

    start = 1 if len(used) == 0 else (used[-1] + 2)
    for i in range(start, n + 1, 2):
        if current_sum + i <= n and not stop:
            used.append(i)
            solve(n, used, current_sum + i)
            used.pop()
        else:
            return

solve(100000000, [], 0)

Which unfortunately doesn't print anything for me. As far as I can tell, he never comes to this condition if. If I print current_sumat every step, it just stops around 16000000when the entire program exits without errors.

I tried to increase the recursion limit, no luck.

I tested it on Idle and Eclipse, in Python 3.4, 64 bit, in Windows 8.1. I have 16 GB of RAM.

If I reduce n, then I get a solution (delete zero, for example).

, , , C. C:

int sol[100000];
bool done = false;
void solve(int n, int k, int sum)
{
    if (done)
        return;

    if (sum == n)
    {
        done = true;
        for (int i = 0; i < k; ++i)
        {
            printf("%d ", sol[i]);
        }
        printf("\n");
        return;
    }

    int start = 1;
    if (k > 0)
        start = sol[k - 1] + 2;
    for (int i = start; i <= n; i += 2)
        if (sum + i <= n && !done)
        {
            sol[k] = i;
            solve(n, k + 1, sum + i);
        }
        else
            return;
}

int main()
{
    solve(100000000, 0, 0);

    return 0;
}

, !

Python ?

C, .

+4
2

Python ?

, . n . Python 2.7.6. , , C, , , .

import sys
sys.setrecursionlimit(100000) 

sol = []
stop = False

def solve(n, k, current_sum):
    global stop

    if stop:
        return

    if current_sum == n:
    stop = True
    for i in xrange(0, k, 1):
            print(sol[i]),
    print
        return

    start = 1 if len(sol) == 0 else (sol[k-1] + 2)
    for i in xrange(start, n + 1, 2):
        if current_sum + i <= n and not stop:
        sol.append(0)
        sol[k] = i
            solve(n, k + 1, current_sum + i)
        else:
            return

solve(100000000, 0, 0)

, . n = 100.000, 370 . 0 . ( Mac OS X ).

, Linux:

import os
import sys

sys.setrecursionlimit(100000)


_proc_status = '/proc/%d/status' % os.getpid()

_scale = {'kB': 1024.0, 'mB': 1024.0*1024.0,
          'KB': 1024.0, 'MB': 1024.0*1024.0}

def _VmB(VmKey):
    '''Private.
    '''
    global _proc_status, _scale
     # get pseudo file  /proc/<pid>/status
    try:
        t = open(_proc_status)
        v = t.read()
        t.close()
    except:
        return 0.0  # non-Linux?
     # get VmKey line e.g. 'VmRSS:  9999  kB\n ...'
    i = v.index(VmKey)
    v = v[i:].split(None, 3)  # whitespace
    if len(v) < 3:
        return 0.0  # invalid format?
     # convert Vm value to bytes
    return float(v[1]) * _scale[v[2]]

def memory(since=0.0):
    '''Return memory usage in bytes.
    '''
    return _VmB('VmSize:') - since


stop = False
def solve(n, used, current_sum):
    global stop

    if stop:
        return

    if current_sum == n:
        print(used)
        stop = True
        return

    start = 1 if len(used) == 0 else (used[-1] + 2)
    for i in range(start, n + 1, 2):
        if current_sum + i <= n and not stop:
            used.append(i)
            solve(n, used, current_sum + i)
            used.pop()
        else:
            return

m0 = memory()
solve(100000, [], 0)
m1 = memory(m0)
print(m1/(1024*1024))

() , , 4 MB n, 100.000.000. .

, . , , ( ).

, , . , . . , .

+1

Python3.4 64 Windows 7.

:

  • IDLE, RESTART, , Python , 4000
  • cmd.exe , - Python ( Python.exe cessé de fonctionner), 4000

FreeBSD 10.1 32 512 , 8000

, CPython . , .

( :-)), : , Python .

, n n 2 ( ), . , 100000000 == 10000 2. used, current_sum 2, . , current_sum 2, .

, , :

import sys
sys.setrecursionlimit(100000) 


stop = False
def solve(n, used, current_sum):
    global stop
    if stop:
        return

# TRACES
##    print (len(used), used[-1] if len(used) > 0 else '', end=' ')
##    if (len(used) % 10) == 0:
##        print('')

    if current_sum == n:
        print(used)
        global stop
        stop = True
        return

    if current_sum > n: # simple optimisation, no need to go further
        return

    # the trick : sum of n first numbers is n*n, and we must start 2 steps before
    if current_sum == 0:
        import math
        l = int(math.sqrt(n)) - 2
        current_sum = l * l
        used = list(range(1, l*2, 2))
        solve(n, used, current_sum)
        return

    start = 1 if len(used) == 0 else (used[-1] + 2)
    for i in range(start, n + 1, 2):
        if current_sum + i <= n and not stop:
            used.append(i)
            solve(n, used, current_sum + i)
            used.pop()
        else:
            return

solve(100000000, [], 0)
+1

More articles:


All Articles