2553 - Josephus: Difference between revisions
No edit summary |
|||
Line 1: | Line 1: | ||
==Cerința== | |||
Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic! | Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic! | ||
Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață. | Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață. | ||
Latest revision as of 14:33, 14 May 2023
Cerința[edit | edit source]
Aceasta este o problemă foarte cunoscută atât în universul informatic, cât și în cel matematic!
Legenda ne povestește că Josephus și alți n-1 soldați evrei se luptau cu trupele romane. Din nefericire pentru aceștia, au ajuns foarte curând încercuiți și doborâți numeric. Ei se hotărăsc rapid să nu se predea, dar nici să nu își ia de unii singuri viața și astfel le vine următoarea idee: se așează cu toții într-un cerc și își scriu pe rând pe frunte câte un număr, reprezentând indicativul fiecăruia (1, 2, …, n). Soldații decid ca soldatul cu numărul 1 să îl trimită în rai pe soldatul încă în viață din stânga sa (notat, în acest context, cu numărul 2), apoi următorul soldat în viață să repete aceeași acțiune până când nu va mai rămâne decât o singură persoană în viață.
Josephus ar fi preferat să se predea. Pe ce poziție ar fi trebuit să se afle soldatul pentru a putea realiza acest lucru?
Date de intrare[edit | edit source]
Se va citi un singur număr natural nenul, n.
Date de ieșire[edit | edit source]
Se va afișa un singur număr ce reprezintă poziția pe care Josephus trebuia să se afle pentru a rămâne în viață, alături de un mesaj de validare a datelor introduse ("Input valid"; se afișează "n trebuie să fie între i și 10^18" în caz contrar).
Restricții și precizări[edit | edit source]
- 1 ≤ n ≤ 1018;
- Se garantează că există o soluție pentru oricare n;
Exemplu[edit | edit source]
- Intrare
- 41
- Ieșire
- Input valid
- 19
Explicație[edit | edit source]
1 ⇒ 2
3 ⇒ 4
…
39 ⇒ 40
41 ⇒ 1
3 ⇒ 5
…
39 ⇒ 41
3 ⇒ 7
11 ⇒ 15
………
19 ⇒ 35
Rezolvare[edit | edit source]
<syntaxhighlight lang="python"> def calculate_exponent(n):
exponent = 0 save_n = n while save_n != 1: save_n //= 2 exponent += 1 return exponent
def is_power_of_two(n):
exponent = calculate_exponent(n) return (1 << exponent) == n
def calculate_result(n):
exponent = calculate_exponent(n) if is_power_of_two(n): return 1 else: return ((n - (1 << exponent)) << 1) + 1
def validate_n(n):
if not 1 <= n <= 10**18: raise ValueError("n trebuie să fie între i și 10^18") else: print("Input valid")
if __name__ == "__main__":
n = int(input()) validate_n(n) print(calculate_result(n))
</syntaxhighlight>
Explicație cod[edit | edit source]
Acest program implementează trei funcții care lucrează împreună pentru a verifica dacă un număr întreg n este o putere a lui 2 și pentru a calcula un rezultat bazat pe n.
Funcția "calculate_exponent" primește un număr întreg n și calculează exponentul său în baza 2. Exponentul este calculat prin împărțirea repetată a lui n la 2 până când n ajunge la valoarea 1, numărul de împărțiri fiind exponentul.
Funcția "is_power_of_two" primește un număr întreg n și verifică dacă este o putere a lui 2, comparându-l cu 2 ridicat la exponentul calculat în funcția anterioară.
Funcția "calculate_result" primește un număr întreg n și calculează rezultatul bazat pe aceasta. Dacă n este o putere a lui 2, rezultatul va fi 1, altfel va fi calculat după o formulă dată.
Funcția "validate_n" primește un număr întreg n și verifică dacă se încadrează între 1 și 10^18 inclusiv. Dacă n nu se încadrează în această plajă, funcția va arunca o excepție "ValueError".
În metoda "main", se primește un număr întreg n de la utilizator, se validează și se calculează și se afișează rezultatul apelând funcția "calculate_result".