Факториалы
def test(n):
if n<1: return
n=n-1
print("туда")
test(n)
print("обратно")
test(5);
#простейшая рекурсия
def test(m,n):
while n>0:
print("m: ",m);
print("n: ",n);
m=m*n;
print("m*n=",m,"\n");
n=n-1;
test(1,5);
#цикл факториал 5(единицу менять нельзя)
# m - это итоговая переменная
def test(n,result):
if n<1: return
result=result*n
print("счетчик=",n," результат=",result,"\n")
n=n-1
test(n,result)
test(5,1);
#рекурсия факториал 5(единицу менять нельзя)
# (n,result): - это итоговая переменная
def test(m,n):
final=m;
while n>m:
print("m: ",m);
print("счетчик n: ",n);
print("final: ",final);
print("final*n=",final,"*",n,"=",final*n);
final=final*n;
print("final: ",final,"\n");
n=n-1;
test(3,6);
#цикл факториал нужного диапазона
# final - это итоговая переменная
def test(n):
if n==1:
return "stop!"
print("Начали! n =",n)
n=n-1
print("n =",n)
print("печать ",test(n))
return n
test(4);
# рекурсия с возвратом значения функции
def test(n):
if n==2:
print("стоп! возвращаю 2 \n")
return 2
print("Начали! n =",n,", n-1=",n-1,"\n")
n=n-1
res_test=test(n)
fact=res_test*(n+1)
print("возврат: n =",n,", n+1 =",n+1,", res_test =",res_test)
print("fact=res_test*(n+1)=",fact,"\n")
return fact
qq=test(5);
print("финальный результат=",qq)
# неуклюжая рекурсия-факториал с возвратом значения функции
def test(n):
if n==1:
print("стоп! возвращаю 1 \n")
return 1
print("Начали! n =",n,", n-1=",n-1,"\n")
fact=test(n-1)*n
print("возврат test(n-1)*n =",fact)
return fact
qq=test(4);
print("QQ=",qq)
# рекурсия-факториал с возвратом значения функции
def test(n):
if n==1:
return 1
fact=test(n-1)*n
return test(n-1)*n
print(test(4))
# изящная рекурсия-факториал с возвратом значения функции
# тут функция возвращается сразу с формулой
Фибоначчи
a=0
b=1
result=a+b
print("a =",a,", b =",b,", result =",a+b)
#преобразование фибоначчи
a=0
b=1
result=a+b
a=b
b=result
result=a+b
print("a =",a,", b =",b,", result =",a+b)
result=a+b
a=b
b=result
result=a+b
print("a =",a,", b =",b,", result =",a+b)
#преобразование фибоначчи (можно повторять)
a=0
b=1
for i in range(7):
result=a+b
a=b
b=result
result=a+b
print("a =",a,", b =",b,", result =",a+b)
#цикл фибоначчи
def test(n):
if n==0: return ("Фома","Ерёма")#возврат кортежа
print("вглубь",n)
a,b=test(n-1) #распаковка кортежа
print("принт",a,b)
return (a,b)
test(5)
#возврат нескольких значений в виде кортежа
def test(n):
if n==0: return (0,1)#изначальные значения Фибоначчи
print("вглубь",n)
a,b=test(n-1) #распаковка кортежа
print("a:",a,", b:",b)
result=a+b;
print("result:",result,"\n")
return (b,result)#всякое число Фибоначчи - это сумма предыдущего результата и бОльшего из его слагаемых
test(8)
#рекурсия фибоначчи (с кортежем)
def test(n):
if n<=0: return (0)
print("вглубь",n)
test(n-1)
test(n-2)
print("обратно",n)
test(4)
#непростая рекурсия с двойным вызовом
def test(n):
if n==1: return (0)
if n==2: return (1)
print("вглубь",n)
a=test(n-1)
b=test(n-2)
print("a:",a,", b:",b)
result=a+b;
print("result =",result)
return (result)
print("Финал!",test(5))
#рекурсия Фибоначчи с двойным вызовом
#выводится только одно значение из всего ряда
Число в степени
def test(a,n):
etalon=a
x=1
while x<n:
print("a:",a)
a=a*etalon
print("a в степени:",a)
x=x+1
return a
print(test(2,6))
# цикл. число в степени
def test(a,n):
etalon=a
if n==1:
return a
print ("a=",a," ,n=",n)
a=a*(test(a,n-1))
print ("сборка a=",a)
return a
print(test(2,6))
# рекурсия. число в степени (только положительные степени)
def test(a,n):
etalon=a
if n==0:
print ("a=",a," ,n=",n)
return 1
if n==1:
print ("a=",a," ,n=",n)
return a
print ("a=",a," ,n=",n)
a=a*(test(a,n-1))
print ("сборка a=",a)
return a
print(test(2,0))
# рекурсия. число в степени (только положительные степени и ноль)
def test(a,n):
if n==0:
print ("a=",a," ,n=",n)
return 1
else:
print ("a=",a," ,n=",n)
return a*(test(a,n-1))
print ("сборка a=",a)
# изящная рекурсия. число в степени (только положительные степени и ноль)
Число через пробелы
def test(n):
if n//10==0:
print("n=",n, ", n%10=",n%10,", n//10=",n//10," STOP!")
return n%10
print("n=",n, ", n%10=",n%10,", n//10=",n//10)
res=str(test(n//10))+" "
print(res)
return res+str(n%10)
print(test(573))
# неуклюжая рекурсия. запись числа через пробелы
Сумма цифр
result=0
n=643
while n>0:
print("результат =",result," , n =",n," , младший разряд n =",n%10)
result=result+n%10
n=n//10
print("результат =",result," , n =",n,"\n")
#цикл сумма цифр числа
def test(n):
print("n =",n)
if n==0:
print("стоп. Тут нет больше цифр.\n")
return 0
print("n>0, OK. нацело =",n//10," , остаток =",n%10,"\n")
res=n%10+test(n//10)
print("res=",res," \n")
return res
test(375)
#рекурсия сумма цифр числа
Двойка в степени
def test(n):
print("n =",n)
if n==1:
print("Это двойка в степени!")
return
elif n<1:
print("неверное число")
return
else:
test(n/2)
test(512)
# неуклюжая рекурсия (двойка ли это в n-степени?)
def test(n):
if n==1:
print("n=1, n =",n)
return "Это двойка в степени!"
if n<1:
print("n<1, n =",n)
return "неверное число"
if n>1:
print("n>1, n =",n)
return test(n/2)
print(test(16))
# ещё одна неуклюжая рекурсия (двойка ли это в n-степени?)
def test(n):
if n<1:
print("n =",n, " , это не двойка...")
return 0
if n==1:
print("n =",n, " , это 2 в степени!")
print("\n2 в степени 0")
return 0
print("n =",n)
exponent=1+test(n/2)
print("степень",exponent)
return exponent
print(test(9))
# ещё одна неуклюжая рекурсия
#(показывает ещё и степень двойки)
Палиндром
n="abcdef"
print("всё слово: ",n)
print("последняя буква: ",n[len(n)-1])
n=n[: - 1]
print("урезанное слово: ",n)
#учимся обращаться с строкой
def test(n):
if len(n)<1: return
print("всё слово: ",n)
print("последняя буква: ",n[len(n)-1],"\n")
test(n[: - 1])
print("обратно: ",n)
test("abcdef")
#"прогоняем" слово через рекурсию
n="abcdef"
x=1
while x<=len(n):
print(n[x-1])
print(n[len(n)-x],"\n")
x+=1
#цикл: "прогоняем" слово через напрямую и задом наперёд
n="abcdbf"
x=1
while x<=len(n):
front=n[x-1]
print(front)
back=n[len(n)-x]
print(back)
if front==back:
print("равенство!","\n")
else:
print("нет равенства...","\n")
x+=1
#цикл: определяем равенство/неравенство
n="abcdcba"
x=1
is_palindrom="это не палиндром... ~_~"
while x<=len(n):
front=n[x-1]
print(front)
back=n[len(n)-x]
print(back)
if front==back:
print("равенство!","\n")
is_palindrom="палиндром! ^_^"
else:
print("нет равенства...","\n")
is_palindrom="это не палиндром... ~_~"
break
x+=1
print(is_palindrom)
#цикл: палиндром
def test(n):
if len(n)<1: return
print("всё слово: ",n)
print("1-я буква: ",n[0])
print("последняя буква: ",n[len(n)-1])
if n[0]==n[len(n)-1]:
print("равно!","\n")
else:
print("не равно...","\n")
return
n=n[1:]
test(n[: - 1])
print("ЭТО ПАЛИНДРОМ!!!")
test("qwerttrewq")
# очень неуклюжая рекурсия-палиндром
def test(n):
if len(n)<1: return True
print("всё слово: ",n)
print("1-я буква: ",n[0])
print("последняя буква: ",n[len(n)-1])
if n[0]==n[len(n)-1]:
print("равно!","\n")
else:
print("не равно...","\n")
return False
n=n[1:]
return test(n[: - 1])
print(test("252"))
# изящная рекурсия-палиндром. Тут всегда по цепочке возвращается TRUE, кроме случаев неравенства.
# Тогда всё прерывается и выводится FALSE
ханойские башни
Неуклюжее, но работающее решение.
Тут аж 4 вспомогательные функции! :-(
axes=[[4,3,2,1,0],[],[]]
#нахождение промежуточной оси
def transitive_axis(a,b):
print(" \n функция \"transitive_axis\", элементы",a,"и",b)
if a+b==1: return 2
if a+b==2: return 1
if a+b==3: return 0
#перемещение элемента с оси на ось
def move(element,start,finish):
print(" \n функция \"move\", элемент",element,"с",start,"на",finish)
print("было: ",axes)
axes[start].remove(element)
axes[finish].append(element)
print("стало:",axes,"\n")
#поиск элемента. возвращается номер оси и позиция (списком)
def search_element(element):
print(" \n функция \"search_element\", элемент",element,":")
for q in range(3):
if axes[q].count(element)>0:
return (q,axes[q].index(element))
#есть ли гнет над элементом? Если есть - возврат элемента гнёта, если нет - возврат False
def pressure(element):
print(" \n функция \"pressure\", элемент",element,":")
search=search_element(element)
element_axes=search[0]
print(" ось элемента",element_axes)
element_position=search[1]
print(" позиция элемента",element_position)
last_element_position=len(axes[element_axes])-1
print(" позиция последнего элемента:",last_element_position)
if last_element_position>element_position:
print(" гнёт присутствует \n")
return axes[element_axes][element_position+1]
else:
print(" гнёта нету \n")
return False
# основная функция. элемент, начало и конец перемещения
def hanoi(element,start,finish):
print("\n Функция \"HANOI\":",element,"с",start,"на",finish)
#вариант 1: отрицательное значение
if element<0:
print("element<0 ! возврат! \n")
return
#вариант 2: 0 (т.е., это вершина пирамиды)
if element==0:
print("element=0 !")
move(element,start,finish)
return
#вариант 3: >0 (т.е., это любой элемент, кроме вершины)
press=pressure(element)
if type(press)==int:
print("есть гнет. Кто угнетает? ",press)
print("рекурсия hanoi(press) на transitive_axis")
hanoi(press,start,transitive_axis(start,finish))
if type(press)==bool:
print("нету гнета. Это ",press)
print("ПРОПУСК")
print("ПЕРЕМЕЩЕНИЕ")
move(element,start,finish)
print("ХАНОЙ (element-1,НЕ_СТАРТ_И_НЕ_ФИНИШ,ФИНИШ)")
hanoi(element-1,transitive_axis(start,finish),finish)
hanoi(4,0,2)