1

Тема: як замінити вкладені цикли на рекурсію?

є код:

n, m = list(map(int, input().split(' ')))
for i in range(n):
    for ii in range(m):
        print(i, ii)

підкажіть - як отримати такий же результат за допомогою рекурсії?
(вкладених циклів може бути багато)

2

Re: як замінити вкладені цикли на рекурсію?

Ще було б добре зрозуміти ваш перший рядок, що то і навіщо? Схоже на якесь дуже дурне отримання двох чисел від користувача. А якщо ж вам потрібно пройтися просто звичайними циклами і отримати всі можливі значення, то спробуйте поглянути на модуль itertools, може там вже є все, що вам потрібно.

3 Востаннє редагувалося ping (15.07.2016 11:28:37)

Re: як замінити вкладені цикли на рекурсію?

Master_Sergius написав:

Ще було б добре зрозуміти ваш перший рядок, що то і навіщо? Схоже на якесь дуже дурне отримання двох чисел від користувача.

підкажіть - як виглядає дуже розумне отримання двох чисел від користувача? а якщо не двох, а двохсот?

А якщо ж вам потрібно пройтися просто звичайними циклами і отримати всі можливі значення, то спробуйте поглянути на модуль itertools, може там вже є все, що вам потрібно.

думаю, що є.

але потрібен код без імпорту модулів.

4 Востаннє редагувалося Master_Sergius (15.07.2016 11:49:03)

Re: як замінити вкладені цикли на рекурсію?

Ну, відштовхуючись від вашого прикладу, можна спробувати такі способи:

1)
s = raw_input()
numbers = map(int, s.split())

2)
numbers = [int(x) for x in input().split()]

Принаймні, щоб хоч не було отого розпаковування, коли у вас дійсно невідома наперед кількість чисел. А так то можна ще кілька способів придумати, навіть просто введення "по одному".

Якщо ж без імпорту модулів, ну є різні алгоритми, можна погуглити. Можна спробувати якось так:

1) вважаємо, що у вас є N чисел, для прикладу, візьмемо N=5, їхні значення -  ABCDE;
2) отже потрібно, імітувати цикли виду:
a : від 0 до A,
b : від 0 до B...
....
e : від 0 до E

Підемо як вкладені цикли з кінця, тобто змінюемо "e", коли е стане E, то ми повинні збільшити d на 1, а е = 0. І пішло далі.
Очевидно, що тут краще скористатися одним загальним циклом while, і перевіряти умову чи продовжувати цикл. А цикл зупинити тоді, коли у нас abcde стане ABCDE.

Подякували: ping1

5

Re: як замінити вкладені цикли на рекурсію?

Перетворення циклів на рекурсію? Як правило, намагаються зробити навпаки, щоб запобігти переповненню стеку. Але, якщо це справді конче необхідно, то можна так:

def inner_loop(i, ii, m):
    if ii<m:
        print(i, ii)
        inner_loop(i, ii+1, m)

def outer_lopp(i, n, m):
    if i<n:
        inner_loop(i, 0, m)
        outer_loop(i+1, n, m)

n, m = list(map(int, input().split(' ')))
outer_loop(0, n, m)

(насправді можна було б зменшити кількість параметрів, розмістивши одну функцію в іншій, але мені лінь це набирати у формі, де немає автовідступу).

Подякували: leofun011

6

Re: як замінити вкладені цикли на рекурсію?

P.Y. написав:

Перетворення циклів на рекурсію? Як правило, намагаються зробити навпаки, щоб запобігти переповненню стеку.

А ще у пайтоні виклик функції "досить" дорого обходиться. Завдання чисто синтетичне.

7

Re: як замінити вкладені цикли на рекурсію?

Master_Sergius написав:

Ну, відштовхуючись від вашого прикладу, можна спробувати такі способи:

1)
s = raw_input()
numbers = map(int, s.split())

в третьому пітоні (замінивши raw_input на input) numbers перетвориьтся в <map object at 0x7f3c69d2d198>



2)

numbers = [int(x) for x in input().split()]

Принаймні, щоб хоч не було отого розпаковування, коли у вас дійсно невідома наперед кількість чисел.

не розумію -  в чому тут відмінність від того, що у мене?


Якщо ж без імпорту модулів, ну є різні алгоритми, можна погуглити. Можна спробувати якось так:

