0806 - Generare sir

Cerinţa

Se consideră şirul definit mai jos:

fn= 1 daca n =1

fn= 1 + f(n-1) daca n e par

fn= 1 + 2*f(n-2) dacă n altfel

în care nu există doi termeni cu aceeași paritate aflați pe poziții consecutive: 1, 2, 3, 4, 7, 8, 15, 16 .....

Pentru un număr natural x, termen al şirului dat, se cere să se afișeze pe ecran, în ordine strict descrescătoare, separați prin câte un spațiu, toţi termenii şirului care sunt mai mici sau egali cu x.

Date de intrare

Programul citeşte de la tastatură numărul x

Date de ieşire

Programul va afişa pe ecran în ordine strict descrescătoare, separați prin câte un spațiu, toţi termenii şirului care sunt mai mici sau egali cu x.

Restricţii şi precizări

• 1 ≤ x ≤ 1.000.000.000

Exemplul 1

Date intrare

15

Date iesire

15 8 7 4 3 2 1

Exemplul 2

Date intrare

0

Cerința

Numărul introdus nu respectă restricțiile.

Rezolvare

def verifica_restrictii(x):
    return 1 <= x <= 1000000000

def genereaza_si_afiseaza_sir(x):
    def f(n):
        if n == 1:
            return 1
        elif n % 2 == 0:
            return 1 + f(n - 1)
        else:
            return 1 + 2 * f(n - 2)

    termeni_sir = []

    # Generăm șirul până când obținem un termen mai mare decât x
    n = 1
    while f(n) <= x:
        termeni_sir.append(f(n))
        n += 1

    # Afișăm termenii în ordine descrescătoare
    termeni_sir.sort(reverse=True)

    print(" ".join(map(str, termeni_sir)))

def main():
    x = int(input("Introduceți numărul x: "))

    if verifica_restrictii(x):
        genereaza_si_afiseaza_sir(x)
    else:
        print("Numărul introdus nu respectă restricțiile.")

if __name__ == "__main__":
    main()