Основи програмирања: вежбе - VI недеља
Задатак 1
Написати функцију која враћа збир првих н бројева. Тражи се рекурзивно решење.
Решење
def suma_do_n_rekurzivno(n):
"""
Написати функцију која враћа збир првих н бројева.
Тражи се рекурзивно решење.
"""
if n == 1:
return 1
return n + suma_do_n_rekurzivno(n-1)
Задатак 2
Написати функциjу коjа не користи петље, а враћа збир цифара унетог произвољног целог броjа.
Решење
def zbir_cifara(n):
if n==0:
return 0
return abs(n)%10 + zbir_cifara(abs(n)//10)
Задатак 3
Написати функциjу коjа врши израчунавање производа два броjа понављањем сабирања.
Решење - итеративно
def mnozenje_iterativno(a, b):
rezultat = 0
while b > 0:
rezultat += a
b -= 1
return rezultat
Решење - рекурзивно
def mnozenje_rekurzivno(a, b):
if b == 0:
return 0
return a + mnozenje_rekurzivno(a, b-1)
Задатак 4
Написати функцију која враћа факторијел броја н.
Решење - итеративно
def faktorijel_iterativno(n):
rezultat = 1
while n > 1:
rezultat *= n
n -= 1
return rezultat
Решење - рекурзивно
def faktorijel_rekurzivno(n):
if n <= 1:
return 1
return n*faktorijel_rekurzivno(n-1)
Задатак 5
Написати функцију која враћа н-ти члан Фибоначијевог низа. Сваки члан Фибоначијевог низа се добија као збир претходна два његова члана. Почетни чланови низа су 0 и 1.
Решење - итеративно
def fibonaci_I(n):
"""Израчунава n-ти Фибоначијев број, за n >= 2."""
prethodni,trenutni = 0, 1 # први и други Фибоначијев број
k = 2 # тренутни Фибоначијев број
while k < n:
prethodni, trenutni = trenutni, prethodni + trenutni
k = k + 1
return trenutni
Решење - рекурзивно
def fibonaci(n):
"""
Написати функцију која враћа н-ти члан Фибоначијевог низа.
Сваки члан Фибоначијевог низа се добија као збир претходна два његова члана.
Почетни чланови низа су 0 и 1.
"""
if n == 1:
return 0
if n == 2:
return 1
return fibonaci(n-1) + fibonaci(n-2)
Задатак 6
Написати функциjу коjа цео броj преводи из декадног у бинарни систем. Траже се и рекурзивно и итеративно решење.
Решење - итеративно
def d2b_iter(n):
k=[]
while (n>0):
a=n%2
k.append(a)
n=n//2
string=""
for j in k[::-1]:
string=string+str(j)
print(string)
#d2b_iter(n)
Решење - рекурзивно
def d2b(n):
if n <=1:
return n
return int(str(d2b(n//2))+str(n%2))
n=int(input())
print(d2b(n))
Задатак 7
Написати функциjу коjа за унети цео броj рачуна следећи поткорени
израз (у примеру jе ’унети’ броj 5):
$\sqrt{5+\sqrt{4+\sqrt{3+\sqrt{2+\sqrt{1}}}}}=2,735877$
Решење - итеративно
from math import sqrt
def korenovi_iterativno(n):
k=0
sum=0
while k<n:
sum=sqrt(sum + k+1)
k+=1
return sum
n=int(input())
print("{:10.6f}".format(korenovi_iterativno(n)))
Решење - рекурзивно
from math import sqrt
def korenovi(n):
if n==1:
return 1
return sqrt(n+korenovi(n-1))
n=int(input())
print("{:10.6f}".format(korenovi(n)))
Задатак 8
Написати функциjу коjа израчунава целоброjну вредност логаритма унетог позитивног природног броjа за задату основу коjа jе већа или jеднака од два, таквог да, када се задата основа степенуjе целоброjном вредношћу коjу процедура враћа, добиjени резултат jе мањи или jеднак унетом броjу.
Решење - итеративно
def moj_logaritam_iterativno(broj, osnova):
vrednost = -1
while broj > 0:
broj//=osnova #broj = broj // osnova
vrednost += 1
if broj == 0:
return vrednost
Решење - рекурзивно
def moj_logaritam_rekurzivno(broj, osnova):
if broj < osnova:
return 0
return 1 + moj_logaritam_rekurzivno(broj/osnova, osnova)
Задатак 9
Написати функцију коjа враћа вредности из одређене врсте и колоне такозваног Паскаловог троугла. Сваки броj унутар Паскаловог троугла представља збир два броjа коjи се налазе изнад њега, док су краjњи броjеви увек jединице. Сматрати да врсте и колоне Паскаловог троугла почињу од jедан, а не од нула.
Решење
def paskalov_trougao(vrsta,kolona):
"""
Написати функцију коjа враћа вредности из одређене врсте и колоне такозваног Паскаловог троугла.
Сваки броj унутар Паскаловог троугла представља збир два броjа коjи се налазе изнад њега, док
су краjњи броjеви увек jединице. Сматрати да врсте и колоне Паскаловог троугла почињу од jедан, а не од нула.
"""
if vrsta == kolona or kolona == 1:
return 1
return paskalov_trougao(vrsta-1,kolona) + paskalov_trougao(vrsta-1,kolona-1)
Задатак 10
Написати рекурзивну функцију коjа врши изокретање ниске, односно ради исто што и ниска[::-1].
Решење
def izokretanje_niske(niska):
"""
Написати рекурзивну функцију коjа врши изокретање ниске, односно ради исто што и ниска[::-1].
"""
if niska == '':
return niska
return izokretanje_niske(niska[1:]) + niska[0]
Задатак 11
Написати функцију која проверава да ли је произвољна реч палиндром.
Тражи се рекурзивно решење.
Решење
def palindrom(niska):
"""
Написати функцију која проверава да ли је произвољна реч палиндром.
Тражи се рекурзивно решење.
"""
if len(niska) == 0 or len(niska) == 1:
return True
if niska[0] != niska[-1]:
return False
return palindrom(niska[1:-1])
Задатак 12
Написати функциjу коjа проверава да ли jе произвољна реченица палиндром.
Тражи се рекурзивно решење.
Решење
def palindrom(n):
def pretvaranje(n):
n = n.lower()
rezultat = ''
for s in n:
if s in 'абвгдђежзиjклљмнњопрстћуфхцчџш':
rezultat = rezultat + s
return rezultat
def pal(n):
if len(n) <= 1:
return True
else:
return n[0] == n[-1] and pal(n[1:-1])
return(pal(pretvaranje(n)))
#print(palindrom('Ана воли Милована.'))
#print(palindrom('Здраво свима.'))
Задатак 13
Написати процедуру коjа прима позитивну целоброjну вредност n, а враћа укупан броj кругова коjи се налази унутар петоугаоног облика у n-тоj итерациjи.
Рекурзивно решење
def petougaoni_broj_rekurzivno(n):
"""
Написати процедуру коjа прима позитивну целоброjну вредност n, а враћа укупан броj кругова коjи
се налази унутар петоугаоног облика у n-тоj итерациjи.
Тражи се рекурзивно решење.
"""
if n ==1:
return 1
return 5*(n-1) + petougaoni_broj_rekurzivno(n-1)
Итеративно решење
def petougaoni_broj_iterativno(n):
"""
Написати процедуру коjа прима позитивну целоброjну вредност n, а враћа укупан броj кругова коjи
се налази унутар петоугаоног облика у n-тоj итерациjи
Тражи се итеративно решење.
"""
broj_kuglica = 1
for i in range(1,n):
broj_kuglica += 5*i
return broj_kuglica
Задатак 14
Написати функцију која враћа број самогласникa у ниски.
Решење - итеративно
def izbroj_samoglasnike_iterativno(niska):
"""
Написати функцију која враћа број самогласникa у ниски.
Тражи се итеративно решење.
"""
res = 0
for char in niska:
res += 1 if char in 'aeiou' else 0
return res
Решење - рекурзивно
def izbroj_samoglasnike_rekurzivno(niska):
"""
Написати функцију која враћа број самогласникa у ниски.
Тражи се рекурзивно решење.
"""
if niska == '':
return 0
res = 1 if niska[0] in 'aeiou' else 0
return res + izbroj_samoglasnike_rekurzivno(niska[1:])
Задатак 15
Написати функцију која враћа број појављивања цифара у ниски. Тражи се рекурзивно решење.
Решење
def izbroj_cifre_rekurzivno(niska):
"""
Написати функцију која враћа број појављивања цифара у ниски.
Тражи се рекурзивно решење.
"""
if niska == '':
return 0
res = 1 if niska[0].isdigit() else 0
return res + izbroj_cifre_rekurzivno(niska[1:])
Задатак 16
Написати функцију коjа прима две ниске произвољних дужина, а враћа ниску коjа садржи испреплетане чланове улазних ниски почевши од прве. За случаj да су дужине улазних ниски различите, одговараjући чланови дуже ниске биће придружени на краjу резултуjуће ниске.
Решење - итеративно
def isprepletaneIterativno(niska1, niska2):
"""
Претпоставља да су улазне ниске (1 и 2) произвољних дужина и произвољног садржаjа.
Прави и враћа ниску сачињену преплитањем чланова улазних ниски почевши од прве.
"""
i = 0
rezultat = ""
while i < len(niska1) and i < len(niska2):
rezultat += niska1[i] + niska2[i]
i += 1
rezultat += niska1[i:] + niska2[i:]
return rezultat
Решење - рекурзивно
def isprepletaneRekurzivno(niska1, niska2):
"""
Претпоставља да су улазне ниске (1 и 2) произвољних дужина и произвољног садржаjа.
Прави и враћа ниску сачињену преплитањем чланова улазних ниски почевши од прве.
"""
if niska1 == "": # или if len(niska1) == 0:
return niska2
if niska2 == "": # или if len(niska2) == 0:
return niska1
return niska1[0] + niska2[0] + isprepletaneRekurzivno(niska1[1:], niska2[1:])