хіба рекурсія не буде найоптимальнішим рішенням?
(так, я знаю, що час її робити на порядки більший , ніж і цикла, але цим параметром нехтуємо)

8 Востаннє редагувалося P.Y. (15.07.2016 12:04:32)

Re: як замінити вкладені цикли на рекурсію?

2)
numbers = [int(x) for x in input().split()]

Чим це принципово відрізнється від того, що було в оригіналі? Хіба що .split() дозволяє використовувати замість одного пробіла будь-яку кількість пробілів та табуляцій, і ввід записується в масив замість двох змінних. Чисел за умовою все одно потрібно два — якщо ми хочемо, щоб програма не вилітала при некоректному вводі, то краще вже ловити виключення:

while True:
    try:
        n, m = list(map(int, input().split(' ')))
        break
    except:
        pass
Подякували: ping1

9

Re: як замінити вкладені цикли на рекурсію?

P.Y. написав:

Перетворення циклів на рекурсію? Як правило, намагаються зробити навпаки, щоб запобігти переповненню стеку. Але, якщо це справді конче необхідно, то можна так:

def inner_loop(i, ii, m):
    if ii<m:
        print(i, ii)
        inner_loop(i, ii+1, m)

def outer_lopp(i, n, m):
    if i<n:
        inner_loop(i, 0, m)
        outer_loop(i+1, n, m)

n, m = list(map(int, input().split(' ')))
outer_loop(0, n, m)

(насправді можна було б зменшити кількість параметрів, розмістивши одну функцію в іншій, але мені лінь це набирати у формі, де немає автовідступу).


дякую. для двох працюватиме.
на жаль, кількість вкладениих циклів наперед не відома.

10 Востаннє редагувалося ADR (15.07.2016 14:48:14)

Re: як замінити вкладені цикли на рекурсію?

ping написав:

на жаль, кількість вкладениих циклів наперед не відома.

Ну так з цього і починати треба було)

Щось типу такого:

def printCombinations(length_list, begin=''):
    for i in range(length_list[0]):
        new_begin = begin + (' ' if begin else '') + str(i)

        if len(length_list) > 1:
            printCombinations(length_list[1:], new_begin)
        else:
            print(new_begin)

printCombinations([n, m])
Приклад

Вхід:

printCombinations([5, 2, 3])

Вихід:

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2
1 0 0
1 0 1
1 0 2
1 1 0
1 1 1
1 1 2
2 0 0
2 0 1
2 0 2
2 1 0
2 1 1
2 1 2
3 0 0
3 0 1
3 0 2
3 1 0
3 1 1
3 1 2
4 0 0
4 0 1
4 0 2
4 1 0
4 1 1
4 1 2

Хоча можливо, що ті цифри є аргументами для вашої функції, яку ви не вказали? Тоді так:

Прихований текст
def printCombinations(length_list, func, begin=[]):
    for i in range(length_list[0]):
        if len(length_list) > 1:
            printCombinations(length_list[1:], func, begin + [i])
        else:
            func(begin + [i])

def custom_func(arg):
    print(' '.join(map(str, arg)))

printCombinations([5, 2, 3], custom_func)

Чи навіть так:

Прихований текст
def printCombinations(argument_list, func, begin=[]):
    for e in argument_list[0]:
        if len(argument_list) > 1:
            printCombinations(argument_list[1:], func, begin + [e])
        else:
            func(begin + [e])

def custom_func(arg):
    print(''.join(map(str, arg)))

printCombinations([['hello', 'world'], ['_'], [0, 5], list(range(2))], custom_func)

Результат:

hello_00
hello_01
hello_50
hello_51
world_00
world_01
world_50
world_51
Подякували: ping, ReAl, leofun013

11

Re: як замінити вкладені цикли на рекурсію?

Здається, почав розуміти, що насправді малось на увазі. Якщо рекурсія потрібна для заміни вкладеності циклів (а не для заміни самих циклів), рівень якої ми не знаємо наперед (а отже, чисел на вході може бути не два, а будь-яка кількість), то тут справді найкраще підійде приклад вводу від Master_Sergius, де ці числа записуються в список.

Тоді увесь приклад матиме приблизно такий вигляд:

def loop(numbers, counters):
    if numbers==[]:
        print(*counters)
    else:
        for i in range(numbers[0]):
            loop(numbers[1:], counters+[i])


numbers = list(map(int, input().split(' ')))
loop(numbers, [])
Подякували: ping, ReAl, leofun013