Calcolatrice rotta

Aiuto
1

Calcolatrice rotta territoriali 2024

Per ottenere il numero 743 la sequenza minima di operazioni ammesse è:
2^10-2^8-2^4-2^3-1

Il numero di operazioni è: 10+8+4+3+1=26.
E’ corretto?

2

No, la soluzione ottimale usa 14 operazioni.

1 Mi Piace
3

Qual è la sequenza minima di operazioni per ottenere il numero 743?

4

Se te la dicessi ti spoilererei tutto il problema.
Piuttosto puoi dirmi la tua sequenza da 26? Non ho davvero capito come è fatta

5

Sto cercando di risolvere il problema “Calcolatrice rotta” in python 3.10.11, con questo codice sono risucito a risolvere fino al 35/50 o 40/50 su alcuni input.

Questo codice somma uno se N è dispari, altrimenti divide N per 2 finche N == 2. Per entrambi questi casi incrementa il contatore delle operazioni di uno. Per contare il primo numero digitato il contatore comincia da 1.

Qualcuno saprebbe dirmi quale/i caso/i questo algoritmo non considera?

file = open("input.txt", "r")
outputFile = open("ouput.txt", "w")

t = int(file.readline())
for case in range(1, t+1):
    file.readline()
    n = int(file.readline().strip())
    operations = 1

    if n == 1 or n == 2: 
        outputFile.write(f"Case #{case}: {operations}\n")
        continue

    while n != 2:
        if n%2 != 0:
            operations+=1
            n+=1
        else:
            n = int(n/2)
            operations+=1
    outputFile.write(f"Case #{case}: {operations}\n")

file.close()
outputFile.close()

Scrivo in questo thread perchè ancora non ho il permesso di creare nuovi argomenti sul forum

6

Prova a considerare ed eseguire il seguente codice:

n = 1999999999275755646 # numero grande
print(n / 2)            # divisione a virgola mobile
print(int(n / 2))       # divisione intera tramite: divisione a virgola mobile + conversione a intero con int()
print(n // 2)           # divisione intera

Noti qualcosa?

7

Ho notato adesso che sono diversi. Non avevo proprio pensato alle formattazzione del risultato.

Mi fa pensare che la divsione corretta da eseguire sia n//2

8

Ho provato adesso a invirare una nuova soluzione e ha funzionato utiliazzando la divisione intera

Grazie mille per l’aiuto

1 Mi Piace