grupuri de conducere de număr între două numere

voturi
-1

(Python) Având în vedere două numere A și B. Trebuie să găsesc toate „grupuri“ imbricate de numere:

range(2169800, 2171194)

leading numbers: 21698XX, 21699XX, 2170XX, 21710XX, 217110X, 217111X, 
217112X, 217113X, 217114X, 217115X, 217116X, 217117X, 217118X, 2171190X, 
2171191X, 2171192X, 2171193X, 2171194X

sau ca aceasta:

range(1000, 1452)

leading numbers: 10XX, 11XX, 12XX, 13XX, 140X, 141X, 142X, 143X, 
144X, 1450, 1451, 1452
Întrebat 08/06/2012 la 12:51
de către utilizator
În alte limbi...                            


3 răspunsuri

voturi
0

Acest lucru ar trebui să vă dau un bun punct de plecare:

def leading(start, end):

    leading = []
    hundreds = start // 100

    while (end - hundreds * 100) > 100:
        i = hundreds * 100
        leading.append(range(i,i+100))
        hundreds += 1

    c = hundreds * 100
    tens = 1

    while (end - c - tens * 10) > 10:
        i = c + tens * 10
        leading.append(range(i, i + 10))
        tens += 1

    c += tens * 10
    ones = 1

    while (end - c - ones) > 0:
        i = c + ones
        leading.append(i)
        ones += 1

    leading.append(end)

    return leading

Ok, întregul ar putea fi un nivel mai profund-buclă. Dar m-am gândit că ar putea fi mai clar în acest fel. Sper, acest lucru vă ajută ...

Actualizare: Acum văd ce vrei. Mai mult decât atât, codul lui maria nu pare a fi de lucru pentru mine. (Scuze ...) Deci , vă rugăm să ia în considerare următorul cod:

def leading(start, end):

    depth = 2
    while 10 ** depth > end : depth -=1
    leading = []
    const = 0
    coeff = start // 10 ** depth

    while depth >= 0:
        while (end - const - coeff * 10 ** depth) >= 10 ** depth:
            leading.append(str(const / 10 ** depth + coeff) + "X" * depth)
            coeff += 1

        const += coeff * 10 ** depth
        coeff = 0
        depth -= 1

    leading.append(end)

    return leading

print leading(199,411)

print leading(2169800, 2171194)

print leading(1000, 1453)

print leading(1,12)

Acum, lasă-mă să încerc să explic abordarea aici. Algoritmul va încerca să găsească „capăt“ pornind de la valoarea „start“ și verificați dacă „sfârșit“ este în următorii 10 ^ 2 (care este de 100 în acest caz). Dacă eșuează, se va face un salt de 10 ^ 2, până când reușește. Când se reușește să-l va merge la un nivel mai scăzut de adâncime. Adică, se va face salturi un ordin de mărime mai mică. Și bucla astfel până la adâncimea este egală cu zero (= salturi de 10 ^ 0 = 1). Algoritmul se oprește când ajunge la valoarea „sfârșit“.

De asemenea, este posibil să observați că am pus în aplicare bucla de ambalaj am menționat, astfel că acum este posibil să se definească adâncimea de pornire (sau dimensiune salt), într-o variabilă.

Prima buclă în timp ce asigură primul salt nu depășire valoarea „sfârșit“.

Dacă aveți întrebări, doar nu ezitați să întrebați.

Publicat 08/06/2012 la 13:50
sursa de către utilizator

voturi
0
def foo(start, end):
    index = 0
    is_lower = False
    while index < len(start):
        if is_lower and start[index] == '0':
            break
        if not is_lower and start[index] < end[index]:
            first_lower = index
            is_lower = True
        index += 1
    return index-1, first_lower


start = '2169800'
end = '2171194'
result = []
while int(start) < int(end):
    index, first_lower = foo(start, end)
    range_end = index > first_lower and 10 or int(end[first_lower])
    for x in range(int(start[index]), range_end):
        result.append(start[:index] + str(x) + 'X'*(len(start)-index-1))
    if range_end == 10:
        start = str(int(start[:index])+1)+'0'+start[index+1:]
    else:
        start = start[:index] + str(range_end) + start[index+1:]

result.append(end)
print "Leading numbers:"
print result

Am testat exemplele care le-ați dat, este corect. Sper că acest lucru vă va ajuta

Publicat 08/06/2012 la 14:27
sursa de către utilizator

voturi
0

Mai greu decât părea prima - destul de sigur că acest lucru este solid și se va ocupa de cele mai multe condiții limită. :) (Sunt câteva!!)

def leading(a, b):
    # generate digit pairs a=123, b=456 -> [(1, 4), (2, 5), (3, 6)]
    zip_digits = zip(str(a), str(b))
    zip_digits = map(lambda (x,y):(int(x), int(y)), zip_digits)

    # this ignores problems where the last matching digits are 0 and 9
    # leading (12000, 12999) is same as leading(12, 12)
    while(zip_digits[-1] == (0,9)):         
        zip_digits.pop()            

    # start recursion
    return compute_leading(zip_digits)

def compute_leading(zip_digits):
    if(len(zip_digits) == 1):   # 1 digit case is simple!! :)
        (a,b) = zip_digits.pop()
        return range(a, b+1)

    #now we partition the problem
    # given leading(123,456) we decompose this into 3 problems
    # lows    -> leading(123,129)
    # middle  -> leading(130,449) which we can recurse to leading(13,44)
    # highs   -> leading(450,456)

    last_digits = zip_digits.pop()
    low_prefix  = reduce(lambda x, y : 10 * x + y, [tup[0] for tup in zip_digits]) * 10     # base for lows e.g. 120
    high_prefix = reduce(lambda x, y : 10 * x + y, [tup[1] for tup in zip_digits]) * 10     # base for highs e.g. 450
    lows = range(low_prefix + last_digits[0], low_prefix + 10)
    highs = range(high_prefix + 0, high_prefix + last_digits[1] + 1)

    #check for boundary cases where lows or highs have all ten digits
    (a,b) = zip_digits.pop()    # pop last digits of middle so they can be adjusted
    if len(lows) == 10:
        lows = []
    else:
        a = a + 1

    if len(highs) == 10:
        highs = []
    else:
        b = b - 1

    zip_digits.append((a,b))    # push back last digits of middle after adjustments

    return lows + compute_leading(zip_digits) + highs       # and recurse - woohoo!!



print leading(199,411)

print leading(2169800, 2171194)

print leading(1000, 1452)
Publicat 08/06/2012 la 14:43
sursa de către utilizator

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more