Problema di programmazione dinamica - Per trovare il numero intero più piccolo 'x' che contiene solo le cifre 1 e 0 in modo che x mod n = 0

Question

Problema di programmazione dinamica - Per trovare il numero intero più piccolo 'x' che contiene solo le cifre 1 e 0 in modo che x mod n = 0

#1 da (2 voti)
#2 da (1 voti)

2

Per progettare un algoritmo che produrrà il numero intero più piccolo 'x' che contiene solo le cifre 1 e 0 in modo che x mod n = 0 e x > 0 ..... Ad esempio:

2 divide 10

3 divide 111

4 divide 100

5 divide 10

6 divide 1110

7 divide 1001 e così via.

Gli 1 e gli 0 sono nella rappresentazione di base 10.

So che possiamo risolvere questo problema usando il principio del piccione ma in questo problema siamo interessati al numero più piccolo.

Stavo pensando di utilizzare un approccio DP simile a un problema di somma parziale in cui il set contiene 1, 10, 100, 1000 e così via. Non sono completamente chiaro su come formulare la relazione di ricorrenza per questo problema. Qualcuno può dare qualche idea?

algorithms dynamic-programming np-complete

posta redDragon 08.02.2015 - 21:13

fonte

2 risposte

2

Solo uno schema di pensiero.

Per me, sembra bruteforce e streetsmart batterà qualsiasi approccio teorico.

Esempio # 1

Se N contiene un fattore da 2 a multiplicities K, allora puoi dedurre che le cifre più basse di X dovranno contenere almeno K zeri consecutivi, perché solo zero consecutivi nelle cifre più basse possono fornire fattori di 2. E presto. Sembra non coinvolgere teorie.

Esempio # 2

Un'altra streetmart è la divisibilità per 9 dei numeri decimali giudicati dalla somma delle cifre decimali. (Più precisamente è la proprietà del modulo per 9. La divisibilità si riferisce al modulo che dà zero. La divisibilità per 3 è un semplice corollario derivato dal modulo per 9.) Si noti che usando "modulo", lo si applica a qualsiasi numero, diciamo 13, filtrando i candidati di X con il requisito che mod(X_candidate, 9) == mod(13, 9) == 4 . Il requisito è necessario ma non sufficiente, ma aiuta a ridurre il numero di casi necessari alla bruteforce.

risposta data 08.02.2015 - 21:56

fonte

Leggi altre domande sui tag algorithms dynamic-programming np-complete

Perché l'euristica è uno svantaggio per i problemi decidibili? Come aggiungere i controlli delle autorizzazioni "dopo il fatto"

score 1 · Accepted Answer

La programmazione dinamica è molto meglio della forza bruta più alcune euristiche.

Cerca di determinare il numero minimo di cifre in modo che il numero intero 0-1 sia un numero.

Ad esempio, potresti creare un dizionario le cui chiavi saranno numeri interi n e i cui valori sono il numero minimo di cifre in modo che ci sia un numero intero 0-1 uguale alla chiave n mod. Inizia con (0,0). Per ogni k, calcola 10 ^ (k-1) mod n e passa attraverso ogni chiave a per vedere se b = a + 10 ^ (k-1) mod n è ancora una chiave. Altrimenti, aggiungere (b, k) al dizionario. Se b è 0, allora abbiamo trovato il numero di cifre necessarie.

Una volta ottenuto il numero di cifre necessario per ogni riduzione di un numero con al massimo k cifre, è possibile determinare il numero minimo in modo ricorsivo. Se raggiungi una mod n con k cifre, allora il minimo 0-1 numero congruente a una mod n è 10 ^ (k-1) più il minimo 0-1 numero congruente a a-10 ^ (k-1) mod n .

Questo richiede O (n ^ 2) tempo, dal momento che per ogni k, si genera almeno una nuova mod di classe di congruenza mentre si aggiunge 10 ^ (k-1) alla maggior parte delle vecchie n classi di congruenza. Forse c'è una memoizzazione che accelererebbe i casi in cui un piccolo numero di classi di congruenza sono generate alla volta, come quando una piccola potenza di 10 è 1 mod n.