A
UBB · Informatică
236 Raspunsuri multiple

Teo vrea să aranjeze pe un raft n cărți în așa fel încât nici o carte să nu își păstreze poziția inițială. Care dintre următorii algoritmi o ajută pe Teo să afle în câte moduri poate aranja cele n cărți pe raft? Algoritmul factorial(n) calculează n!.

Algoritm 1

Algorithm chapter(n)
  d ← 0
  s ← 1
  For k = 0, n execute
    d ← d + s * factorial(n) DIV factorial(k)
    s ← −s
  EndFor
  Return d
EndAlgorithm

Algoritm 2

Algorithm fiction(n)
  If n = 0 then
    Return 1
  EndIf
  If n = 1 then
    Return 0
  EndIf
  Return (n − 1) * (fiction(n − 1) + fiction(n − 2))
EndAlgorithm

Algoritm 3

Algorithm novel(n)
  d ← 0
  s ← 1
  For k = 0 to n execute
    d ← d + s * factorial(n) DIV factorial(n − k)
    s ← s * (−1)
  EndFor
  Return d
EndAlgorithm

Algoritm 4

Algorithm story(n)
  d ← 0
  s ← 1
  For k = 1, n execute
    d ← d + s * factorial(n) DIV factorial(k)
    s ← s * (−1)
  EndFor
  Return d
EndAlgorithm

Care dintre algoritmii de mai sus calculează corect numărul de derangements pentru n cărți?

19 / 22