1330 - ParitiiMultime: Diferență între versiuni
De la Universitas MediaWiki
(Pagină nouă: = Cerința = Fie <code>n</code> un număr natural nenul și mulțimea <code>A={1,2,3,...,n}</code>. Să se determine toate partițiile disjuncte ale mulțimii <code>A</code>. O partiție a mulțimii <code>A</code> este formată din <code>m</code> (<code>1 ≤ m ≤ n</code>) submulțimi disjuncte ale lui <code>A</code>: <code>A1</code>, <code>A2</code>, …, <code>Am</code> cu proprietatea că <code>A=A1U A2</code> <code>U...U Am</code>. = Date de intrare = Fișierul de int...) |
(Nicio diferență)
|
Versiunea curentă din 18 mai 2024 19:44
Cerința
Fie n
un număr natural nenul și mulțimea A={1,2,3,...,n}
. Să se determine toate partițiile disjuncte ale mulțimii A
.
O partiție a mulțimii A
este formată din m
(1 ≤ m ≤ n
) submulțimi disjuncte ale lui A
: A1
, A2
, …, Am
cu proprietatea că A=A1U A2
U...U Am
.
Date de intrare
Fișierul de intrare partitiimultimeIN.txt
conține pe prima linie numărul n
.
Date de ieșire
Fișierul de ieșire partitiimultimeOUT.txt
va conține câte o linie pentru fiecare partiție determinată. Submulțimile vor fi separate în fiecare linie cu ajutorul caracterului *
, iar elementele fiecărei submulțimi se vor scrie fără spațiere, ca în exemplul de mai jos.
Restricții și precizări
1 ≤ n ≤ 9
- Partițiile determinate se vor afișa în ordine lexicografică
Exemplul 1:
partitiimultimeIN.txt
3
partitiimultimeOUT.txt
123* 12*3* 13*2* 1*23* 1*2*3*
Explicație
Sunt determinate 5
partiții distincte ale mulțimii A
.
{1,2,3}
{1,2} U {3}
{1,3} U {2}
{1} U {2,3}
{1} U {2} U {3}
Exemplul 2:
partitiimultimeIN.txt
10
partitiimultimeOUT.txt
Datele nu corespund restrictiilor impuse
Rezolvare
def maxim(k, x):
z = 0
for i in range(1, k):
z = max(x[i], z)
return z
def scrie(x, n, g):
z = maxim(n + 1, x)
for i in range(1, z + 1):
for j in range(1, n + 1):
if x[j] == i:
g.write(str(j))
g.write("*")
g.write("\n")
def back(k, n, x, g):
if k == n + 1:
scrie(x, n, g)
else:
for i in range(1, maxim(k, x) + 2):
x[k] = i
back(k + 1, n, x, g)
def verifica_restrictii(n, g):
if not (1 <= n <= 9):
g.write("Datele nu corespund restrictiilor impuse\n")
return False
return True
def main():
with open("partitiimultimeIN.txt", "r") as f:
n = int(f.readline().strip())
with open("partitiimultimeOUT.txt", "w") as g:
if verifica_restrictii(n, g):
x = [0] * (n + 1)
x[1] = 1
back(2, n, x, g)
if __name__ == "__main__":
main()