2427 - Sir 10: Difference between revisions
Sinn Erich (talk | contribs) |
Sinn Erich (talk | contribs) |
||
(8 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp] | Sursa: [https://www.pbinfo.ro/probleme/4273/prodpp] | ||
== Cerinţa == | == Cerinţa == | ||
Gigel se distrează construind şiruri crescătoare de numere din mulţimea '''{1,2,…,n}'''. La un moment dat observă că unele şiruri, de cel puţin ''' | Gigel se distrează construind şiruri crescătoare de numere din mulţimea '''{1,2,…,n}'''. La un moment dat observă că unele şiruri, de cel puţin k '''nr_termeni''' '''(k ≥ 3)''', au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru '''n ≥ 22''': | ||
2, 3, 4 | 2, 3, 4 | ||
Line 26: | Line 26: | ||
3 ≤ '''n''' ≤ 20000 | 3 ≤ '''n''' ≤ 20000 | ||
3 ≤ ''' | 3 ≤ '''nr_termeni''' ≤ n | ||
== Exemplul 1 == | == Exemplul 1 == | ||
Line 32: | Line 32: | ||
: N este: | : N este: | ||
: 3 | : 3 | ||
; Datele de ieșire | |||
: Datele sunt introduse corect. | : Datele sunt introduse corect. | ||
: 1 | : 1 | ||
<br> | <br> | ||
Line 41: | Line 41: | ||
: N este: | : N este: | ||
: 4 | : 4 | ||
; Datele de ieșire | |||
: Datele sunt introduse corect. | : Datele sunt introduse corect. | ||
: 3 | : 3 | ||
<br> | <br> | ||
Line 48: | Line 48: | ||
== Exemplul 3 == | == Exemplul 3 == | ||
; Datele de intrare | ; Datele de intrare | ||
: N este: | |||
: 5 | : 5 | ||
; Datele de ieșire | |||
: Datele sunt introduse corect. | : Datele sunt introduse corect. | ||
: 7 | : 7 | ||
<br> | <br> | ||
Line 57: | Line 58: | ||
<syntaxhighlight lang="python" line> | <syntaxhighlight lang="python" line> | ||
#2427 | #2427 | ||
def has_valid_input(n, | def has_valid_input(n, nr_termeni): | ||
if not (3 <= n <= 20000): | if not (3 <= n <= 20000): | ||
print("Datele nu corespund restricțiilor impuse.") | print("Datele nu corespund restricțiilor impuse.") | ||
return False | return False | ||
if not (3 <= | if not (3 <= nr_termeni <= n): | ||
print("Datele nu corespund restricțiilor impuse.") | print("Datele nu corespund restricțiilor impuse.") | ||
return False | return False | ||
return True | return True | ||
def has_property(sir): | |||
d = sir[1] - sir[0] | |||
for i in range(2, len(sir)): | |||
if sir[i] - sir[i - 1] != d: | |||
return False | |||
return True | |||
def backtracking(sir, pozitie): | |||
global nr_siruri | |||
if len(sir) >= nr_termeni: | |||
if has_property(sir): | |||
nr_siruri += 1 | |||
for i in range(pozitie + 1, n + 1): | |||
sir.append(i) | |||
backtracking(sir, i) | |||
sir.pop() | |||
if __name__ == '__main__': | if __name__ == '__main__': | ||
n = int(input("N este:")) | n = int(input("N este:")) | ||
nr_termeni = 3 | |||
nr_siruri = 0 | nr_siruri = 0 | ||
if not has_valid_input(n, | if not has_valid_input(n, nr_termeni): | ||
exit() | exit() | ||
backtracking([], 0) | backtracking([], 0) | ||
print("Datele sunt introduse corect.") | print("Datele sunt introduse corect.") | ||
print(nr_siruri) | print(nr_siruri) | ||
</syntaxhighlight> | </syntaxhighlight> | ||
'''Explicatie cod:''' | '''Explicatie cod:''' | ||
Acest program calculează numărul de șiruri aritmetice de lungime fixă și dimensiune n, care încep cu un element oarecare și au cel puțin trei elemente și diferența constantă între oricare două elemente consecutive. Programul utilizează un algoritm de backtracking pentru a genera toate șirurile posibile, verificând dacă acestea au proprietatea cerută. | |||
Funcția has_valid_input(n, nr_termeni) verifică dacă inputul dat este valid, adică dacă n și nr_termeni se încadrează într-un interval specificat. În caz contrar, se afișează un mesaj de eroare și se returnează False. | |||
Funcția has_property(sir) verifică dacă un șir dat are proprietatea cerută (adică diferența dintre oricare două elemente consecutive este constantă). Dacă această proprietate este îndeplinită, funcția returnează True. Dacă nu, funcția returnează False. | |||
Funcția backtracking(sir, pozitie) utilizează un algoritm de backtracking pentru a genera toate șirurile posibile care îndeplinesc cerințele. Aceasta primește ca argumente sir, care reprezintă șirul curent, și pozitie, care reprezintă poziția curentă în șirul n. Dacă șirul sir are cel puțin nr_termeni elemente și îndeplinește proprietatea cerută, se incrementează nr_siruri. Altfel, se explorează toate combinațiile posibile ale elementelor următoare în șirul n cu ajutorul unei bucle for. În continuare, se adaugă elementul curent în sir, se apelează recursiv funcția backtracking() pentru a explora toate posibilitățile ulterioare, se scoate ultimul element adăugat din sir și se continuă cu următoarea iterație a buclei. | |||
În | În blocul if __name__ == '__main__': se citesc datele de intrare n și se inițializează variabilele nr_termeni și nr_siruri. Apoi, se verifică dacă datele introduse sunt valide, utilizând funcția has_valid_input(). Dacă inputul este valid, se apelează funcția backtracking() pentru a calcula numărul de șiruri cerute și se afișează rezultatul. |
Latest revision as of 08:43, 29 April 2023
Sursa: [1]
Cerinţa[edit | edit source]
Gigel se distrează construind şiruri crescătoare de numere din mulţimea {1,2,…,n}. La un moment dat observă că unele şiruri, de cel puţin k nr_termeni (k ≥ 3), au o proprietate mai aparte: diferența dintre doi termeni consecutivi este constantă. Iată câteva exemple de astfel de şiruri pentru n ≥ 22:
2, 3, 4
1, 5, 9, 13
7, 10, 13, 16, 19, 22
Dându-se numărul natural n ajutați-l pe Gigel să numere câte astfel de șiruri poate să construiască.
Date de intrare[edit | edit source]
Programul conține pe prima linie numărul n.
Date de ieșire[edit | edit source]
Programul va conține pe prima linie numărul cerut.
Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează câte astfel de șiruri poate să construiască poate să construiască Gigel.
În caz contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."
Restricţii şi precizări[edit | edit source]
3 ≤ n ≤ 20000
3 ≤ nr_termeni ≤ n
Exemplul 1[edit | edit source]
- Datele de intrare
- N este:
- 3
- Datele de ieșire
- Datele sunt introduse corect.
- 1
Exemplul 2[edit | edit source]
- Datele de intrare
- N este:
- 4
- Datele de ieșire
- Datele sunt introduse corect.
- 3
Exemplul 3[edit | edit source]
- Datele de intrare
- N este:
- 5
- Datele de ieșire
- Datele sunt introduse corect.
- 7
Rezolvare[edit | edit source]
<syntaxhighlight lang="python" line>
- 2427
def has_valid_input(n, nr_termeni):
if not (3 <= n <= 20000): print("Datele nu corespund restricțiilor impuse.") return False if not (3 <= nr_termeni <= n): print("Datele nu corespund restricțiilor impuse.") return False return True
def has_property(sir):
d = sir[1] - sir[0] for i in range(2, len(sir)): if sir[i] - sir[i - 1] != d: return False return True
def backtracking(sir, pozitie):
global nr_siruri if len(sir) >= nr_termeni: if has_property(sir): nr_siruri += 1 for i in range(pozitie + 1, n + 1): sir.append(i) backtracking(sir, i) sir.pop()
if __name__ == '__main__':
n = int(input("N este:")) nr_termeni = 3 nr_siruri = 0
if not has_valid_input(n, nr_termeni): exit()
backtracking([], 0) print("Datele sunt introduse corect.") print(nr_siruri)
</syntaxhighlight>
Explicatie cod:
Acest program calculează numărul de șiruri aritmetice de lungime fixă și dimensiune n, care încep cu un element oarecare și au cel puțin trei elemente și diferența constantă între oricare două elemente consecutive. Programul utilizează un algoritm de backtracking pentru a genera toate șirurile posibile, verificând dacă acestea au proprietatea cerută.
Funcția has_valid_input(n, nr_termeni) verifică dacă inputul dat este valid, adică dacă n și nr_termeni se încadrează într-un interval specificat. În caz contrar, se afișează un mesaj de eroare și se returnează False.
Funcția has_property(sir) verifică dacă un șir dat are proprietatea cerută (adică diferența dintre oricare două elemente consecutive este constantă). Dacă această proprietate este îndeplinită, funcția returnează True. Dacă nu, funcția returnează False.
Funcția backtracking(sir, pozitie) utilizează un algoritm de backtracking pentru a genera toate șirurile posibile care îndeplinesc cerințele. Aceasta primește ca argumente sir, care reprezintă șirul curent, și pozitie, care reprezintă poziția curentă în șirul n. Dacă șirul sir are cel puțin nr_termeni elemente și îndeplinește proprietatea cerută, se incrementează nr_siruri. Altfel, se explorează toate combinațiile posibile ale elementelor următoare în șirul n cu ajutorul unei bucle for. În continuare, se adaugă elementul curent în sir, se apelează recursiv funcția backtracking() pentru a explora toate posibilitățile ulterioare, se scoate ultimul element adăugat din sir și se continuă cu următoarea iterație a buclei.
În blocul if __name__ == '__main__': se citesc datele de intrare n și se inițializează variabilele nr_termeni și nr_siruri. Apoi, se verifică dacă datele introduse sunt valide, utilizând funcția has_valid_input(). Dacă inputul este valid, se apelează funcția backtracking() pentru a calcula numărul de șiruri cerute și se afișează rezultatul.