Effettuare una sequenza strettamente crescente unendo i numeri vicini usando il minor numero di mosse

Question

Effettuare una sequenza strettamente crescente unendo i numeri vicini usando il minor numero di mosse

#1 da (3 voti)
#2 da (-1 voti)

4

Ho un problema seguente da risolvere:

You are given a list of positive integers [x_1;x_2;...;x_n]. You are allowed to 
change 2 integers standing next to each other to one equal to their sum. (So for
example in list [x_1;...;x_3;x_4;x_5;x_6;...;x_n] you pick x_4 and x_5 and the new list
becomes [x_1;...;x_3;(x_4+x_5);x_6;...;x_n]). Find the minimum number of such changes
needed to get a list in which integers are in strictly increasing order.

Come affrontare un simile problema? Intuitivamente sembra un problema di programmazione dinamica (qualcosa come moltiplicare le matrici) ma non riesco a trovare alcun sottoproblema collegato. Qualche idea su come risolverlo usando qualcos'altro che la forza bruta?

algorithms

posta qiubit 30.01.2015 - 20:20

fonte

2 risposte

Leggi altre domande sui tag algorithms

Separazione dei modelli di Django per SOA Metodologia per l'esplorazione di API in lingue dinamiche

score 3 · Answer 1

Vorrei utilizzare un algoritmo di ricerca A * . A * è la migliore prima ricerca utilizzando sempre il nodo con il costo totale più basso g(l)+h(l) , dove g è la "funzione costo percorso passato" e h è la "funzione costo futuro percorso". Lo spazio di ricerca è un grafico in cui ogni nodo è uno degli elenchi possibili che è possibile raggiungere aggiungendo successivamente due numeri, a partire dall'elenco iniziale. I bordi del grafico sono definiti dalle mosse. La funzione del costo del percorso passato g(l) è data dal numero di spostamenti finora raggiunti per raggiungere l'elenco l . La funzione futuro costo-percorso h(l) è data dal numero di coppie (x_i,x_(i+1)) nella lista l dove x_(i+1) è minore o uguale a x_i . Ad esempio, quando h(l)=0 , la lista l è strettamente crescente e hai raggiunto un nodo finale nel tuo grafico.

Nota che ogni mossa può ridurre il numero di tali coppie di una al massimo , quindi h non sarà mai una sovrastima, il che garantisce che la ricerca A * trovi la soluzione ottimale.

Per questo tipo di problema, avrà sicuramente senso evitare di analizzare due volte la stessa lista l , poiché la stessa lista può essere raggiunta da diverse sequenze di sommatoria. Quindi durante la ricerca, memorizza ogni elenco (= nodo grafico visitato) in un set di hash e sfrutta la ricerca quando raggiungi di nuovo lo stesso elenco.

score -1 · Answer 2

-1

Se ti è permesso combinare più volte, sommi tutti i numeri in un singolo valore. Un elenco di un numero è ordinato :) Quindi il numero di mosse è n-1.

risposta data 30.01.2015 - 20:40

fonte