Salve a tutti.
Relativamente al problema “Piroette” quindi alla ricerca della permutazione divisibile per 180 di valore maggiore.
Ebbene, immagino che l’enumerazione di tutte le possibili permutazioni non sia una mossa astuta (e infatti la soluzione ricorsiva fallisce al subtask 3).
Ma anche fare un’analisi del tipo “tutti i numeri divisibili per 180 terminano con uno 0 e la penultima cifra pari” non è sufficiente. Infatti tale condizione è necessaria ma non sufficiente per la divisibilità per 180.
Infatti dato per input 1 2 3 4 0, il numero 12340 soddisfa in effetti la condizione ma non è divisibile per 180.
Restringendo la considerazione a input “validi” ovvero tali per cui la condizione è soddisfatta, secondo quale dimostrazione il massimo numero divisibile per 180 ha come penultima cifra la più piccola cifra pari dell’insieme e le restanti ordinate in senso decrescente ??
Grazie a tutti
Per essere divisibile per 180=9*20 deve essere divisibile sia per 9 che per 20.
Per essere divisibile per 9 la somma delle cifre deve essere divisibile per 9. Ma la somma delle cifre non cambia modificando l’ordine delle cifre, quindi sicuramente la somma delle cifre del numero input è già divisibile per 9.
Per essere divisibile per 20 deve finire per 00, 20, 40, 60, 80.
Siccome per confrontare due numeri con lo stesso numero di cifre si comincia col confrontare la cifra più significativa, per avere il numero più grande possibile metti le cifre più grandi come più significative e poi via via in ordine (debolmente) decrescente. Ovviamente lasciando la più piccola pari come cifra delle decine.
1 Mi Piace
Quindi, data l’assunzione “Esiste almeno una permutazione delle cifre di G che conduce ad un numero divisibile per 180”, si dà per scontato che qualsiasi input venga passato al programma questo sia divisibile per 9 e quindi si verifica solamente la divisibilità per 20.
Pertanto il problema si riduce a trovare la permutazione di G che offra il numero più alto divisibile per 20.
Quindi, rivisto in questo termini, ci sta che tale permutazione abbia le cifre ordinate in senso decrescente, avendo fissato le ultime 2.